Входные данные

BCD Е f S н~

Задана нахождения кратчайшего пути

i--

К-во умов

N1 NZ NJ Ш N5

Спрос

. .максимум Ш

Матрица удельных стоимостей

Предложения

9999 100 30 9999 9999

9999 9999 30 9999 9999

9999 9999 9999 10 60

9999 15 9999 9999 50

9999 9999 9999 9999 9999

Опттшальное решение

Общая стоимость 55

От- в

N1 -N2 N1 - N3 N1 -N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2-N5 N3-N1 N3-N2 N3-N4 N3-N5 N4 - N1

Поток

0 1 0 0 0 0 0 О

о о 1

1Е-13 0

Ъ спос 999999 999999 999999 999999

999999 999999 999999 999999 999999 999999 999999

999999 999999

Промежуточные вычисления

Имя Узел

N2 N3 N4 N5

Поток

1Е-11 0

1Е 13

Спрос

От В Уд. стоимость

100 30 9999 9999 9999 30 9999 9999

1 9999

2 9999

4 10

5 60

1 9999

2 15

Поиск решения

Установить целевую ячейку:

1*8*18

Равной: <~

максимальному значению

ЭНЭЧбНИО

Выполнить ~] Закрыть I

с минимальному значению Иэменая ячейки.

$B*20:$S$39

Ограничения

$F*19:$F$23 = $G$19:$G$23

31 Предположить

ры {

Добавить

Изменить

У далить

Параметры

Восстановить

Справка

Рис. 6.26. Вычисление кратчайшего пути в Excel

На рис. 6.26 строки от 11 до 15 и столбец К скрыты для экономии места.

Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно немного модифицировать для решения задачи нахождения кратчайшего пути. Для решения задачи используется первая формализация (раздел 6.3.3). Максимальный размер сети - 10 узлов. На рис. 6.26 показан рабочий лист, на котором решается задача из примера 6.3.4 (файл ch6SolverShortestRoute.xls). Матрица расстояний записана в диапазоне В6:К15.3 Бесконечное значение расстояния (равное здесь 9999 или другому достаточно большому числу) вводится для несуществующих дуг. Поскольку определяется кратчайшее расстояние между узлами 1 и 2, величина предложения для узла 1 и величина спроса для узла 2 устанавливаются равными 1. Остальные значения спроса и предложения остаются равными нулю.

После того как будут введены значения спроса и предложения, рабочий лист пе-ресчитывается автоматически. Выделенные столбцы В, С, F и G содержат исходные данные задачи, необходимые для использования средства Поиск решения. Диапазон В20:В39 (изменяемые ячейки для средства Поиск решения) содержит величины потоков, проходящие по каждой дуге. Столбец С содержит значение пропускных способностей дуг (диапазон С20:С39). В задаче поиска кратчайшего пути эти пропускные способности в вычислениях не участвуют, поэтому они имеют бесконечные значения (равные 99999). Ограничения модели представляют балансы потоков, проходящих через каждый узел. Как показано в разделе 5.3.3, с помощью функций СУММЕСЛИ вычисляются чистые потоки через каждый узел, для чего используются данные из столбцов I и J. Все эти вычисления выполняются автоматически. Все, что необходимо сделать вам для решения задачи, - это указать диапазон изменяемых ячеек и задать ограничения в диалоговом окне средства Поиск решения. На рис. 6.26 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются в виде равенства F19:F23=G19:G23.

Решение N1-N3 = 1, N3-N4 = 1 и N4-N2 = 1, показанное на рис. 6.26, дает общее расстояние 55 миль. Это решение означает, что кратчайший путь проходит через узлы 1 - 3 -> 4 -> 2.

УПРАЖНЕНИЯ 6.3.5

1. Измените рабочую книгу ch6SolverShortestRoute.xls применительно к задаче примера 6.3.4, чтобы найти кратчайшие пути между следующими парами узлов.

a) От узла 1 до узла 5.

b) От узла 4 до узла 3.

2. Измените рабочую книгу ch6SolverShortestRoute.xls применительно к задаче из упражнения 6.3.1.2, чтобы найти кратчайший путь между узлами 4 и 7.

6.4. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперегонных заводов. Для перекачки нефти предусмотрены магистральные насосные станции. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты трубопровода могут быть как однонаправленные (осуществляют перекачку нефти только в одном направлении), так и двунаправленные. В однонаправленных сегментах положительная пропускная способность предполагается в одном направлении и нулевая - в другом. На рис. 6.27 показана типовая сеть нефтепроводов. Как определить максимальную пропускную способность (т.е. максимальный поток) между нефтяными скважинами и нефтеперегонными заводами?

При решении данной задачи исходную сеть необходимо свести к сети с одним источником и одним стоком. Этого можно достичь, вводя дополнительные дуги с бесконечной пропускной способностью от источника к скважинам и от нефтеперегонных заводов к стоку (на рис. 6.27 эти дуги показаны пунктирными линиями).

Для ребра (/, у), где i < у, используем запись (С,Су,) для представления пропускных способностей в направлениях i -> у и у -> i соответственно. Во избежание недоразумений на схеме сети С. будем располагать на ребре (t, у) ближе к узлу i, a Cjt - ближе к узлу у, как показано на рис. 6.28.

Источник

Скважиньп Насосные станции i Нефтеперегонные заводы

Рис. 6.27. Сеть, связывающая скважины, насосные станции и нефтеперегонные заводы

Рис. 6.28. Обозначение пропускных способностей

6.4.1. Перебор разрезов

Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к стоку. Пропускная способность разреза равна сумме пропускных способностей разрезанных ребер. Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.

Пример 6.4.1

Рассмотрим сеть, показанную на рис. 6.29. На этом рисунке при обозначении пропускных способностей двунаправленных ребер придерживались соглашения, принятого ранее (рис. 6.28). Например, для ребра (3, 4) пропускная способность в направлении 3 -> 4 равна 10, а в направлении 4 -> 3 - только 5. >

Разрез 2

Рис. 6.29. Пример разрезов сети