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. Поэтому получение перед реализацией алгоритма целочисленного решения исходной задачи может оказаться весьма полезным. Такое решение даёт начальную нижнюю границу, которая используется для получения лучшей нижней границу в процессе ветвления.