Minimale Kosten in einem Diagramm ermitteln [Optimierung] |
| 23.01.2015, 12:11 | mathefan93 | Auf diesen Beitrag antworten » |
| Minimale Kosten in einem Diagramm ermitteln [Optimierung] brauche Hilfe zur folgenden Aufgabe: Gegeben ist ein Flussnetzwerk mit folgenden Angaben: Knoten = {1,2,3,4}, Bogen = {(1,2), (1,3), (2,4), (3,4), (2,3)} Kapazitäten: alle 3, außer (2,3): 2 Kosten: alle 1 außer (3,4): 4 Anfangsfluss: alle Bogen außer (2,3): 2 Im folgenden bezeichnet b_v die Differenz eingehender Fluss - ausgehender Fluss im Knoten v Die Aufgabe ist es nun, die Kosten zu minimieren, sodass folgende Nachfrage erfüllt wird: b_1 = 4, b_4 = -4 alle anderen 0; Ich habe jedoch Probleme passende Flüsse zu bilden, und hoffe ihr könnt mir helfen Schöne Grüße, mathefan93 |
||
| 24.01.2015, 18:30 | Elvis | Auf diesen Beitrag antworten » |
Wenn du alle Anfangsflüsse umdrehst, also -2 statt +2, hast du schon mal eine Anfangslösung, die die Nachfrage erfüllt. Dann musst du nur noch die Kosten minimieren. Dass dieser Ansatz gut ist, glaube ich nicht, obwohl er von mir ist. 
|
||
| 25.01.2015, 01:20 | mathefan93 | Auf diesen Beitrag antworten » |
aber wenn ich alle anfangsflüsse umdrehe, dann habe ich an den Knoten 2 bzw 3 ein angebot von 2 bzw -2 Mir fällt grade auf ich habe vergessen folgenden Satz zu erwähnen: Sei (G,u,s,t) eine Instanz des MINIMUM_COST_FLOW_PROBLEMS. Ein b-Fluss hat genau dann minimale Kosten, wenn es keinen f-augmentierenden Kreis mit negativem Gesamtgewicht Hierbei ist f wohl ein s-t-fluss, wie kann ich mir f-augmentierend vorstellen? Vielleicht hilft euch das beim mir helfen ja weiter^ Schöne Grüße, mathefan93 |
||
| 25.01.2015, 11:25 | Elvis | Auf diesen Beitrag antworten » |
Der Anfangsfluss (2,3) ist 0, also ist b_2=b_3=0, und das bleibt auch bei Flussumkehr so. Wegen der hohen Kosten von (3,4) sagt meine Anschauung, dass der Fluss (3,4)=(1,3)=-4, sonst 0, schon die minimale Lösung ist. Wer bietet weniger ? Nachtrag: Es geht noch erheblich bessser ! |
||
| 25.01.2015, 22:12 | mathefan93 | Auf diesen Beitrag antworten » |
ich dachte wegen der hohen Kosten der Kante (3,4) sollte man diese möglichst umgehen? also wäre ein möglicher minimalster fluss (1,2)-(2,4)? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
