Задача минимальной стоимости потока

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

Определение [ править ]

Потоковая сеть - это ориентированный граф с исходной вершиной и вершиной- приемником , где каждое ребро имеет пропускную способность , поток и стоимость , при этом большинство алгоритмов потока с минимальной стоимостью поддерживают ребра с отрицательной стоимостью. Стоимость отправки этого потока по ребру составляет . Проблема требует, чтобы поток был отправлен от источника к приемнику .${\displaystyle G=(V,E)}$${\displaystyle s\in V}$${\displaystyle t\in V}$${\displaystyle (u,v)\in E}$${\displaystyle c(u,v)>0}$${\displaystyle f(u,v)\geq 0}$${\displaystyle a(u,v)}$${\displaystyle (u,v)}$${\displaystyle f(u,v)\cdot a(u,v)}$${\displaystyle d}$${\displaystyle s}$${\displaystyle t}$

Определение проблемы состоит в том, чтобы минимизировать общую стоимость потока по всем ребрам:

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

с ограничениями

Ограничения мощности :	${\displaystyle \,f(u,v)\leq c(u,v)}$
Косая симметрия :	${\displaystyle \,f(u,v)=-f(v,u)}$
Сохранение потока :	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t}$
Требуемый поток :	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}$

Отношение к другим проблемам [ править ]

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

При использовании некоторых решений найти максимальный поток с минимальной стоимостью очень просто. Если нет, то можно найти поток максимального посредством выполнения двоичного поиска на .${\displaystyle d}$

Связанная с этим проблема - проблема обращения с минимальными затратами , которую можно использовать для решения потока минимальных затрат. Это достигается путем установления нижней границы по всем краям до нуля, а затем сделать дополнительный край от раковины к источнику , с мощностью и нижней границы , заставляя общий поток от до также быть .${\displaystyle t}$${\displaystyle s}$${\displaystyle c(t,s)=d}$${\displaystyle l(t,s)=d}$${\displaystyle s}$${\displaystyle t}$${\displaystyle d}$

Следующие проблемы являются частными случаями проблемы потока минимальных затрат (мы, в свою очередь, даем краткие наброски каждого применимого сокращения): ^[1]

• Проблема кратчайшего пути (из одного источника). Требовать, чтобы возможное решение проблемы потока с минимальной стоимостью отправляло одну единицу потока из назначенного источника в назначенный приемник . Дайте всем ребрам бесконечную емкость.${\displaystyle s}$${\displaystyle t}$
• Проблема максимального расхода . Пусть все узлы имеют нулевой спрос, и пусть стоимость, связанная с прохождением любого ребра, равна нулю. Теперь представьте новое ребро от текущего приемника к текущему источнику . Предположите, что удельные затраты на отправку потока через границу равны , и разрешите бесконечную пропускную способность. (Это сокращение также упоминается в проблеме обращения ).${\displaystyle (t,s)}$${\displaystyle t}$${\displaystyle s}$${\displaystyle (t,s)}$${\displaystyle -1}$${\displaystyle (t,s)}$
• Проблема с присвоением . Предположим, что в каждом частичном множестве в двудольном множестве есть вершины, и обозначим это разбиение через . Дайте каждое предложение и дайте каждое требование . Каждое ребро должно иметь единицу мощности.${\displaystyle n}$${\displaystyle (X,Y)}$${\displaystyle x\in X}$${\displaystyle 1/n}$${\displaystyle y\in Y}$${\displaystyle 1/n}$

Решения [ править ]

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

Кроме того, существует множество комбинаторных алгоритмов, подробный обзор см. В ^[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

Ссылки [ править ]

1. ^ Равиндра К. Ахуджа ; Томас Л. Маньянти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . ISBN компании Prentice-Hall, Inc. 978-0-13-617549-0.
2. ^ Мортон Кляйн (1967). «Первичный метод потоков минимальных затрат с приложениями к командировочным и транспортным задачам». Наука управления . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . DOI : 10.1287 / mnsc.14.3.205 . 
3. ↑ Эндрю В. Голдберг и Роберт Э. Тарьян (1989). «Нахождение минимальных тиражей за счет отмены отрицательных циклов». Журнал ACM . 36 (4): 873–886. DOI : 10.1145 / 76359.76368 .
4. ^ Джек Эдмондс и Ричард М. Карп (1972). «Теоретические улучшения алгоритмической эффективности для задач сетевого потока». Журнал ACM . 19 (2): 248–264. DOI : 10.1145 / 321694.321699 .
5. ↑ Эндрю В. Голдберг и Роберт Э. Тарьян (1990). «Нахождение минимальных тиражей методом последовательного приближения». Математика. Опер. Res . 15 (3): 430–466. DOI : 10.1287 / moor.15.3.430 .
6. ^ Джеймс Б. Орлин (1997). "Полиномиальный простой сетевой симплекс-алгоритм для потоков с минимальной стоимостью". Математическое программирование . 78 (2): 109–129. DOI : 10.1007 / bf02614365 . ЛВП : 1721,1 / 2584 .

Внешние ссылки [ править ]

• Библиотека LEMON C ++ с несколькими алгоритмами обращения с максимальным потоком и минимальной стоимостью
• Библиотека проектов MCFClass C ++ с некоторыми алгоритмами минимальной стоимости и кратчайшего пути