Lineare Optimierung mit dualen Problem

Question

Aufgabe:

Gegeben sei das folgende Problem

Minimiere: Z = 10y₁ + 30y₂ + 18y₃

unter den Nebenbedingungen:

1y₁ + 1y₂ + 1y₃ ≥ 12 
1y₁ + 6y₂ + 3y₃ ≥ 15

1. Erstellen Sie für das oben aufgeführte Problem das duale.
2. Lösen Sie das duale Problem.
3. Leiten Sie aus der Lösung des dualen Problems die Lösung des ursprüng-
lichen Problems her

Problem/Ansatz:

ich weiß leider überhaupt nicht wie ich an diese Aufgabe rangehen soll.

Könnte mir jemand die Vorgehensweise erklären? Eine solche Aufgabe haben wir in unserer Vorlesung nie besprochen und auch google hilft leider nicht weiter.

Comments

in unserer Vorlesung nie besprochen und auch google hilft leider nicht weiter.

Ich könnte mir vorstellen, dass es in Lehranstalten wo vorgelesen wird, neben Google auch Bücher gibt. Oder Online-Skripten? Denn woraus sollte sonst vorgelesen worden sein in der Vorlesung?

Professor kommt ja von öffentlich vorlesen (franz. "professer"), sich bekennen (Profess ablegen, darum tragen sie manchmal seltsame Gewänder), lat. profiteor (darum kriegen sie dafür Geld).

---

Das stimmt. Durch die habe ich mich auch schon gewälzt, werde aber einfach nicht schlau aus den Ausführungen und habe auch nirgends eine solche Aufgabe gefunden. Wir saßen gestern zu 4 fast 8 Stunden an dieser Aufgabe und sind nicht weitergekommen. Heute das gleiche Bild...

---

Ich verstehe. Wenn man in 8 Stunden nichts dazu im Buch findet, dann steht ziemlich sicher nichts dazu im Buch. Vielleicht war es das falsche Buch. Es dürfte einige Zeit dauern, bis jemand die Muße findet, diese Frage in der gebotenen Vollständigkeit zu beantworten.

Answer 1

Ich hab hier einen Artikel zum Thema - guckst Du?

Die Daten im Tableau

$\small \left(\begin{array}{rrrr}1&1&1&12\\1&6&3&15\\10&30&18&0\\\end{array}\right)$

und fürs Duale Programm transponiert und mit Schlupfvariablen versehen, das StartTableau

$\small \left(\begin{array}{rrrrrr}1&1&1&0&0&10\\1&6&0&1&0&30\\1&3&0&0&1&18\\-12&-15&0&0&0&0\\\end{array}\right)$

Die Zielfunktionszeile ist bei meinem Algorithmus negativ und stoppt wenn alle Koeff positiv

Pivotspalte 2 ===>  b/spalte2 = {10, 5, 6} Pivotzeile 2

$\small \left(\begin{array}{rrrrrr}0.833&0&1&-0.167&0&5\\0.167&1&0&0.167&0&5\\0.5&0&0&-0.5&1&3\\-9.5&0&0&2.5&0&75\\\end{array}\right)$

Pivotspalte 1 ===> b/spalte1 = {6, 30, 6} Pivotzeile 1

$\small \left(\begin{array}{rrrrrr}1&0&1.2&-0.2&0&6\\0&1&-0.2&0.2&0&4\\0&0&-0.6&-0.4&1&-40.143\\0&0&\textcolor{red}{11.4_{y_1}}&\textcolor{red}{0.6_{y_2}}&\textcolor{red}{0_{y_3}}&\textcolor{red}{132_{min}}\\\end{array}\right)$

Was man für eine ursprüngliche Lösung herleiten soll erschließt sich mir nicht....

Comments

Vielen Dank für die Antwort! Das Aufstellen der Matrix und das Umformen habe ich jetzt verstanden.

Nur noch eine Frage: Wie bestimmt man die y-Werte aus dem letzten Tableau das verstehe ich noch nicht ganz wieso genau diese verwendet werden?

---

Hast Du meinen Artikel angeschaut?

PivotSpalte und Pivotzeile is klar? ===> Pivot

die Pivotzeile wird durch den Pivot dividiert (Pivot ist dann 1) und mit entsprechenden Vielfachen zu allen anderen addiert um in der Pivotspalte Nullen zu erzeugen

==> sieht man aber an den vorgerechneten Beispielen, hat was mit dem Gaußalgorithmus !

Fehlt da was, von wegen ursprüngliche Lösung?