Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Lineare Optimierung - Rechenweg? Lösung vorhanden

Lineare Optimierung - Rechenweg? Lösung vorhanden

Universität / Fachhochschule

Finanzmathematik

Tags: Lineare Optimierung, Pivotelement, Simplex Algorithmus

senjaudikoepek aktiv_icon

00:34 Uhr, 18.01.2018

Die Aufgabe sowie die Lösung sind im Anhang.

Im Aufgabenblatt ist links das primale Programm und rechts das duale Programm.
Die Aufgabe ist die optimale Lösung für das duale Programm zu bestimmen.
Dazu soll ich die Standardform von I* bestimmen und danach den 2-Phasen-Simplexalgoriythmus anwenden.

Also soweit gegeben (siehe Anhang):

I*

min 720 y 1 + 1800 y 2 + 900 y 3

Nebenbedingungen:

y 1 + 5 y 2 + 3 y 3 \geq 2

2 y 1 + 4 y 2 + y 3 \geq 2,5

Nichtnegativitätsbedingung:

y 1, y 2, y 3 \geq 0

Die Standardform habe ich so angewendet:

I*

max - 720 y 1 - 1800 y 2 - 900 y 3

- y 1 - 5 y 2 - 3 y 3 \leq - 2

- 2 y 1 - 4 y 2 - y 3 \leq - 2,5

Nichtnegativitätsbedingung

y 1, y 2, y 3 \geq 0

Um aus der Ungleichung eine Gleichung zu machen muss ich noch Schlupfvariablen einsetzen.

- y 1 - 5 y 2 - 3 y 3 + y 4 = - 2

- 2 y 1 - 4 y 2 - y 3 + y 5 = - 2,5

Da die rechte Seite negativ ist, habe ich keine zulässige Lösung, wie ich das verstanden habe. Also muss ich das sogenannte "Hilfsprogramm"

(= y 0)

einsetzen.

y 0 - y 1 - 5 y 2 - 3 y 3 + y 4 = - 2

y 0 - 2 y 1 - 4 y 2 - y 3 + y 5 = - 2,5

So würde das Anfangstableau aussehen: siehe Anhang.
(Tippfehler bei

y 2 :

da steht

- 1900,

das müsste

- 900

sein)

Nach welchen Kriterien suche ich jetzt das Pivotelement? Die negativen Zahlen an der RHS verwirren mich.
Stimmt meine Vorgehensweise im allgemeinen überhaupt?

Danke.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Enano

13:57 Uhr, 18.01.2018

"Die negativen Zahlen an der RHS verwirren mich."

Wenn du die Zweiphasenmethode anwendest, so wie sie

z . B

. unter dem folgenden Link beschrieben ist, hast du in der Spalte RHS keine negativen Zahlen:

www.wiwiweb.de/operations-research/minimierungsprobleme/zweiphasenmethode/methode.html

senjaudikoepek aktiv_icon

19:50 Uhr, 18.01.2018

ok danke das hat weitergeholfen. Ich versteh des weiteren nicht den Zusammenhang der verschiedenen Simplexalgorithmen.
Es gibt den
- Primalen Simplex
- Dualen Simplex

- 2

Phasen Simplex
- Hilfsprogramm
- Dualität?/Duale Lineare Optimierung? wird transponiert?

Wie stehen die in Zusammenhang zueinander und woher weiß ich welche ich wann nutzen muss?
Bauen diese Verfahren aufeinander auf?

senjaudikoepek aktiv_icon

21:41 Uhr, 18.01.2018

Ich schaff es nicht diesen Link an meiner Aufgabe anzuwenden.
Im speziellen bleibe ich bei der Standardform hängen.

Bei der 2 Phasen Methode muss ich

\cdot (- 1)

rechnen damit aus

\geq \to \leq

wird.
Das führt aber dazu dass die rechte Seite negativ wird:

ZF:

- 700 y 1 - 1800 y 2 - 900 y 3

- y 1 - 5 y 2 - 3 y 3 \leq - 2

- 2 y 1 - 4 y 2 - y 3 \leq - 2,5

y 1, y 2, y 3 \geq 0

Hier komm ich nicht weiter? Ich kann aufgrund der negativen RHS kein Tableau anwenden ergo brauch ich auch keine Schlupfvariablen einzufügen. Ich versteh gar nicht wie ich die 2-Phasen-Methode an dieser Aufgabe anwenden kann.

Enano

02:42 Uhr, 19.01.2018

"Bei der 2 Phasen Methode muss ich ⋅(-1) rechnen damit aus ≥→≤ wird.
Das führt aber dazu dass die rechte Seite negativ wird:"

Um aus der Minimierungsaufgabe eine Maximierungsaufgabe zu erstellen, wird die Zielfunktion mit „-1“ multipliziert, aber nicht die

\geq

-Bedingungen.
Deshalb bleiben die rechten Seiten auch positiv.
Allerdings wird bei ≥-Restriktionen die Schlupfvariable mit einem Minus-Zeichen und Hilfsschlupfvariablen (künstliche Variablen), sowie eine sekundäre Zielfunktion (fiktive Zielfunktion) eingeführt.
Ist doch alles in dem von mir verlinkten Artikel - wie ich finde - sehr gut beschrieben.

