Problém toku minimálních nákladů - Minimum-cost flow problem

The problém toku minimálních nákladů (MCFP) je optimalizace a rozhodovací problém najít nejlevnější možný způsob odeslání určitého množství toku a toková síť. Typická aplikace tohoto problému zahrnuje nalezení nejlepší trasy dodání z továrny do skladu, kde má silniční síť spojenou určitou kapacitu a náklady. Problém s minimálními náklady je jedním z nejzásadnějších ze všech problémů s tokem a oběhem, protože většinu ostatních takových problémů lze považovat za problém s tokem minimálních nákladů a také to, že jej lze efektivně vyřešit pomocí síťový simplexní algoritmus.

Definice

Toková síť je a řízený graf ${displaystyle G = (V, E)}$ se zdrojovým vrcholem ${displaystyle sin V}$ a vrchol dřezu ${displaystyle tin V}$, kde každý okraj ${displaystyle (u, v) v E}$ má kapacitu ${displaystyle c (u, v)> 0}$, průtok ${displaystyle f (u, v) geq 0}$ a náklady ${displaystyle a (u, v)}$, přičemž většina algoritmů toku minimálních nákladů podporuje okraje se zápornými náklady. Náklady na odeslání tohoto toku podél okraje ${displaystyle (u, v)}$ je ${displaystyle f (u, v) cdot a (u, v)}$. Problém vyžaduje určité množství toku ${displaystyle d}$ k odeslání ze zdroje ${displaystyle s}$ potopit se ${displaystyle t}$.

Definicí problému je minimalizovat Celkové náklady toku přes všechny hrany:

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

s omezeními

Omezení kapacity:	${displaystyle, f (u, v) leq c (u, v)}$
Šikmá symetrie:	${displaystyle, f (u, v) = - f (v, u)}$
Zachování toku:	${displaystyle, sum _ {win V} f (u, w) = 0 {ext {pro všechny}} ueq s, t}$
Požadovaný průtok:	${displaystyle, sum _ {win V} f (s, w) = d {ext {and}} součet _ {win V} f (w, t) = d}$

Vztah k dalším problémům

Variací tohoto problému je najít tok, který je maximální, ale má nejnižší náklady z řešení maximálního toku. To by se dalo nazvat problémem s minimálním nákladem a maximálním tokem a je užitečné pro nalezení maxima s minimálními náklady párování.

U některých řešení je nalezení maximálního toku minimálních nákladů místo toho jednoduché. Pokud ne, lze najít maximální průtok provedením a binární vyhledávání na ${displaystyle d}$.

Souvisejícím problémem je problém s minimálními náklady na oběh, které lze použít k řešení minimálního toku nákladů. Toho je dosaženo nastavením dolní meze na všech hranách na nulu a následným vytvořením další hrany z umyvadla ${displaystyle t}$ ke zdroji ${displaystyle s}$, s kapacitou ${displaystyle c (t, s) = d}$ a dolní mez ${displaystyle l (t, s) = d}$, vynucení celkového toku z ${displaystyle s}$ na ${displaystyle t}$ být také ${displaystyle d}$.

Následující problémy jsou speciální případy problému s minimálním tokem nákladů (poskytujeme zase stručné náčrtky každé použitelné redukce):^[1]

• Problém s nejkratší cestou (jediný zdroj). Vyžadovat, aby proveditelné řešení problému toku minimálních nákladů poslalo jednu jednotku toku z určeného zdroje ${displaystyle s}$ do určeného umyvadla ${displaystyle t}$. Dejte všem hranám nekonečnou kapacitu.
• Problém s maximálním průtokem. Nechejte všechny uzly nulovou poptávku a náklady spojené s procházením libovolnou hranou nechte nulové. Nyní představte novou výhodu ${displaystyle (t, s)}$ ze současného umyvadla ${displaystyle t}$ k aktuálnímu zdroji ${displaystyle s}$. Stanovte, že jednotkové náklady na odesílání plynou přes okraj ${displaystyle (t, s)}$ rovná se ${displaystyle -1}$a povolení ${displaystyle (t, s)}$ nekonečná kapacita. (Toto snížení je také zmíněno v Problém oběhu ).
• Problém s přiřazením. Předpokládejme, že každá partita v bipartici má ${displaystyle n}$ vrcholy a označte biparticii ${displaystyle (X, Y)}$. Dejte každému ${displaystyle xin X}$ zásobování ${displaystyle 1 / n}$ a dát každému ${displaystyle yin Y}$ poptávka ${displaystyle 1 / n}$. Každá hrana má mít jednotkovou kapacitu.

