назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [ 105 ] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


105

где 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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [ 105 ] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]