 |
 |
 |
 |
 |
 |
Startseite » Forum » Transportproblem
Transportproblem
Universität / Fachhochschule
Tags: MODI-Methode anwenden
 
|
  |
|---|
|
Hi Leute, Prüfung steht an und ich stecke gerade in einem Problem fest: Ich soll die Startlösung eines Transportproblem optimieren! Und zwar mit der MODI-Methode bzw. Methode der Potentiale.
Soviel weiß ich:
- Ich nehme die Startlösung. - ich belege die Zeilen mit den Potentialen "u" und die Spalten mit "v" - die erste zeile bekommt ein u1 = 0 -> über die gegeben Kosten bei der jeweiligen Basisvariable in Zeile 1 erhalte ich die das dazugehörige v1 - jetzt rechne ich immer Kij - uij bzw. vij und komme immer auf die entsprechenden Potentiale - dann schau ich mir die NICHT Basisvariablen an, nehmen deren Kij und ziehe dann die Summe aus den dazugehörigen Potentialen (uij+vij) ab. -Das sich daraus ergebende Delta Kij wird in der jeweiligen Zelle vermerkt - ist MINDESTENS ein Delta Kij NEGATIV ist die Lösung nicht optimal!
Soweit so gut - aber ich habe das mit dem darauf folgenden "Kreis" und der Verschiebung irgendeiner Menge nicht so ganz verstanden!
Meine Frage: Wie ermittle ich den Kreis? Welche Menge müssen verschoben werden? Und: Wie stelle ich dann Optimalität fest?
Ich hoffe ihr könnt mir helfen - stellt euch bitte vor ich wäre 8 Jahre alt ;-) Je einfacher desto verständlicher!! Es ist sicher nicht schwer - aber den Algorithmus möchte ich verstehen - die Problematik an sich ist schon recht interessant!
Viele Grüße
Schroedinger Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Du bist dann optimal, wenn alle (aus genommen der Basisvariablen) größer gleich 0 sind. Wenn das erreicht ist, folgt aus dem Satz vom schwachen komplementären Schlupf oder den Karush-Kuhn Tucker Bedingungen die Optimalität der Lösung.
Um den Kreis zu finden, kann man sich entweder den zu den Basisvariablen gehörigen Baum aufzeichnen und das dann ablesen oder bei kleinen Probleme, also so 4 Anbieter und Nachfrager kann man das durch hinschauen erkennen. Mach doch mal ein Beispiel.   |
 |
