[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/03\/minimalkostenflussproblem-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/03\/minimalkostenflussproblem-wikipedia\/","headline":"Minimalkostenflussproblem \u2013 Wikipedia","name":"Minimalkostenflussproblem \u2013 Wikipedia","description":"Mathematisches Optimierungsproblem Die Minimum-Cost-Flow-Problem (MCFP) ist ein Optimierungs- und Entscheidungsproblem, um den g\u00fcnstigsten Weg zu finden, eine bestimmte Menge an","datePublished":"2021-11-03","dateModified":"2021-11-03","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/03\/minimalkostenflussproblem-wikipedia\/","wordCount":6729,"articleBody":"Mathematisches Optimierungsproblem  Die Minimum-Cost-Flow-Problem (MCFP) ist ein Optimierungs- und Entscheidungsproblem, um den g\u00fcnstigsten Weg zu finden, eine bestimmte Menge an Fluss durch ein Flussnetz zu senden.  Eine typische Anwendung dieses Problems besteht darin, den besten Lieferweg von einer Fabrik zu einem Lager zu finden, wo das Stra\u00dfennetz eine gewisse Kapazit\u00e4t und damit verbundene Kosten hat.  Das Minimalkostenflussproblem ist eines der grundlegendsten unter allen Fluss- und Zirkulationsproblemen, da die meisten anderen dieser Probleme als Minimalkostenflussproblem betrachtet werden k\u00f6nnen und auch effizient unter Verwendung des Netzwerksimplexalgorithmus gel\u00f6st werden k\u00f6nnen.Table of ContentsDefinition[edit]Bezug zu anderen Problemen[edit]L\u00f6sungen[edit]Anwendung[edit]Bipartite Matching mit minimalem Gewicht[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Definition[edit]Ein Flussnetzwerk ist ein gerichteter Graph   g=(V,E){displaystyle G=(V,E)}  mit einem Quellknoten S\u2208V{displaystyle sin V}  und ein Senkenscheitel T\u2208V{displaystyle tin V}, wobei jede Kante (du,v)\u2208E{displaystyle (u,v)in E}  hat Kapazit\u00e4t    0″\/>, flie\u00dfen F(du,v)\u22650{displaystyle f(u,v)geq 0}  und kosten ein(du,v){displaystyle a(u,v)}, wobei die meisten Flow-Algorithmen mit minimalen Kosten Kanten mit negativen Kosten unterst\u00fctzen.  Die Kosten f\u00fcr das Senden dieses Flusses entlang einer Kante (du,v){displaystyle (u,v)}  ist F(du,v)\u22c5ein(du,v){displaystyle f(u,v)cdot a(u,v)}.  Das Problem erfordert eine Menge an Durchfluss D{displaystyle d}  von Quelle gesendet werden S{displaystyle s}  sinken T{displaystyle t}.Die Definition des Problems besteht darin, die Gesamtkosten der Str\u00f6mung \u00fcber alle Kanten:\u03a3(du,v)\u2208Eein(du,v)\u22c5F(du,v){displaystyle sum _{(u,v)in E}a(u,v)cdot f(u,v)}mit den Einschr\u00e4nkungenKapazit\u00e4tsengp\u00e4sse:F(du,v)\u2264C(du,v){displaystyle ,f(u,v)leq c(u,v)}Symmetrie verzerren:F(du,v)=\u2212F(v,du){displaystyle ,f(u,v)=-f(v,u)}Str\u00f6mungserhaltung:\u03a3w\u2208VF(du,w)=0 f\u00fcr alle du\u2260S,T{displaystyle ,sum _{win V}f(u,w)=0{text{ f\u00fcr alle }}uneq s,t}Erforderlicher Durchfluss:\u03a3w\u2208VF(S,w)=D und \u03a3w\u2208VF(w,T)=D{displaystyle ,sum _{win V}f(s,w)=d{text{ und }}sum _{win V}f(w,t)=d}Bezug zu anderen Problemen[edit]Eine Variation dieses Problems besteht darin, einen maximalen Durchfluss zu finden, der jedoch die niedrigsten Kosten unter den L\u00f6sungen mit maximalem Durchfluss aufweist.  Dies k\u00f6nnte ein Minimum-Cost-Maximum-Flow-Problem genannt werden und ist n\u00fctzlich, um Minimum-Cost-Maximum-Matchings zu finden.Bei einigen L\u00f6sungen ist es stattdessen einfach, den minimalen Kosten-Maximum-Flow zu finden.  Wenn nicht, kann man den maximalen Durchfluss finden, indem man eine bin\u00e4re Suche nach durchf\u00fchrt D{displaystyle d}.Ein verwandtes Problem ist das Minimalkostenzirkulationsproblem, das zur L\u00f6sung des Minimalkostenflusses verwendet werden kann.  Dies wird erreicht, indem die untere Grenze an allen Kanten auf Null gesetzt wird und dann eine zus\u00e4tzliche Kante aus der Senke erstellt wird T{displaystyle t}  zur Quelle S{displaystyle s}, mit Kapazit\u00e4t C(T,S)=D{displaystyle c(t,s)=d}  und untere Grenze l(T,S)=D{displaystyle l(t,s)=d}, erzwingt den Gesamtfluss von S{displaystyle s}  zu T{displaystyle t}  auch sein D{displaystyle d}.Die folgenden Probleme sind Spezialf\u00e4lle des Minimalkostenflussproblems (wir geben der Reihe nach kurze Skizzen zu jeder anwendbaren Reduktion):[1]K\u00fcrzeste-Weg-Problem (Single-Source).  Erfordern, dass eine praktikable L\u00f6sung f\u00fcr das Problem des minimalen Kostenflusses eine Flusseinheit von einer bestimmten Quelle sendet S{displaystyle s}  zu einem ausgewiesenen Waschbecken T{displaystyle t}.  Gib allen Kanten unendliche Kapazit\u00e4t.Problem des maximalen Durchflusses.  Alle Knoten haben eine Nachfrage von Null und die Kosten, die mit dem Durchqueren einer beliebigen Kante verbunden sind, seien Null.  F\u00fchren Sie nun eine neue Kante ein (T,S){displaystyle (t,s)}  aus der aktuellen Sp\u00fcle T{displaystyle t}  zur aktuellen Quelle S{displaystyle s}.  Legen Sie fest, dass die Kosten pro Einheit f\u00fcr das Senden \u00fcber die Kante flie\u00dfen (T,S){displaystyle (t,s)}  gleich \u22121{displaystyle -1}, und erlauben (T,S){displaystyle (t,s)}  unendliche Kapazit\u00e4t.  (Diese Reduzierung wird auch im Kreislaufproblem erw\u00e4hnt).Zuordnungsproblem.  Angenommen, jede Teilmenge in der Bipartition hat n{displaystyle n}  Scheitelpunkte und bezeichnen die Bipartition mit (x,Ja){displaystyle (X,Y)}.  Gib jedem x\u2208x{displaystyle xin X}  liefern 1\/n{displaystyle 1\/n}  und gib jedem ja\u2208Ja{displaystyle yin Y}  Anforderung 1\/n{displaystyle 1\/n}.  Jede Kante soll eine Einheitskapazit\u00e4t haben.L\u00f6sungen[edit]Das Problem des minimalen Kostenflusses kann durch lineare Programmierung gel\u00f6st werden, da wir eine lineare Funktion optimieren und alle Nebenbedingungen linear sind.Dar\u00fcber hinaus existieren viele kombinatorische Algorithmen, f\u00fcr einen umfassenden \u00dcberblick siehe [1].  Einige von ihnen sind Verallgemeinerungen von Maximum-Flow-Algorithmen, andere verwenden v\u00f6llig andere Ans\u00e4tze.Bekannte fundamentale Algorithmen (sie haben viele Variationen):Anwendung[edit]Bipartite Matching mit minimalem Gewicht[edit]  Reduzieren des zweiteiligen Abgleichs mit minimalem Gewicht auf das Problem der minimalen Kosten und des maximalen FlussesGegeben einen bipartiten Graphen g = (EIN \u222a B, E), das Ziel ist es, das maximale Kardinalit\u00e4tsmatching in zu finden g das hat minimale kosten.  Lassen w: E \u2192 R sei eine Gewichtsfunktion auf den Kanten von E.  Das bipartite Matching- oder Zuweisungsproblem mit minimalem Gewicht besteht darin, ein perfektes Matching zu finden m \u2286 E  deren Gesamtgewicht minimiert wird.  Die Idee ist, dieses Problem auf ein Netzwerkflussproblem zu reduzieren.Lassen G’ = (V\u2032 = EIN \u222a B, E\u2032 = E).  Weisen Sie die Kapazit\u00e4t aller Kanten in . zu E\u2032 zu 1. F\u00fcgen Sie einen Quell-Scheitelpunkt hinzu S und verbinde es mit allen Scheitelpunkten in EIN’ und f\u00fcge einen Senkenscheitelpunkt hinzu T und verbinde alle Scheitelpunkte innerhalb der Gruppe B’ zu diesem Scheitelpunkt.  Die Kapazit\u00e4t aller neuen Kanten ist 1 und ihre Kosten sind 0. Es ist bewiesen, dass es in . ein perfektes bipartites Matching mit minimalem Gewicht gibt g genau dann, wenn ein Mindestkostenstrom einflie\u00dft G’. [9][dead link]Siehe auch[edit]Verweise[edit]^ Ahuja, Ravindra K.;  Magnanti, Thomas L.;  Orlin, James B. (1993). Netzwerkfl\u00fcsse.  Theorie, Algorithmen und Anwendungen.  Lehrlingssaal.^ Ravindra K. Ahuja;  Thomas L. Magnanti & James B. Orlin (1993). Netzwerkfl\u00fcsse: Theorie, Algorithmen und Anwendungen.  Prentice-Hall, Inc. ISBN 978-0-13-617549-0.^ Morton Klein (1967). “Eine Urmethode f\u00fcr minimale Kostenfl\u00fcsse mit Anwendungen auf die Zuordnungs- und Transportproblematik”. Managementwissenschaft. 14 (3): 205\u2013220.  CiteSeerX 10.1.1.228.7696.  mach:10.1287\/mnsc.14.3.205.^ Refael Hassin (1983). “Das minimale Kostenflussproblem: Ein vereinheitlichender Ansatz f\u00fcr bestehende Algorithmen und ein neuer Baumsuchalgorithmus”. Mathematische Programmierung. 25: 228\u2013239.  mach:10.1007\/bf02591772.^ Thomas R. Ervolina & S. Thomas McCormick (1993). “Zwei stark polynomiale Cut-Cancelling-Algorithmen f\u00fcr minimalen Netzwerkfluss”. Diskrete Angewandte Mathematik. 4: 133\u2013165.  mach:10.1016\/0166-218x(93)90025-j.^ Andrew V. Goldberg & Robert E. Tarjan (1989). “Ermittlung von Auflagen mit minimalen Kosten durch Aufhebung negativer Zyklen”. Zeitschrift der ACM. 36 (4): 873\u2013886.  mach:10.1145\/76359.76368.^ Jack Edmonds & Richard M. Karp (1972). “Theoretische Verbesserungen der algorithmischen Effizienz f\u00fcr Netzwerkflussprobleme”. Zeitschrift der ACM. 19 (2): 248\u2013264.  mach:10.1145\/321694.321699.^ Andrew V. Goldberg & Robert E. Tarjan (1990). “Ermittlung der kostenminimierten Auflagen durch sukzessive Approximation”. Mathematik.  Oper.  Aufl\u00f6sung. f\u00fcnfzehn (3): 430\u2013466.  mach:10.1287\/moor.15.3.430.^ James B. Orlin (1997). “Ein Polynomialzeit-Primal-Network-Simplexalgorithmus f\u00fcr minimale Kostenfl\u00fcsse”. Mathematische Programmierung. 78 (2): 109\u2013129.  mach:10.1007\/bf02614365.  hdl:1721.1\/2584.Externe Links[edit]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/03\/minimalkostenflussproblem-wikipedia\/#breadcrumbitem","name":"Minimalkostenflussproblem \u2013 Wikipedia"}}]}]