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


[Старт] [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]


98

• TORA D:\Work\ToraFII«tch6Tor*CPM[<6 6 3 t*l

Рис. 6.59. Результаты вычислений для задачи из примера 6.6.2

Рис. 6.60. Временной график проекта из примера 6.6.2



УПРАЖНЕНИЯ 6.6.3

1. Дан процесс (i, j) длительностью £>,., самый ранний срок его начала - Ц и самый поздний срок его завершения - Д. Определите самый ранний срок завершения этого процесса и самый поздний срок его начала.

2. Чему равны общий и свободный запасы времени критических процессов?

3. Для следующих процессов определите максимальный сдвиг начала их выполнения (относительно самого раннего срока начала выполнения), который не нарушает никаких отношений следования с другими процессами.

a) TF= 10, FF= 10, D = 4.

b) TF=10,FF=5,D = 4.

c) TF = 10,FF = 0, £> = 4.

4. В задаче из примера 6.6.4 на основе значений запасов времени ответьте на следующие вопросы.

a) Пусть процесс В начался в 1-й день от начала выполнения всего проекта, а процесс С - в 5-й день (см. рис. 6.57). Каков самый ранний срок начала процессов Е и F?

b) Пусть процесс В начался на 3-й день от начала выполнения проекта, а процесс С - на 7-й. Каков самый ранний срок начала процессов Е и F?

c) Может ли процесс В начаться после 6-го дня от начала выполнения проекта?

5. Пусть в проекте из примера 6.6.2 (рис. 6.54) длительность процессов В и F возросла до 20 и 25 дней соответственно.

a) Определите критический путь.

b) Найдите общие и свободные запасы времени для некритических процессов и пометьте при необходимости их "красными флажками".

c) Пусть процесс А начался на 5-й день от начала выполнения всего проекта. Определите по возможности самые ранние сроки начала процессов С, D, Е и Н.

d) Предположим, для выполнения процессов F, G и Н необходимо одно и то же оборудование. Определите минимально необходимое количество этого оборудования.

6. Вычислите запасы времени и расставьте "красные флажки" процессам проектов, показанных на рис. 6.56. Затем постройте временные графики при соблюдении следующих условий.

Проект А

1. Процесс (1, 5) не может начаться раньше 14-го момента времени.

2. Процессы (5, 6) и (5, 7) используют одинаковое оборудование, которое в любой момент времени может использоваться только в одном процессе.

3. Все другие процессы начинаются так рано, как только возможно. Проект Б

1. Процесс (1, 3) должен начаться так рано, как только возможно, с учетом того, что процессы (1, 2), (1, 3) и (1, 6) используют одинаковое оборудование, которое в любой момент времени может использоваться только в одном процессе.

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



6.6.4. Формализация задачи поиска критического пути как задачи ЛП

Задача определения критического пути в сети проектов, решаемая методом СРМ, противоположна задаче вычисления кратчайшего пути (раздел 6.3) в том смысле, что здесь ищется самый длинный путь от начального узла до конечного. Можно применить формализацию задачи поиска кратчайшего пути из раздела 6.3.3 к задачам нахождения критического пути, решаемых метом СРМ (для краткости будем называть такие задачи задачами СРМ), следующим образом. Предположим, что в сеть в начальном узле поступает одна единица потока, которая покидает сеть в конечном узле. Обозначим

хц - величина потока, проходящего по дуге (£, j), соответствующей процессу (г, j), Dtj - длительность процесса (i, ;). В этих обозначениях целевая функция задачи линейного программирования запишется как

максимизировать г =

но всем процессам

(Сравните с формализацией задачи вычисления кратчайшего пути, где целевая функция минимизируется.) Для каждого узла (проекта) определяется только одно ограничение, задающее баланс потока, проходящего через данный узел:

общий входной поток = общий выходной поток.

Очевидно, что все переменные xtj неотрицательны. Отметим, что одно из ограничений избыточно.

Опять, как и в задачах поиска кратчайшего пути, для решения задачи СРМ можно применить двойственную задачу ЛП. В следующем примере покажем две формализации задачи СРМ.

Пример 6.6.5

Ниже дана формулировка задачи из примера 6.6.2 (см. рис. 6.54) в терминах сетевых моделей линейного программирования. Отметим, что узлы 1 и 6 являются соответственно начальным и конечным узлами.

Фиктивный

Максимизировать z

Узел 1

= -1

Узел 2

Узел 3

Узел 4

Узел 5

Узел 6

С помощью программы TORA было получено следующее оптимальное решение: 2 = 25, х12(А)= 1, x2i(D) = 1, х45(Фиктивный) = 1, x66(G) = 1, все другие переменные равны 0. Решение определяет следующий критический путь: А -> D -> Фиктивный -» G, при этом длительность проекта равна 25 дней.

[Старт] [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]