Шпаргалка по исследованию операций

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

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

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

3е предприятие, завершающее реконструкцию и освоение новейшей технологии, выпускать продукцию при условии, что ему будут переданы все распределяемые средства ( в противном случае ввод мощностей переносится на более поздний срок)

Требуется так распределить капиталовложения, чтобы суммарный объем получаемой продукции оказался максимальным.

Пусть х1,х2,х3 – размеры капиталовложений для рассматриваемых предприятий, ограниченные общим бюджетом (условной единицей)

Выход продукции первого предприятия определяется как ln (1+ x1), 2го предприятия как х2 и 3го – х3²

Требуется найти Z=ln(1+x1)+x2+ х3² →max  при ограничениях х1+х2+х3≤1;х1≥0;х2≥0;х3=0 или 1.

Можно применить 2 стратегии капиталовложений, ориентируясь либо на 2ое либо на 3е предприятие.

Окончательный выбор делается неформально, с учетом обстоятельств, не отраженных в модели.

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

ОДЗ – область допустимых значений. Теорема 1: если есть ОДЗ, то она всегда выпукла. Теорема 2: поиск оптимальных решений задачи следует осуществлять в вершинах ОДЗ.

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

Сетевая модель(сеть), или структурный план, отражающий отношение порядка, существующее на множестве оп – ий программы, а также последовательность выполнения работ и в комплексе с временными параметрами работ и событий образует план реализаций суммы оп – ий программы.

Исходной информацией для построения сетевой модели является перечень работ или оп – ий программы, сведения об их технологической последовательности, длительности, и необходимых ресурсов для их выполнения.

Исходная информация и результаты последующих расчетов заносятся в специальную формулу.

Которая называется «Таблица работ». В таблице работ исходная информация занимает 1,2,3,6 столбцы, а остальные заполняются по мере построения и расчета временных параметров модели.

Наименование работ заносятся в произвольной последовательности и им присваиваются неповторяющиеся номера. Далее, исходя из принятой последовательности работ, в столбце 3 перечисляются номера непосредственно предшествующих работ.

Составление перечня предшествующих работ выполняются по следующим правилам:

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

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

3) если две работы могут выполняться частично параллельно, то их части, выполняемые последовательно и параллельно, рассматриваются как самостоятельные операции и им присваиваются собственные названия и номера;

4) если в процессе выполнения работы есть периоды со значительным колебанием расхода ресурсов, то эта работа разделяется на последовательные операции с постоянными расходами ресурсов, им присваиваются собственные названия и номера.

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

На этом этапе могут быть допущены следующие ошибки:

1) при составлении перечня условий выполнения работ ошибочно включен номер параллельно выполняемой или пропущен номер предшествующей работы. Эта ошибка может быть выявлена только в результате тщательного сравнения записи условия и последовательности работ в прогрессе

2)  В таблицу включен комплекс замкнутых циклических операций

Для проведения последующих расчетов временные параметры все событий сетевой модели дать им неповторяющиеся номера. Нумерацию выполняют со строгим соблюдением условий – каждому последующему событию дают номер больше, чем все предыдущие.

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

Исследование операций – прикладное направление кибернетики, используемое для решения организационных, в том числе экономических (взаимосвязь с экономикой), задачи ( распределения ресурсов, управление балансами, упорядочение, согласование и др.)

Исследование операций основывается на математическом аппарате максимального прогрессирования, теории массового обслуживания, математической статистике, теории игр и др.

Существующие и развиваемые подходы к анализу прикладных проблем проникают в новую область автоматизированного управления, перестраиваемой технологии, робототехники, ООС, направления создание модели экологического конфликта (взаимосвязь с экологией)

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

БИЛЕТ 3 ВОПРОС 1 Этап сетевого планирования и управления реализацией программ.

1) Структурное планирование

На этом этапе выполняется: разбиение программы на операции и определение условий их выполнения; построение сетевой модели и нумерация ее событий. Построение сетевой модеи а этом этапе позволяет детально проанализировать программу и внести улучшения в ее структуру еще до начала реализации.

2) Календарное планирование (планирование во времени)

Целью этого этапа является построение плана, определяющего моменты начала и окончания каждой операции, а также ее взаимосвязь с другими операциями программы.

