Информационные технологии сетевого планирования в управлении

Рис. 3.12 Данные для решения задачи о максимальном потоке

Диапазон ячеек A6:Q6 отведем под расчетные значения переменных. В ячейки A8:A14, а также в целевую ячейку F13 введем следующие формулы:

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

В окне диалога Поиска решения для диапазона изменяемых ячеек укажем A6:Q6.

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

Следует отметить, что данная задача имеет неединственное оптимальное решение, то есть при максимальном потоке в 17 единиц может иметь место различное распределение потоков по дугам.

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

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

(3.12)

(3.13)

(3.14)

(3.15)

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

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

Пример 4

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

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

 Скачать реферат