Проблема циркуляции и ее варианты являются обобщением задач сетевого потока с добавленным ограничением нижней границы для граничных потоков, а также с сохранением потока , требуемым для источника и стока (т. Е. Нет специальных узлов). В вариантах проблемы есть несколько товаров, проходящих через сеть, и затраты на поток.
Определение
Данная сеть потока с участием:
- , нижняя граница потока из узла к узлу ,
- , верхняя граница потока из узла к узлу ,
- , стоимость единицы расхода на
и ограничения:
- ,
- (поток не может появиться или исчезнуть в узлах).
Нахождение задания потока, удовлетворяющего ограничениям, дает решение данной проблемы циркуляции.
В минимально затратном варианте задачи минимизировать
Многотоваровое обращение
В задаче оборота нескольких товаров также необходимо отслеживать поток отдельных товаров:
Поток товаров из к . Общий расход.
Также существует нижняя граница для каждого товарного потока.
Ограничение консервации должно соблюдаться индивидуально для товаров:
Решение
Для проблемы циркуляции было разработано много полиномиальных алгоритмов (например, алгоритм Эдмондса и Карпа , 1972; Tarjan 1987-1988). Тардос нашел первый сильно полиномиальный алгоритм. [1]
В случае нескольких товаров проблема NP-полная для целочисленных потоков. [2] Для дробных потоков она разрешима за полиномиальное время , так как задачу можно сформулировать как линейную программу .
Связанные проблемы
Ниже приведены некоторые проблемы и способы их решения с помощью приведенной выше общей схемы циркуляции.
- Задача об обращении нескольких товаров с минимальными затратами - Использование всех ограничений, указанных выше.
- Проблема обращения с минимальными затратами - используйте один товар
- Многотоварный оборот - решайте без оптимизации затрат.
- Простое обращение - используйте только один товар и бесплатно.
- Многопродуктовый поток - Если обозначает потребность для товара из к , создать край с участием для всех товаров . Позволять для всех остальных краев.
- Проблема с потоком нескольких товаров с минимальными затратами - То же, что и выше, но минимизация затрат.
- Проблема потока минимальных затрат - Как указано выше, с 1 товаром.
- Проблема с максимальным потоком - установите все затраты на 0 и добавьте край раковины. к источнику с участием , ∞ и .
- Задача минимальной стоимости максимального потока - сначала найдите максимальный объем потока. Затем решите с помощью а также .
- Кратчайший путь из одного источника - Пусть а также для всех ребер в графе и добавьте ребро с участием а также .
- Кратчайший путь для всех пар - Пусть все емкости неограничены, и найдите поток, равный 1 для товары, по одному на каждую пару узлов.
Рекомендации
- ^ Эва Тардос. «Сильно полиномиальный алгоритм обращения с минимальными затратами». Combinatorica . 5 : 247–255. DOI : 10.1007 / BF02579369 .
- ^ С. Эвен, А. Итаи и А. Шамир (1976). «О сложности расписания и проблем многопродуктовых потоков» . SIAM Journal on Computing . СИАМ. 5 (4): 691–703. DOI : 10.1137 / 0205048 . Архивировано из оригинала на 2013-01-12.