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


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


75

5.4. Авиакомпания KeeWee выполняет полеты между городами А и В согласно расписанию, приведенному в табл. 5.54. Экипаж может вернуться в свой город не ранее чем через 90 минут после прилета либо на следующий день. Составьте расписание назначения экипажей на рейсы, минимизирующее суммарное время простоев всех экипажей.

Таблица 5.54

Рейс Отлет из города А Прилет в город В Рейс Отлет из города В Прилет в город А

6:00

8:30

7:30

9:30

8:15

10:45

9:15

11:15

13:30

16:00

16:30

18:30

15:00

17:30

20:00

22:00

Таблица 5.53



ГЛАВА 6

СЕТЕВЫЕ МОДЕЛИ

В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Недавние исследования показывают, что не менее 70% реальных задач математического программирования можно представить в виде сетевых моделей. Приведем несколько конкретных примеров.

1. Проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода.

2. Поиск кратчайшего маршрута между двумя городами по существующей сети дорог.

3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.

4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.

5. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).

Решение приведенных задач (как и многих аналогичных) требует применения различных сетевых оптимизационных алгоритмов. В этой главе будут рассмотрены следующие пять алгоритмов.

1. Алгоритм нахождения минимального остовного дерева (пример 1).

2. Алгоритм поиска кратчайшего пути (пример 2).

3. Алгоритм определения максимального потока (пример 3).

4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью (пример 4).

5. Алгоритм определения критического пути (пример 5).

Задачи, вытекающие из перечисленных примеров, можно сформулировать и решать как задачи линейного программирования. Однако специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стандартный симплекс-метод.



6.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Сеть состоит из множества узлов, связанных дугами (или ребрами).1 Таким образом, сеть описывается парой множеств (N, А), где N - множество узлов, а А- множество ребер. Например, сеть, показанная на рис. 6.1, описывается следующим образом.

N={1,2, 3,4, 5},

А= {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}.

Рис. 6.1. Пример сети

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

Ребро называется направленным, или ориентированным (и в этом случае ребро будем называть дугой), если в одном направлении возможен только положительный поток, а в противоположном - только нулевой. В ориентированной сети все ребра ориентированы.

Путем называется последовательность различных ребер, соединяющих два узла, независимо от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис. 6.1 дуги (2, 3), (3, 4) и (4, 2) составляют цикл. Ориентированный цикл - это цикл, в котором все дуги ориентированы в определенном направлении.

Связная сеть - такая сеть, у которой любые два узла связаны по крайней мере одним путем. На рис. 6.1 показан именно такой тип сети. Деревом называется связная сеть, содержащая подмножество узлов исходной сети и не имеющая циклов. Остовное деревог- это дерево, содержащее все узлы сети. На рис. 6.2 показаны дерево и остовное дерево для сети из рис. 6.1.

Дерево Остовное дерево

Рис. 6.2. Дерево и остовное дерево для сети из рис. 6.1

1 Чтобы согласовать используемую здесь терминологию с терминологией теории графов, составляющей основу рассматриваемых сетей, будем называть дугами только ориентированные ребра. Термин "ребро" (как более общее понятие) часто будем употреблять для обозначения как ребер, так и дуг. Также отметим очевидное соответствие между узлом сети и вершиной графа. - Прим. ред.

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