Minstekostnadsproblem - Minimum-cost flow problem

Den minimale kostnader strømning problem ( MCFP ) er en optimaliserings og beslutningsproblemet for å finne den billigst mulig måte for å sende en viss mengde av strømningen gjennom en strømnings nettverk . En typisk anvendelse av dette problemet innebærer å finne den beste leveringsruten fra en fabrikk til et lager der veinettet har litt kapasitet og kostnader forbundet. Minstekostnadsflytproblemet er et av de mest grunnleggende blant alle strømnings- og sirkulasjonsproblemer fordi de fleste andre slike problemene kan kastes som et minimumskostnadsflytproblem og også at det kan løses effektivt ved hjelp av nettverks simpleksalgoritmen .

Definisjon

Et strømningsnettverk er en rettet graf med et kilde-toppunkt og et synke-toppunkt , der hver kant har kapasitet , flyt og kostnad , med de fleste strømningsalgoritmer med laveste kostnad som støtter kanter med negative kostnader. Kostnaden for å sende denne flyten langs en kant er . Problemet krever at en mengde flyt sendes fra kilde til vask . ${\ displaystyle G = (V, E)}$${\ displaystyle s \ i V}$${\ displaystyle t \ in V}$${\ displaystyle (u, v) \ i 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}$

Definisjonen av problemet er å minimere den totale kostnaden for strømmen over alle kanter:

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

med begrensningene

Kapasitetsbegrensninger :	${\ displaystyle \, f (u, v) \ leq c (u, v)}$
Skjev symmetri :	${\ displaystyle \, f (u, v) =-f (v, u)}$
Bevarelse av flyt :	${\ displaystyle \, \ sum _ {w \ in V} f (u, w) = 0 {\ text {for alle}} u \ neq s, t}$
Nødvendig flyt :	${\ displaystyle \, \ sum _ {w \ i V} f (s, w) = d {\ text {og}} \ sum _ {w \ i V} f (w, t) = d}$

Forholdet til andre problemer

En variant av dette problemet er å finne en strømning som er maksimal, men som har den laveste kostnaden blant de maksimale strømningsløsningene. Dette kan kalles et minimumskostnad maksimalflytproblem og er nyttig for å finne minimumskostnader maksimal samsvar .

Med noen løsninger er det enkelt å finne minimumskostnadsstrømmen i stedet. Hvis ikke, kan man finne maksimal flyt ved å utføre et binært søk på . ${\ displaystyle d}$

Et relatert problem er problemet med minimumskostnadssirkulasjon , som kan brukes til å løse minimumskostnadsflyt. Dette oppnås ved å sette den nedre grensen på alle kanter til null, og deretter lage en ekstra kant fra vasken til kilden , med kapasitet og nedre grense , og tvinge den totale strømmen fra til å også være . ${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle c (t, s) = d}$${\ displaystyle l (t, s) = d}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle d}$

Følgende problemer er spesielle tilfeller av minimumskostnadsflytproblemet (vi gir korte skisser av hver gjeldende reduksjon):

• Korteste baneproblem (enkeltkilde). Krev at en gjennomførbar løsning på minimumskostnadsstrømningsproblemet sender én strømmenhet fra en angitt kilde til en angitt vask . Gi alle kantene uendelig kapasitet.${\ displaystyle s}$${\ displaystyle t}$
• Maksimal strømningsproblem . La alle noder ha null etterspørsel, og la kostnaden forbundet med å krysse en kant være null. Innfør nå en ny kant fra den nåværende vasken til den nåværende kilden . Bestem at kostnaden per enhet for å sende flyt over kant er lik , og tillat uendelig kapasitet. (Denne reduksjonen er også nevnt i sirkulasjonsproblem ).${\ displaystyle (t, s)}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle (t, s)}$${\ displaystyle -1}$${\ displaystyle (t, s)}$
• Oppgaveproblem . Anta at hvert partitt -sett i bipartisjonen har hjørner, og beteg bipartisjonen med . Gi hver forsyning og gi hver etterspørsel . Hver kant skal ha enhetskapasitet.${\ displaystyle n}$${\ displaystyle (X, Y)}$${\ displaystyle x \ i X}$${\ displaystyle 1/n}$${\ displaystyle y \ i Y}$${\ displaystyle 1/n}$

Løsninger

Minstekostnadsflytproblemet kan løses ved lineær programmering , siden vi optimaliserer en lineær funksjon, og alle begrensninger er lineære.

