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


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


72

-ао (2)

Рис. 8.4

Решение. Вершина 1 называется источником, поскольку поток только вытекает из данной вершины. Вершина 5 называется стоком, поскольку поток только втекает в данную вершину. Мы также добавляем некоторую фиктивную дугу из стока в источник с неограниченной пропускной способностью. Данные о пропускных способностях дуг сети приведены в табл. 8.4.

Таблица 8.4

Дуги

(Ь2)

(1,4)

(2,3)

(2,4)

(3,5)

(4,5)

Пропускные способности

Обозначим величину потока из вершины / в вершину j через Ху. В качестве допустимого потока можно предложить поток = 2, = О,

= О, Х24 = 2, JC35 = О, Х45 = 2, = 2 . Для того, чтобы поток бьш допустимым, он должен удовлетворять двум группам условий, которые схематично можно изобразить как

О < поток по дуге < пропускная способность дуги, (8.1)

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

Пусть Z- величина потока. Тогда задачу о максимальном потоке можно представить как задачу линейного программирования.



maxz

< 2 (ограничения на пропускные способности дуг)

<3,

хз5<1, < 2 ,

z = + 14 (условие сохранения потока в вершине 1) 12 = 23 + 24 (условие сохранения потока в вершине 2) 23 = 35 (условие сохранения потока в вершине 3) + Х23 = Х45 (условие сохранения потока в вершине 4) Х45 + Х35 = z (условие сохранения потока в вершине 5)

Ху>0,

Одно из оптимальных решений этой задачи линейного программирования

z = 3, Х12 = 2 , = 1, Х23 = 1, Х24 = 1, Х35 = 1, Х45 = 2 , Х51 = 3.

т 8.3.1. Метод Форда и Фалкерсона

Величина максимальг ного потока из источника в сток равна, величине минимального разреза.

для решения задачи о максимальном потоке. Предположим, что уже найден какой-либо допустимый поток (например, нулевой поток является допустимым). Зададимся двумя вопросами: 1) как, имея допустимый поток, определить, является ли он оптимальным? 2) как в случае, если допустимый поток не является оптимальным, получить другой допустимый поток больше по величине данного?

Первоначально ответим на второй вопрос. Для этого для каждой дуги выясним, каким из двух приведенных свойств обладает каждая из дуг сети: 1) поток по дуге (ij) меньше, чем пропускная способность дуги (ij), что, естественно, означает, что поток по дуге может быть увеличен.



Множество таких дуг сети обозначим /; 2) поток по дуге (iJ) положителен, что означает, что он может быть уменьшен. Множество таких дуг сети обозначим R.

В качестве иллюстрации множеств 1и R рассмотрим сеть, изображенную на рис. 8.5.

Рис. 8.5

Дуга (1,2) принадлежит множеству /, дуга (1,3) принадлежит множествам/и дуга (3,4) принадлежит множеству R, дуга (2,4) принадлежит множеству /.

Теперь можем описать процедуру метода Форда и Фалкерсона расстановки меток для построения потока большей величины, чем данный.

Шаг 1. Присвоим метку источнику (вершине 1).

Шаг 2. Присвоим остальные метки вершинам и дугам (кроме дуги (4,1)), исходя из следующих правил: 1) если вершина х имеет метку, а вершина у не помечена и дуга (х,>) е /, то пометим дугу (х,у) и вершину у. В этом случае дуга {х,у) называется дугой прямого направления; 2) если вершина х имеет метку, а вершина у не помечена и дуга (у,х) е R, то пометим дугу (урс) и вершину у. В этом случае дуга (у,х) называется дугой обратного направления.

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

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

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