Min-Cost-Fluss-Problem

Neue Frage »

Musican Auf diesen Beitrag antworten »
Min-Cost-Fluss-Problem
Da ich bemerktee, wie viele schlaue Köpfe hier unterwegs sind, hier einmal folgendes Problem smile

In meiner letzten Klausur im Bereich kombinatorischer Optimierung kam folgende Aufgabe vor, die niemand meiner bekannten Kommilitonen lösen konnte, mich würde interessieren, was ihr dazu sagt, bzw. ob mir jemand einen Tipp geben könnte, da ich diese Klausur nochmal schreiben muss :-(

Aufgabe :
"Gegeben sei ein Min-Cost-Fluss-Problem und Zahlen für alle Knoten . Zeigen Sie: Ersetzt man für alle Kanten die Kosten durch die Kosten , so erhält mein ein zum Ausgangsproblem äquivalentes Problem"

Die große Frage hierbei ist, wie man es zeigen soll... Es zu widerlegen, wäre mittels eines GegenBeispiels ja ziemlich leicht. Aber es zu zeigen? Vielleicht findet ja jemand einen gescheiten Ansatz.

Meine Idee:

Bei einem Min-Cost-Problem ist einer der Knoten ja ein Nachfrage- und der andere ein Angebotsknoten. Da diese Werte sich bei einem zulässigen Fluss aufheben, ist ja klar, dass o.g. zu einem äquivalenten Problem führt?
Ich könnte aber auch total daneben liegen.

Ich wäre dankbar für alle Arten von Tipps verwirrt



Vielen Dank schonmal im Voraus!
Elvis Auf diesen Beitrag antworten »

Spontane Idee, aber noch nicht über den IA n=1 hinaus ausgeführt : vollständige Induktion nach n=Anzahl der Knoten von V.

Ich glaube, ich brauche noch ein paar Definitionen. Was ist ein min-cost-fluss-Problem ? Was sind äquivalente Probleme ? (Wenn ich die Definitionen raten muss, kann ich auch ein Gegenbeispiel angeben.)
Musican Auf diesen Beitrag antworten »

Hm, ich hatte auch wegen einer V.Induktion überlegt. Mir fehlt aber total der Ansatz.
Ein Direktbeweis wäre klasse Big Laugh

Also bezogen auf einen gerichteten Graphen ist ein Min-Cost-Problem ein Fluss, von der Quelle zur Senke bei dem die Transportkosten minimal sind. Siehe auch "Transport- oder Umladeproblem".
Ich hab' dir mal unsere Definition abfotografiert, bevor ich hier etwas unverständlich ausdrücke.
Elvis Auf diesen Beitrag antworten »

Knifflig ... Sind "äquivalente Probleme" "Probleme mit gleicher Lösung" ? Was immer Du antwortest, ich durchschaue das ganze noch nicht. Vielleicht schaffen wir es ja gemeinsam ... irgendwann bestimmt, aber wir sollten uns beeilen, damit wir vor deiner Klausur durchblicken.
Musican Auf diesen Beitrag antworten »

nicht wahr?
Also unter einem äquivalenten Problem verstehe ich auf dieses Problem bezogen, dass sich der Ausgangsgraph in seiner Sinnhaftigkeit nicht ändert. Sprich, die Kosten an den Kanten, sind nach der Addition von und nach der Subtraktion von noch immer die selben.
Das widerrum lässt mich vermuten, dass es etwas mit dem durch die Kante verbundenen Angebots - bzw. Nachfrageknoten zu tun hat.
Weil ich glaube, dass der Fluss nur zulässig ist, wenn der Nachfragende auch kriegt was er bekommt. Sprich : Angebot und Nachfrage heben sich auf.
Ist aber nur mein bisheriger Gedankengang...
Elvis Auf diesen Beitrag antworten »

Vielleicht ein Gegenbeispiel.
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 (oder ich habe etwas falsch verstanden).
 
 
Oggel Auf diesen Beitrag antworten »

Ich würde das ganze Thema noch einmal gerne aufgreifen. Da ich anscheinend mich gerade für die gleiche Klausur vorbereite, hänge ich auch vor der Aufgabe und habe nicht so wirklich den Plan Big Laugh

Vllt noch einmal zum äquivalenten Problem: In unserem Skript steht ein Beispiel zu einem äquivalenten Problem, das habe ich mal abfotografiert. Das ist auch alles soweit verständlich aber ich weiß nicht wie ich an die Aufgabe herangehen soll.

Elvis, vielleicht hast du nochmal Lust zu helfen? Gott
Neue Frage »
Antworten »



Verwandte Themen

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