Задача о потоке минимальной стоимости

Задана сеть с одним источником , одним стоком и промежуточными вершинами .

(3.12)

(3.13)

(3.14)

(3.15)

Отметим, что если бы не было ограничений на пропускные способности дуг (ребер), то для решения задачи достаточно было бы найти самый экономичный путь (путь минимальной стоимости) из в и пропустить по нему весь поток (путь минимальной стоимости — это путь, сумма стоимостей которого, приписанных дугам, является минимальной).

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

Пример 4.

Рассмотрим решение задачи, относящейся к классу задач о потоке минимальной стоимости. Рассматривается сеть, представленная на Рис. 3.13.

Рис. 3.13. Транспортная сеть примера 4.

Цифры в скобках обозначают: в случае узла 1 (источника) – количество имеющегося продукта, в случае узлов 4 и 5 – потребности соответствующих объектов в продукте. Первые числа у стрелок означают удельную стоимость транспортировки продукта ( ), а вторые – пропускную способность дуги (например, магистрали). Индекс * у дуги (2,3) и (4,5) означает, что пропускные способности данных дуг могут считаться неограниченными (например, они значительно превосходят имеющиеся в наличии запасы продукта).

Требуется определить интенсивности потоков, при которых суммарная стоимость доставки была бы минимальной, а потребности узлов 4 и 5 были бы удовлетворены.

Решение.

Очевидно, задача сводится к минимизации функции

при ограничениях

,

,

,

,

,

Введем исходные данные на рабочий лист Excel в соответствии с Рис. 3.14. В качестве целевой ячейки выберем E13; для расчетных значений неизвестных интенсивностей потока выделим диапазон ячеек A6:I6. В ячейки A8:A12 и целевую ячейку введем формулы для ограничений задачи и целевой функции в соответствии с приведенной ниже таблицей.

Рис. 3.14. Форма для решения примера 4.

После вызова Поиска решения введем следующие ограничения: