Lösbarkeit durch Simplex < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:16 Mo 14.05.2007 | | Autor: | Simple84 |
| Aufgabe | Folgendes lineares Optimierungsproblem liegt vor: (im Rahmen des LP- Verfahrens für Markoventscheidungsprozesse)
ZF: 10 [mm] x_1 [/mm] + 9 [mm] x_2 [/mm] + 12 [mm] x_3 [/mm] + 11 [mm] x_4 [/mm] + 14 [mm] x_5 [/mm] + 13 [mm] x_6 [/mm] = max !
unter den NB:
(1) 0.4 [mm] x_1 [/mm] + [mm] \bruch{2}{3} x_2 [/mm] - 0.2 [mm] x_3 [/mm] - [mm] \bruch{1}{3} x_4 [/mm] - 0.1 [mm] x_5 [/mm] - [mm] \bruch{1}{3} x_6 [/mm] = 0
(2) -0.3 [mm] x_1 [/mm] - [mm] \bruch{1}{3} x_2 [/mm] + 0.4 [mm] x_3 [/mm] + [mm] \bruch{2}{3} x_4 [/mm] - 0.3 [mm] x_5 [/mm] - [mm] \bruch{1}{3} x_6 [/mm] = 0
(3) -0.1 [mm] x_1 [/mm] - [mm] \bruch{1}{3} x_2 [/mm] - 0.2 [mm] x_3 [/mm] - [mm] \bruch{1}{3} [/mm] + 0.4 [mm] x_5 [/mm] + [mm] \bruch{2}{3} x_6 [/mm] = 0
(4) [mm] x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] + [mm] x_4 [/mm] + [mm] x_5 [/mm] + [mm] x_6 [/mm] = 1
[mm] x_1, x_2, x_3, x_4, x_5, x_6 \ge [/mm] 0 |
Ich habe im Internet einige Applets zur Lösung ausprobiert. Bei einigen erhielt ich gar keine Lösung, bei den anderen erhielt ich eine Lösung, jedoch stimmte diese nicht mit meinen Erwartungen überein. Meine Frage: Ist dieses Problem überhaupt gescheit lösbar? Gibt es ein gutes Programm für diese Art von Problemen?
Meine erhaltene Lösung war:
Value of objective function: -12.000000425747558
[mm] x_1 [/mm] = 0.28571363492876556
[mm] x_2 [/mm] = 0.0
[mm] x_3 [/mm] = 0.42857145289985815
[mm] x_4 [/mm] = 0.0
[mm] x_5 [/mm] = 0.2857144864238437
[mm] x_6 [/mm] = 0.0
Wenn ich die Parameter so ändere, dass eigentlich [mm] x_2 [/mm] in die Lösung kommen müsste, ändert sich die Lösung jedoch nicht so wie ich es mir vorstelle. Wie kann ich meine erhaltene Lösung verifizieren.
Danke!!
-----------------------------------------------------------------------------
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:39 Di 15.05.2007 | | Autor: | piet.t |
Hallo,
also die -12 als Zielfunktionswert können ja schon mal gar nicht stimmen: alle Variablen sollen >=0 sein und in der Zielfunktion stehen nur positive Koeffizienten, also sind Zielfunktionswerte <0 schon gar nicht zulässig, geschweige denn optimal!
Ich habe mich mal dran versucht, das Problem abzutippen (bei der dritten Restriktion habe ich mir noch ein [mm] x_4 [/mm] dazugedacht) und folgendes Ergebnis erhalten:
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 12.18749
VARIABLE VALUE REDUCED COST
X1 0.000000 0.656229
X2 0.187502 0.000000
X3 0.437499 0.000000
X4 0.000000 0.875007
X5 0.374999 0.000000
X6 0.000000 2.687475
ROW SLACK OR SURPLUS DUAL PRICES
A) 0.000000 0.000000
B) 0.000000 2.875036
C) 0.000000 6.687542
D) 0.000000 12.187494
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 10.000000 0.656229 INFINITY
X2 9.000000 7.000176 0.999960
X3 12.000000 43.003990 0.636373
X4 11.000000 0.875007 INFINITY
X5 14.000000 3.500125 1.954540
X6 13.000000 2.687475 INFINITY
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
A 0.000000 0.000000 0.000000
B 0.000000 0.000000 0.000000
C 0.000000 0.000000 0.000000
D 1.000000 INFINITY 1.000000
Verwendet habe ich dazu eine Probeversion von LINDO, guckst Du hier: ![[]](/images/popup.gif) www.lindo.com
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:44 Mi 16.05.2007 | | Autor: | Simple84 |
Hallo,
danke für die Bemühungen ,
ich habe mir das Problem auch noch einmal angeschaut. Das [mm] x_4 [/mm] zusätzlich ist natürlich richtig. Durch einen Zufall ist mir aufgefallen, dass bei meinem Problem, die oberen drei NB linear abhängig sind. Wenn ich eine weglasse, kommen auch einige Java applets mit Hilfe der 2 - Phasenmethode zum richitgen Ergebis. (äquivalent zu deinem ).
Gruß
|
|
|
|
