Formulierung lineares Programm

18.04.2010, 11:59	Fynn	Auf diesen Beitrag antworten »
Formulierung lineares Programm Meine Frage: Guten Morgen Folgende Aufgabenstellung: $\begin{eqnarray} A \in \mathbb{R}^{m \times n} \end{eqnarray}$ und $\begin{eqnarray} b \in \mathbb{R}^m \end{eqnarray}$ sind gegeben. Ich soll nun lineare Programme für folgende zwei Probleme formulieren: $\begin{eqnarray} \min_{x \in \mathbb{R}^n} \\| Ax-b\\|_\infty \end{eqnarray}$ und $\begin{eqnarray} \min_{x \in \mathbb{R}^n} \\| Ax-b\\|_1 \end{eqnarray}$ Meine Ideen: Ich weiß. dass die 1-Norm die Summe der Beträge der Komponenten eines Vektors ist und dass die Maximumsnorm das betragsmäßig größte Eleement eines Vektors ist. Ich hab mit überlegt, dass der best case wohl Ax=b ist, denn da sind die beiden Minima jeweils 0. Also will man x wohl so wählen, dass Ax möglichst nahe an b herankommt. Allerdings ist mir wirklich schleierhaft, wie ich die beiden Normen in der Zielfunktion für das lineare Programm ausdrücken soll, denn Beträge dürfen da ja sicherlich nichtmehr drinsein. Kann mir da jemand auf die Sprünge helfen? Vergess ich irgendwas wichtiges?
20.04.2010, 11:30	Reksilat	Auf diesen Beitrag antworten »
RE: Formulierung lineares Programm Hi Fynn, Nein, Beträge dürfen da nicht drin sein, denn die Betragsfunktion ist nicht linear. Du wirst also noch mehr Variablen und auch ein paar Restriktionen benötigen, um das Problem zu lösen. Du willst ja Ausdrücke der Form $\begin{eqnarray} \left\|\sum_{j=1}^na_{ij}x_j-b_i\right\| \end{eqnarray}$ darstellen, also schreiben wir die Summe doch mal als (noch nicht unbedingt eindeutige) Differenz zweier nichtnegativer Zahlen: $\begin{eqnarray} \sum_{j=1}^na_{ij}x_j-b_i=y_i-z_i \end{eqnarray}$ , mit $\begin{eqnarray} y_i,z_i\geq 0 \end{eqnarray}$ . Wenn nun die Summe negativ ist und $\begin{eqnarray} y_i=0 \end{eqnarray}$ , so ist $\begin{eqnarray} \left\|\sum_{j=1}^na_{ij}x_j-b_i\right\|=z_i \end{eqnarray}$ . Ist die Summe dagegn nicht negativ und $\begin{eqnarray} z_i=0 \end{eqnarray}$ , so ist $\begin{eqnarray} \left\|\sum_{j=1}^na_{ij}x_j-b_i\right\|=y_i \end{eqnarray}$ . Somit ist $\begin{eqnarray} \left\|\sum_{j=1}^na_{ij}x_j-b_i\right\| \end{eqnarray}$ genau dann minimal, wenn $\begin{eqnarray} y_i+z_i \end{eqnarray}$ minimal wird. Diese Überlegungen sollten ausreichen, um zumindest für $\begin{eqnarray} \\|Ax-b\\|_1\to \min \end{eqnarray}$ die Restriktionen und die Zielfunktion zu formulieren. Der zweite Teil ist danach auch nicht mehr so schwer. Gruß, Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »