<<
>>

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

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

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

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

Ячейка Формула
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
<< | >>

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

  1. 4.3 Метод диагностического определения потребительной стоимости.
  2. 2.1 Постановка и математическая модель задачи
  3. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  4. Поток минимальной стоимости.
  5. Региональная политика в сфере туризма, цели и задачи.
  6. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  7. Критерии оптимальности.
  8. ФОРМИРОВАНИЕ СИСТЕМЫ ЦЕЛЕВЫХ ПАРАМЕТРОВ ОРГАНИЗАЦИИ ДЕНЕЖНЫХ ПОТОКОВ ПРЕДПРИЯТИЯ
  9. МЕХАНИЗМ ФОРМИРОВАНИЯ [. ИНВЕСТИЦИОННОЙ ПРИБЫЛИ И ИНВЕСТИЦИОННОГО чистого ДЕНЕЖНОГО ПОТОКА
  10. ЦЕЛЬ И ЗАДАЧИ ФИНАНСОВОГО МЕНЕДЖМЕНТА
  11. Определение стоимости инвестиционного проекта.
  12. Основы оценки стоимости предприятия [бизнеса)
  13. Доходный подход к оценке стоимости предприятия (бизнеса]
  14. 1.4. Постановка задач управления службой скорой медицинской помощи
  15. Задачи