Vogelsche Approximationsmethode

kann mir jemand vielleicht das Branch & Bound-Verfahren und die Vogelsche Methode erklären? Verstehe nur, dass man zunächst die Differenzen bildet und dann die größte Differenz bestimmt....und dann???

Gruß und danke, Luisa

Vogel

Hallo Luisa,

zum Vogel habe ich mir das so gemerkt:

1. Aus allen Spalten und Zeilen von dem zweitkleinsten und dem kleinsten Wert jeweils die Differenz notieren
2. Nun die Spalte mit dem höchsten Wert suchen
3. Die Anfrage mit den niedrigsten Kosten zuerst befriedigen
4. Das Angebot entsprechend runterrechnen bzw. Zeile streichen, wenn Angebot verbraucht; sollte das Angebot nicht reichen, zum nächst günstigen Preis gehen und dort mit diesem Angebot die restliche Nachfrage befriedigen.
5. wenn das Angebot aufgebraucht ist, die Zeile streichen - nennt sich „markieren“
6. In einem weiteren Tableau die jeweiligen Ergebnisse an die gleiche Zeilen-/Spaltenposition eintragen.
7. Gibt es zu Positionen keine Einträge, einfach leer lassen, was Null bedeutet
8. Ergebnisse ablesen in Reihenfolge Zeile, Spalte. xij: i = Zeile, j = Spalte

Natürlich kannst du die Werte auch aus dem Tableau ablesen, in dem du gearbeitet hast, brauchst nicht ein neues zu erstellen, ist aber eventuell übersichtlicher.


Gruß
Gabi

danke, das hat mir schonmal geholfen. Das Beispiel im Skript verstehe ich nun 🙂 . Hänge aber nun bei der Aufgabe B0509. Nach Berechnung der Differenzen transportiert A3 600 Einheiten zu B1. B1 hat also eine weitere Nachfrage von 150 Einheiten. Wieso liefert die nicht A1? Der hat doch die nächst niedrigeren Kosten?

Gruß Luisa

B 50509

Hallo Luisa,

habe das mal geschwind nachgerechnet und folgendes ermittelt:

x13 = 300; x21 = 150; x22 = 240; x31 = 600; x 42 = 120, x43 = 90

Somit komme ich auch auf 7260 wie die Lösung der Uni, nur dass die ihre 90 und 120 irgendwie vertauscht haben oder sich einfach vertippt hatten.

Ciao
Gabi

Tut mir leid...irgendwie habe ich da eine Blockade. Also: Ich berechne zunächst die Differenzen der Spalten und Zeilen. Die größe Differenz habe ich in Spalte 1. Die niedrigsten Kosten habe ich hier bei A3. Also liefert A3 600 Einheiten zu B1. B1 hat nun noch eine Rest-Anfrage von 150 Einheiten und die Zeile von A3 wird gestrichen. Wie geht es nun weiter? Ich dachte, dass ich wegen der Rest-Anfrage nun zum Anbieter mit den nächst höheren Kosten wechsele, also hier A1. Das ist aber wohl falsch. Was nun???

Wie geht es nun weiter?

Zum Vergrößern anklicken....

Du berechnest nun wieder die Differenzen. Der Kreislauf beginnt immer wieder von vorne, bist du alle Zeilen und Spalten streichen konntest. Der Rest von 150 Einheiten bleibt so lange bestehen bis du da wieder die größte Differenz ausrechnest.

LuisaBrandis schrieb:

Tut mir leid...irgendwie habe ich da eine Blockade. Also: Ich berechne zunächst die Differenzen der Spalten und Zeilen. Die größe Differenz habe ich in Spalte 1. Die niedrigsten Kosten habe ich hier bei A3. Also liefert A3 600 Einheiten zu B1. B1 hat nun noch eine Rest-Anfrage von 150 Einheiten und die Zeile von A3 wird gestrichen. Wie geht es nun weiter? Ich dachte, dass ich wegen der Rest-Anfrage nun zum Anbieter mit den nächst höheren Kosten wechsele, also hier A1. Das ist aber wohl falsch. Was nun???

Zum Vergrößern anklicken....

Hallo Luisa,

vielleicht habe ich in meinem "Kochrezept" nicht ganz sauber abgetippt ...

Du nimmst den höchsten Wert der Differenzen, der in Zeilen bzw. Spalten ist, also nicht nur in den Spalten gucken ... - Das wäre dann die 1. Zeile mit dem höchsten Wert 4. Wahrscheinlich lag da der Fehler - sorry. Probier es jetzt mal, dann klappt es bestimmt. Ich schreibe grad nochmal kurz das Prozedere ab:

1. Aus allen Spalten und Zeilen von den beiden kleinsten Werten jeweils die Differenz notieren (falls es zweimal die 6 gibt als kleinste Zahl, dann ist die Differenz natürlich Null)
2. Nun die Spalte bzw. Zeile mit dem höchsten Wert suchen
3. Die Anfrage mit den niedrigsten Kosten zuerst befriedigen
An dieser Stelle dann wieder neue Zeilen- bzw. Spaltenminimum(s) bestimmen ...
4. Das Angebot entsprechend runterrechnen bzw. Zeile streichen, wenn Angebot verbraucht; sollte das Angebot nicht reichen, zum nächst günstigen Preis gehen und dort mit diesem Angebot die restliche Nachfrage befriedigen.
5. wenn das Angebot aufgebraucht ist, die Zeile streichen - nennt sich „markieren“
6. In einem weiteren Tableau die jeweiligen Ergebnisse an die gleiche Zeilen-/Spaltenposition eintragen.
7. Gibt es zu Positionen keine Einträge, einfach leer lassen, was Null bedeutet
8. Ergebnisse ablesen in Reihenfolge Zeile, Spalte. xij: i = Zeile, j = Spalte

Mittlerweile mache ich mir aus Zeitgründen auch keine zweite Tabelle darunter. Ich markiere einfach farbig die Werte, die ich ermittelt habe.

Melde dich einfach, wenn es noch nicht klar ist.
Ciao
Gabi

Mein Gott jetzt hat sie es 😉)) Vielen Dank für die Hilfe!

LuisaBrandis schrieb:

Mein Gott jetzt hat sie es 😉)) Vielen Dank für die Hilfe!

Zum Vergrößern anklicken....

Freut mich. War ja auch durch meine unsaubere Übermittlung.

Ciao
Gabi