Lineare Optimierung < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:46 Mi 11.01.2012 | | Autor: | Klemme |
| Aufgabe | Gegeben Sei die Lineare Optimierungsaufgabe
[mm] $\IZ [/mm] = 3 [mm] x_1 [/mm] - 2 [mm] x_2 [/mm] + 3 [mm] x_3 \to [/mm] max!$
[mm] $\begin{matrix}
x_1 & + x_2 & & + x_4 & & & = 10 \\
& + x_2 & + x_3 & & + x_5 & & = 20 \\
x_1 & & + x_3 & & & -x_6 & = 15 \\
& & & & & x & \ge 0.\\
\end{matrix}$
[/mm]
Es ist P = (10,0,5,0,15,0) ein Eckpunkt des zugehörigen zulässigen Bereichs, dem eine Basislösung eindeutig zugeordnet ist.
a) Bestimmen Sie die zugehörige kanonische Form des linearen Gleichungssystems.
b) Berechnen Sie die Optimallösung. |
Hallo,
ich hoffe, dass mir jemand einen Tipp geben kann, wie genau ich mit dieser Aufgabe, vor allem Teil b umgehen soll.
zu a)
Das LGS als Matrix:
[mm] $\pmat{ 1 & 1 & 0 & 1 & 0 & 0 & |10 \\
0 & 1 & 1 & 0 & 1 & 0 & |20 \\
1 & 0 & 1 & 0 & 0 & -1 & |15}$
[/mm]
Nach Abziehen der 1. von der 3. Zeile und Addieren der 2. zur 3. Zeile habe ich die kanonische Form:
[mm] $\pmat{ 1 & 1 & 0 & 1 & 0 & 0 & |10 \\
0 & 1 & 1 & 0 & 1 & 0 & |20\\
0 & 0 & 2 & -1 & 0 & -1 & |15}$
[/mm]
zu b) Nun frage ich mich, was genau ich mit dem vorgegebenen Eckpunkt anfangen soll. Müssen jetzt [mm] $x_1, x_3$ [/mm] und [mm] $x_5$ [/mm] als Basisvariablen gewählt werden? Wenn ja, hätten diese bei Teilaufgabe a) bereits die Einheitsmatrix bilden sollen?
Wär nett wenn jemand nen guten Tipp hätte, wie ich da am besten anfange. :)
lg
Klemme
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 22:57 Do 12.01.2012 | | Autor: | Klemme |
Hallo liebes Forum,
weiß vielleicht jemand, ob ich Teilaufgabe a überhaupt richtig gelöst habe. Wär super, wenn doch noch jemand etwas zu dieser Aufgabenstellung sagen könnte.
Danke schon mal.
lg
Klemme
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 So 15.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Fr 13.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:35 Mo 16.01.2012 | | Autor: | Klemme |
Hallo,
falls irgendjemand mir heelfen kann, wäre ich wirklich sehr an einem Tipp oder Ansatz interessiert.
lg
Klemme
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:09 Di 17.01.2012 | | Autor: | Stoecki |
hallo klemme,
als erstes solltest du mittels gaus eine basislösung erzeugen. ich gehe mal davon aus, das das bei euch als kanionische form definiert ist. bei einer basislösung sind in deinem gleichungssystem 3 spalten vorhanden, in denen jeweils in nur einer zeile eine 1 und sonst nur nullen stehen. dabei müssen die einsen jeweils in verschiedenen spalten stehen (durch umsortieren der spalten musst du also die einheitsmatrix erhalten können). dann gilt: setzt du die variablen, die nicht zu diesen spalten gehören auf 0 erhälst du eine eindeutige lösung bzgl der restlichen variablen. ist diese lösung nicht-negativ, ist diese zulässig.
zum aufgabenteil b solltest du dich entweder in den simplex-algorithmus einlesen, oder die sog KKT-bedingungen (karush-kuhn-tacker) aufstellen und die mit dem fourier-motzkin-algorithmus lösen (simplex geht i.d.r. deutlich schneller). infos dazu findest du z.b. hier:
![[]](/images/popup.gif) OR-skript
|
|
|
|