Řešení

Problém s minimálními náklady lze vyřešit pomocí lineární programování, protože optimalizujeme lineární funkci a všechna omezení jsou lineární.

Kromě toho existuje mnoho kombinatorických algoritmů, pro komplexní průzkum viz ^[1]. Některé z nich jsou zevšeobecněním algoritmy maximálního toku, jiní používají zcela odlišné přístupy.

Známé základní algoritmy (mají mnoho variant):

• Zrušení cyklu: obecná prvotní metoda.^[2]
• Minimální průměrné zrušení cyklu: jednoduchý silně polynomický algoritmus.^[3]
• Postupná nejkratší cesta a škálování kapacity: duální metody, které lze považovat za zobecnění Algoritmus Ford-Fulkerson.^[4]
• Škálování nákladů: prvotně-dvojí přístup, který lze chápat jako zevšeobecnění algoritmus push-relabel.^[5]
• Síťový simplexní algoritmus: specializovaná verze lineární programování simplexní metoda.^[6]
• Algoritmus out-of-kilter podle D. R. Fulkerson

aplikace

Minimální hmotnost bipartitní shody

Snížení bipartitní shody minimální hmotnosti na minimální náklady s maximálním problémem průtoku

Vzhledem k bipartitní graf G = (A ∪ B, E), cílem je najít maximální shodu mohutnosti G to má minimální náklady. Nechat w: E → R být váhovou funkcí na okrajích E. Minimální váha problému dvojího párování nebo přiřazení je najít perfektní párování M ⊆ E jejichž celková hmotnost je minimalizována. Cílem je snížit tento problém na problém toku sítě.

Nechat G' = (PROTI' = A ∪ B, E' = E). Přiřaďte kapacitu všech hran v E' do 1. Přidejte zdrojový vrchol s a připojte jej ke všem vrcholům v A' a přidejte vrchol dřezu t a spojit všechny vrcholy uvnitř skupiny B ' k tomuto vrcholu. Kapacita všech nových hran je 1 a jejich cena je 0. Je prokázáno, že v minimální bipartitní shodě existuje minimální hmotnost G právě tehdy, pokud v systému dochází k minimálním nákladům G'. ^{[7][mrtvý odkaz ]}

Viz také

• LEMON (knihovna C ++)
• Sada lineárního programování GNU

Reference

1. ^ Ravindra K. Ahuja; Thomas L. Magnanti & James B. Orlin (1993). Toky sítě: Teorie, algoritmy a aplikace. Prentice-Hall, Inc. ISBN  978-0-13-617549-0.
2. ^ Morton Klein (1967). "Prvotní metoda pro minimální toky nákladů s aplikacemi na problémy s přiřazením a přepravou". Věda o řízení. 14 (3): 205–220. CiteSeerX  10.1.1.228.7696. doi:10,1287 / mnsc.14.3.205.
3. ^ Andrew V. Goldberg & Robert E. Tarjan (1989). Msgstr "Hledání cirkulací s minimálními náklady zrušením negativních cyklů". Deník ACM. 36 (4): 873–886. doi:10.1145/76359.76368.
4. ^ Jack Edmonds & Richard M. Karp (1972). Msgstr "Teoretická vylepšení v algoritmické efektivitě při problémech s tokem sítě". Deník ACM. 19 (2): 248–264. doi:10.1145/321694.321699.
5. ^ Andrew V. Goldberg & Robert E. Tarjan (1990). "Nalezení oběhů s minimálními náklady postupnou aproximací". Matematika. Oper. Res. 15 (3): 430–466. doi:10,1287 / bř. 15.3.430.
6. ^ James B. Orlin (1997). "Polynomiální časově primitivní síťový simplexní algoritmus pro minimální toky nákladů". Matematické programování. 78 (2): 109–129. doi:10.1007 / bf02614365. hdl:1721.1/2584.

externí odkazy

• Knihovna LEMON C ++ s několika algoritmy maximálního toku a minimálního oběhu nákladů
• Knihovna projektů MCFClass C ++ s některými algoritmy minimálních nákladů a nejkratší cestou