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

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

Задана сеть  с одним источником , одним стоком  и промежуточными вершинами . Каждой дуге  сети поставлены в соответствие две величины: пропускная способность дуги (ребра) ; дуговая стоимость  (стоимость доставки единицы потока по дуге), одинаковая в обоих направлениях. Необходимо найти поток из источника в сток заданной величины , обладающий минимальной стоимостью. Под стоимостью потока будем понимать стоимость доставки того или другого количества вещества из источника в сток. При этом предполагается, что заданная величина потока не превышает величины максимального потока из  в . Формальная запись задачи имеет вид:

                              (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.

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

В результате решения получим ответ:   , и для интенсивностей дуговых потоков

Пример 5.

Рассмотрим еще один пример решения задач подобного типа.

Имеется транспортная система, представленная сетевой моделью следующего вида (Рис. 3.15). Цифры у дуг означают удельные стоимости перевозки по дугам, соединяющим соответствующие узлы. Требуется определить маршрут, стоимость которого была бы минимальна.

Рис. 3.15. Сетевая модель транспортной системы примера 5.

Решение. Введем данные на рабочий лист в соответствии с Рис. 3.16.

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

Введем следующие формулы в указанные ячейки

Введем все необходимые ограничения. С помощью Поиска решения получим ответ:

                   .

Маршрут, перевозка по которому имеет наименьшую стоимость, есть

                   (1-3-5-6-7).