Аа, {А\,.,.,Ам}, которое остается оптимальным для всех точек многогранника В..
Доказательство. Как было показано, при фиксированном времени выполнения работ для каждого базового расписания можно построить такой орграф G из работ исходного орграфа G, что длина базового расписания будет равна длине критического пути орграфа G. Построим для базового расписания Д соответствующий орграф G, отображающий последовательность выполнения работ по расписанию Д. Пусть Z)p...,Z) - все пути орграфа G/, соответствующего базовому расписанию Тогда среди путей Dj,...,Z) существует, по крайней мере, один критический путь
Dk\ такой, что для точки t е Д длина расписания Д равна Z •
JeDl
Интервал изменения длины пути D, а значит и интервал изменения длины расписания [Т,!] могут быть оценены, если будут вычислены максимум и минимум функционала:
Z tj(11.34)
jeD[
при ограничениях:
ct<V;(11.35)
/>0;(11.36)
где Г = (/!,...,/„), с -матрица Ь<«;
У= Сь..., Vk), неравенства (11.35)-(11.36) задают многогранник .
Пусть [TJ,Tj] (/=1,...Д)- верхнее и нижнее значения соответствующего базового расписания Д на многограннике Bj. Определим для
заданного разбиения величины Т \ и Т 2 по формулам:
min min
Г 1 = min Tj; min у-1,...,Л
Т 2 = max Ту. max J=\y...,N
Рассмотрев все возможные разбиения параллелепипеда Р на систему многогранников {5р...,5дг (/=1,..., /з)» де - количество разбиений при всех возможных вариантах выбора максимальных векторов на всех этапах построения допустимого расписания, получим возможность попарно сравнивать значения расписаний на общей части многогранников Bj. На каждом шаге 1{\<1<п) построения допустимого базового
расписания при новом разбиении параллелепипеда Р можем оценить снизу значение этого расписания.
Пусть Dl,..., Die - все пути орграфа G, задающего последовательность выполнения работ. Вычислим минимум следующего выражения:
min I tj=Tj U = l...,k), 1Щ
При ограничениях
сЧ>Ои>0,
где Dj - невьшолненные работы пути D/, с- матрица кхп;
к-количество ограничений, полученных за / шагов построения базового расписания. Ограничения (11.37) задают построенный многогранник при составлении базового расписания. Обозначим Т[ = min Г,. Если окажет-
У=1,...Д
ся, что
ч mm - max
где t} - нижняя оценка на этапах 1,2, ... / - 1, то прекращаем дальнейшее построение допустимого расписания, так как оно заведомо хуже составленного ранее. После того как построено очередное разбиение, на пересечении многогранников можно оценить длину нового допустимого расписания и составленного ранее, при этом возможно:
1)интервалы длительности допустимых расписаний не пересекаются;
2)интервалы длительности пересекаются.
В первом случае на пересечении многогранников задается то допустимое расписание, у которого верхняя оценка времени выполнения всех работ ниже.
Во втором случае проводится дополнительная разделяющая гиперплоскость вида
Z / = Z и,
где в левой части равенства (11.38) стоит сумма длительностей работ соответствующего критического пути для нового, а в правой части критического пути для ранее полученного допустимого расписания. Таким образом, мы разделили гиперплоскостью (11.38) общую часть многогранников для решения и Аст на два многогранника и поставили каждому из них в соответствие решения А» и Аст- После того как будут произведены все возможные выборы максимальных векторов при построении допустимых расписаний получим такое разбиение параллелепипеда Р на многогранники B,„.,Bj, что каждому многограннику Д
будет поставлено в соответствие расписание Д, которое будет наилучшим среди базовых допустимых расписаний для всех / е Д, а поэтому
оно будет и оптимальным для этих точек.
Далее многогранники, полученные при разбиении, о котором говорится в теореме 11.1, будем называть многогранниками устойчивости оптимальных решений.
Рассмотрим некоторые свойства разбиений, полученных в теореме 11.1.
Лемма 11.3. Пусть для орграфа G и параллелепипеда возможных времен вьшолнения работ Р существует разбиение на такие многогранники Bi(i = \,,..,N), что каждому многограннику соответствует некоторое оптимальное для всех точек Д решение Д(/= l,...,iV). Тогда, если /€?(/ = (/!,...,/„)), и существует такое Я>0, что At е Р, и такое Aj с {Д, что А, является оптимальным расписанием для точки
Xt, то расписание А, будет оптимальным и для точки L
Доказательство. Утверждение леммы 11.3 следует из того факта, что если в орграфе G с фиксированной длительностью выполнения работ и оптимальным расписанием А время выполнения всех работ умножить на одну и ту же константу с >0, то расписание А останется оптимальным для орграфа G, продолжительность работ которого cti (/=1,...,«), где первоначальная продолжительность работ.
Предположим, что для всех работ di (/=1,...,«) продолжительность работ изменяется в интервале 0,/ (/=1,...,«) т.е. параллелепипед