Optimale Lösung eines LUGS < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:20 Do 29.01.2009 | | Autor: | Uschel |
| Aufgabe | Seien A = [mm] \pmat{ -14 & 14 & 10 \\ 2 & 1 & 1 \\ -2 & 5 & 3 \\ -4 & 1 & 1 }
[/mm]
b = [mm] \pmat{ 9 \\ 3 \\ 5 \\ -3 } [/mm] und
[mm] \gamma [/mm] (x) = [mm] -x_{1} [/mm] - [mm] 2x_{3} [/mm] +1 für x = [mm] (x_{1} [/mm] , [mm] x_{2} [/mm] , [mm] x_{3} [/mm] )
Frage: Gibt es eine optimale Lösung für /gamma auf der Lösungsmenge
A*x [mm] \ge [/mm] b ? (Begründung!!)
(Hinweis: z.B. Satz 12.4. Zeigen Sie dazu, dass (1,1,1) eine Lösung von A*x [mm] \ge [/mm] b ist.) |
Hallo zusammen.
Wir haben diese Aufgabe vor kurzem in einer Übungsgruppe besprochen und ich konnte sie später trotzdem nicht ohne Hilfe lösen, weil mir einiges einfach noch unklar ist.
Als erstes haben wir den Punkt (1,1,1) untersucht (schließlich ist er ja extra angeben)
A * [mm] \vektor{1\\1\\1\\1} \ge [/mm] b
[mm] \vektor{10\\4\\6\\-2} \ge \vektor{9\\3\\5\\-3}
[/mm]
[mm] \vektor{10\\4\\6\\-2} [/mm] - [mm] \vektor{9\\3\\5\\-3} [/mm] = [mm] \vektor{1\\1\\1\\1}
[/mm]
[mm] \vektor{1\\1\\1\\1} \ge \vektor{0\\0\\0\\0}
[/mm]
Meine Frage hierzu, warum hört man nach [mm] \vektor{10\\4\\6\\-2} \ge \vektor{9\\3\\5\\-3} [/mm] nicht auf? Wozu sind die übrigen Schritte?
Als nächstes haben wir dann B erstellt, wobei wir nun den [mm] \vektor{1\\1\\1\\1} [/mm] als Kontrollspalte benutzen.
Es ergibt sich:
B: = [mm] \pmat{ -14 & 14 & 10 & 1\\ 2 & 1 & 1 & 1\\ -2 & 5 & 3 & 1\\ -4 & 1 & 1 & 1 \\ -1 & 0 & -2 & -2}
[/mm]
und die -2 unten rechts erhalten wir einfach dadruch, dass man die Werte aus der Kontrollspalte in die Gewinnfunktion einsetzt. Soweit hab ich Alles verstanden.
Aber wir wissen doch jetzt erst, dass dies EINE, aber vlt nicht die optimale Lösung ist oder verstehe ich das falsch?
Dann habe ich mir Satz 12.4 nochmal angeschaut, der besagt:
Sei u eine Lösung des linearen Ungleichungssystems A*x [mm] \ge [/mm] b mit mxn-Koeffizientenmatrix A. Sei [mm] \gamma [/mm] (x) = g0 + g * x die Gewinnfunktion und B = [mm] \pmat{ A & k \\ g & G} [/mm] die zu u gehörige Ausgangsmatrix.
Sei C eine Matrix, welche aus B durch zulässige Spaltenumformungen hervorgeht. Wenn C einen Spaltenvektor sj mit j [mm] \le [/mm] n hat, dessen Komponenten alle das gleiche Vorzeichen haben und dessen letzte
Komponente von Null verschieden ist, dann gelten folgende Aussagen:
a) Es gibt ein m [mm] \in F^{n} [/mm] mit [mm] \gamma [/mm] (m) > g0 und A*m [mm] \ge [/mm] 0
b) [mm] \gamma [/mm] ist auf der Lösungsmenge L von A*x ßge b nach oben unbeschränkt.
Versteh ich das jetzt richtig, dass ich versuchen soll Matrix C zu erzeugen (durch zuläsige Spaltenumformung) in der es einen Spaltenvektor geben soll der durchweg positiv ist und der letzte Eintrag echt positiv, also [mm] \ge [/mm] 0 sein soll?
Aber dann wäre nach b) doch gezeigt, dass es keine optimale Lösung gibt.
Vielleicht tue ich mir mit den ganzen Sätzen und Formeln auch nur unnötig schwer, deswegen würde ich mich über schnelle Hilfe anhand dieses Beispieles freuen.
Mit freundlichen Grüßen
Uschel
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Fr 06.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
