Simplex Verfahren / lineare Optimierung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
habe Fragen zu folgender Aufgabe:
Es soll die Gewinnfunktion [mm] G(x_1,x_2) [/mm] = [mm] x_1+2x_2
[/mm]
unter den Nebenbedingungen
[mm] 2x_1+x_2\le60
[/mm]
[mm] x_1+x_2\le48
[/mm]
[mm] x_2\le40
[/mm]
und den Nichtnegativitätsbedingungen maximiert werde.
Lösen Sie das Problem graphisch. Markieren Sie das Gewinnmaximum!
Zunächst mal die Nichtnegativitätsbedingung: [mm] x_1,x_2\le0
[/mm]
Punkte für x und y bestimmen:
[mm] 2x_1+x_2\le60
[/mm]
[mm] x_2 [/mm] gleich Null setzen;x_1gleich Null setzen
[mm] x_1=30;x_2=60
[/mm]
[mm] x_1+x_2\le48
[/mm]
[mm] x_1=48,x_2=48
[/mm]
Hier im Forum kann man das ja schlecht graphisch machen, aber diese beiden Geraden würde ich im Koordinatensystem einzeichen, um den zulässigen Bereich zu begrenzen.
Wie erhalten ich die Punkte der Gewinnfunktion und der dritten Nebenbedingung ? Wieviele Geraden kann ich insgesamt mit diesen Informationen erhalten? Wo ist das G-Maximum?
Wie würde das Ausganstableau für diesen Simplexalgorithmus aussehen?
Vielen Dank im Voraus für eine Antwort.
Viele Grüße
Sabrina
Ich habe diese Frage in keinem weiteren Forum gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:41 Do 05.08.2004 | | Autor: | thoomas |
Hallo Sabrina,
möchte mich zunächst auf das Anfangstableau des Simplexalgorithmis beschränken. Zunächst muss es heißen: x1>=0 und x2>=0 (Nichtnegativität: wahrscheinlich nur ein Scheibfehler von dir).
G=x0=x1 + x2 - > x0 - x1 - x2 =0
2x1+x2<=60 -> 2x1+x2+ x3 =60
x1+x2<=48 -> x1+ x2 + x4 =48
x2<=40 -> x2 +x5 =40
mit nichtnegativen Schlupfvariablen x3,x4,x5.
Dies führt zum Tableau
x0 x1 x2 x3 x4 x5 RS
1 -1 -1 0 0 0 0
0 2 1 1 0 0 60
0 1 1 0 1 0 48
0 0 1 0 0 1 40
Wie du wahrscheinlich weißt, müssen in der 0-ten Zeile die Koeffizienten nichtnegativ sein. Wenn du das mit Hilfe des Algorithmus erreicht hast, kannst du das Maximum als RS in der nullten Zeile ablesen.
Checke das Tableau bitte auf evt. Fehler von mir und und schau mal wie weit du kommst.
Viele Grüße
Thomas
(Mein Browser ist zur Zeit nicht gut drauf und arbeitet leider nicht mit den Formeln!!)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:01 Do 05.08.2004 | | Autor: | andreas |
hi Sabrina
noch eine kurze anmerkung zur graphischen lösungsvariante:
durch [mm] $x_2 \leq [/mm] 40$ erhälst du eine weitere bedingung. und zwar musst du in das koordinatensystem eine parallele zur [mm] $x_1$-achse [/mm] einzeichen, die die [mm] $x_2$-achse [/mm] beim wert 40 schneidet. das (unter dieser nebenbedingung) zulässige gebiet liegt dann unterhalb dieser geraden.
insgesamt solltets du dann 5 begrenzende geraden für ein gebiet erhalten haben (3 aus den nebenbedingungen und 2 aus den nichtnegativitätsbedingungen).
bei der gewinnfunktion kannst du erstamal den gewinn $g$ als reelle zahl annhemen, dann erhälst du:
[m] G(x_1, x_2) = x_1 + 2x_2 = g [/m],
da $G$ ja genau den gewinn beschreibt. dies kannst du nun folgendermaßen umformen:
[m] x_1 + 2x_2 = g \; \Longleftrightarrow \; 2x_2 = - x_1 + g \; \Longleftrightarrow \; x_2 = -\frac{1}{2}x_1 + \frac{g}{2} [/m]
die ist offensichtlich eine geradenschargleichung in der form [m] x_2 = mx_1 + c(g) [/m]. zeichen mal eine "beispielgerade" dieser schar ein. (z.b. für [m] g=0 [/m]). die anderen geraden dieser schar sind nun einfach parallel zu dieser "beispielgerade" und man sieht, dass [m] g [/m] maximal wird, wenn der schnittpunkt mit der [m] x_2 [/m]-achse am höchsten liegt. also probiere deine "beispielgerade" so nach "oben" zu verschieben, dass sie gerade noch einen punkt mit dem 'erlaubten' gebiet gemeinsam hat und lies dann den [m] x_2 [/m]-achsenabschnitt ab. das doppelte davon ist dann der maximale gewinn!
andreas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:04 Do 05.08.2004 | | Autor: | Sabrina04 |
Danke für die gut verständlichen Antworten auf meine Fragen.
|
|
|
|
