где YijU и = l,2v..,NfJi k)задает линейный функционал базового /=1
расписания Д.
Описанная выше процедура позволяет получить многогранник устойчивости М оптимального решения по заданной точке tеР, и расписание А остается оптимальным для всех точек t еМ. Это позволяет строить мно-гофанники устойчивости оптимальных решений, не делая полного разбиения параллелепипеда Р на многогранники устойчивости оптимальных решений.
Рассмотрим случай разбиения на многогранники устойчивости опти-мальньпс решений, если время вьшолнения работ изменяется на множестве, заданном ограничениями вида
hijtiBj, j = \,2,...,l(11.39)
,>0(/= !,...,«).(11.40)
Пусть G,,„,G -вершины многогранника, заданного неравенствами (11.39)-( 11.40), координаты которых соответственно равны Gj =(GJv..,Gr)v..,GA =(G!tv..,GD- Построим параллелепипед Р с вершинами
t}= min {g/} (/ = 1,...,«);(11.41)
tf= max {g/1 (/ = 1,...,«).(11.42)
Этот параллелепипед будет содержать в себе многофанник, заданный неравенствами (11.39)-(11.40). Для решения задачи разбиения на многофанники устойчивости для случая, когда время вьшолнения работ меняется на множестве, заданном неравенствами (11.39)-(11.40), можно сделать разбиение на многофанники устойчивости оптимальных решений для пал-лелепипеда, заданного формулами (11.41)-(11.42), и после этого для каждой системы неравенств, задающих многофанник, добавить офаничения (11.39).
Пусть длина вьшолнения работ изменяется на многофаннике Р, заданном неравенствами (11.39)-( 11.40). Рассмотрим следующую задачу:
среди точек многогранника Р найти такую, для которой значение оптимального расписания было бы не больше, чем для всех других точек многогранника Р. Назовем эту точку точкой глобального оптимума задачи (11.22)-(11.26). Если многогранник Р является параллелепипедом п \ ]
Р = Y\ tjjf » то решение этой задачи дается следующей леммой. /=1
Лемма 11.6. Вершина параллелепипеда Р, удовлетворяющая условию ti = ti\ является точкой глобального оптимума для задачи (11.22)-(11.26) с нефиксированным временем выполнения работ.
Доказательство. Предположим, что существует t tnAt < At, где At HAt - значения оптимальных расписаний для точек t и f. Тогда среди координат точки t = (tu...,fn) существует tj> tj(\ <j< n\ a для всех остальных / (/ = 1,..., n\ i Ф j) fl > ti. Это означает, что, увеличив продолжительность работы dj, сократим длину оптимального расписания. Полученное противоречие и доказывает утверждение леммы.
В случае если многогранник М, заданный (11.39)-(11.40), не является параллелепипедом, точка глобального оптимума может быть определена следующим образом. Сначала осуществляется разбиение многогранника М на многогранники устойчивости оптимальных решений MXi = l,...,N), где N- количество многогранников, полученных при
разбиении, и пусть /(; = 1,...,Л) - линейные функционалы, соответствующие оптимальному решению Д для многогранника . Далее решается для каждого задача минимизации функционала / на многограннике и затем определяется
min fl,(11.43)
где - минимум функционала/ на многограннике .
Точка teM, на которой будет выполняться (11.44), будет точкой глобального оптимума.
Теорема 11.2. Пусть длина выполняемых работ заключена в многограннике М, заданном неравенствами (11.39)-(11.40). Тогда точка глобального оптимума является граничной точкой многогранника М.
Для доказательства теоремы 11.2. покажем справедливость следующих вспомогательных лемм.
Лемма 11.7. Пусть задан орграф G, отражающий последовательность выполнения работ с фиксированным временем выполнения работ / и су-
шествует базовое оптимальное расписание Аопт для работ орграфа G. Тогда если длины всех работ умножить на с > О, то оптимальное расписание сохранится и Т - сТ , где - длина оптимального расписания для работ длительности и, а - длина оптимального
расписания для работ с временем выполнения cuQ =\,,,,,п).
Доказательство, Утверждение леммы очевидно. Геометрически это означает, что если Аопт является оптимальным расписанием для точки t, то оно будет оптимально и для всех точек прямой, проходящей через начало координат и через точку t.
Лемма 11.8. Если в орграфе G с фиксированными длительностями выполнения работ время выполнения всех работ уменьшить на величину > О, то длина оптимального расписания уменьшится не менее чем на €,
Доказательство, Выберем среди работ = !,...,«) работу с максимальной продолжительностью , время вьшолнения всех работ разделим на величину с, где
с =
max
Из леммы 11.6 следует, что оптимальное расписание при этом не изменится.
Пусть - время оптимального расписания для орграфа работ G с продолжительностью работ и и - врем я вьшолнения работ, ко-
гда длительность выполнения работ t\, Dk - критический путь в графе,
соответствующему оптимальному расписанию.
Оценим, как изменилась продолжительность работ по сравнению с /,.(/ = 1,...,2);
maxmax
Оценим, как изменилось время оптимального расписания:
ПН- I.tl< I MWl£)=Jf,
ieDii ieDii isDi isDjc maxmax