Кроме того календарный план дает обеспечить возможность выявления критических (по времени) операций (которым необходимо уделять особое внимание, чтобы выполнять программу в директивный срок), а также резервов времени не критических операций. Этап включает: расчет временных параметров событий и работ сетевой модели и определение критического пути; построение календарного плана и его оптимизацию.

3) Оперативное управление процессом реализации программы (заключительный этап)

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

БИЛЕТ 3 ВОПРОС 2 Правила выбора вершин для ветвления в процессе реализации алгоритма ЛиД.

1) выбираемая вершина, которой соответствует задача ЛП с наибольшим значением функции Z-цели в оптимальном решении

2) вершина выбирается произвольным образом

БИЛЕТ 4 ВОПРОС 1 Алгоритм  оптимизации первоначального структурного плана по числу элементов.

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

Сетевая модель в каноническом виде дает им единственный исход и завершающее событие, min фиктивных работ с одними и теми же начальными и конечными событиями.

Приведение к каноническому виду выполняют в следующей последовательности

1) В сеть вводят единые исходные и завершающие события. Для этого берут, одно из исходных событий и соединяют его фиктивные работы с остальными считая их конечным событием этих

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

3) Из сетевой модели исключают лишние фиктивные работы, т.е. такие, без которых не нарушается последовательность выполнения работ. Для этого объединяют начальные и конечные события фиктивных работ в одно событие и проверяют сохранение условий выполнения последующих работ.

     БИЛЕТ 4 ВОПРОС 2  Правила выбора переменной для ветвления в процессе реализации алгоритма Л и Д.

1) выбирается переменная, имеющая  значение собственной дробной части наиболее близкое к 0,5

2) выбор переменной с наибольшим приоритетом по следующим соображениям:

- важность определения значения переменной с точки зрения решения применяемого в рамках рассматриваемой задачи

- величиной ее коэффициента (стоимости или прибыли в целевой функции)

3) переменную выбрать произвольным образом ЦЛП

     БИЛЕТ 5 ВОПРОС 1  Этапы календарного планирования реализации программ.

1) Построение графика

2) Построение диаграммы потребления (расхода) ресурсов

Получен план, который называется исходным, подвергают анализу с точки зрения его допустимости.

Во – первых, исходный план может быть недопустим по времени его реализации.

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

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

связей между работами. В его основе лежит модель и расчет временных параметров событий и работ.

     БИЛЕТ 5 ВОПРОС 2 Зондирование вершин для ветвления в процессе реализации алгоритма ЛиД.

Вершина, имеется ввиду дерево, является прозондированной (явным или неявным образом) в том случае если она отвечает одному из следующих условий:

1) соответствующее вершине оптимальное решение целочисленное и следовательно допустимо другой исходной задаче ЦЛП

2) задача ЛП соответствующая рассматриваемой вершине не имеет дополнительных решений

3) значение Z в оптимизации решения соответствующей задаче ЛП не превосходят текущей нижней границе по Z.

