Linear Programming Output summary 17 страница

Программа TORA также может применять алгоритм Флойда для решения сете­вых задач. Для этого в меню SOLVE/MODIFY выберите команду Solve problem^ Iterations^ Floyd's algoritm (Алгоритм Флойда). На рис. 6.22 показано выходное ок­но TORA с решением задачи из примера 6.3.5 (файл ch6ToraFloydEx6-3-5.txt).

УПРАЖНЕНИЯ 6.3.3

1. В задаче из примера 6.3.5 определите кратчайшие пути между следующими парами узлов.

a) От узла 5 к узлу 1.

b) От узла 3 к узлу 5.

c) От узла 5 к узлу 3.

d) От узла 5 к узлу 2.

2. Примените алгоритм Флойда к сети, показанной на рис. 6.23. Заметьте, что ребра (7, 6) и (6, 4) ориентированы. Определите кратчайшие пути между сле­дующими парами узлов.

Глава 6. Сетевые модели

- TORA D:\Work\ToraFiles\ch6ToraFloydEx6 3 5Ы

то ид орт, Ли i»i».mh— ид -и its ripii. Диктат пя

NETWORK MODELS

FLOYu S SHORTEST ROUT E ALuuRITHM Select Output Option

wo			DO			SO
	N 1	hz	N3	N4	N5 Hi	hz *i	N4 N5
InI	■		10,00	mnn»y;		2_3|	4 5
№	1 зло	■		5,00	infinity H 1		4 5
Iю	mmm			5.00,	15,00 H 1
N4		5,oo|	«,00	----<м1"Ш г i: 5]
Ins	■Zu ~j	MiMyl	If IV	4,001	H№ 1		_«
tar 1			Dl			S1
	hi	нг	N3	N4	N5 hi	N2 N3	N4 hs

Puc. 6.22. Решение задачи из примера 6.3.5

a) От узла 1 к узлу 7.

b) От узла 7 к узлу 1.

c) От узла 6 к узлу 7.

Рис. 6.23. Сеть для задачи из упражнения 2

3. Телефонная компания обслуживает шесть удаленных друг от друга районов, которые связаны сетью, показанной на рис. 6.24. Расстояния на схеме сети указаны в милях. Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между любыми двумя районами.

6.3. Задача поиска кратчайшего пути

Рис. 6.24. Сеть для задачи из упражнения 3

6.3.3. Формализация задачи поиска кратчайшего пути как задачи ЛП

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

Пусть сеть состоит из п узлов и нужно найти кратчайший путь между некото­рыми узлами s и t этой сети.

Формализация 1. В этой формализации предполагается, что в узел s входит од­на единица внешнего потока и этот поток выходит через узел t сети. Обозначим

х_1} — величина потока, проходящего по дуге (£, у), с_у — длина дуги (г, у).

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

минимизировать Х^СЛ

по всем существующим дутам (>./)

Для каждого узла определяется только одно ограничение, задающее баланс по­тока, проходящего через данный узел:

общий входной поток = общий выходной поток.

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

Пусть

у. — переменная двойственной задачи, ассоциированная с узлом у.

Считая узлы s и t начальным и конечным узлами сети, двойственная задача за­пишется следующим образом.

Максимизировать z = у, - у_г

при ограничениях

!/.-!/,< с_ц для всех возможных пар / и у, все y_t свободные переменные.

Глава 6. Сетевые модели

Пример 6.3.6

Рассмотрим сеть из примера 6.3.4. Предположим, что необходимо определить кратчайший путь из узла 1 в узел 2. Таким образом, здесь s = 1 и t = 2. На рис. 6.25 показано, как одна единица потока входит в узел 1 и выходит из узла 2.

Рис. 6.25. Входной и выходной потоки

Первая формализация дает следующую задачу ЛП.

	Х12	Х13	Х23	Х34	Х35	Х42	Х45
Минимизировать z =
Узел 1	-1	-1						= -1
Узел 2			-1					= 1
Узел 3				-1	-1			= 0
Узел 4						-1	-1	= 0
Узел 5								= 0

