Задача о потоке минимальной стоимости
Задана сеть
с одним источником
,
одним стоком
и промежуточными вершинами
.
Каждой дуге
сети поставлены в соответствие две
величины: пропускная способность дуги
(ребра)
;
дуговая стоимость
(стоимость доставки единицы потока по
дуге), одинаковая в обоих направлениях.
Необходимо найти поток из источника в
сток заданной величины
,
обладающий минимальной стоимостью. Под
стоимостью потока будем понимать
стоимость доставки того или другого
количества вещества из источника в
сток. При этом предполагается, что
заданная величина потока не превышает
величины максимального потока из
в
.
Формальная запись задачи имеет вид:
(3.12)
(3.13)
(3.14)
(3.15)
Отметим, что если бы не было ограничений на пропускные способности дуг (ребер), то для решения задачи достаточно было бы найти самый экономичный путь (путь минимальной стоимости) из в и пропустить по нему весь поток (путь минимальной стоимости — это путь, сумма стоимостей которого, приписанных дугам, является минимальной).
Приведем пример решения задачи потока минимальной стоимости в Excel.
Пример 4
Рассмотрим решение задачи, относящейся к классу задач о потоке минимальной стоимости. Рассматривается сеть, представленная на Рис. 3.13.
Цифры в скобках обозначают: в случае
узла 1 (источника) – количество имеющегося
продукта, в случае узлов 4 и 5 – потребности
соответствующих объектов в продукте.
Первые числа у стрелок означают удельную
стоимость транспортировки продукта (
), а вторые – пропускную способность
дуги (например, магистрали). Индекс * у
дуги (2,3) и (4,5) означает, что пропускные
способности данных дуг могут считаться
неограниченными (например, они значительно
превосходят имеющиеся в наличии запасы
продукта).
Требуется определить интенсивности потоков, при которых суммарная стоимость доставки была бы минимальной, а потребности узлов 4 и 5 были бы удовлетворены.
Решение.
Очевидно, задача сводится к минимизации функции:
при ограничениях:
,
,
,
,
,
Введем исходные данные на рабочий лист Excel в соответствии с Рис. 3.14. В качестве целевой ячейки выберем E13; для расчетных значений неизвестных интенсивностей потока выделим диапазон ячеек A6:I6. В ячейки A8:A12 и целевую ячейку введем формулы для ограничений задачи и целевой функции в соответствии с приведенной ниже таблицей.
Рис. 3.14. Форма для решения примера 4.
Ячейка |
Формула |
A8 |
=A6+B6 |
A9 |
=A6-D6-E6-C6 |
A10 |
=B6+C6+H6-F6-G6 |
A11 |
=D6+F6-I6 |
A12 |
=G6+E6+I6-H6 |
E13 (целевая ячейка) |
=СУММПРОИЗВ(A4:I4;A6:I6) |
После вызова Поиска решения введем следующие ограничения:
$A$6<=15 |
$A$10=0 |
$B$6<=8 |
$F$6<=15 |
$A$8<=20 |
$A$11=5 |
$D$6<=4 |
$G$6<=5 |
$A$9=0 |
$A$12=15 |
$E$6<=10 |
$H$6<=4 |
В результате решения получим ответ:
,
и для интенсивностей дуговых потоков:
(1,2) |
12 |
(2,4) |
4 |
(3,5) |
1 |
(1,3) |
8 |
(2,5) |
0 |
(5,3) |
0 |
(2,3) |
8 |
(3,4) |
15 |
(4,5) |
14 |
Пример 5
Рассмотрим еще один пример решения задач подобного типа.
Имеется транспортная система, представленная сетевой моделью следующего вида (Рис.3.15). Цифры у дуг означают удельные стоимости перевозки по дугам, соединяющим соответствующие узлы. Требуется определить маршрут, стоимость которого была бы минимальна.
Решение. Введем данные на рабочий лист в соответствии с Рис.3.16.
Рис. 3.16. Форма для решения примера 5
Введем следующие формулы в указанные ячейки:
Ячейка |
Формула |
A8 |
=A6+B6 |
A9 |
=A6+C6-D6-E6 |
A10 |
=B6-C6-F6 |
A11 |
=D6-H6-G6 |
A12 |
=F6+G6-I6 |
A13 |
=I6-J6 |
A14 |
=E6+H6+J6 |
E13 |
=СУММПРОИЗВ(A4:J4;A6:J6) |
Введем все необходимые ограничения. С помощью Поиска решения получим ответ:
.
Маршрут, перевозка по которому имеет наименьшую стоимость, есть: (1-3-5-6-7).