Главная: Рефераты

Рефераты. Шпаргалка по исследованию операций

 

    БИЛЕТ 13 ВОПРОС 1 Математическая модель задача оптимизации календарного плана по стоимости.

Затраты на отдельную операцию не постоянна и зависит от деятельности её выполнения. Кривая зависимости затрат на выполнение операций от её длительности. РИСУНОК! Оптимальным будет план при t i j = D i j. Для всех i j принадлежащих Q. Если же сократить длительность выполнения операций до значения t i j = d i j, то это приведёт к сокращению срока реализации программы, но увеличит затраты. После введения ограничений на длительность работ и сроки выполнения программы, а так же минимизации затрат. С i j = С и j min + б i j *(D i j – t i j) примет вид: 1) идентификация переменных d i,j <= t i,j <= D i,j , для всех (i , j ) принадл Q. 2) t i,j <= T , k=1,2,...,Г - система ограничений. 3) Формирование функции цели Z=E , б i,j (D i,j - t i,j) -> min. Z – дополнительные затраты, связанные с ускорением сроков реализации программы по сравнению с нормальным планом. Q – множество работ сетевой модели. Б i j  - удельный затраты на сокращение длительности выполнения операций на 1 единицу. d i j и D i j – нижние и верхние пределы изменения длительности работ соответственно выбранные организационным и технологическим соображением, таким образом, что при t i j = T i j затраты на выполнение операций минимальных Lк – множество работ "к"-го полного пути сетевой модели. Г – число полных путей модели, Т – установленный срок реализации программы. Сокращение размерности задачи: 1) в качестве оптимизационной переменной используется t i j. 2) первая система ограничений: 1) t i,j >= 0 ; 2) - t i,j + (D i,j - d i,j) >=0 ; 3) для всех (i,j) принадл Q. Вторая система ограничений: t i,j + (T - E d i,j) >=0 , k=1,2,...Г. Третий пункт увеличение t i j снижает затраты от уровня срочного плана, поэтому в качестве критерия оптимальности можно взять максимум суммарной экономии C=E  , б i,j*t i,j -> max.

 

БИЛЕТ 13 ВОПРОС 2 Достоинства и недост лин. моделей задачи планирования произв-ти.

Достоинства:

1)Снижена трудоёмкость за счёт пренебрежения зависимостью коэф целевой ф-ции или части ограничений (парам моделей) от оптимизируемых величин.

2)прим-е для реш-я большого количества плановых задач, причём форма задач во многих случаях повторяется, задачи одного класса возникают в разл отраслях гор пром-ти, сферах деят-ти гор предприятия

 

   БИЛЕТ 14 ВОПРОС 1 Управление процессом реализации программ на основе структурного и календарного планов.

Управление процессом реализации программы можно представить как задачу периодической выработанности решения , определяющих какие работы и с какой интенсивностью следует их выполнять в каждый период в будущем с целью получения максимального эффекта (с позиций выбранного критерия оптимальности). Процесс вырабатывания решения называется периодичным , если время , через которое вырабатываетяс след решение , пост или крайно определяемому периоду. Таким образом в основу управления процессом реализации программы положена задача регуляции по отклонениям.

Выбор периода контроля зависит от особых объектов , в условиях которого реализуется программа. В процессе контроля особое внимание уделяется операциям крит. пути. Ход выполнения программы отображается на календарном плане. Влияние задержки какой-либо операции остальные программы легче оцениваются по сетевой модели. Если отклонения от календарного плана не приводят к изменению длительности крит. пути , то календарный план корректируется , в противных случаях строится новый календарный план.

 

БИЛЕТ 15 ВОПРОС 1 Структура оптимизационных моделей.

1)Переменные (управляемые, оптимиз-емые, значения которых необходимо найти в результате решения)

2)Параметры (свободные члены и const при переем)

3)Система ограничений. В модель вводятся две системы ограничений. Одна связываетет оптимизируемые величины и параметры модели с гранич условиями оптимизации, заданными постановкой задачи. Но этих ограничений часто бывает не достаточно, тк они обычно учитывают внешние условия оп-ии и не отражают внутренних связей существ парам сист. С этой целью в модель вводится др сист ограничений, отражающая внутр усл поведения оп-ии. Каждое ограничение этой сист – результат исслед-я возможных последствий изм-ия оптимизируемыъ величин в условиях конкретной произв-ой системы.

4)Функция цели. Она связывает критерий оптимальности (показатель эффективности решения, выбираемый на стадии постановки оптимизации задачи) с иптимизируемыми переменными и параметрами модели. Целевая функция должна соотв след требованиям: однозначно связывать все оптимизируемые переменные с критерием оптимальности; не иметь разрывов на всем множестве допустимых значений оптимизируемых переем.

 

   БИЛЕТ 15 ВОПРОС 2  Графическая интерпретация неограниченной функции цели.

