Min-Cost-Fluss-Problem |
25.03.2016, 21:09 | Musican | Auf diesen Beitrag antworten » |
Min-Cost-Fluss-Problem 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 Vielen Dank schonmal im Voraus! |
||
25.03.2016, 22:33 | 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.) |
||
26.03.2016, 19:13 | 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 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. |
||
26.03.2016, 19:57 | 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. |
||
26.03.2016, 20:55 | 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... |
||
26.03.2016, 22:20 | 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). |
||
Anzeige | ||
|
||
01.02.2017, 15:59 | 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 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? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|