Simplex-Algorithmus < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:09 Mi 25.03.2009 | | Autor: | barsch |
Hi,
kann mir jemand in seinen eigenen Worten erklären, wie im Simplex-Algorithmus die Einträge des reduzierten Kostenvektors zu interpretieren sind?!
Ich meine, in diesem Zusammenhang mal was mit Opportunitätskosten gelesen zu haben?!
Danke.
MfG barsch
Achso, ich habe schon im Internet gesucht, aber zufriedenstellend war für mich keine der wenigen Interpretationen. Deswegen hoffe ich auf Antworten von euch 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:28 Fr 27.03.2009 | | Autor: | koepper |
Hallo barsch,
> kann mir jemand in seinen eigenen Worten erklären, wie im
> Simplex-Algorithmus die Einträge des reduzierten
> Kostenvektors zu interpretieren sind?!
die reduzierten Kosten einer Spalte (d.h. einer Zielvariablen) geben an, wie stark der Zielfunktionswert ansteigt bzw. (bei negativen red. Kosten) abfällt, wenn diese Spalte (d.h. Zielvariable) mit Koeffizient 1 in die Basis aufgenommen wird. Beim Basiswechsel wird die neue Spalte mit Koeffizient=Minimalquotient aufgenommen. D.h. die tatsächliche Veränderung des Zielfunktionswertes ist red.Kosten*Minimalquotient.
LG
Will
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:26 Fr 27.03.2009 | | Autor: | barsch |
Hallo,
vielen Dank.
Ich wollte mir das gleich mal an einem Beispiel verdeutlichen... und leider scheiterte es. Ich will mein Problem mal kurz skizzieren, vielleicht habe ich etwas falsch verstanden.
(Ich hoffe, im Folgenden wird deutlich, was ich meine - wir haben nämlich nie die Tableau-Schreibweise eingeführt.)
Problem:
[mm] \min_{x\in\IR^2}-2x_1-3x_2
[/mm]
[mm] -4x_1+3x^2+x_3=12
[/mm]
[mm] 2x_1+3x_2+x_4=30
[/mm]
Basis [mm] B=\{3,4\}, [/mm] Nichtbasis [mm] N=\{1,2\}
[/mm]
Basismatrix [mm] A_B=\pmat{ 1 & 0 \\ 0 & 1 }
[/mm]
[mm] x_B=\pmat{ 1 & 0 \\ 0 & 1 }*b=\pmat{ 1 & 0 \\ 0 & 1 }*\vektor{12 \\ 30}=\vektor{12 \\ 30}.
[/mm]
Also ist [mm] x=\vektor{x_B \\ x_N}=\vektor{A_B^{-1}*b\\ 0}\ge{0} [/mm] zulässige Basislösung.
Nun zu den reduzierten Kosten:
Der Eintrag für Variablen [mm] x_3 [/mm] und [mm] x_4 [/mm] ist $0$ - klar, die beiden Variablen befinden sich in der Basis.
Der Eintrag für die Variable [mm] x_1 [/mm] ist $-2$ und der für die Variable [mm] x_2 [/mm] ist $-3$
Zum jetzigen Zeitpunkt ist der Zielfunktionwert -2*0-3*0=0
Wenn ich jetzt Variable [mm] x_1 [/mm] in die Basis hole, müsste, sofern ich das richtig verstanden habe, im nächsten Schritt der Zuielfunktionswert -4 betragen (da reduzierte Kosten $-2$ sind (also fällt der Zielfunktionwert um $-2*2=-4$ ab?))
Aber im nächsten Iterationsschritt erhalte schon die Optimallösung und einen Zielfunktionswert von $-30$.
Wo liegt mein Fehler?
MfG barsch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:48 Fr 27.03.2009 | | Autor: | barsch |
Es hat mir einfach keine Ruhe gelassen; ich bin den Simplex wieder und wieder durchgegangen - mit Erfolg. Ich weiß jetzt, was du mit Minimalquotient meintest. Und jetzt habe ich es insgesamt nachvollziehen können.
Danke.
MfG barsch
|
|
|
|