По определению множество называется неограниченным , если нельзя построить сферы конечного радиуса из какой либо точки множества , включающую все это множество. Графики неиграниченное множество представляющее собой незамкнутый многоугольник. Также для если рассмотреть подробнее , для того , чтобы показать , что для неограниченности множества решений достаточно наличие возможности бесконечного роста хотябы одной независимой переменной.

 

    БИЛЕТ 16 ВОПРОС 1 Этапы построения оптимизационных моделей.

1)Идентификация перем – исследования системы и выявление существ для решения задачи параметров, формулировка  групп оптимиз и неуправляемых величин. Под существ параметром понимаются показатели сист, определяющие результат и эффекты оптимизации. В качестве оптимизации переменных берут те показатели, на которые может влиять руководитель оп-ии.  Значения ост оцениваются статистич путём, прогнозируются или определяются заданиями вышестоящих организаций и включаются в модель в виде числовых параметров.

2)Определение системы ограничений, которые связывают оптимиз величины, парам модели с гранич условием операции, заданными постановкой задачи и отражают внутренние условия проведения операции.

3) Формирование функции цели (ф-ция, аргументами которой являются допустимые решения, а значения – числа, характеризующие меру достижения поставленной цели при различных аргументах).

 

    БИЛЕТ 16 ВОПРОС 2 Графическая интерпритация случая несовместимости системы ограничений.

Случай несовместимости возникает тогда, когда общей области пересекающихся полуплоскостей или оно попадает в отриц. В этом случае гворят, что множество решений пустое.

 

    БИЛЕТ 17 ВОПРОС 1 Примеры моделей задач планирования производства.

Небольшая фабрика имеет 2 вида красок: для внутр (I) и наружн(E) работ.

Продукция обоих видов поступает в опт продажу. Для производства используется 2 компонента: A и В. Макс возможно этих компонентов 6 и 8т соответственно. Расходы компонентов Аи В на производство 1т:

 

Продукт

Расход в т

Е

I

А

1

2

В

2

1

 

 

 

 

 

 

Изучение рынка показало, что суточный спрос на краску I никогда не превышал на краску Е более чем на 1т. Кроме того, спрос на краску I никогда не превышал 2т/сут. Опт цены красок: E – 3уе за 1т, I – 2уе за 1т. Какое кол-во краски каждого вида фабрика должна произв ежесуточно.

Xi – объём производства краски I

Хе – объем производства краски Е

2Хi+1Хе<=6 – расход компонента А

1Хi+2Хе<=8 – расход компонента В

Хi<=2

Хi-Хе<=1

2Хi+3Хе -> мах

 

    БИЛЕТ 17 ВОПРОС 2 Графический метод решения задачи ЛП.

1)В принятой системе координат построить Ур-я всех ограничений, суммы которых даст многоугольник (многогор) ограничений.

2)Построить уравнение целевой функции, проходящее через нач корд.

3)Определить направление роста (убывания) целевой функции, перемещая прямую (пл-ть), соотв-щую целевой ф-ции, параллельно самой себе.

4)В соответствии с целью ЗЛП и направлением роста (убывания) целевой функции найти точку касания этой прямой (пл-ти) с многоугольником (многогр) ограничений – вершину многоуг-ка, имеющую мах отклонение от прямой (пл-ти), проходящей через начало корд.

 

 

    БИЛЕТ 18 ВОПРОС 2 Свойства множества решений в задаче ЛП.

Исследование свойств множества решений должно дать ответ на вопрос о том, в каких точках находится оптимум и какие исходы возможны при решении основной задачи ЛП. Оптимальное решением осн задачи ЛП представляет собой одно из неотриц решений системы ограничений, при поиске которых может возникнуть след случаи:

- система Ур-й несовместна, те не имеет ниодного решения

- имеет единств решение, но хотяб одна перем имеет отриц знач

- система имеет единств неотриц решение

- беск множ-во неотриц решений

Геометрически решение представляет собой точку в пространстве с прямоуг системой координат, тк решение задачи ЛП может содержать только неотриц значения перем, то множ-во всех решений системы ограничений может располаг только в положит пространстве и образ-ть некоторую геом фигуру. Важнейшим свойством множества реш является его выпуклость, определяющая условие существования экстремума.

 

 

    БИЛЕТ 19 ВОПРОС 2 Структура сетевой модели

Сетевая модель или сеть - это график , составленный из вершин - событий и напвленных дуг - работ или операций.

i -> j -> k , i -> k

