4.1. Оптимальные циклы в графах с двойными весами [24.9]

Во многих ситуациях возникает следующая задача. Дан граф, дугам которого приписаны два числа — вес и некоторое другое число Нужно найти такой цикл для которого целевая функция

минимальна (или максимальна).

Рассмотрим, например, обслуживание судном или самолетом некоторой сети маршрутов и предположим, что «выгода», а «время», необходимое для прохождения по дуге Задача нахождения замкнутого обслуживаемого маршрута максимизирующего выгоду, относится к задачам описываемого типа. Более реалистичные задачи, учитывающие емкость транспортных средств рассмотрены в работе [93.

Другими задачами, которые можно сформулировать как задачи нахождения оптимальных циклов в графах с двойными весами, являются задачи планирования параллельных вычислений [31] и управления технологическими процессами [6].

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

Возьмем некоторое пробное значение целевой функции и рассмотрим граф с модифицированными весами

Попытка найти в цикл отрицательного веса с матрицей может привести к следующим трем возможностям.

A. Существует цикл отрицательного веса, для которого

Б. Не существует никакого цикла с отрицательным весом и

B. Существует цикл с нулевым (но не отрицательным) весом, т. е.

В случае (минимальное значение меньше чем так как неравенство

может выполняться только при

а это, очевидно, означает, что должно быть меньше чем

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