1. Максимальный поток через дугу (4, 5), определяемый пропускной способностью, равен со.

2. Максимальное увеличение потока через дугу (1, 4) равно 35 - 30 = 5 единиц.

3. Максимальное уменьшение потока через дугу (1, 3) равно 10 единиц.

4. Максимальное уменьшение потока через дугу (3, 5) равно 30 единиц.

Таким образом, поток через дугу (4, 5) можно увеличить до 5 единиц; эта дуга входит в базис, а дуга (1, 4) с потоком в 35 единиц исключается из базиса.

Выполнив подстановку хы = 35 - х41, получим сеть, показанную на рис. 6.46, где дуги (1, 3), (2, 3), (3, 5) и (4, 5) формируют остовное дерево сети (базисное решение). Для дуги (1, 4) с обратным направлением потока изменена стоимость прохождения потока до -5 долл. Проверьте самостоятельно, что в уравнения для потоков в узлах 1 и 4 будет добавлено 5 единиц входного потока.

<4)[5]

5(оо)

12 *-12 z41 ~ с41=

с12=0-(-5)-3 = 2

11 - 0 - (-5) = -6 15-(-5)-(-1) = -9

[-30]

Рис. 6.46. Сеть на итерации 2

Итерация 3. Вычисленные новые значения разностей z(/ - ct/ для небазисных дуг (1, 2), (4, 1) и (5, 2) показаны на рис. 6.46. Из этих значений вытекает, что в базис следует ввести дугу (1, 2) с потоком в 5 единиц, тогда как дуга (1, 3) исключается из базиса с нулевым значением потока. Новое решение представлено на рис. 6.47.

w, = 0

41 Ml

= 0-(-5)-7 = -: 9 0-(-5) =

52 ь52

с52=-13-(-3)-(-1) = -9

Оптимальное решение:

;5, *1з=0 35 -0 = 35

х23=25

х =30-0 = 30

*35:

= 25, х,

Суммарная стоимость = 490 Рис. 6.47. Сеть на итерации 3

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

УПРАЖНЕНИЯ 6.5.3

1. Решите задачу из упражнения 6.5.1.1 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью. Покажите также, что эту задачу можно решить как транспортную.

2. Решите задачу из упражнения 6.5.1.2 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью. Покажите также, что эту задачу можно решить как транспортную.

3. Решите задачу из упражнения 6.5.1.3 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.

4. Решите задачу из упражнения 6.5.1.4 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.

5. Решите задачу из упражнения 6.5.1.5 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.

6. Решите задачу из примера 6.5.3 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.

7. Электрическая компания Вайоминга транспортирует по трубопроводам угольную пульпу от трех шахт (1, 2 и 3) к трем электростанциям (4, 5 и 6). Каждый трубопровод может транспортировать не более 10 тонн пульпы в час. Стоимость транспортировки одной тонны пульпы (в долл.), а также предложение шахт и спрос электростанций представлены в следующей таблице.

4 5 6 Предложение

Спрос 16 6 14

Найдите оптимальную схему транспортировки угля к электростанциям.

8. На рис. 6.48 показана сеть из семи городов и расстояния между ними. С помощью симплексного алгоритма для сетей с ограниченной пропускной способностью найдите кратчайший маршрут между городами 1 и 7. (Совет. Пусть узлы 1 и 7 имеют результирующие потоки [+1] и [-1] соответственно, а все остальные - нулевые результирующие потоки.)

Рис. 6.48. Сеть для задачи из упражнения 8

9. Покажите, что симплексный алгоритм вычисления потока минимальной стоимости для сетей с ограниченной пропускной способностью можно применить, чтобы найти максимальный поток в сети (см. раздел 6.4). С его помощью решите задачу из примера 6.4.2. Для определенности положите стоимость прохождения потока от узла 4 к узлу 3 нулевой, остальные данные остаются без изменений.

6.5.4. Решение задачи вычисления потока наименьшей стоимости в Excel

Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно применить, чтобы найти поток наименьшей стоимости. На рис. 6.49 показан рабочий лист, на котором решается задача из примера 6.5.4 (файл

2 Входны дайны

В С Е F G Н

нахождение потока наименьшей стоимости

Матрица пропускных <

N1 N2 N3 N4 N5

10 35 60 0

17 Оптимальное решение

18 Сщая стоимост,

19 От-в Ш N1-N2

N1 - N3 N1 - N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2- N5 N3-N1 N3-N2 N3- N4 N3-N5 N4- N1 N4-M?

Поток

Пр спос

35 0 0

25 О

30 0 0 О

25 0

9999Э9 10 35 0 0 60 0 30 0 0 0

999999 0

Промежуточные вычисления

Имя Узел

м N2 N3

N4 N5

Поток

40 50 0 -30 -60

Спрос От В Уд стоимость

40 50

-30 60

поиск решения

установить целевую ячейку: равной: С максимальному значению

р минимальному значению изменяя ячейки:

$В$1в

$В$20:$В$39 Ограничения:

$В$20:$В$Э9 <= $С$20:$С$39

значению:

31 Гдпопожить ~~3 Добавить I

Выполнить

Закрыть

Параметры

Изменить ]

Удалить

Восс1ановить 1 Справка I

Рис. 6.49. Поиск потока минимальной стоимости в Excel