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;
Определенный из этого выражения Тпоз(0) должен быть равен нулю. В противном случае в расчетах допущена ошибка.
Резервы времени свершения событий определяются по формуле:
Rсоб(i) = Тпоз(i) - Тран(i) (10.5),
причем для событий критического пути они равны нулю.
Расчет резервов времени наступления событий по формуле (10.5) позволяет определить критический путь сетевой модели. Знание критического пути важно с практической точки зрения, т.к. критические работы не имеют резерва, и изменение их длительности приводит к изменению сроков выполнения комплекса работ.
Страницы: 1, 2, 3, 4, 5, 6
