Min-Cost-Fluss Problem

Neue Frage »

Oggel Auf diesen Beitrag antworten »
Min-Cost-Fluss Problem
Hallo liebe Community,

ich brauche mal Hilfe zu einer Aufgabe. Diese wurde schonmal in diesem Forum gestellt, meine Antwort ist wahrscheinlich einfach untergegangen:
Min-Cost-Fluss-Problem

Vielleicht kann einer von euch da nochmal drauf schauen smile

Danke schonmal smile
Elvis Auf diesen Beitrag antworten »

Stelle die neue Zielfunktion auf. Wenn die Behauptung stimmt, heben sich die (meisten) y's gegenseitig weg. Vermutlich werden sie in einer Kante positiv und in einer anderen Kante negativ gezählt. Was an y's übrig bleibt, sind nur die Werte an den Quellen und Senken, womit zur Zielfunktion eine Konstante hinzutritt, die die Lösung nicht verändert. (Habe ich noch nicht ganz durchgerechnet, nur so ins Unreine gedacht. Bitte um Bestätigung.)
 
 
Oggel Auf diesen Beitrag antworten »

Ich weiß leider noch nicht ganz was ich machen soll.

Meinst du die Zielfunktion in folgende ändern:

?
Elvis Auf diesen Beitrag antworten »

ja
Oggel Auf diesen Beitrag antworten »

Okay aber ich komme trotzdem noch nicht so richtig weiter verwirrt Wie zeige ich jetzt, dass das ein äquivalentes Problem ist?
Elvis Auf diesen Beitrag antworten »

Ich glaube immer noch, dass mein Gegenbeispiel vom 26.01.2017 zeigt, dass die Aussage falsch ist.

2 Versorger a und b, 1 Verbraucher v. Kosten av=1 ,bv=2, Loesung a versorgt v. Knotenkosten ya=2, Lösung b versorgt v. Also Probleme nicht aequivalent.
Oggel Auf diesen Beitrag antworten »

Mhh. Aber die Aufgabenstellung verstehe ich so, dass es ein äquivalentes Problem sein soll. Und die Aufgabe kam sogar in 2 verschiedenen Klausuren dran verwirrt

Es müssen sich auch alle Knotenkosten aufheben, wie in dem Bild z.B., d.h. A und B haben 2 bzw. 3 Einheiten abzugeben und V muss 5 Einheiten aufnehmen.

Also wäre in diesem Fall die Lösung: A und B versorgen V

Komme echt nicht weiter unglücklich
Elvis Auf diesen Beitrag antworten »

Ich setze
und dann kommen die y's dazu: , weil

In der Aufgabe steht nicht, dass das Versorgungsproblem fixiert ist und auch nicht, dass die Knotenkosten ausbalanciert sind.
Oggel Auf diesen Beitrag antworten »

Was sind in deinem Fall die b's?
c: Kosten
y: Zahlen an den Knoten
Elvis Auf diesen Beitrag antworten »

b ist Angebot (+) und Nachfrage (-) (siehe definition)
Oggel Auf diesen Beitrag antworten »

Okay und was sind dann die y's? Ich dachte in der Aufgabe wären die y's Angebot bzw. Nachfrage.
Elvis Auf diesen Beitrag antworten »

Nein, die y's sind zusätzliche Knotenkosten, die vom Startknoten auf die Transportkosten aufgeschlagen und vom Zielknoten von den Transportkosten abgezogen werden. (siehe Aufgabe)
Oggel Auf diesen Beitrag antworten »

Ahh. Ich habe ganze Zeit das Problem falsch verstanden. Forum Kloppe

Aber laut Definition müssen die Summe aller b's 0 sein. In deinem Beispiel wäre das ja nicht gegeben.
Elvis Auf diesen Beitrag antworten »

Das sind ja stinklangweilige Probleme. Darf ich mir als Kunde nicht mehr aussuchen, ob ich bei Putin oder bei Trump kaufe ? Muss ich beiden ihren Mist abnehmen? Nö, mach ich nicht. Weder noch, ich kauf bei Aldi, wegen der Transportkosten und wegen der Kollateralschäden.

Wieso muss die Summe der b's 0 sein ?? Ich habe diese Behauptung gelesen aber nicht verstanden.
Oggel Auf diesen Beitrag antworten »

Big Laugh keine ahnung so steht es in dem Skript von unserem Prof.
ich weiß aber immer noch nicht wirklich weiter verwirrt
Oggel Auf diesen Beitrag antworten »

Habe nochmal über deine Aussage oben nachgedacht und mir das mal veranschaulicht. Am Ende bleiben dann nur noch die y's der Quelle und die der Senke.
Oggel Auf diesen Beitrag antworten »

Wenn ich jedoch folgenden Graph habe, bleibt noch ein y der Knoten über, ist das immer noch ein äquivalentes Problem ? verwirrt
Elvis Auf diesen Beitrag antworten »

Alles was hergestellt wird, wird mit minimalen Transportkosten verkauft. Ich finde kein Gegenbeispiel mehr. Das ist noch kein Beweis, aber ein solcher macht mir auch Mühe. Intuitiv sage ich jetzt mal, dass alle von einem Knoten ausgehenden Wege in gleicher weise bestraft und alle in einem Knoten mündenden Wege in gleicher weise belohnt werden. "Also" sind die Probleme äquivalent. (Das überzeugt mich zwar nicht so richtig, aber ich krieg's nicht besser hin.)
Oggel Auf diesen Beitrag antworten »

Alles Klar dankeschön smile

Mir ist noch aufgefallen, dass die Änderung der Gesamtkosten vom jeweiligen Eingangsgrad bzw. Ausgangsgrad der Knoten abhängen. Also wieviele Eingänge bzw. Ausgänge der Knoten hat. Falls Eingänge = Ausgänge heben sich die auf.
Oggel Auf diesen Beitrag antworten »

Habe hier nach ein bisschen Recherche evtl einen Beweis gefunden. Allerdings verstehe ich den vorletzten Schritt nicht verwirrt
Elvis Auf diesen Beitrag antworten »

Vermutlich wird das Zielfunktional nur parallel verschoben, also ändert sich im wesentlichen nichts.
Oggel Auf diesen Beitrag antworten »

Der Beweis passt aber oder?

Verstehe folgenden Schritt iwie nicht wieso sind die beiden Gleichungen gleich? verwirrt
Elvis Auf diesen Beitrag antworten »

Passt schon, das sind ja nur endliche Summen. Beachte das Distributivgesetz.
Oggel Auf diesen Beitrag antworten »

Okay danke dir smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »