ЛЕКЦИЯ 10. Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод

Зададим стоимость c_ij передачи единицы потока через каждую дугу e_ij. Можно поставить две задачи:

1. Какова минимальная стоимость передачи заданной величины потока из V₀ в V_n?

2. Какова максимальная величина потока, который можно передать из V₀ в V_n при заданном фиксированном бюджете?

Задачу 1 формально можно представить в виде:

,

при условиях

и ,

где v — требуемая величина потока.

Задачу 2 можно записать в виде:

при условиях , где con – заданная константа,

.

Возможны случаи:

1) Если ограничения на пропускные способности дуг отсутствуют, то величины c_ij можно считать длинами дуг и найти самый дешевый (кратчайший) путь из V₀ в V_n, а затем отправить вдоль него требуемую величину потока.

2) При наложении ограничений на пропускные способности дуг метод передачи потока вдоль самого дешевого пути будет работать, если минимальная пропускная способность этого пути больше, чем v.

3) Если минимальная пропускная способность , то эта дуга будет насыщена и дальнейшее продвижение вдоль этого пути станет невозможным. Это эквивалентно тому, что стоимость дуги становится бесконечной.

Отсюда возникает идея «модифицированной стоимости», когда стоимость зависит от потока, протекающего через дугу.

Схему алгоритма решения задачи 1.

Шаг 0. Начать с нулевых значений потоков на всех дугах.

Шаг 1. Определить модифицированные стоимости , порожденные суще­ствующими потоками, следующим образом:

, если ,

, если ,

, если .

Шаг 2. Найти самый дешевый путь при модифицированных стоимостях , полученных на шаге 1, и передать вдоль него е единиц потока, где

,

среди величин по всем прямым дугам,

среди величин по всем обратным дугам.

Скорректировать текущую величину потока на единиц и вернуться на шаг 1. (Остановиться, если текущий поток стал равен v.)

Этот алгоритм в действительности строит поток с минимальной стоимостью величиной в р единиц для р = 1,2,..., v. Для нахождения самого дешевого пути на шаге 2 можно использовать алгоритм поиска кратчайших путей из раздела, в котором допускаются отрицательные длины дуг (замечание – алгоритм Дейкстра не используется в общем случае для сети с отрицательными длинами дуг).

Пример 10.1. Применим выше описанный алгоритм для передачи 4 единиц потока с минимальной стоимостью в сети, показанной на рис. 27. Для каждой дуги заданы пропускная способность и стоимость передачи единицы потока .

Рис. 27.

Вначале пошлем одну единицу потока вдоль пути V ₀, V ₁, V ₂, V_n, дуга e ₁₂ станет насыщенной. Остаточные пропускные способности станут равны , , а модифицированные стоимости примут значения , . Стоимость передачи потока z ₁=4*1 + 3*1 + 2*1=9. Остаточные пропускные способности дуг и модифицированные стоимости показаны на рис. 28.

Посылаем еще единицу потока по пути V ₀, V ₁, V_n, получим остаточную сеть, показанную на рис. 29. Стоимость передачи потока z ₂=4*1 +8*1=12.

Рис. 28.

Рис. 29.

После передачи еще единицы потока по пути V ₀, V ₂, V_n получится сеть, изображенная на рис. 30. Стоимость передачи потока z ₃=8*1 +4*1=12.

Рис. 30.

Далее мы вынуждены передать одну единицу вдоль пути V ₀, V ₂, V ₁, V_n, после чего модифицированные стоимости станут такими, как показано на рис. 31. Это окончательные остаточные пропускные способности дуг. Стоимость передачи потока на этом шаге z ₄=8*1 - 3*1 + 8*1=13. Итоговый поток: v = 1+ 1 + 1 + 1 = 4. Итоговая стоимость передачи этого потока .

.

Рис. 31.

Заметим, что в окончательном потоке примера 9.1 не используется самый дешевый путь.

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