1)Допустим имеется задача ЦЛП предусматривающая максимизацию функций цели. В соответствии с алгоритмом ЛиД  сначала необходимо решить задачу ЛП-1, полученную из задачи ЦЛП путём исключения требования целочисленности. Предположим что в оптимальном решении задачи ЛП-1 некоторые целочисленные переменные принимают дробное значение, а значит функции цели = Z1. Следовательно оптимальное решение задачи ЛП-1 не является оптимальным решением задачи ЦЛП. Величина Z1 представляет собой верхнюю границу оптимального значения Z исходной задачи ЦЛП, т.к. при выполнении требования целочисленности значения Z модель лишь уменьшается. Затем производится ветвление по одной из целочисленных переменных имеющих дробное значение в оптимальное решении задал ЛП-1. Допустим что ветвление происходит по целочисленной переменно x3, дробное значение которой в оптимально решении задали ЛП-1 равняется A5. Тогда далее формулируется 2 новые задачи ЛП-2 и ЛП-3. Они получаются путём введения в задачу ЛП-1 ограничений х5 <= A5 и х5 >= A5+1 соответственно. Предположим, что оптимальное решение задачи ЛП-2 и ЛП-3 так же содержит дробное значение целочисленной переменной и поэтому не является допустимым решением задач ЦЛП. Далее необходимо выбрать задачу ЛП-2 или ЛП-3 и произвести ветвление соответствующей вершине, вводя новое ограничение. После определения вершины для дальнейшего ветвления выбирается целочисленная переменная, которая в оптимальном решении соответствующей задачи ЛП имеет дробное значение и производится ветвление по этой переменной. Процесс ветвления и решения задачи ЛП продолжается до получения целочисленного оптимального решения одной из задач ЛП. Значение Z в этом решении представляет собой нижнюю границу функций цели в оптимальном решении исходной задачи ЦЛП. На этом этапе фиксируется все вершины до которых значение Z в оптимальном решении не превосходит полученные нижние границы. Эти вершины называются прозондированными, поскольку обе допускают решение соответствующих им задач ЛП не содержащих решение лучших чем полученные. Естественно что в дальнейшем в дальнейшем ветвлении они не участвуют. При использовании алгоритма ЛиД выбор вершин для дальнейшего ветвления осуществляется до тех пор, пока остаётся хотя бы одна непрозондированная вершина. Эффективность алгоритма существенно зависит от скорости последовательного зондирования вершин. Обычно для выполнения условий 1 и 2 требуется значительное время. Условие 3 нельзя применять до получения нижней границы. Однако нижняя граница определяется только после рассматривания вершины с допустимым решением исходной задачи, то есть вершины удовлетворяющие условию 1. Поэтому получение перед реализацией алгоритма целочисленного решения исходной задачи может оказаться весьма полезным. Такое решение даёт начальную нижнюю границу, которая используется для получения лучшей нижней границу в процессе ветвления.

    БИЛЕТ 6 ВОПРОС 1 Алгоритм нумераций событий структурного плана

Упорядоченную нумерацию событий проводят по алгоритму:

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

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

    БИЛЕТ 6 ВОПРОС 2 Метод ветвей и границ.

Для определения истинного значения целочисленных переменных применяется метод отсечений и метод ветвей и границ.

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

Т.е. была бы построена область, для которой оптимальное решение соответствующей задачи ЛП совпадает с оптимальным решением задачи ЦЛП.

Указанная деформация осуществляется путем введения специальных дополнительных ограничений.

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

БИЛЕТ 7 ВОПРОС 1 Расчет временных параметров событий структурного плана: организационный смысл параметров и методика определения значений

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

Расчет начинается с ранних сроков наступления событий, определяемых по формуле 10.1.

                                                                              (10.1),

где Тран(j) - ранний срок свершения события j;

Ui - множество событий, непосредственно предшествующих событию j;

Тран(i) - ранний срок свершения события i;

tij - продолжительность работы (i, j).

Определение Тран(j) - ведут строго по порядку номеров, начиная с первого события, приняв ранний срок свершения исходного события равным нулю Тран(0)=0.

Вычисления продолжают вплоть до завершающего n -го события.

С организационной точки зрения ранний срок свершения события - это минимально необходимое время для выполнения всех предшествующих работ. Отсюда ранний срок свершения конечного события представляет - собой минимальное время, необходимое для выполнения комплекса работ. Это время необходимо для реализации самого длинного, "критического" пути, соединяющего начало и конец сети. В дальнейшем это время будет обозначаться S и определятся как

S = Тран(n)                                                                                                              (10.2).

Поздние сроки наступления событий определяются из условия сохранения сроков выполнения комплекса работ. Отсюда поздний срок свершения конечного события

Тпоз(n) = Тран(n) = S                                                                                             (10.3).

Вычисления выполняют, начиная с последнего события, в порядке строгого убывания номеров по формуле

                                                                               (10.4),

где Тпоз(i) - поздний срок свершения события i;

Uj - множество событий, непосредственно следующих за событием i;

tij - продолжительность работы (i, j).

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

Резервы времени свершения событий определяются по формуле:

Rсоб(i) = Тпоз(i) - Тран(i)                                                                                       (10.5),

причем для событий критического пути они равны нулю.

Расчет резервов времени наступления событий по формуле (10.5) позволяет определить критический путь сетевой модели. Знание критического пути важно с практической точки зрения, т.к. критические работы не имеют резерва, и изменение их длительности приводит к изменению сроков выполнения комплекса работ.

Полные и свободные резервы времени выполнения работ определяются из следующих выражений:

1) полный резерв времени

Rij = Тпоз(j) - Тран(i) - tij                                                                                       (10.6);