Bortsett fra det finnes det mange kombinatoriske algoritmer, for en omfattende undersøkelse, se. Noen av dem er generaliseringer av maksimal flyt algoritmer , andre bruker helt andre tilnærminger.

Kjente grunnleggende algoritmer (de har mange varianter):

• Syklusavbrytelse : en generell primærmetode.
• Kuttavbrytelse : en generell dobbel metode.
• Minimum gjennomsnittlig syklusavbrudd : en enkel sterkt polynom algoritme.
• Etterfølgende korteste vei og kapasitetsskala : to metoder, som kan sees på som en generalisering av Ford – Fulkerson -algoritmen .
• Kostnadsskala : en primal-dobbel tilnærming, som kan sees på som en generalisering av push-relabel-algoritmen .
• Network simplex algoritme : en spesialisert versjon av den lineære programmerings simplex metoden .
• Uten kilter-algoritme av DR Fulkerson

applikasjon

Minste vekt topartsmatching

Redusere minimumsvekt -topartsmatching til minimumskostnad maksimal strømningsproblem

Gitt en todelt graf G = ( A ∪ B , E ) , er målet å finne maksimal kardinalitetsmatching i G som har minimumskostnad. La w : E → R være en vektfunksjon på kantene av E . Minste vekt bipartitt matching problem eller oppgave problem er å finne en perfekt matchende M ⊆ E hvis totalvekt er minimert. Tanken er å redusere dette problemet til et nettverksflytproblem.

La G ′ = ( V ′ = A ∪ B , E ′ = E ) . Tilordne kapasiteten til alle kantene i E ′ til 1. Legg til et kildepunkt s og koble det til alle hjørnene i A ′ og legg til et synke -toppunkt t og koble alle hjørnene inne i gruppe B ′ til dette toppunktet. Kapasiteten til alle de nye kantene er 1 og kostnadene deres er 0. Det er bevist at det er minimumsvekt perfekt bipartitt -matching i G hvis og bare hvis det er en minimumskostnadsstrøm i G ′ .

Se også

• SITRON (C ++ bibliotek)
• GNU lineært programmeringssett

Referanser

1. ^ Ravindra K. Ahuja ; Thomas L. Magnanti & James B. Orlin (1993). Nettverksflyt: Teori, algoritmer og applikasjoner . Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
2. ^ Morton Klein (1967). "En primær metode for minimale kostnadsflyter med applikasjoner til oppdraget og transportproblemer". Ledelsesvitenskap . 14 (3): 205–220. CiteSeerX  10.1.1.228.7696 . doi : 10.1287/mnsc.14.3.205 .
3. ^ Refael Hassin (1983). "Problemet med minstekostnadsflyt: En samlende tilnærming til eksisterende algoritmer og en ny tresøkalgoritme". Matematisk programmering . 25 : 228–239. doi : 10.1007/bf02591772 .
4. ^ Thomas R. Ervolina & S. Thomas McCormick (1993). "To sterkt polynomiske kuttavbruddsalgoritmer for nettverkstrøm med minimumskostnader" . Diskret anvendt matematikk . 4 : 133–165. doi : 10.1016/0166-218x (93) 90025-j .
5. ^ Andrew V. Goldberg & Robert E. Tarjan (1989). "Finne sirkulasjoner med laveste kostnad ved å avbryte negative sykluser". Journal of the ACM . 36 (4): 873–886. doi : 10.1145/76359.76368 .
6. ^ Jack Edmonds & Richard M. Karp (1972). "Teoretiske forbedringer i algoritmisk effektivitet for nettverksflytproblemer". Journal of the ACM . 19 (2): 248–264. doi : 10.1145/321694.321699 .
7. ^ Andrew V. Goldberg & Robert E. Tarjan (1990). "Finne sirkulasjoner med laveste kostnad ved påfølgende tilnærming". Matte. Oper. Res . 15 (3): 430–466. doi : 10.1287/moor.15.3.430 .
8. ^ James B. Orlin (1997). "En polynom tidsprimal nettverk simpleksalgoritme for minimale kostnadsstrømmer". Matematisk programmering . 78 (2): 109–129. doi : 10.1007/bf02614365 . hdl : 1721.1/2584 .

Eksterne linker

• LEMON C ++ -bibliotek med flere algoritmer for maksimal flyt og laveste kostnadssirkulasjon
• MCFClass C ++ - prosjektbiblioteket med noen minimumskostnadsflyt og korteste banealgoritmer