Primales in duales Problem

Neue Frage »

18.11.2009, 16:25	ThLu	Auf diesen Beitrag antworten »
Primales in duales Problem Hi ihr Experten, meine (Teil-)Aufgabe lautet: Gegeben sei das folgende lineare Optimierungsproblem: Maximiere $\begin{eqnarray} F(x) = 6x_1 + 4x_2 \end{eqnarray}$ unter den Nebenbedingungen: $\begin{eqnarray} x_1 + 2x_2 \leq 8 \end{eqnarray}$ $\begin{eqnarray} 3x_1 + x_2 \leq 9 \end{eqnarray}$ $\begin{eqnarray} x_1, x_2 ~\geq 0 \end{eqnarray}$ a) Wie lautet das zugehörige duale Problem? Ich habe im Internet (weil auf den Aufzeichnungen von meinem Prof ist es für mein Verständnis schlecht beschrieben) die Umformungsregeln gesucht und bin auf folgenden Ansatz gekommen: Minimiere $\begin{eqnarray} F(x) = 8u_1 + 9u_2 \end{eqnarray}$ unter den Nebenbedingungen: $\begin{eqnarray} u_1 + 3u_2 ~\geq 6 \end{eqnarray}$ $\begin{eqnarray} 2u_1 + u_2 ~\geq 4 \end{eqnarray}$ $\begin{eqnarray} u_1, u_2 ~\geq 0 \end{eqnarray}$ Ich habe aber überhaupt keine Ahnung, ob das stimmt. Außerdem verstehe ich nicht genau, was ich überhaupt mache. Ich versuche einfach nur die Formeln anzuwenden. Ich hoffe ihr könnt mir helfen. Beste Grüße, Thomas.
18.11.2009, 21:39	Mystic	Auf diesen Beitrag antworten »
Ja, das duale Problem ist korrekt formuliert... Wenn du eines der beiden Probleme mit dem Simplexverfahren löst, hast du gewissermaßen automatisch das duale Problem gleich mitgelöst... Du kannst z.B. im Falle der eindeutigen Lösbarkeit in den Spalten der jeweiligen Schlupfvariablen und in der Zeile der Zielfunktion die Lösungen für die Nichtschlupfvariablen des jeweils dualen Problems (in genau der durch die Indizierung vorgegebenen Reihenfolge!) ablesen und auch der optimale Wert der Zielfunktion ist für beide Probleme der gleiche...
19.11.2009, 15:09	ThLu	Auf diesen Beitrag antworten »
jetzt kommt da noch ein b) und ein c) Teil. b) Formulieren Sie das zugehörige Problem als Maximierungsproblem mit $\begin{eqnarray} \leq \end{eqnarray}$ - Nebenbedingungen und berechnen Sie mit dem dualen Simplex-Algorithmus eine Optimallösung. c) Bestimmen Sie anhand des Optimaltableaus des dualen Problems die Optimallösung des primalen Problems. zu der b) habe ich: Maximiere $\begin{eqnarray} F(x) = - 8u_1 - 9u_2 \end{eqnarray}$ unter den Nebenbedingungen: $\begin{eqnarray} - u_1 - 3u_2 \leq - 6 \end{eqnarray}$ $\begin{eqnarray} - 2u_1 - u_2 \leq - 4 \end{eqnarray}$ $\begin{eqnarray} u_1, u_2 ~\geq 0 \end{eqnarray}$ Wenn ich das jetzt mit dem dualen Simplex-Algorithmus lösen möchte bekomme ich keine Lösung, kann mir da jemand weiterhelfen?
16.01.2010, 14:55	MoinsenIII	Auf diesen Beitrag antworten »
ja das würde ich auch gerne wissen. Wie würde man hier jetzt vorgehen. muss man den "normalen" simplex anwenden ?? gruß Moinsen
17.01.2010, 17:30	MoinsenIII	Auf diesen Beitrag antworten »
weiß da denn niemand warum da keine lösung rauskommt : ( es ist wirklich dringend! gruß M.
01.02.2011, 19:07	hellopaplo	Auf diesen Beitrag antworten »
dual sobald die rechte seite in deinem tableau nichtnegativ ist kannst du primalen simplex anwenden
Anzeige

21.09.2011, 11:35	Hansfranz	Auf diesen Beitrag antworten »
Hey soweit ich das weiß muss das Problem in standardform sein, um den Simplex anwenden zu können. Also: min cTx s.t. Ax = b x >= 0 versuchs dann mal
11.10.2011, 22:37	Kunieberth	Auf diesen Beitrag antworten »
Also man kann ja nur maximieren. Ich hole mir dann wieder das Ausgangstableau und schreibe Maximiere F(x) = 6x1 + 4x2 unter den Nebenbedingungen: x1 + 2x2 + y1 = 8 3x1 + x2 + y2 = 9 x1, x2, y1, y2 >=0 Dann sollte x1 = 2 und x2 = 3 rauskommen Grüße Kunie
20.02.2012, 10:53	Twanger	Auf diesen Beitrag antworten »
Mit dem Simplex kann man nur Maximierungsprobleme lösen (LP2). Hat man ein Minimierungsproblem, kann man das Lösen, indem man die Zielfunktion mit -1 multipliziert, dadurch ändern sich alle Vorzeichen und natürlich auch das MIN in ein MAX, die Nebenbedingungen müssen natrlich dann auch eine <= Bedingung haben. Danach kann man es mit dem Simplex rechnen.

Neue Frage »

Antworten »

Primales in duales Problem

Verwandte Themen