2) свободный резерв времени

rij = Тран(j) - Тран(i) - tij                                                                                         (10.7).

Все полные резервы времени работ критического пути равны нулю.

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

Результаты расчетов параметров событий заносятся в специальную форму, которая называется «таблица событий»

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

Задача ЦЛП – это задача математического программирования, в которой все или некоторые переменные должны принять только целочисленное значение, а целевая функция и функции, входящие в ограничение – линейное.

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

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

При решении задач в которых целочисленные переменные принимают малые значения округляются не могут привести к далекому от истинного оптимума целочисленного решения.

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

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

Т.е. была бы построена область, для которой оптимальное решение соответствующей задачи ЛП совпадает с оптимальным решением задачи ЦЛП.

Указанная деформация осуществляется путем введения специальных дополнительных ограничений.

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

   БИЛЕТ 8 ВОПРОС 1 Методика определения длины критического пути структурного плана.

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

Когда будет вычислен ранний срок наступления завершающего события n (столбец 2 в б

таблице событий), тогда может быть определена длина критического пути структурного плана, т.к. S= Трn

а n=N завершающего события сетевой модели

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

В общем виде модель задачи ЦОП может быть представлена следующим образом Z=C*X стремится к максимуму, а X+B=0, X>=0, Xi – целые числа, J принадлежит Т, где Т – множество значений индекса J, соответствующих целочисленных переменных. Причём задача называется полностью целочисленная, если все значения J принадлежат Т и частично целочисленная в противном случае. Если целочисленная переменная может принимать значения равные только 0 или 1, то выше изложенная модель задачи ЦЛП является моделью задачи с булевыми переменными. Любая целочисленная переменная может быть выражена через булевую переменную. Допустим 0<=Х<=N – целочисленная переменная, значения которой не превышают некоторого целого положительного числа N. Тогда если Б1, Б1 БN.. булевая переменная, все допустимые значения Х представляются в виде Х = Б1+Б1+БN…Другое(более экономичное) двоичное представление в котором кол-во булевых переменных меньше N, задаётся формулой Х=Б1+2Б2+2в квадрате Б3 + и т.д. + 2(K-1)*BK, где K – наименьшее целое число удовлетворяющее условие 2 в степени К-1 >=N. Таким образом любую целочисленную задачу можно записать в булевых переменных.

   БИЛЕТ 9 ВОПРОС 1 Расчет времени парам. работ структурного плана: организационный смысл работ структурного плана и методика определения значений.

В результате расчетов определяется временный параметры работы сети к числу которых относится: полная(Г i, j) и свободная(D i, j). Резервы времени выполнения работ(i j). С организационной точки зрения резервы времени работ(полная и свободная) показывают насколько можно увеличить её длительность или задержать срок её начала, причём свободная – при условии неизменности сроков выполнения других работ, а полная – при сохранении длительности критического пути. А ещё свободных резервов времени: D i, j = Tpj - Tpi - t i,j , (i,j) принадлежат Q. D i,j - свободный резерв времени работ. Q - множество работ сетевой модели. Расчет полных резервов времени Г i,j = Rj + D i,j = Тpj - Tpi - t i,j. Г i ,j - полный резерв времени работ. Для работ критического пути справедливо соотношение: Tpj = Tpi + t i,j. Все резервы времени критических работ = 0. Расчет резервов времени работ позволяет определить критический путь сетевой модели.

   БИЛЕТ 10 ВОПРОС 1 Методика определения состава работ критического пути структурного плана

Для того чтобы определить состав работ критического пути структурного плана, необходимо рассчитать полные резервы времени всех работ, которые принадлежат данному структурному плану. Если полный резерв времени какой – либо работы =0, то эта работа входит в состав работ критического пути. Таким образом выясняется, как проходит критический путь, то есть какие работы в критическом пути.

БИЛЕТ 10 ВОПРОС 2 Транспортная задача ЛП

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

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

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

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

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

Решение задач ТЗЛП включает 2 основных этапа построение опорного решения (начального плана перевозок) и построение оптимального решения.

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

Условия и метод построения оптимального решения транспортной задачи.

Один из наиболее простых и распространённых методов оптимизации транспортной задачи – метод потенциалов. Условия оптимальности плана транспортной задачи существует тогда, когда им соответствуют условия потенциальности оптимального плана транспортной задачи.

