Задача потока с минимальными затратами ( MCFP ) - это проблема оптимизации и принятия решений для поиска наиболее дешевого из возможных способов отправки определенного количества потока через сеть потоков . Типичное применение этой проблемы включает поиск наилучшего маршрута доставки от завода до склада, где дорожная сеть связана с определенной пропускной способностью и стоимостью. Проблема потока с минимальной стоимостью является одной из самых фундаментальных среди всех проблем потока и циркуляции, потому что большинство других таких проблем можно представить как проблему потока с минимальной стоимостью, а также то, что ее можно эффективно решить с помощью симплексного алгоритма сети .
Определение [ править ]
Потоковая сеть - это ориентированный граф с исходной вершиной и вершиной- приемником , где каждое ребро имеет пропускную способность , поток и стоимость , причем большинство алгоритмов потока с минимальной стоимостью поддерживают ребра с отрицательной стоимостью. Стоимость отправки этого потока по ребру составляет . Проблема требует, чтобы поток был отправлен от источника к приемнику .
Определение проблемы - минимизировать общую стоимость потока по всем ребрам:
с ограничениями
Ограничения мощности : Косая симметрия : Сохранение потока : Требуемый расход :
Отношение к другим проблемам [ править ]
Вариант этой проблемы - найти максимальный поток, но с наименьшими затратами среди решений с максимальным потоком. Это можно назвать проблемой минимальной стоимости и максимального потока, и она полезна для поиска сопоставлений минимальной стоимости и максимальной .
В некоторых решениях найти максимальный поток с минимальной стоимостью очень просто. Если нет, то можно найти поток максимального посредством выполнения двоичного поиска на .
Связанная с этим проблема - проблема обращения с минимальными затратами , которую можно использовать для решения потока минимальных затрат. Это достигается путем установления нижней границы по всем краям до нуля, а затем сделать дополнительный край от раковины к источнику , с мощностью и нижней границы , заставляя общий поток от до также быть .
Следующие проблемы являются частными случаями проблемы потока минимальных затрат (мы, в свою очередь, даем краткие наброски каждого применимого сокращения): [1]
- Проблема кратчайшего пути (из одного источника). Требовать, чтобы возможное решение проблемы потока с минимальной стоимостью отправляло одну единицу потока от назначенного источника к назначенному приемнику . Дайте всем ребрам бесконечную емкость.
- Задача максимального расхода . Пусть все узлы имеют нулевую потребность, и пусть стоимость, связанная с прохождением любого ребра, равна нулю. Теперь представьте новый край от текущего стока к текущему источнику . Предположите, что удельная стоимость отправки потока через границу равна , и разрешить бесконечную пропускную способность. (Это сокращение также упоминается в проблеме обращения ).
- Проблема с присвоением . Предположим, что в каждом частичном множестве в двудольном множестве есть вершины, и обозначим двудольность через . Дайте каждое предложение и дайте каждое требование . Каждое ребро должно иметь единицу мощности.
Решения [ править ]
Задача потока минимальных затрат может быть решена с помощью линейного программирования , поскольку мы оптимизируем линейную функцию, и все ограничения являются линейными.
Кроме того, существует множество комбинаторных алгоритмов, подробный обзор см. В [1] . Некоторые из них являются обобщениями алгоритмов максимального потока , другие используют совершенно другие подходы.
Хорошо известные фундаментальные алгоритмы (у них много вариаций):
- Отмена цикла : общий основной метод. [2]
- Отмена минимального среднего цикла : простой сильно полиномиальный алгоритм. [3]
- Последовательный кратчайший путь и масштабирование емкости : двойные методы, которые можно рассматривать как обобщение алгоритма Форда – Фулкерсона . [4]
- Масштабирование затрат : первично-двойной подход, который можно рассматривать как обобщение алгоритма push-relabel . [5]
- Сетевой симплексный алгоритм : специализированная версия симплексного метода линейного программирования . [6]
- Необычный алгоритм Д. Р. Фулкерсона
Заявление [ править ]
Двудольное соответствие минимального веса [ править ]
Для двудольного графа G = ( A ∪ B , E ) цель состоит в том, чтобы найти максимальное соответствие мощности в G, которое имеет минимальную стоимость. Пусть ш : Е → R является функцией веса по краям Е . Задача двустороннего согласования с минимальным весом или задача назначения состоит в том, чтобы найти идеальное согласование M ⊆ E , общий вес которого минимизирован. Идея состоит в том, чтобы свести эту проблему к проблеме сетевого потока.
Пусть G ′ = ( V ′ = A ∪ B , E ′ = E ). Присвойте емкость всех ребер в E ′ равной 1. Добавьте исходную вершину s и соедините ее со всеми вершинами в A ′, добавьте вершину приемника t и соедините все вершины внутри группы B ′ с этой вершиной. Вместимость всех новых ребер равна 1, а их стоимость равна 0. Доказано, что существует совершенное двудольное паросочетание с минимальным весом в G тогда и только тогда, когда существует поток с минимальной стоимостью в G ' . [7] [ мертвая ссылка ]
См. Также [ править ]
- LEMON (библиотека C ++)
- Комплект для линейного программирования GNU
Ссылки [ править ]
- ^ Ахуджа, Равиндра К .; Magnanti, Thomas L .; Орлин, Джеймс Б. (1993). Сетевые потоки. Теория, алгоритмы и приложения . Прентис Холл.
- ^ Равиндра К. Ахуджа ; Томас Л. Маньянти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . ISBN компании Prentice-Hall, Inc. 978-0-13-617549-0.
- ^ Мортон Кляйн (1967). «Первичный метод потоков минимальных затрат с приложениями к командировочным и транспортным задачам». Наука управления . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . DOI : 10.1287 / mnsc.14.3.205 .
- ^ Эндрю В. Голдберг и Роберт Э. Тарьян (1989). «Нахождение минимальных тиражей путем отмены отрицательных циклов». Журнал ACM . 36 (4): 873–886. DOI : 10.1145 / 76359.76368 .
- ↑ Джек Эдмондс и Ричард М. Карп (1972). «Теоретические улучшения алгоритмической эффективности для задач сетевого потока». Журнал ACM . 19 (2): 248–264. DOI : 10.1145 / 321694.321699 .
- ^ Эндрю В. Голдберг и Роберт Э. Тарьян (1990). «Нахождение минимальных тиражей методом последовательного приближения». Математика. Опер. Res . 15 (3): 430–466. DOI : 10.1287 / moor.15.3.430 .
- ^ Джеймс Б. Орлин (1997). «Полиномиальный простой сетевой симплекс-алгоритм для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. DOI : 10.1007 / bf02614365 . ЛВП : 1721,1 / 2584 .
Внешние ссылки [ править ]
- Библиотека LEMON C ++ с несколькими алгоритмами обращения с максимальным потоком и минимальной стоимостью
- Библиотека проектов MCFClass C ++ с некоторыми алгоритмами минимальной стоимости и кратчайшего пути