Transportproblem/Netzwerkfluss < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:55 Sa 17.06.2006 | | Autor: | Karsten1 |
| Aufgabe | | Gesucht: Maximal mögliche Transportmenge |
Ich habe z.b folgenden Graphen:
Punkt2
5 Einheiten (1->2) 4 Einheiten (2->4)
Punkt1 3 Einheiten (3->2) Punkt4
4 Einheiten(1->3)
5 Einheiten (3->4)
Punkt3
Ist das klar?
Ich habe also einen Startpunkt 1. Von diesem können 5 Einheiten nach Punkt 2 geliefert werden und 4 Einheiten nach Punkt 3.
Von Punkt 2 können nur 4 Einheiten nach 4 geliefert werden
Von Punkt 3 können 3 Einheiten nach 2 und 5 Einheiten nach 4 geliefert werden.
Nun möchte ich die maximlae Transportmenge bestimmen. Diese müßte ja 8 sein. Irgendwie schaffe ich es aber nicht die richtigen Beziehungen aufzustellen....
Mein Versuch in Mathematica sieht so aus:
funk = 5*x12 + 4*x13 + 3*x32 + 4*x24 + 4*x34
nb = {x12 + x32 - x24 ≤ 4,
x13 - x32 - x24 ≤ 5,
x12 + x13 - x24 - x34 == 0,
0 <= x12 ≤ 5,
0 <= x13 ≤ 4,
0 <= x32 ≤ 3,
0 <= x24 ≤ 4,
0 <= x34 ≤ 5}
Minimize[{funk, nb}, {x12, x13, x32, x24, x34}]
und das Ergebnis: {86, {x12 -> 5, x13 -> 4, x32 -> 3, x24 -> 4, x34 -> 5}}
Es kommt also 86 raus....
Sieht jemand meinen Fehler?
Danke
Karsten
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
die Werte auf den Kanten sollen ja Kapazitäten sein, dann kannst Du nicht noch in der Zielfunktion mit den Kapazitäten multiplizieren.
Ausserdem moechtest Du den Flusswert maximieren, das ist nicht die Summe von etwas ueber alle Kanten, sondern nur ueber die
eines Cut, zB alle von Punkt 1 (Quelle) ausgehenden Kanten.
Das LP zum Flussproblem (Maximaler Fluss von 1 nach 4) sieht also so aus:
maximiere [mm] x_{12}+x_{13} [/mm] so dass
[mm] 0\leq x_{12}\leq [/mm] 5,
[mm] 0\leq x_{13}\leq [/mm] 4
usw (Kantenkapazitätsbedingungen)
[mm] x_{12}+x_{32}=x_{24}
[/mm]
[mm] x_{13}=x_{32}+x_{34}
[/mm]
(Flusserhaltungsgleichungen an den Knoten 2 und 3)
und wenn Du das in was auch immer ausrechen laesst, sollte auch 8 herauskommen.
Gruss,
Mathias
|
|
|
|
