Optimierungsproblem

19.05.2007, 11:01

Sunwater

Optimierungsproblem

Hi...

ich solle die folgende Aufgabe als lineare Optimierungsaufgabe formulieren (d.h. mit Zielfunktion über einem zulässigen Bereich) und die duale Aufgabe formulieren. Als Hinweis ist gegeben, dass eine zusätzliche Variable eingeführt werden kann. Die Aufgabe die als Lineares Optimierungsproblem formuliert werden soll:

$\begin{eqnarray*} \underset{1 \leq i \leq n }{ \max} \left\{ \sum_{j=1}^n a_{ij}x_j \right\} \rightarrow \underset{x: \sum_{j=1}^n x_j = 1, x_1,...,x_n \geq 0} {\operatorname{Min!}} \end{eqnarray*}$

jetzt wollte ich mir das erstmal im Fall n=2 verdeutlichen mit einer Beispielmatrix:

$\begin{eqnarray*} A = \begin{pmatrix} 2 & 4 \\ 1 & 5 \end{pmatrix} \end{eqnarray*}$

die Aufgabe lautet jetzt über dem Bereich:

$\begin{eqnarray*} x_1 + x_2 = 1, x_1,x_2 \geq 0 \end{eqnarray*}$

eine Funktion zu minimieren... - aber welche?

was ist denn $\begin{eqnarray*} \max \{(2x_1 + 4x_2),( x_1 + 5x_2)\} \end{eqnarray*}$ ???

19.05.2007, 11:54

WebFritzi

Auf diesen Beitrag antworten »

RE: Optimierungsproblem
Na,

$\begin{eqnarray*} f(x_1,x_2) = \max \{(2x_1 + 4x_2),( x_1 + 5x_2)\}. \end{eqnarray*}$

Das ist doch eine Funktion, oder?

19.05.2007, 12:53

Sunwater

Auf diesen Beitrag antworten »

stimmt *g* - auf die absurde Idee, bin ich gar nicht gekommen Augenzwinkern

19.05.2007, 14:35

WebFritzi

Auf diesen Beitrag antworten »

Aber wie man jetzt eine dritte Variable einführen soll, weiß ich ehrlich gesagt auch nicht.

21.05.2007, 22:09

llllllllllllll

Auf diesen Beitrag antworten »

warum ist x1+x2=1?

22.05.2007, 08:09

Dual Space

Auf diesen Beitrag antworten »

RE: Optimierungsproblem

Zitat:

Original von Sunwater
die Aufgabe lautet jetzt über dem Bereich:

$\begin{eqnarray*} x_1 + x_2 = 1, x_1,x_2 \geq 0 \end{eqnarray*}$

Ich vermute du meinst mit der dritten Variable eine sogenannte Schlupfvariable. Diese wird aber nur bei Ungleichungsrestriktionen benötigt. Also z.B. falls du $\begin{eqnarray*} x_1+x_2\leq 1 \end{eqnarray*}$ forderst, kannst du anstelle dessen auch $\begin{eqnarray*} x_1+x_2+x_S=1 \end{eqnarray*}$ mit einem $\begin{eqnarray*} x_S\geq 0 \end{eqnarray*}$ betrachten.

23.05.2007, 23:10

Sunwater

Auf diesen Beitrag antworten »

ok - für alle, die die Lösung interessiert:

es ist eigentlich denkbar einfach, aber manchmal denkt man einfach über zu viele Ecken. Das Problem kann man wie folgt formulieren:

$\begin{eqnarray*} t \rightarrow \min ! \end{eqnarray*}$

$\begin{eqnarray*} P = \left\{ \binom x t \in \mathbb R^{n+1} \vert \sum_{j=1}^n a_{ij}x_j \leq t, \sum_{j=1}^nx_j = 1, x_j \geq 0 ~~\forall j=1,...,n \right \} \end{eqnarray*}$

Also t soll über dem Polyeder P minimiert werden. t ist gleichzeitig auch die Variable, deren Einführung helfen sollte...

Neue Frage »

Antworten »

Optimierungsproblem

Verwandte Themen