Условие потенциальности показывает, что разность потенциалов потребителя и поставщика = стоимости перевозки между ними, если перевозка осуществляется, и не больше стоимости перевозки при её отсутствии.

Алгоритм решения транспортной задачи методом потенциалов состоит из двух этапов: предварительного и общего. Первый включает: 1. построение опорного решения 2. присвоение и расчёт системы потенциалов 3. проверка первоначального плана на оптимальность. Если опорное решение не является оптимальным, то переходят ко второму (общему) этапу, который включает: 1. улучшение плана перевозок 2. исправление системы потенциалов 3. проверка улучшенного плана на оптимальность. Общий шаг циклически выполняется до получения оптимального плана перевозок.

Алгоритм решения транспортной задачи на сети. В ряде случаев транспортную задачу целесообразно решать в сетевой постановке, отличающейся наглядностью. Транспортная сеть это совокупность вершин или узлов (пункты отправления и приёма грузов, промежуточные пункты) и соединяющих их транспортных коммуникаций или звеньев. На каждом звене проставляются удельная стоимость перевозки груза по данному транспортному участку Сij , а при ограниченности пропускной способности звена также и её максимальное значение dij. Около каждой вершины в скобках со знаком + или – проставляются объемы отправления и приёма грузов. Соответственно.

Нахождение оптимального при сетевой постановке транспортной задачи плана осуществляется методом потенциалов: 1)Строится опорное решение 2) Для построения системы потенциалов любой вершине присваивается какой-л потенциал. 3)Проверка плана на оптимальность осуществляется для всех звеньев без грузопотока. 4)  При улучшении плана по звену, на котором нарушено первое условие оптимальности (разность потенциалов потребителя и поставки = стоимости перевозки между ними), должна пройти перевозка; если нарушено 3е условие опт-ти (разность потенциалов потребителя и поставка должна быть больше стоимости перевозок по звену если по нему осуществляется перевозка, объёмом равной его пропускной способности), то на этом звене перевозка должна уменьшаться.

Постановка и решение ТЗ по критерию времени.

Иногда (перевозка возгорающихся полезных ископаемых, оперативное управление работой транспорта и др.) перевозку грузов от поставщиков i=1,n до потребителей j=1,m необходимо спланировать и организовать за минимальное время.

Решение ТЗ задачи по критерию времени осуществляется в следующем порядке. 1) Методом с-з угла или наименьшего элемента троится опорное решение ТЗ.  2)Из всех клеток, занятых перевозками, выбирается наибольшее время. 3) Клетки исходной матрицы, в которых время перевозки превышает максимальное для допустимого плана, зачёркиваются. 4)Улучшается допустимый план 5) Улучшение допустимого плана осуществляется до тех пор, пока полученный план не станет оптимальным 

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

Календ. план строится в соответствии со спец.формой, совмещающей в себе график и диаграмму потребления ресурсов.

В верхней части формы слева фиксируется инфа из табл.раб. и сведения о расходе рес.на каждой операции, справа выбирается масштаб и строится сетка времени, охватывающая отрезок [0,5]. На сетке вертикальные линии обозначают ранние сроки наступления событий и под ними проставляют их NN. Затем на сетке времени в соответствующих строках строят раб.прог-м.

Для построения раб(i,j) на отрезке меж вертикальными отметками нач i конеч j событияв масштабе откладывают длительность задержки gi,j работы и времени её вып-я ti,j. Оставшаяся часть отрезка соответствует свободному резерву времени. При построении обозначают: задержку gi,j – симв.«ооо»; время выполнения раб ti,j – сплошной чертой (для ???); свободный резерв di,j – символ «+++». Фиктивная работа на графике обозначается T. По законченному графику строится диаграмма расхода ресурсов. На сетке диаграммы вертикальной линией обозначаются все начала и завершения работ. Эти отметки определяют границы интервалов, в течение которых  расход рес.не изменятеся. Если обозначить через pi,j количество однор.рес., требуемого для выполнения операции (i,j) за время t , то его суммарный расход на одновременно выполняемые работы в «k»-ом интервале определяется по формуле Mk=Eijеk(сумма)pij  и записывается в соответствующуу строку таблицы.

Множество одновременно выполняемых работ определяется по ленточно-сетевому графику как сумма работ, попадающих в границы интервала.

