Пример 6.3.6
Рассмотрим сеть из примера 6.3.4. Предположим, что необходимо определить кратчайший путь из узла 1 в узел 2. Таким образом, здесь s = 1 и t = 2. На рис. 6.25 показано, как одна единица потока входит в узел 1 и выходит из узла 2.
Рис. 6.25. Входной и выходной потоки
Первая формализация дает следующую задачу ЛП.
| | | | | | | | |
Минимизировать z = | | | | | | | | |
Узел 1 | | | | | | | | = -1 |
Узел 2 | | | | | | | | |
Узел 3 | | | | | | | | |
Узел 4 | | | | | | | | |
Узел 5 | | | | | | | | |
Ограничения представляют балансы потоков, протекающих через каждый узел. Например, в узле 2 баланс потоков "входной поток = выходной поток" выражается как равенство х12 + х42 - 1 + х23. Отметим, что одно из ограничений всегда будет излишним. Например, сумма четырех последних ограничений дает равенство х12 + хп = 1, которое совпадает с первым ограничением.
Оптимальным решением (полученным с помощью программы TORA, файл ch6ToraLpShortRouteEx6-3-6.txt) является z - 55, х13 = 1, x3i = 1, xt2 = 1. Это решение дает кратчайший путь 1-»3-»4-»2из узла 1 в узел 2 длиной 2 = 55 (миль).
При использовании второй формализации задача, двойственная к представленной выше задаче ЛП, имеет вид.
Максимизировать z = у2 - уг
при ограничениях
y2-yt< 100 (маршрут 1-2), y3-yt< 30 (маршрут 1-3), у3-у2< 20 (маршрут 2-3), у4-у3< 10 (маршрут 3-4), Уь~Уг 60 (маршрут3-5),
y2-yt<15 (маршрут 4-2),
У5-у4< 50 (маршрут 4-5),
yv у2, у5 - свободные переменные.
Хотя двойственная задача строится чисто математическим путем на основе прямой задачи, ее можно сформулировать, не опираясь напрямую задачу.
Определим yt как расстояние до узла £.2 Из этого определения следует, что кратчайшее расстояние между узлами 1 и 2 можно найти путем максимизации величины у2 - уг Ограничение, связанное с маршрутом (£, у), показывает, что расстояние от узла i до узла у не может превышать длину этого маршрута. Это расстояние может быть меньше длины маршрута, если узел у можно достичь из узла t через другие промежуточные узлы, как предлагает кратчайший путь. Например, расстояние от узла 1 до узла 2 не может превышать 100.
Если переменные yt интерпретируются как расстояния, то мы вправе предположить, что все эти переменные неотрицательны (вместо условия, что они свободны). Мы также можем положить, что уг = 0 как расстояние до узла 1. Исходя из этих предположений получаем оптимальное решение: z = 55, у1 = 0, у2 - 55, у3 = 30, yt = 40, ys = 0. Значение z = 55 дает кратчайшее расстояние от узла 1 до узла 2. Это же значение можно получить как у2 - у = 55 - 0 = 55.
Определение кратчайшего пути из этого решения не очевидно. Нетрудно проверить непосредственными вычислениями, что решение удовлетворяет ограничениям для маршрутов 1-3, 3-4 и 4-2 в виде равенств. Эти ограничения и определяют кратчайший путь как 1 -> 3 -> 4 -> 2.
Другой способ найти ограничения, которые выполняются в виде равенств, заключается в использовании решения двойственной задачи, полученной с помощью второй формализации. Любое ограничение, которое включает ненулевую двойственную переменную, должно выполняться в виде равенства (см. раздел 4.2.4). Следующая таблица показывает маршруты (ограничения) и значения соответствующих двойственных переменных.
Маршрут (ограничение) | | | | | | | |
Двойственная переменная | | | | | | | |
УПРАЖНЕНИЯ 6.3.4
1. В примере 6.3.6, используя обе формализации, найдите кратчайшие пути для следующих пар узлов.
a) От узла 1 до узла 5.
b) От узла 2 до узла 5.
Здесь предполагается отсчитывать расстояние от некоторой фиксированной точки, одной для всех узлов. Ниже в качестве такой начальной точки взят узел 1. - Прим. ред.
Входные данные
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. Остальные значения спроса и предложения остаются равными нулю.