Min-Cost-Fluss Problem |
| 03.02.2017, 23:59 | Oggel | Auf diesen Beitrag antworten » |
| Min-Cost-Fluss Problem 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 
Danke schonmal
|
||
| 04.02.2017, 10:09 | 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.) |
||
| 04.02.2017, 10:43 | Oggel | Auf diesen Beitrag antworten » |
Ich weiß leider noch nicht ganz was ich machen soll. Meinst du die Zielfunktion in folgende ändern: ? |
||
| 04.02.2017, 13:34 | Elvis | Auf diesen Beitrag antworten » |
ja |
||
| 04.02.2017, 14:31 | Oggel | Auf diesen Beitrag antworten » |
Okay aber ich komme trotzdem noch nicht so richtig weiter 
Wie zeige ich jetzt, dass das ein äquivalentes Problem ist? |
||
| 05.02.2017, 11:39 | 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. |
||
| Anzeige | ||
|
|
||
| 05.02.2017, 12:23 | 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
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 
|
||
| 05.02.2017, 12:55 | 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. |
||
| 05.02.2017, 13:00 | Oggel | Auf diesen Beitrag antworten » |
Was sind in deinem Fall die b's? c: Kosten y: Zahlen an den Knoten |
||
| 05.02.2017, 13:02 | Elvis | Auf diesen Beitrag antworten » |
b ist Angebot (+) und Nachfrage (-) (siehe definition) |
||
| 05.02.2017, 13:11 | 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. |
||
| 05.02.2017, 13:15 | 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) |
||
| 05.02.2017, 13:45 | Oggel | Auf diesen Beitrag antworten » |
Ahh. Ich habe ganze Zeit das Problem falsch verstanden. 
Aber laut Definition müssen die Summe aller b's 0 sein. In deinem Beispiel wäre das ja nicht gegeben. |
||
| 05.02.2017, 14:21 | 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. |
||
| 05.02.2017, 14:36 | Oggel | Auf diesen Beitrag antworten » |
keine ahnung so steht es in dem Skript von unserem Prof.ich weiß aber immer noch nicht wirklich weiter
|
||
| 05.02.2017, 15:03 | 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. |
||
| 05.02.2017, 15:09 | 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 ?
|
||
| 05.02.2017, 18:42 | 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.) |
||
| 05.02.2017, 19:29 | Oggel | Auf diesen Beitrag antworten » |
Alles Klar dankeschön
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. |
||
| 05.02.2017, 19:56 | Oggel | Auf diesen Beitrag antworten » |
Habe hier nach ein bisschen Recherche evtl einen Beweis gefunden. Allerdings verstehe ich den vorletzten Schritt nicht
|
||
| 05.02.2017, 20:01 | Elvis | Auf diesen Beitrag antworten » |
Vermutlich wird das Zielfunktional nur parallel verschoben, also ändert sich im wesentlichen nichts. |
||
| 05.02.2017, 20:07 | Oggel | Auf diesen Beitrag antworten » |
Der Beweis passt aber oder? Verstehe folgenden Schritt iwie nicht wieso sind die beiden Gleichungen gleich?
|
||
| 05.02.2017, 22:08 | Elvis | Auf diesen Beitrag antworten » |
Passt schon, das sind ja nur endliche Summen. Beachte das Distributivgesetz. |
||
| 06.02.2017, 20:20 | Oggel | Auf diesen Beitrag antworten » |
Okay danke dir
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