По ряду значений Mk оперделяется размах расхода ресурсов

dM=max{Mk}-min{Mk}=Mmax-Mmin

и масштаб диаграммы.

Значение (Mmax-Mmin) откладывается в принятом масштабе от уровня Mmin в границах соответствующих интервалов.

Первоначально строится календарный план при условии, что ни одна из работ не имеет задержек (gij =0; (ij)пренадлQ).

БИЛЕТ 11 ВОПРОС 2 Анализ чувствительности линейных моделей к изменению значений параметров системы ограничений.

При решении любой оптимиз. задачи важно проанализировать, насколько устойчиво оптимальное решение к изменению параметров задачи.

При решении задачи ЛП удельной стоимости, показатели (с1,с2,сj,сn ), входящие в функцию цели, уровень z рес bi и нормы их расхода aij принытя строго пост. На практике технико-экономические показатели (Сj и aij )определяются с некоторой погрешностью. Кроме того может меняться и уровень z рес bi

Т.о.,анализ чувствит-ти сводится к решениям задачи исслед-я оптимизаций, когда парам ci aij bj изм-ся в определённом диапазоне.

Разраба-ся спец методы реш-я задач, когда параметры модели (ci aij bj ) изменяются в некотором диапазоне. Эти задачи сост-ют парам программирование.

Различают прям и двойств задачи парам прогр-ия. В двойств задаче рассм случаи переменных запасов ресурсов. Модель двойств задачи парам прогр-я имеет вид:

Максимизирвоать ф-цию цели

Z=Enj=1CjXj ->max

При ограничениях

Yi=Enj=1aijXj<=Bi+tg (i=1,2,…m),

Дельта1<=t<=дельта2

Требуется разбить сегмент [дельта1,дельта2] на конеч число подынтервалов т.о., чтобы для всех знач парам t из каждого подынтервала мах знач ф-ции цели достигались в вершинах, определяемых одной и той же подсист системой ограничений, или достигались бы в вершинах, отличающихся лишь параллельным сдвигом определяющих их плоскостей. Решение двойств задачи позволяет указать пределы изм-я ресурсов, не влияющих на положение оптимума.

   БИЛЕТ 12 ВОПРОС 2  Анализ чувствительности лин моделей к изменению параметров ф-ции цели.

При решении любой оптимиз. задачи важно проанализировать, насколько устойчиво оптимальное решение к изменению параметров задачи.

При решении задачи ЛП удельной стоимости, показатели (с1,с2,сj,сn ), входящие в функцию цели, уровень z рес bi и нормы их расхода aij принытя строго пост. На практике технико-экономические показатели (Сj и aij )определяются с некоторой погрешностью. Кроме того может меняться и уровень z рес bi

Т.о.,анализ чувствит-ти сводится к решениям задачи исслед-я оптимизаций, когда парам ci aij bj изм-ся в определённом диапазоне.

Разраба-ся спец методы реш-я задач, когда параметры модели (ci aij bj ) изменяются в некотором диапазоне. Эти задачи сост-ют парам программирование.

Различают прям и двойств задачи парам прогр-ия.

В прямой задаче рассм изм, когда коэфф. цели Cj линейно зависит от параметра t, изменяющегося в определенных пределах. Модель прямой задачи имеет вид:

Максимизировать ф-цию цели

Z=Enj=1(Pi+tgi)Xj ->max

Дельта1<=t<=дельта2

При ограничениях

Enj=1aijXj+Bi>=0  (i=1,2…m)

Требуется разбить сегмент [дельта1,дельта2] на конеч число подынтервалов т.о., чтобы для всех знач парам t из каждого подынтервала мах знач ф-ции цели достигались в одной и той же вершине многогранника. В реальных задачах величины Pi часто являются коэфф функции цели, а gi – долямипогрешностиих определения. Парам t в этом случае изменяется от 0 в сторону увеличения или уменьш-я при анализе влияния внижения точности оценок Pj. Геом смысл задачи парам прогр-я состоит в том, что при изм t изменяется наклон пл-ти соответствующей ф-ции цели. При этом оптимальное решение остаётся без изм-й до тех пор пока Z не станет паралл какому-н ребру. (в этом случае бесчисл много реш-й).

    БИЛЕТ 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т. Кроме того, спрос на краску 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