имеет одно избыточное ограничение, мы можем присвоить произвольное значение одной из переменных двойственной задачи (сравните с алгоритмом решения транспортной задачи из раздела 5.3). Для определенности положим wx = 0. Затем следует решить (базисную) систему уравнений wt - w. = ci;, чтобы вычислить остальные переменные двойственной задачи. Далее находим разности z - сц для небазисных переменных согласно формуле

zlj-cirwl-wrclj.

Теперь осталось показать, как определяется исключаемая из базиса переменная. Для этого рассмотрим следующий числовой пример.

Пример 6.5.4

Сеть трубопроводов связывает две станции опреснения воды с двумя городами. Ежедневное предложение опреснительных станций составляет 40 и 50 миллионов галлонов воды, города ежедневно потребляют 30 и 60 миллионов галлонов воды. Каждая станция трубопроводами соединена с каждым городом непосредственно, однако они могут также перекачивать воду в города через специальную насосную станцию. Кроме того, станция 1 может транспортировать воду на станцию 2, а город 1 - в город 2. Данная сеть сбалансирована, так как в ней суммарный спрос равен суммарному предложению. Описанная сеть показана на рис. 6.43.

Удельная стоимость Пропускная способность

Рис. 6.43. Сеть для примера 6.5.4

Определение начального допустимого базисного решения. Нетрудно построить остовное дерево (на рис. 6.44 показано сплошными дугами) для рассматриваемой сети. Отсюда получаем начальное допустимое базисное решение. Обычно, чтобы найти такое решение, используется метод введения искусственных переменных (подробности см. в [2]).

На рис. 6.44 показано, что базисному решению соответствуют дуги (1, 3), (1, 4), (2, 3) и (3, 5) с потоками 30, 10, 50 и 60 единиц соответственно. Оставшиеся дуги (показаны пунктиром) представляют небазисные переменные. Запись х(с) показывает, что через соответствующую дугу с пропускной способностью с проходит поток х. По умолчанию считается, что х = 0 и с = со.

Итерация 0 Шаг 0.

Рис. 6.44. Сеть на итерации О

Итерация 1

Шаг 1. Определение вводимой в базис переменной. При решении системы уравнений

w, = 0,

w, - wj = cLj для базисных дуг получим значения переменных двойственной задачи.

Дуга (1, 3): w, - w3 = 7 w3 = -7.

Дуга (1, 4): w, - wt = 5 w4 = -5.

Дуга (2, 3): w2 - w3 = 2 w2 = -5.

Дуга (3, 5): w3 - w5 = 8 => wb = -15. Теперь вычисляем разности z,. - с . для небазисных переменных.

Дуга (1, 2): w, - w2 - с12 = 0 - (-5) -3 = 2.

Дуга(2, 5): w2-w5-с25 = (-5) - (-15) -1 = 9.

Дуга (4, 5): wt - w5 - с4б = (-5) - (-15) -4 = 6.

Таким образом, дуга (2, 5) будет введена в базисное решение.

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

5 Направление обхода дуг цикла всегда совпадает с направлением потока, протекающего через дугу, вводимую в базис. В данном случае это направление совпадает с направлением против часовой стрелки, но это, конечно, совсем не обязательно. - Прим. ред.

1. Новый поток в текущей базисной дуге не может быть отрицательным.

2. Поток через вводимую в базис дугу не может превышать ее пропускную способность.

Применение правила 1 показывает, что потоки через дуги (2, 3) и (3, 5) нельзя уменьшить более, чем на min{50, 60} = 50 единиц. Из правила 2 следует, что поток через дугу (2, 5) не может превышать 30 единиц (пропускная способность этой дуги равна 30). Поэтому поток через дуги цикла изменится не более, чем на min{30, 50} = 30 единиц. Таким образом, поток через дугу (2, 5) равен 30 единиц, через дугу (2, 3) 50 - 30 = 20 единиц, а через дугу (3, 5) - 60 - 30 = 30 единиц.

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

*25 = 30 -х52,0<х52<30. Эта подстановка изменит уравнения для потоков, протекающих через узлы 2 и 5.

Текущее уравнение для потоков узла 2: 50 + х]2 = х23 + х2Ъ.

Текущее уравнение для потоков узла 5: х2ь + х35 + х45 = 60. После подстановки х2Ъ - 30 - хЬ2 получим следующее.

Новое уравнение для потоков узла 2: 20 + х12 + х52= х2Г

Новое уравнение для потоков узла 5: х35 + xi5 = хь2 + 30.

Результаты этих изменений показаны на рис. 6.45. Направление потока через дугу (2, 5) изменилось на обратное (от узла 5 к узлу 2), причем, как и ожидалось, хЬ2 = 0. Описанная подстановка также требует изменения стоимости прохождения потока по дуге (2, 5) до -1 долл. Те дуги, направления потоков которых изменены на противоположные, помечены в сети звездочкой.

w, = 0 w4 = -5

-1) = -9 = 6

Рис. 6.45. Сеть на итерации 1

Итерация 2. На рис. 6.45 представлены новые значения разностей z,. - сц (проверьте эти значения!). Очевидно, что в базис следует ввести дугу (4, 5). Введение в базис этой дуги также приводит к образованию цикла.

Величину потока через дугу (4, 5) можно увеличить до наименьшей из следующих величин.