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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


99

Приведем формулировку двойственной задачи ЛП.

Минимизировать w = y6- ух

при выполнении условий

- Уг > 5 (А),

-г/,>б(В),

-у2>3(С),

-y2>S(T>),

~ У3 2(E),

- У3 > 11(F),

- у4 > 0 (Фиктивный),

-у4>1(Щ,

-уъ> 12(G),

все yt не ограничены в знаке.

В формулировке двойственной задачи можно дать интересную интерпретацию двойственных переменных. Пусть yt - время узла отсчитываемое от некоторого момента времени, общего для всех узлов. В этом случае w = уе - у1 будет представлять длительность проекта. Каждое ограничение связано с определенным процессом, они устанавливают отношения предшествования между различными процессами. Например, неравенство у2-ул > 5 эквивалентно неравенству у2>у] + 5, которое показывает, что для узла 2 время у2 не может быть меньшим времени у, + 5. Минимум целевой функции определяет наименьший промежуток времени, при котором будут выполняться все ограничения. В этой интерпретации двойственные переменные могут принимать только неотрицательные значения. Время начала выполнения проекта г/, естественно установить равным нулю. В этом случае целевую функцию можно переписать как w = у&. Задание значения у1 = О также согласуется с тем, что одно из первоначальных условий лишнее.

С учетом того, что переменные могут принимать только неотрицательные значения, в программе TORA было получено следующее оптимальное решение двойственной задачи: w = 25, г/, = 0, у2 = 5, у3 = 11, у4 = 13, уъ = 13, ув = 25. Из полученного решения видно, что длительность проекта составляет w = 25 дней.

В соответствии с ограничениями, которые выполняются строго в виде равенств, определяем критические процессы: А -> D -> Фиктивный -> G. Из того факта, что, если ограничение удовлетворено в виде равенства, то соответствующее значение двойственной задачи должно быть положительным, в данном случае вытекает, что значения переменных прямой задачи СРМ (поскольку мы решаем двойственную), ассоциированные с такими ограничениями, будут равны 1. На этом основании можно заполнить следующую таблицу.

Ограничение А

Фиктивный

Переменная прямой задачи 1

Отсюда получаем, что путь А -» D -» Фиктивный -> G является критическим. Заметьте, что положительное значение переменной прямой задачи всегда равно 1, поскольку задержка в один день для любого критического процесса приведет к увеличению продолжительности проекта на один день (напомним, что двойственные переменные интерпретируются как стоимость единицы ресурса, см. раздел 4.3.1).



УПРАЖНЕНИЯ 6.6.4

1. Используя формализацию линейного программирования, определите критический путь для сети проекта, показанного на рис. 6.55.

2. Используя формализацию линейного программирования, определите критический путь для сетей проектов, которые представлены на рис. 6.56.

6.6.5. Сети PERT

Метод PERT отличается от СРМ тем, что здесь длительность процессов характеризуется тремя оценками.

1. Оптимистичная оценка времени а, когда предполагается, что выполнение процесса будет происходить максимально быстро.

2. Наиболее вероятная оценка времени т, когда предполагается, что выполнение процесса будет происходить нормально.

3. Пессимистическая оценка времени Ь, когда предполагается, что выполнение процесса будет происходить очень медленно.

Любая возможная оценка времени выполнения процесса будет лежать в интервале (а, Ь). Поэтому оценка времени т также должна лежать в этом интервале. На основе этих оценок среднее время D выполнения процесса и дисперсия v вычисляются по формулам

- a + Am + b (b-a\2

Все вычисления метода СРМ, которые описаны в разделах 6.6.2 и 6.6.3 выполнимы, если заменить значения длительностей D процессов оценками D .

Теперь можно определить вероятность того, что узел модели будет достигнут в заранее запланированное время Sf. Пусть е.- время наискорейшего достижения узла Поскольку длительности выполнения процессов, которые ведут от начального узла к узлу j, - случайные величины, то ej также является случайной величиной. Предположив, что все процессы в сети статистически независимы, можно определить среднее (математическое ожидание) М{е;) и дисперсию var{e;} следующим образом. Если существует только один путь от начального узла к узлу j, то среднее является суммой ожидаемых длительностей D выполнения всех процессов, входящих в этот путь, а дисперсия равна сумме дисперсий v тех же процессов. С другой стороны, если к узлу ведет более одного пути, то до того, как будут вычислены среднее и дисперсия, необходимо найти вероятностное распределение длительности выполнения процессов, которые составляют самый длинный путь. Эта задача достаточно сложная, поскольку она эквивалентна задаче, вычисляющей распределение максимума нескольких случайных величин. Для упрощения этой задачи среднее МЦ} и дисперсия var{e} вычисляются только для пути, для которого сумма ожидаемой длительности выполнения процессов максимальна. Если несколько путей имеют равные значения среднего, то выбирается тот, для которого дисперсия больше, поскольку этот путь отражен наименее четко, и поэтому будет вычислена более общая оценка вероятностей.

После того как будет вычислено среднее М{е} и дисперсия уагЦ}, вероятность того, что узел будет достигнут в запланированное время S, можно вычислить по формуле

\е -Ще } S.-M{e }} P{jZS,} = P\ ; < ; \ = P{z<K,},



где 2 - случайная величина, имеющая стандартное нормальное распределение, к 5,-М{е,.}

Случайная величина z имеет среднее 0 и стандартное отклонение 1 (см. приложение В). В данном случае использование нормального распределения оправдано тем, что е. является суммой независимых случайных переменных. Согласно центральной предельной теореме (см. раздел 12.5.4) величина ef приближенно распределена по нормальному закону.

Пример 6.6.6

Рассмотрим проект из примера 6.6.2. Чтобы не повторять вычисление критического пути, значения а, т и Ь, представленные в таблице ниже, были выбраны так, чтобы ZX = Dy для всех i и /.

Процесс i-j (а, т, Ь) Процесс i-j (а, т, Ь)

А 1-2 (3,5,7)

(1.2, 3)

В 1-3 (4,6,8)

(9,11,13)

С 2-3 (1,3,5)

(1.1.1)

D 2-4 (5,8,11)

(Ю, 12, 14)

Средние D:j и дисперсии Vtj для различных процессов даны в следующей табли-

це. Заметьте, что для фиктивного процесса (а, т, Ъ) -

(0, 0, 0), поэтому его среднее

и дисперсия также равны нулю.

Процесс i-j Dij Vij

Процесс

Dij Vn

А 1-2 5 0,444

2 0,111

В 1-3 6 0,444

11 0,444

С 2-3 3 0,444

1 0,000

D 2-4 8 1,000

12 0,444

В таблице ниже приведены самые длинные пути (которые были определены по

средней длительности) от начального узла 1 ко всем остальным узлам, а также со-

ответствующие средние значения и дисперсии.

Узел Самый длинный путь i

Среднее пути

Стандартное отклонение пути

2 1-2

5,00

0,67

3 1-2-3

8,00

0,94

4 1-2-4

13,00

1,20

5 1-2-4-5

13,00

1,20

6 1-2-4-5-6

25,00

1,37

И наконец, в следующей таблице представлены вычисленные аналитиком значения вероятностей того, что каждый узел будет достигнут в запланированное время Stj.

[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]