Ограничения представляют балансы потоков, протекающих через каждый узел. Например, в узле 2 баланс потоков "входной поток = выходной поток" выражается как равенство х₁₂ + х₄₂ — 1 + х₂₃. Отметим, что одно из ограничений всегда будет из­лишним. Например, сумма четырех последних ограничений дает равенство х₁₂ + х₁₃ = 1, которое совпадает с первым ограничением.

Оптимальным решением (полученным с помощью программы TORA, файл ch6ToraLpShortRouteEx6-3-6.txt) является z — 55, х₁₃ = 1, x_3i = 1, x_t2 = 1. Это решение дает кратчайший путь 1-»3-»4-»2из узла 1 в узел 2 длиной 2 = 55 (миль).

При использовании второй формализации задача, двойственная к представленной выше задаче ЛП, имеет вид.

Максимизировать z = у₂ - у_г

при ограничениях

y₂-y_t< 100 (маршрут 1-2), y₃-y_t< 30 (маршрут 1-3), у₃-у₂< 20 (маршрут 2-3), у₄-у₃< 10 (маршрут 3-4), Уь~Уг^ ⁶⁰ (маршрут3-5),

6.3. Задача поиска кратчайшего пути

y₂-y_t<15 (маршрут 4-2),

У₅-у₄< 50 (маршрут 4-5),

y_v у₂, у₅ — свободные переменные.

Хотя двойственная задача строится чисто математическим путем на основе прямой задачи, ее можно сформулировать, не опираясь напрямую задачу.

Определим y_t как расстояние до узла £.² Из этого определения следует, что крат­чайшее расстояние между узлами 1 и 2 можно найти путем максимизации величи­ны у₂ - у_г Ограничение, связанное с маршрутом (t, j), показывает, что расстояние от узла i до узла j не может превышать длину этого маршрута. Это расстояние мо­жет быть меньше длины маршрута, если узел j можно достичь из узла t через дру­гие промежуточные узлы, как предлагает кратчайший путь. Например, расстояние от узла 1 до узла 2 не может превышать 100.

Если переменные y_t интерпретируются как расстояния, то мы вправе предполо­жить, что все эти переменные неотрицательны (вместо условия, что они свободны). Мы также можем положить, что у_г = 0 как расстояние до узла 1. Исходя из этих предположений получаем оптимальное решение: z = 55, у₁ = 0, у₂ — 55, у₃ = 30, y_t = 40, y_s = 0. Значение г = 55 дает кратчайшее расстояние от узла 1 до узла 2. Это же значение можно получить как у₂ - у^ = 55 - 0 = 55.

Определение кратчайшего пути из этого решения не очевидно. Нетрудно проверить непосредственными вычислениями, что решение удовлетворяет ограничениям для маршрутов 1-3, 3-4 и 4-2 в виде равенств. Эти ограничения и определяют крат­чайший путь как 1 —> 3 —> 4 —> 2.

Другой способ найти ограничения, которые выполняются в виде равенств, заклю­чается в использовании решения двойственной задачи, полученной с помощью вто­рой формализации. Любое ограничение, которое включает ненулевую двойствен­ную переменную, должно выполняться в виде равенства (см. раздел 4.2.4). Следующая таблица показывает маршруты (ограничения) и значения соответст­вующих двойственных переменных.

Маршрут (ограничение)	1-2	1-3	2-3	3-4	3-5	4-2	4-5
Двойственная переменная

УПРАЖНЕНИЯ 6.3.4

1. В примере 6.3.6, используя обе формализации, найдите кратчайшие пути для следующих пар узлов.

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

b) От узла 2 до узла 5.

Здесь предполагается отсчитывать расстояние от некоторой фиксированной точки, од­ной для всех узлов. Ниже в качестве такой начальной точки взят узел 1. — Прим. ред.

Глава 6. Сетевые модели

6.3.4. Решение задачи поиска кратчайшего пути в Excel

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