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

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

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

БИЛЕТ 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. Расчет резервов времени работ позволяет определить критический путь сетевой модели.