События в сетевой модели задаются индексом и обозначаются моментом начала или окончания работ. События обозначающее только начальные моменты работ называются исходным , а события составляющие только в конечных работах - заверщающими (к). Промежуток событий или просто события (j) , состоит в окончании и начале других работ.

 

Если событие завершает несколько работ , то оно наступает только в момент окончания последней по времени , входящей в него работ.

Каждая работа в модели однозначно определяется начальным и конечным событием (i,j) - работа с начальным событием i и конечным событием j.

В сети не должно быть:

1) петель , т.е. одно и тоже событие не может быть начальным и конечным событием работы.

2) 2 работы , имеющих общее начало и общее конечное событие.

Работа в сети и модели может означать:

1) действит работа - реальный процесс , требующий затрат времени и ресурсов

2) ожидание - процесс , имеющий длительность , но не требующий ресурсов

3) фиктивные работы. Если событие i и j сведены фиктивной работой , то событие j наступит только после свершения события i. Фиктивные работы имеют нулевые длительность и расход ресурсов.

 

    БИЛЕТ 20 ВОПРОС 1Модель транспортной задачи ЛП.

ТЗЛП заключается в определении объёма перевозок от поставщиков к потребителям, если известны выпуск продукции у каждого поставщика и потребности потребителей; затраты на перемещение грузов от поставщиков к потребителям. План грузоперевозок дающий мин затраты. Причём это может быть затраты денежных средств, транспортных работ или времени перевозок.

Формулировка задачи:

Имеется n поставщиков одного груза, i-тый поставщик имеет запас груза ai (i=1,2..n) и m потребителей, j-тый потребитель имеет потребность в грузе bj (j=1,2..m). Затра ты на перевозку груза от i-поставщика к j-потребителю составляют cij . Требуется определить объёмы грузоперевозок от i-поставщика к j-потребителю хij , при которых достигается минимальная суммарная стоимость перевозок W=Eni=1Emj=1cij xij ->min

При этом весь запас груза должен быть вывезен:

xi1+xi2+…+xij+…+xim=ai, (i=1,n)

а потребности всех потребителей удовлетворены:

x1j+x2j+…+xij+…+xnj=bj  (j=1,m)

Рассматривается закрытая модель, при которой сумма всех запасов = сумме всех потребностей. Любая задача может быть сведена к закрытой путём введения фиктивного поставщика или фиктивного потребителя.

Особенности транспортной задачи:

1)Все ограничения имеют вид равенств.

2)Каждая переменная входит всего в два ограничения.

3)Коэффициенты при переменных в ограничениях равны единице

 

    БИЛЕТ 20 ВОПРОС 2 Использование булевых переменных при построении целочисл моделей задач планирования производства.

Практическая ценность: представл открываемые целочисленным программированием возможности приведения «некоррект» задач к стандартному виду задач математического программирования. Использование специальный приёмов позволяет получить решение в ряде случаев, когда его поиск с помощью прямых способов оказывается затруднительным.

Ввод дополнительных булевых переменных позволяет преобразовать задачу к виду «более приемлемых» с аналит позиций. Преобразованная задача является частично целочисленной (не все знач индекса j пренадл множеству Т) с булев перем.

При решении задачи планирования гор производстваможет возникнуть ситуация, когда требуется выпол-ие нескольких из общего количества линейных ограничений. Причём заранее неизвестно, какие именно играничения должны выполняться. Аналогичная ситуация возникает, когда прав ч некоторого лин ограничения может принять одно из неск значений. Это так называемые задачи с дихотомией. Причём способ решении заключается в том, что определяется количество возможных наборов ограничений и решается соответствующее количество различных возможных линейных задач. Окончат решение выбирается по лучшему значению функции цели. Аналогично поступают и в случае с несколькими возможными значениями прав ч одного из ограничений. Однако если ввести специальным образом булевую переменную, то решение можно получить в рамках одной частично целочисленной задачи.

      

       БИЛЕТ 23 ВОПРОС  1 Временные параметры и события структурного плана.

1)tij – длительность работы ij

2)Tpi – ранний срок наступления события i

3)Tпi – поздний срок наступления события i

4)Ri – резерв времени наступления события i

5)Гij – полный резерв времени выполнения работы ij

6)ТL (i,j…f) – продолжительность пути L(i,j…f)

7)S – продолжительность критического пути.

8)dij – свободный резерв времени выполнения работы ij

Путь L(i,j…f), где i,j…f – индексы событий, через которые проходит этот путь, - это последовательность работ, соединение 2 событий i и f.

 

 

 

Москва , 2007

Московский Государственный Горный Университет

Prik


Страницы: 1, 2, 3, 4, 5, 6



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.