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

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

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

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

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

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

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

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

по всем существующим яутам (l,/)

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

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

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

Пусть

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

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

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

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

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

Пример 6.3.6

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

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

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

Ограничения представляют балансы потоков, протекающих через каждый узел. Например, в узле 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. - Прим. ред.