Basislösung < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei [mm] \overline{x} [/mm] eine zulässige Basislösung eines Optimierungsproblems mit der zulässigen Menge X= {x [mm] \in \IR^{n}:Ax [/mm] = b, [mm] x\ge [/mm] 0} mit A [mm] \in \IR^{m\times n}, [/mm] b [mm] \in \IR^{m} [/mm] und Rang(A) = m < n. Geben sie ein c [mm] \in \IR^{n} [/mm] so an, dass [mm] \overline{x} [/mm] die einzige Lösung des Problems
min [mm] c^T [/mm] x
s.t. Ax=b
[mm] x\ge [/mm] 0
ist und weisen Sie die Eigenschaften nach. |
Ich weiß nicht, wie ich mit dieser Aufgabe beginnen kann. Wollte fragen, ob mir jemand dabei helfen könnte?
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:36 Mi 23.11.2011 | | Autor: | Stoecki |
habt ihr euch schon mit dem simplexalgorithmus beschäftigt? in dem wird der zielfunktionsvektor durch elementare zeilenumformungen manipuliert. sei hierbei [mm] \overline{x} [/mm] deine Basislösung. dann gibt es eine mxm- Matrix [mm] A_{\overline{x}} [/mm] mit [mm] A_{\overline{x}}*\overline{x} [/mm] = b und x [mm] \ge [/mm] 0, wobei x hier alle einträge von x sind.
damit [mm] \overline{x} [/mm] optimal ist, muss nun noch folgendes gelten:
sei [mm] \overline{c} [/mm] := [mm] c-A^{T}*(A_{\overline{x}}^{-1})*c_{\overline{x}} (A_{\overline{x}} [/mm] muss also invertierbar sein, was sie jedoch ist, da [mm] \overline{x} [/mm] basislösung ist)
dabei müssen die komponenten von [mm] \overline{c}, [/mm] die zum basisteil gehören null sein und die restlichen großer gleich null, damit diese ecke optimal ist. damit sie eine eindeutige lösung ist, müssen die komponenten des nichtbasisteils echt größer null sein.
näheres hierzu findest du auch ![[]](/images/popup.gif) hier.
gruß bernhard
|
|
|
|
