Alternative Modellierung eines Optimierungsproblems

02.11.2012, 19:03	wdposchmann	Auf diesen Beitrag antworten »
Alternative Modellierung eines Optimierungsproblems Hi, ich habe zum Thema Optimierung folgende Frage zu bearbeiten: Es seien $\begin{eqnarray} A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m \mbox{ und } c \in \mathbb{R}^n \end{eqnarray}$ gegeben. Zeigen Sie: Jedes binär-lineare Optimierungsproblem, d.h. jedes Problem der Form $\begin{eqnarray} \min_{x \in \mathbb{R}^n} c^Tx \end{eqnarray}$ unter den Nebenbedingungen $\begin{eqnarray} Ax \leq b, \end{eqnarray}$ $\begin{eqnarray} x \in \left\{0,1\right\}^n \end{eqnarray}$ kann als nichtlineares Optimierungsproblem mit stetigen Variablen (d.h. ohne 0/1-Bedingung) modelliert werden. Meine Ideen: Bisher leider keine wirklichen. In der Vorlesung haben wir bisher kennengelernt, dass man jede vorzeichenfreie Variable x durch zwei neue rein positive Variablen definiert, so dass gilt $\begin{eqnarray} x = x^+ - x^- \end{eqnarray}$ , wobei x die ursprüngliche und x^+ bzw. x^- die neuen Variablen sind. Allerdings hilft mir das hier nicht weiter. In einer zweiten Teilaufgabe sollen wir das Gleiche nochmal zeigen, nur dass dann gefordert ist, dass die Ganzzahligkeitsbedingung vernachlässigt werden kann. Ich hoffe ihr habt einige Tipps für mich. Danke schonmal und viele Grüße!
03.11.2012, 14:53	Mystic	Auf diesen Beitrag antworten »
RE: Alternative Modellierung eines Optimierungsproblems Naja, ich rate mal, dass man mit $\begin{eqnarray} e=(1,1,\ldots,1)^T \end{eqnarray}$ das auch in Form der Nebenbedingung $\begin{eqnarray} x(e-x)=0 \end{eqnarray}$ schreiben kann...
04.11.2012, 19:43	wdposchmann	Auf diesen Beitrag antworten »
RE: Alternative Modellierung eines Optimierungsproblems Hey Mystic, vielen Dank, damit hat es problemlos geklappt. Ich stand einfach auf dem Schlauch Viele Grüße
04.11.2012, 23:14	Mystic	Auf diesen Beitrag antworten »
RE: Alternative Modellierung eines Optimierungsproblems Ich hab's nur leider sehr mißverständlich angeschrieben... Ich hoffe, du hast es so aufgefasst, wie es gemeint war, nämlich als die n Nebenbedingungen $\begin{eqnarray} x_k(1-x_k)=0, \quad k=1,...,n \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »