Optimierungsproblem Polyeder < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:10 So 18.11.2012 | | Autor: | Sam90 |
| Aufgabe | Es seien das Polyeder P = $ [mm] \{x \in \IR^{3}|Ax \le b, x \ge 0\} [/mm] $ durch
$A [mm] =\pmat{ 6 & 2 & 4 \\ 0 & 3 & 1 }, [/mm] $ $b = [mm] \vektor{12 \\ 15} [/mm] $
sowie das lineare Optimierungsproblem LP durch
$ [mm] max\{c^{T} x | x \in P\} [/mm] $ für $ [mm] c^{T} [/mm] = (3,1,1)$
gegeben.
(a) Bringen Sie die kanonische Form von LP auf die Normalform.
(b) Bestimmen Sie alle Basen des Gleichungssystems der Normalform.
(c) Welche der Basislösungen sind Ecken von P, welche nicht?
(d) Gibt es entartete Basislösungen?
(e) Berechnen Sie mit Hilfe von (c) alle optimalen Lösungen der Optimierungsaufgabe LP. |
Hey! Da sich leider niemand gefunden hat, der meine Frage während des Fälligkeitszeitraumes beantworten konnte, hier nochmal meine Frage ;)
Mein Lösungsansatz sieht so aus:
(a) max $ [mm] 3x_{1} [/mm] $ + $ [mm] x_{2} [/mm] $ + $ [mm] x_{3} [/mm] $
unter $ [mm] 6x_{1} [/mm] $ + $ [mm] 2x_{2} [/mm] $ + $ [mm] 4x_{3} \le12 [/mm] $
$ [mm] 3x_{2} [/mm] $ + $ [mm] x_{3} \le15 [/mm] $
$ [mm] x_{1}, x_{2}, x_{3} \ge0 [/mm] $
Bei (b) gehts dann schon los mit meinen Problemen. Ich hab das mal in einen Simplexrechner eingegeben und kann damit nicht viel anfangen... Ich versuche das mal hier so gut wie möglich darzustellen:
$ [mm] \begin{bmatrix} . & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & . \\ x_{4} & 6 & 2 & 4 & 1 & . & 12 \\ x_{5} & 0 & 3 & 1 & . & 1 & 15 \\ F & -3 & -1 & -1 & 0 & 0 & . \end{bmatrix} [/mm] $
$ [mm] \begin{bmatrix} . & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & . \\ x_{1} & 1 & \bruch{1}{3} & \bruch{2}{3} & \bruch{1}{6} & 0 & 2 \\ x_{5} & 0 & 3 & 1 & 0 & 1 & 15 \\ F & 0 & 0 & 1 & 0,5 & 0 & 6 \end{bmatrix} [/mm] $
optimale Lösung: $ [mm] x_{1}=2 [/mm] $
Zielfunktionswert: 6
(Die Punkte sind leere Stellen)
Irgendwie weiß ich nicht, ob das richtig ist und außerdem bringt mich das auch nicht weiter. Wie löse ich denn solche Aufgaben? Hilfe wäre super.
LG Olli
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:23 Mo 19.11.2012 | | Autor: | Stoecki |
hallo
> Es seien das Polyeder P = [mm]\{x \in \IR^{3}|Ax \le b, x \ge 0\}[/mm]
> durch
> [mm]A =\pmat{ 6 & 2 & 4 \\ 0 & 3 & 1 },[/mm] [mm]b = \vektor{12 \\ 15}[/mm]
>
> sowie das lineare Optimierungsproblem LP durch
> [mm]max\{c^{T} x | x \in P\}[/mm] für [mm]c^{T} = (3,1,1)[/mm]
> gegeben.
> (a) Bringen Sie die kanonische Form von LP auf die
> Normalform.
> (b) Bestimmen Sie alle Basen des Gleichungssystems der
> Normalform.
> (c) Welche der Basislösungen sind Ecken von P, welche
> nicht?
> (d) Gibt es entartete Basislösungen?
> (e) Berechnen Sie mit Hilfe von (c) alle optimalen
> Lösungen der Optimierungsaufgabe LP.
> Hey! Da sich leider niemand gefunden hat, der meine Frage
> während des Fälligkeitszeitraumes beantworten konnte,
> hier nochmal meine Frage ;)
>
> Mein Lösungsansatz sieht so aus:
>
> (a) max [mm]3x_{1}[/mm] + [mm]x_{2}[/mm] + [mm]x_{3}[/mm]
> unter [mm]6x_{1}[/mm] + [mm]2x_{2}[/mm] + [mm]4x_{3} \le12[/mm]
> [mm]3x_{2}[/mm] + [mm]x_{3} \le15[/mm]
>
> [mm]x_{1}, x_{2}, x_{3} \ge0[/mm]
>
> Bei (b) gehts dann schon los mit meinen Problemen. Ich hab
> das mal in einen Simplexrechner eingegeben und kann damit
> nicht viel anfangen... Ich versuche das mal hier so gut wie
> möglich darzustellen:
>
> [mm]\begin{bmatrix} . & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & . \\ x_{4} & 6 & 2 & 4 & 1 & . & 12 \\ x_{5} & 0 & 3 & 1 & . & 1 & 15 \\ F & -3 & -1 & -1 & 0 & 0 & . \end{bmatrix}[/mm]
>
> [mm]\begin{bmatrix} . & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & . \\ x_{1} & 1 & \bruch{1}{3} & \bruch{2}{3} & \bruch{1}{6} & 0 & 2 \\ x_{5} & 0 & 3 & 1 & 0 & 1 & 15 \\ F & 0 & 0 & 1 & 0,5 & 0 & 6 \end{bmatrix}[/mm]
>
> optimale Lösung: [mm]x_{1}=2[/mm]
> Zielfunktionswert: 6
> (Die Punkte sind leere Stellen)
>
> Irgendwie weiß ich nicht, ob das richtig ist und außerdem
> bringt mich das auch nicht weiter. Wie löse ich denn
> solche Aufgaben? Hilfe wäre super.
>
in deiner F zeile stehen die reduzierten kosten des problems. damit eine optimallösung vorliegt, müssen alle reduzierten kosten nichtnegativ sein. also musst du diese durch elementare zeilenoperationen umändern.das geht allerdings nicht beliebig. hierzu führst du in jedem schritt einen sogenannten basistausch durch. es muss also in den beiden zeilen darüber jeweils immer eine teilmatrix existieren, die durch vertauschen von spalten zu einer basismatrix wird.
![[]](/images/popup.gif) Hier ist noch ein link zu einem skript, dass ich ganz gut finde. dort ist ein beospiel schritt für schritt durchgerechnet und graphisch dargestellt.
> LG Olli
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
gruß bernhard
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:59 Mo 19.11.2012 | | Autor: | Sam90 |
Danke für deine Antwort.
> in deiner F zeile stehen die reduzierten kosten des
> problems. damit eine optimallösung vorliegt, müssen alle
> reduzierten kosten nichtnegativ sein. also musst du diese
> durch elementare zeilenoperationen umändern.das geht
> allerdings nicht beliebig. hierzu führst du in jedem
> schritt einen sogenannten basistausch durch. es muss also
> in den beiden zeilen darüber jeweils immer eine teilmatrix
> existieren, die durch vertauschen von spalten zu einer
> basismatrix wird.
Die reduzierten Kosten sind ja hier in diesem Fall nichtnegativ. Auch, wenn ich es per Hand nachrechne, komme ich auf [mm] x_{1}=2 [/mm] gleich nach dem ersten Schritt des Simplexverfahrens. Somit habe ich doch aber nur eine Baislösung bzw. die optimale Lösung. Was sollen dann also die Aufgabenteile (b) - (d)? Oder verstehe ich da was falsch?
>
> Hier
> ist noch ein link zu einem skript, dass ich ganz gut finde.
> dort ist ein beospiel schritt für schritt durchgerechnet
> und graphisch dargestellt.
Danke für den Link.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Mi 21.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