Das Simplexverfahren ist eine rechnerische Lösungsmethode für allgemeine LO-Probleme.
Bei einem Standard - Maximum -Problem,

d . h

. wenn bei der Zielfunktion nach einem Maximum gesucht ist, alle Restriktionen vom "<=" - Typ und alle Seiten nichtnegativ sind, kannst du das Simplexverfahren direkt anwenden, weil es keine Schwierigkeiten bereitet, eine erste zulässige Basislösung zu erhalten.
Bei LO-Problemen mit ">=" - Restriktionen besteht das Problem aber darin, zunächst eine erste zulässige Basislösung zu finden, bevor auf die übliche Weise mit dem Simplexverfahren fortgefahren werden kann.Dazu eignet sich die Zweiphasenmethode.
Zu jedem linearen Maximierungsproblem gibt es ein korrespondierendes lineares Minimierungsproblem und umgekehrt.
Das Original-Problem wird primales LO-Problem (Primal) und das korrespondierende Problem duales LO-Problem (Dual) genannt.
Nach formalen Regeln kann aus einem primalen Problem ein duales Problem konstruiert werden.
Wird ein primales LO-Problem mit dem Simplexverfahren gelöst, so liefert das primale optimale Simplextableau auch die optilmale Lösung des korrespondierenden dualen Problems,

d . h

. für die optimale Lösung eines LO-Problems ist es unerheblich, welches der beiden Probleme , Primal oder Dual, mit Hilfe des Simplexverfahrens gelöst wird.
Wenn die Lösung des dualen Miinimumproblems mittels Zweiphasenmethode nicht vorgeschrieben wäre, könntest du deshalb anstatt des dualen Minimum-Problems das primale Standard-Maximum-Problem mit dem gleichen Ergebnis, aber weniger Rechenaufwand lösen.

senjaudikoepek aktiv_icon

00:29 Uhr, 20.01.2018

Ok ich glaube soweit habe ich jetzt alles verstanden und ich komme auch auf das richtige Ergebnis. Tausend Dank nochmals.

"Wenn die Lösung des dualen Miinimumproblems mittels Zweiphasenmethode nicht vorgeschrieben wäre, könntest du deshalb anstatt des dualen Minimum-Problems das primale Standard-Maximum-Problem mit dem gleichen Ergebnis, aber weniger Rechenaufwand lösen. "

Meinst du damit den Satz des komplementären Schlupfs? Angenommen ich habe die optimale Lösung vom primalen Problem ausgerechnet. Jetzt kann ich auf die optimalen Werte des dualen Problems schließen. Das Optimum (Rechte Seite bei der Zielfunktion im Tableau) bleibt dabei immer das selbe, oder kann das auch unterschiedlich sein?

Noch eine Frage:
Muss ich für die künstlichen Variablen eine Nichtnegativitätsbedingung formulieren?

Enano

14:34 Uhr, 20.01.2018

"Meinst du damit den Satz des komplementären Schlupfs?"

Ja,

u . a

. auch, als Teil der Dualitätssätze.

"Angenommen ich habe die optimale Lösung vom primalen Problem ausgerechnet. Jetzt kann ich auf die optimalen Werte des dualen Problems schließen.Das Optimum (Rechte Seite bei der Zielfunktion im Tableau) bleibt dabei immer das selbe, oder kann das auch unterschiedlich sein?"

Ja, genau. Die optimalen Zielfunktionswerte von Primal und Dual sind identisch,

d . h

.
bei deiner Aufgabe

M = m = 990

.
Die optimale Lösung des Dual ergibt sich aus den Werten der Zielfunktionszeile des primalen Optimaltableaus.

x_{1} = 120, x_{2} = 300

usw., die in dem primalen Optimaltableaus in der rechten Spalte (RHS) stehen, findest du in der Zielfunktionszeile des dualen Optimaltableaus wieder und die Werte die in der rechten Spalte des dualen Optimaltableaus stehen, findest du in der Zielfunktionszeile des primalen Optimaltableaus wieder.

"Muss ich für die künstlichen Variablen eine Nichtnegativitätsbedingung formulieren?"

Ja, die Hilfsschlupfvariablen oder künstlichen Variablen müssen ebenfalls die Nichtnegativitätsbedingungen erfüllen, also

z . B

k_{j} \geq 0

senjaudikoepek aktiv_icon

15:39 Uhr, 20.01.2018

Danke nochmals. :-)
Ich hab nur noch zwei offene Fragen auf dieser Plattform, ansonsten habe ich alles verstanden.

www.onlinemathe.de/forum/2-Phasen-Simplex-Algorithmus-Frage-zu-Pivotschritt
www.onlinemathe.de/forum/Ist-mein-Rechenweg-korrekt-komplementaerer-Schlupf

1410861

1410350

	Status: nicht eingeloggt	Noch nicht registriert?