|
Ein Bsp. würde jetzt leider zu lange dauern... Vielleicht hat hier jemand ein einfaches auf lager?! - mein Bsp sind recht komplex...
VG |
|
|
|
Sagt dir das mit dem Baum etwas? Weißt du wie man auf den kommt? Zunächst mal nur die schwarzen Kanten. |
|
|
|
Sei mal das obige Tableau gegeben. Von den Nichtbasisvariablen sucht man sich das Feld raus, in dem der Eintrag am kleinsten ist. Dort ist die zugehörige Ungleichung im dualen Problem am "meisten verletzt". (Hoffe das sagt dir was!) In dem Beispiel ist es die Verbindung von Anbieter 2 zu Nachfrager 3.
Jetzt gilt es den Kreis zu finden. Hierzu kann man das Problem mal als Baum aufmalen. Die Anbieter (A) und Nachfrager (B) sind die Knoten des Graphen und die existierenden Lieferverbindungen sind die Kanten des Baumes. Am Anfang sind nur die schwarzen Kanten zu beachten. Da der Graph eine Baum ist, existiert kein Kreis! Jetzt wird die Variabele in die Basis aufgenommen. Es wird im Baum also eine Verbindung zwischen A2 und B3 eingezeichnet (grüne Linie). Dadurch ist jetzt eine Kreis entstanden (rote Kanten). Jetzt gilt es zu bestimmen welche Variable die Basis verlässt. Das Update des Kreises geschieht dadurch, dass man der neue Kante ein bestimmtes Gewicht a gibt, hier also der Kante 2-3. Jetzt läuft man den Kreis in einer Richtung ab. Die Nächste Kante wird um a reduziert. Hier also zum Beispiel 2-1. Die darauffolgende um a erhöht, also hier 1-3. Die nächste wieder um a reduziert, hier also 3-3. Die Nächste wäre wieder 2-3, da waren wir aber schon also hören wir auf. Zusammengefasst: Gehe den Kreis ab und erhöhe und veringere abwechselnd die Kantengewichte jeweils um a. Nun die Frage was ist a: a wird so bestimmt, dass man primal zulässig bleibt, es darf also keine Basisvariable negativ werden. Wenn wir jede zweite Kante/Variable reduzieren, darf als keine von diesen negtiv werden. Also wählen wir a als das Minimum von diesen Kanten. In dem Beispiel sind das die Kanten 2-1 und 3-3. a ist demnach also 1. Wenn wir das Update durchgeführt haben, ist die Variable/Kante 2-1 auf 0, verlässt somit die Basis und 2-3 wird als neue mit Gewicht 1 aufgenommen. Zu beachten ist, wenn mehrere Variablen gleichzeitig auf 0 gesetzt werden, darf nur eine die Basis verlassen! |
|
|
|
Die Erläuterung war schon recht ausführlich, aber ganz durchgestiegen bin ich noch nicht... Die gegebene Matrix enthält jetzt die Kosten für jede Zelle (also die Transportkosten für jede einzelen Verbindung) - check. Irgendjemand hat jetzt Zeile 3 mit dem Potential belegt - check. Ich schätze mal, die viereckig eingerahmten Zahlen sollen die Basisvariablen darstellen?! Frage Warum haben die Zellen und NEGATIVE Mengenwerte? Ich geh mal davon aus, dass die hochgestellten Zahlen die Kosten pro Zelle/Transport darstellen sollen (daraus ergeben sich ja schließlich auch meine Potentiale vj und ui) und dass die "großen" Zahlen die Mengen sind - wobei das dann eine komische Startlösung wäre, da sich eigentlich die Mengen auf entsprechende Zellen je Zeile/Spalte aufteilen! Ich sehe da nicht so recht den Zusammenhang. Warum sollte man negative Mengen liefern? Das müsste ja bedeuten, ich liefere vom Empfangsort zum Versender zurück?! Ist mir zu abstrakt. Frage Warum habe ich bei KEINE Kosten? Oder ist das schon der verbesserte Kreis? Mir sind das zuviele Sprünge auf einmal - sry... Ich hoffe ich habe meine Fragen und Vermutungen klar ausformuliert - hoffentlich könnt ihr mir helfen! Eine step-by-step Bsp wäre optimal - habe schon im Netz gesucht, aber leider nichts passendes gefunden. VG |
|
|
|
Ich habe hier mal ein Beispiel vom herrn Schwarze dargestellt - die Startlösung wurde mit N-W-Eckenregel erstellt - Potentiale und die neuen Kostenwerte kann ich berechnen - wie gehts jetzt weiter?! Es ist eine Excel-Datei. Habs mal als .gif hochgeladen - sollte alles klar leserlich sein. Die roten Zahlen sind die bereits berechneten DELTA Cij = Cij - uij - vij Ich weiß auch, dass ich mir jetzt von den errechneten Werten den kleinsten negativen Wert aussuchen muss. Wäre der kleinste Wert größer gleich Null hätte ich ja bereits die optimale Lösung!! Wie gehts jetzt weiter??  |
|
|
|
Ich mache das mal an deinem Beispiel. Du schaust dir an, welche der roten Zahlen am kleinsten ist. Sollte das Minimum größer oder gleich 0 sein, ist man dual und primal zulässig => man ist bereits optimal. In dem Fall ist das Minimum, welches in den Feldern V4-E1 und V4-E2 angenommen wird. Man kann sich eins der beiden Felder aussuchen, ich wähle das Feld V4-E2, da hier der Kreis Kürzer ist. Jetzt kann man sich den zu der Basislösung gehörigen Baum aufmalen. Siehe unten. In diesen füge ich jetzt die Kante V4-E2 ein. Hierdurch entsteht genau eine Kreis (der immer eine gerade Anzahl von Kanten hat), den man ablaufen kann. Jetzt kommt das Update. Man muss nun ermitteln um wie viel man die "Kosten" der Kanten erhöhen bzw. reduzieren muss. Es wird immer abwechselnd erhöht und reduziert (da der Kreis eine gerade Anzahl an Kanten hat, funktioniert das immer). Im Beispiel werden die Kanten V4-E2, V3-E4 und V2-E3 erhöht und V4-E4, V3-E3 und V2-E2 reduziert. Beim Reduzieren ist zu beachten, dass man primal zulässig bleibt, also alle Basisvariablen einen Wert größer gleich 0 haben. Deswegen muss man sich unter den zu reduzierenden Kanten diejenige Kante herraussuchen die das kleinste Gewicht hat. Zur Auswahl stehen dann . Das Minimum ist bei Kante V2-E2. Damit kann man den Kreis nun updaten: V4-E2 +14, also 14 (war vorher 0) -> tritt in die Basis ein V4-E4 -14, also 24 V3-E4 +14, also 18 V3-E3 -14, also 2 V2-E3 +14, also 30 V2-E2 -14, also 0 -> verlässt die Basis Wenn mehrere Kanten/Variablen gleichzeit 0 werden sollten, darf nur eine von diesen aus dem Graph entfernt werden, da sonst nicht mehr zwangsläufig eine Baum vorliegt. Soweit klar? Wenn man ein wenig Übung im Updaten hat, kann man das Suchen der Kreise durch hinschauen lösen, was um einiges schneller geht.   |
|
|
|
"Jetzt kann man sich den zu der Basislösung gehörigen Baum aufmalen. Siehe unten. In diesen füge ich jetzt die Kante ein. Hierdurch entsteht genau eine Kreis (der immer eine gerade Anzahl von Kanten hat), den man ablaufen kann. Jetzt kommt das Update. Man muss nun ermitteln um wie viel man die "Kosten" der Kanten erhöhen bzw. reduzieren muss. Es wird immer abwechselnd erhöht und reduziert (da der Kreis eine gerade Anzahl an Kanten hat, funktioniert das immer). Im Beispiel werden die Kanten und erhöht und und reduziert." Den "Baum" habe ich immernoch nicht so recht verstanden... Welche "Kante" meinst du? Die Linien um der Zelle, in der steht? Woher weiß ich in welche Richtung ich gehen muss? Woher weiß ich, welche Basisvariablen betroffen sein müsse? These: Die kleinste Basisvariable meines Kreises muss ich nach der Regel von den anderen Feldern abziehen bzw. dazurechnen. Wann ist die Lösung optimal? Ich hoffe du gibst mich nicht auf - aber ich kann es mir nicht so recht vorstellen! Aber bis jetzt: Vielen vielen Dank! |
|
|
|
Zur Erklärung des Baumes: Ein Baum ist ein Graph. Der besteht aus Knoten und Kanten. Die Knoten sind in dem Fall die Anbieter V1,..V4 und die Nachfrager E1,..,E5. Wenn man eine Basislösung hat und dabei ist (also nicht 0)dann liefert man zum Beipsiel von Anbieter 4 zu Nachfrager 4. Im Graphen wird das ausgedrückt, indem man diese beiden Knoten verbindet, also eine Kante einfügt. Am Anfang hat man den Graphen im ersten Bild. Da muss man sich zunächst mal die orange Line wegdenken. Jetzt hat man festgestellt, dass man in der Matrix beim Eintrag V4-E2 den minimalen Wert der Matrix hat, also -6. Man beschließt also etwas von V4 nach E2 zu liefern. Dies wird in dem Graphen dadurch ausgedrückt, dass man eine Kante von V4 nach E2 einfügt. Das ist die orange Linie. zu 2: Die Richtung ist egal. Das liegt daran das der Kreis eine gerade Anzahl an Kanten hat. zu 3: Jede Kante in dem Graphen steht für eine Basisvariable. Also die Kante V4-E2 bedeutet ja das man was von V4 nach E2 schicken möchte, also nicht mehr 0 ist. Es sind alle Basisvariabeln betroffen, die auf dem Kreis "liegen". Etwas genauer: V4-E2 -> V3-E2 -> V2-E3 -> V4-E4 -> V3-E3 -> V2-E2 -> zu 4: Nein! Nicht die Kleinste. Sonder die kleinste von jeder Zweiten, da man ja nur von jeder zweiten Basisvariable etwas abzieht. Weil nur da kann es passieren das die Basisvariable negativ wird, was ja nicht erlaubt ist. Das habe ich oben mit dem Minimum von gemeint. Der Kreis hat hat ja sechs Kanten und ich nehmen nur 3 davon zur Auswahl, nämlich jede Zweite. zu 5: Die Lösung ist dann optimal, wenn für alle gilt, wobei keine Basisvariable ist. Habt ihr keine Theorie dahinter gehabt, mit primalen und dualen Problem? |
|
|
|
Hi, habe noch eine Rückfrage - müsste jetzt fast bei Ergebnis sein! Ich nehme jetzt eine der beiden Zellen bei der sich das DELTA Cij mit ergbit - sagen wir die äußerste links unten! Ich gehe jetzt von Zelle zu den Basisvariablen: erste Überlegung: Ich kann doch eigentlich nur den KLEINSTEN Wert von einer Basisvariable verschieben, also eigentlich die 4 oder? ODER mache da noch etwas was falsch, was die Kanten angeht? Ich darf ja NICHT diagonal irgendwelche Felder schneiden sondern muss immer die waagerechte/senkrechte Verbindung suchen, bis ich wieder bei meiner Startposition angelangt bin! Jetzt versehe ich die Startposition mit einem PLUS (MUSS ja, ich will ja hierhin eine neue Basisvariable verschieben!) und dann immer im wechsel usw bis ich wieder bei der Startposition bin. Mein Dilemma: Warum nimmst du die und nicht die 4? Außerdem, wenn ich die 4 nehme würde, würde das System nachweislich nicht aufgehen und ich würde bei 4 nochmal 4 addieren?! Es scheitert wahrscheinlich noch an dieser KANTEN geschichte Aber es wird langsam schlüssig ;-) EDIT: was mir gerade noch einfällt: ANGENOMMEN mein kleinster Wert wäre die bei dann müsste doch mein Kreis und wieder zurück zu sein? Das würde sich aber mit dem obigen Kreis widersprechen oder? Nach deiner Methode interessieren mich nur die Kanten, sobald ich aber direkt auf eine Ecke treffe . bei oder zweige ich nur ab und gehe zur nächsten Kante usw... Die Systematik ist einfach noch nicht ganz schlüssig |
|
|
|
Nehmen wir mal an wir würden die 4 nehmen. Dann würde man den Kreis eben mit 4 updaten. Das Problem ist dann nur das keine Basisvariable auf 0 geht. Rechne das mal nach. Also hätte man dadurch nichts gewonnen, da keine Variable die Basis für die neu eintretende verlässt. Deswegen schau ich bei den Kanten nach, bei den der Wert abgezogen wird. Da kann das "Gewicht" das abgezogen/addiert werden muss so bestimmen werden , das ich eine /einige Basisvariablen auf 0 bekomme, diese also die Basis verlassen.
EDIT: Wenn man das Feld von nimmt so bekommt man natürlich einen anderen Kreis. Das ist normal. Die Wahl der Kanten erfolgt einfach nur über den Baum. Sturr den Baum aufmalen, also alle Verbindungen einmalen, dann die Knate/Basisvariable die man hinzufügt einzeichnen und dann den Kreis ablesen. |
|
|
|
Ok - aber dann müsste ich doch von den Basisvariablen "4" und "8" (welche ja auch zum Kreis gehören) ebenfalls abziehen! Das wäre ja dann negativ, was ja bei Kosten nicht sein kann... Oder anders gefragt - woran erkenne ich dann den richtigen Kreis? Leider kommt jetzt NOCH eine Frage zum Thema hinzu... Ich habe unten noch ein Bildchen angefügt - hier möchte ich gerne die Potentiale berechnen! Das Ergebnis habe ich über Vogel bekommen - man hätte es aber auch irgendwie über die MODI-Methode erhalten (logischerweise) Meine Frage: Wie berechne ich und ? Ich weiß aus der Lsg. dass sein soll - wie komme ich darauf. Die abgebildetet Matrix ist natürlich die Kostenmatrix - die "gerahmten" Werte entsprechen den Zellen der Basisvariablen. Durch stupides Cij = Ui Vj komme ich da nicht mehr weiter - gibts da irgendeinen Trick? Ich kann ja nicht einfach Werte annehmen, dachte ich mir...  |
|
|
|
"Ok - aber dann müsste ich doch von den Basisvariablen "4" und "8""
Es wird doch nur jede zweite Variable reduziert. Die von dir angesprochenen Felder gehören aber nicht dazu. "Oder anders gefragt - woran erkenne ich dann den richtigen Kreis?" Da gibt es nicht viel zu erkennen. Es gibt nur einen! "Das Ergebnis habe ich über Vogel bekommen - man hätte es aber auch irgendwie über die MODI-Methode erhalten" Da verstehe ich nicht was du mit Vogel meinst. Die Vogelsche Approximationsmethode? Dann macht der zweite Teil aber keinen so rechten Sinn, da man mit der Vogelschen Approximationsmethode eine zulässige Startlösung findet, wärend man mit MODI die Startlösung verbessert. "Meine Frage: Wie berechne ich u1,v1 und v4? Ich weiß aus der Lsg. dass u1=1 sein soll - wie komme ich darauf." Also bei MODI stellt man seine Gleichungen auf, insgesamt ( Anzahl der Anbierter, Anzahl der Nachfrager). Da man aber ein unterbestimmtes Gleichungssystem hat, kann man sich eine Variable aussuchen und zum Beispiel 0 setzen. Die restlichen kann man dann mit den Gleichungen bestimmen. |
|
|
|
Hi daspo, erstmal vielen Dank, dass du mich trotz meiner Fragerei nicht hängen gelassen hast - das mit den Kreis habe ich jetzt kapiert! Einfach die Startlösung nehmen, beim Feld mit den "negativsten" Kosten, die sich aus Kij-ui-vj ergeben, starten. Dieses Startfeld muss mit einem PLUS belegt werden (hier will ich ja eine "alte" Menge "neu" transportieren mit dem Ziel Kosten einzuspaeren!) Dann muss ich mir die Basisvariablen suchen (den kreis nur horizontal oder vertikal "ablaufen"). . schauen, wo die nächstgelegene Basisvariable ist, dann von dort aus weiter schauen usw. bis ich wieder beim Startfeld angekommen bin! Wenn ich den Kreis fertig habe (idealer weise so klein wie möglich halten) die Basisvariablen immer im Wechsel mit und - versehen, dann nur die mit einem versehenen Basisvariablen herauspicken und dort den kleinsten Wert suchen! Im obigen Fall ist das natürlich ;-) Dann wird immer im Wechsel addiert, subtrahiert usw. bis ich am Ende bei meinem Startfeld stehen habe, und in meinem Feld (basisvariable) mit der kleinsten Transportmenge steht. Dann habe ich eine NEUE Startlösung, wobei ich wieder neue Potentiale aufstellen muss und diese dann schrittweise neu berechnet werden. Am Ende berechne ich wieder meine DELTA-Kosten (DELTA Kij = Kij - ui - vj) und prüfe, ob noch irgendwo negative Werte rauskommen. Ist dies der Fall ist die Lösung noch nicht optimal! Wenn alle Werte positiv sind, ist sie optimal und ich habe meine Transportkosten auf ein Minimum reduziert. Sind wir uns da einig? ;-) |
|
|
|
Ja das sieht schon einmal ganz gut aus. Bis auf einen Teil:
"D.h. schauen, wo die nächstgelegene Basisvariable ist, dann von dort aus weiter schauen usw. bis ich wieder beim Startfeld angekommen bin!" Die "nächstgelegene Basisvariable" darf man nicht immer nehmen. Hier mal ein frei erfundenes Beispiel. Die roten Zahlen stehen für Basisvariablen und die schwarzen Zahlen für die . offensichtlich muss man die Variable aufnehmen. Die nächsten Basisvariablen wären dann und . Allerdings kann man keine von diesen nehmen, da wenn von horizontal bzw. von vertikal geht, zu keiner anderen Basisvariable kommt. Der Kreis hier würde aus bestehen. Deswegen solltest du dir am Anfang wirklich den Baum aufmalen. Wenn das klappt kann man dazu übergehen das durch hinschauen zu lösen, eben mit der Regel das man abwechselnd horizontal und vertikal gehen muss und der KREIS in jeder Zeile und Spalte entweder zwei Basisvariablen oder gar keine hat.  |
|
|
|
hi, kannst du nochmal das bild posten? wird leider nur als fehlermeldung angezeigt!! DANKE |
|
|
|
AH danke!! Bild konnte ich jetzt doch sehen! . ich muss nicht nur nach der Basisvariable gehen, sondern danach, dass ich ich den Kreis auch vervollständigen kann?! Eine letzte These: Ich darf beim Kreis nur die Basisvariablen nehmen, bei denen wieder eine Verzweigung in horizontaler bzw. vertikaler Richtung stattfindet? Falls (wie in diesem Bsp) noch andere Basisvariablen . oder auf dem "Weg" liegen, dürfen diese für die weitere Rechnung NICHT in Betracht gezogen werden?! Kann man das so stehen lassen?? |
|
|
Ja genau. Immer schauen das man einen Kreis "schließen" kann. Deswegen nochmal meine Empfehlung für den Anfang: Mal dir den Baum auf. Daran ist der dann gut abzulesen.   |
 |
