Simplex ohne (0/0) < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:41 So 19.02.2006 | | Autor: | ardik |
| Aufgabe | Gegeben ist das folgende LOP:
$ z = [mm] 3x_1 [/mm] - [mm] 5x_2 [/mm] -> Min!$
u.B.d.R.
[mm] $2x_1 [/mm] + [mm] x_2 \le [/mm] 15$
[mm] $x_1 [/mm] + [mm] 3x_2 \ge [/mm] 20$
[mm] $x_1,x_2 \ge [/mm] 0$
a) Bestimmen Sie rechnerisch eine optimal zulässige Lösung des gegebenen Problems
b) Bilden Sie das duale Problem des angegebenen Optimierungsproblems
c) Bestimmen Sie aus der ermittelten Lösung des Primals ein ezulässig optimale Lösung ds Duals |
[okokok, ich hab's! Beim Aufbereiten meiner Tableaus für den Scanner hab ich bemerkt, dass ich das, was ich jetzt unten rot und fett markiert habe, übersehen hatte...]
Kann man eigentlich seine eigenen Fragen löschen? Oder wenigstens selbst als beantwortet markieren? ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Hallo Ihr,
[das war mal eine Klausuraufgabe für WiWis - und jetzt soll ich die jemandem erklären...]
zunächst: Im Augenblick frage ich hier nur nach a). Zum Thema "dual" lese ich gerade noch Skript, falls dann noch was unklar ist, frage ich weiter 
Simplex-Tableau für den einfachen Fall ist mir (schematisch) klar, aber hier gehört (0/0) nicht zum zulässigen Lösungsraum. Da fehlt mir jetzt wohl einfach die passende "Regel".
Nach Umwandlung des LOP habe ich:
$ z = [mm] -3x_1 +5x_2 [/mm] -> Max!$
u.B.d.R.
[mm] $2x_1 [/mm] + [mm] x_2 \le [/mm] 15$
$\ [mm] -x_1 [/mm] - [mm] 3x_2 \le [/mm] -20$
[mm] $x_1,x_2 \ge [/mm] 0$
und damit das Tableau:
[Dateianhang nicht öffentlich]
(btw: wie kriegt man das mit LaTEX hin?)
Ich kenne zwei "Methoden". kurzgefasst:
1) "einfacher Fall:" Kleinster neg. Koeff. i.d. Zielfunktion definiert Pivot-Spalte, kleinster Quotient aus Koeff. der b-Spalten und pos. Koeffs der Pivotspalte definiert Pivotzeile, dann in Pivotspalte Einheitsvektor bilden (mit 1 i.d. Pivotzeile) etc. und wieter geht's von vorn bis alle Koeffs. der Zeilfunktionszeile positiv sind => opt. Lösung.
2) "(0/0) keine zulässige Lösung:" Start "verdreht": kleinster neg. Koeff aus b-Spalte, größter Quot. aus Zielfunktionskoeffs und neg. Koeffs der Pivotzeile. Dann wieder weiter wie oben bis alle Koeffs der b-Spalte positiv sind => zulässige Lösung. Falls diese Lösung noch nicht optimal (d.h. neg. Koeffs in Zielfkt.-Zeile vorhanden?) weiter wie unter 1)
Ich starte also mit 2), erhalte gleich im nächsten Tableau nur positive Koeffizienten i.d. b-Spalte, habe aber noch negative in der Zielfunktionszeile. Also mache ich weiter mit 1) und lande gleich wieder beim Ausgangstableau.
Das kann's also nicht sein. da muss mir irgendeine Regel fehlen.
[restliche tableaus haben sich erübrigt]
Aber danke...!
ardik
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:25 So 19.02.2006 | | Autor: | ardik |
Leider kann ich meine Frage nicht selbst als beantwortet markieren - oder gar selbst löschen.
Jedenfalls hab' ich meinen - blöden - Fehler inzwischen gefunden...
Grüße,
ardik
|
|
|
|
