БИЛЕТ 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 Сетеваямодель – структурный план реализации программы работ.
Сетевая модель(сеть), или структурный план, отражающийотношение порядка, существующее на множестве оп – ийпрограммы, а также последовательность выполнения работ и в комплексе свременными параметрами работ и событий образует план реализаций суммы оп – ий программы.
Исходной информацией для построения сетевой модели являетсяперечень работ или оп – ий программы, сведения об ихтехнологической последовательности, длительности, и необходимых ресурсов для ихвыполнения.
Исходная информация и результаты последующих расчетовзаносятся в специальную формулу.
Наименование работы
Номер работы
Номера непосредственно предшествующих работ
Индекс начального события работы, i
Индекс конечного события работы, j
Длительность работы, tij
Полный резерв времени, Rij
Свободный резерв, rij
1
2
3
4
5
6
7
8
Которая называется «Таблица работ». В таблице работ исходнаяинформация занимает 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+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).
Все полные резервы времени работ критического пути равнынулю.
С организационной точки зрения свободный резерв времениработы показывает, насколько можно увеличить её длительность без изменениясроков выполнения других работ, а полный резерв — при сохранении длительностикритического пути.
Результаты расчетов параметров событий заносятся вспециальную форму, которая называется «таблица событий»
Индекс события
Ранний срок свершения события, Тран
Поздний срок свершения события, Тпоз
Резерв времени свершения события, Rсоб
1
2
3
4
БИЛЕТ 7 ВОПРОС 2 Особенность линейно – целочисленных задач иметодов их решения
Задача ЦЛП – это задача математического программирования, вкоторой все или некоторые переменные должны принять только целочисленноезначение, а целевая функция и функции, входящие в ограничение – линейное.
Т.е. это такая нелинейная задача, которая может бытьлинейной, если бы не требования целочисленности ряда переменных. Задачу ЦЛП можно решатьнапример, как задачу ЛП без учета условий целочисленностипеременных, а затем округлить полученное решение с избытком или недостатком.При этом будет получено некоторое целочисленное решение.
Однако использование такого подхода требует обязательнойпроверки допустимости решений. Таким методом часто пользуются при решениипрактических задач, особенно когда значения переменных настолько велики, чтоможно пренебречь ошибками округления.
При решении задач в которых целочисленные переменныепринимают малые значения округляются не могут привести к далекому от истинногооптимума целочисленного решения.
Таким образом, эвристический метод решения задач ЦЛПоснованный на округлении оптимального решения соответствующей задачи ЛП,позволяет получать в общем случае только приближенные решения. Для определенияистинного значения целочисленных переменных применяется метод отсечений и методветвей и границ.
Первый базируется на идее деформации ОДР задачи ЛП таким образом,чтобы от нее было отсечено оптимальное нецелочисленное решение, но сохраненывсе допустимые целочисленные решения.
Т.е. была бы построена область, для которой оптимальноерешение соответствующей задачи ЛП совпадает с оптимальным решением задачи ЦЛП.
Указанная деформация осуществляется путем введенияспециальных дополнительных ограничений.
Второй метод основан на идее проверочной подстановки всехдопустимых целочисленных значений в целевую функцию и сравнении полученногорезультата. Естественно что удобной для использования это идея становится лишьтогда, когда полный перебор может быть сокращен дополнительными рассуждениями,основанными на принципе разветвления комбинаторского прог — ия.
БИЛЕТ 8 ВОПРОС 1 Методикаопределения длины критического пути структурного плана.
Длительность критического пути сетевой модели определяется спомощью анализа данных из таблицы событий.
Индекс события
Ранний срок свершения события, Тран
Поздний срок свершения события, Тпоз
Резерв времени свершения события, Rсоб
1
2
3
4
Когда будет вычислен ранний срок наступления завершающегособытия n (столбец 2 в б
таблице событий), тогда может быть определена длинакритического пути структурного плана, т.к. S= Трn
а n=N завершающего события сетевоймодели
БИЛЕТ 8 ВОПРОС 2 Применение булевых переменных при построениимоделей задачи планирования производства.
В общем виде модель задачи ЦОП может быть представленаследующим образом Z=C*X стремится к максимуму, а X+B=0, X>=0, Xi – целые числа, J принадлежит Т, где Т – множествозначений индекса J, соответствующих целочисленных переменных. Причём задачаназывается полностью целочисленная, если все значения J принадлежат Т ичастично целочисленная в противном случае. Если целочисленная переменная можетпринимать значения равные только 0 или 1, то выше изложенная модель задачи ЦЛПявляется моделью задачи с булевыми переменными. Любая целочисленная переменнаяможет быть выражена через булевую переменную.Допустим 0=N. Таким образом любуюцелочисленную задачу можно записать в булевых переменных.
БИЛЕТ 9 ВОПРОС 1 Расчетвремени парам. работ структурного плана: организационный смысл работструктурного плана и методика определения значений.
В результате расчетов определяется временный параметрыработы сети к числу которых относится: полная(Г i, j) и свободная(D i, j). Резервы времени выполнения работ(ij). С организационной точки зрения резервы времениработ(полная и свободная) показывают насколько можно увеличить её длительностьили задержать срок её начала, причём свободная – при условии неизменностисроков выполнения других работ, а полная – при сохранении длительностикритического пути. А ещё свободных резервов времени: 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 + ti,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 Методика построения календарного плана идиаграмм потребления рес.
Календ. план строится в соответствии со спец.формой,совмещающей в себе график и диаграмму потребления ресурсов.
Название работы
Номер раб
Инд нач соб-й
i
Инд конца соб
j
Длит раб-ты
tij
Расход рес
Pij
Сроки вып-я раб от нач реализ-и программы в теч времени 5
1
2
3
5-2
5-1
5
NN наступающий событий
Границы интервалов с пост числом работ
Mmax
Суммарный расход рес-ов
Mmin
Сумм расход рес в интервале времени
В верхней части формы слева фиксируется инфаиз табл.раб. и сведения о расходе рес.на каждойоперации, справа выбирается масштаб и строится сетка времени, охватывающаяотрезок [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 Анализ чувствительности линейных моделей кизменению значений параметров системы ограничений.
При решении любой оптимиз. задачиважно проанализировать, насколько устойч