|
So - jetzt habe ich es geschnallt! Wird alles in der Formelsammlung vermerkt ;-) Danke für die Hilfestellung!! VG Schroedinger |
|
|
|
Ich habe mir die Erklärung durchgelesen und finde sie wirklich sehr gut! Hilft weiter :-) Allerdings habe ich eine Frage: werden denn im zweiten Durchlauf (ang. das Ergebnis ist noch nicht optimal) die alten Basisvariablen, die im ersten Durchlauf auf 0 gesetzt wurden im Baum betrachtet? |
|
|
|
Hey Viki, das Thema liegt ja nun doch schon einige Monde zurück ;-) Ich selbst kann dir aktiv leider keine Unterstützung geben. Ich habe mir damals auf Empfehlung unserer Mathe-Professorin den Schwarze gekauft (besonders toll für OR, Graphentheorie und Statistik IMHO), ist auch nicht allzu teuer: www.amazon.de/Mathematik-f%C3%BCr-Wirtschaftswissenschaftler-Graphentheorie-Betriebswirtschaft/dp/3482515832/ref=sr_1_1?s=books&ie=UTF8&qid=1478527367&sr=1-1&keywords=Schwarze+lineare+Algebra Ich wünsche dir alles Gute - vielleicht kann jemand hier im Forum ausführlicher auf deine Frage eingehen. Schroedinger |
1333961
967477