| |
| Autor |
 Simplexverfahren |
|
rocaflex
Junior 
Dabei seit: 10.02.2022
Mitteilungen: 5
 |  Themenstart: 2022-02-10
|
Hallo, habe ein Problem bei folgendem Minimierungsproblem:
https://matheplanet.com/matheplanet/nuke/html/uploads/b/55381_minimierung.PNG
Habe die Aufgabe Transponiert um ein Maximierungsproblem zu schaffen, komme aber nicht auf die Lösung.
https://matheplanet.com/matheplanet/nuke/html/uploads/b/55381_l_sung.PNG
Wie genau muss ich bei diesem Problem vorgehen?
|
 Profil
|
Goswin
Senior 
Dabei seit: 18.09.2008
Mitteilungen: 1792
Wohnort: Chile, Ulm
 | Beitrag No.1, eingetragen 2022-02-10
|
Hallo rocaflex,
willkommen auf Matroids Matheplaneten!
\quoteon(2022-02-10 12:49 - rocaflex im Themenstart)
https://matheplanet.com/matheplanet/nuke/html/uploads/b/55381_minimierung.PNG
Habe die Aufgabe Transponiert um ein Maximierungsproblem zu schaffen, komme aber nicht auf die Lösung. Wie genau muss ich bei diesem Problem vorgehen?
\quoteoff
So wie hier. (Geh nicht zu Wikipedia:Simplexverfahren, das ist ein fragwürdiges Sammelsurium wo du verwirrt wirst)
Der erste Schritt ist
\[
\begin{matrix}
z & = &(&~~~~0 &-~ 10x_1 &-~ 20x_2 &)~/~1
\\[2pt]
x_3 & = &(&-~ 12 &+~ ~1x_1 &+~ ~4x_2 &)~/~1
\\[2pt]
x_4 & = &(&-~ 18 &+~ ~6x_1 &+~ ~1x_2 &)~/~1
\\[2pt]
x_5 & = &(&-~ 10 &+~ ~2x_1 &+~ ~1x_2 &)~/~1
\\~
\end{matrix}
\\[4pt]
\max z, \qquad x_1\ge0,~ \ldots,~ x_5\ge0
\]
und die duale Aufgabe dazu ist
\[
\begin{matrix}
w & = &(&~~~~0 &+~ 12y_3 &+~ 18y_4 &+~ 10y_5 &)~/~1
\\[2pt]
y_1 & = &(&+~ 10 &-~ ~1y_3 &-~ ~6y_4 &-~ ~2y_5 &)~/~1
\\[2pt]
y_2 & = &(&+~ 20 &-~ ~4y_3 &-~ ~1y_4 &-~ ~1y_5 &)~/~1
\\~
\end{matrix}
\\[4pt]
\max w, \qquad y_1\ge0,~ \ldots,~ y_5\ge0
\]
(Niemand baut eine duale Aufgabe, um zu maximieren, sondern höchstens, wenn die duale Aufgabe eine zulässige Startbasis hat. Aber selbst dann würde man wohl eher einen dualen Simplexalgorithmus verwenden)
|
Profil
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 2320
 | Beitrag No.2, eingetragen 2022-02-10
|
Hallo rocaflex!
Mit den Variablen x1 und x2 kann man das Ganze auch grafisch lösen.
Viele Grüße
Ronald
|
Profil
|
rocaflex
Junior 
Dabei seit: 10.02.2022
Mitteilungen: 5
| Beitrag No.3, vom Themenstarter, eingetragen 2022-02-10
|
Hallo @Delastelle, danke für den Hinweis, aber leider müssen wir es rechnerisch mit dem Simplexverfahren machen.
@Goswin
Vielen dank schon mal für deine schnelle und ausführliche Antwort!
So wie ich deine Schilderung verstanden habe, muss ich als erstes 12, 18 und 10 auf die linke Seite bringen und die Zielfunktion mit (-1) multiplizieren.
Danach wird die Matrix transponiert und dann alle Funktionen mal (-1)?
Also würde mein Tableau wie folgt aussehen:
X1 X2 X3 S1 S2 b
T1 -1 -6 -2 1 0 10
T2 -4 -1 -1 0 1 20
Z 12 18 10 0 0 0
Um die optimale Lösung zu erhalten, muss ich dann in der zielfunktion alle Lösungen in den negativen Bereich bringen?
|
Profil
|
Goswin
Senior 
Dabei seit: 18.09.2008
Mitteilungen: 1792
Wohnort: Chile, Ulm
| Beitrag No.4, eingetragen 2022-02-10
|
\quoteon(2022-02-10 15:50 - rocaflex in Beitrag No. 3)
Also würde mein Tableau wie folgt aussehen:
X1 X2 X3 S1 S2 b
T1 -1 -6 -2 1 0 10
T2 -4 -1 -1 0 1 20
Z 12 18 10 0 0 0
Um die optimale Lösung zu erhalten, muss ich dann in der Zielfunktion alle Lösungen in den negativen Bereich bringen?
\quoteoff
(1)
[In meiner obigen Beitrag (inzwischen berichtigt) hatte ich an einer Stelle die falschen Indizes "ge-copy-paste-t"]. Aber ungeachtet der Indizes sind die unabhängigen Variablen im Tableau deiner Dualaufgabe nie und nimmer primale Variablen \(x_1,~ x_2,~ x_3\), sondern (in deiner Notation anscheinend) \(s_3,~ s_4,~ s_5\), das darfst du nicht verwechseln. Und die Zielvariable der Dualaufgabe sollte nicht \(z\) genannt werden. Wenn du die optimale Basis der Dualaufgabe gefunden hast, mußt du die entsprechenden Gleichungen der Primalaufgabe aufstellen, um dort die Lösung abzulesen (siehe hier).
(2)
Du musst dir im Klaren sein, welche Gleichungen du durch dein Tableau darstellen möchtest, sonst kannst du es nie richtig auslegen (am besten verwendest du überhaupt keine Tableaus, ist das wirklich eine Vorgabe des Übungsleiters?). Wenn dein Tableau das obige duale Gleichungssytem darstellt (egal wie), dann ist es richtig, ansonsten ist es falsch. Es gibt Bücher, wo das Gleichungssystem so hingeschrieben wird:
\[
\begin{matrix}
+~ ~1s_3 &+~ ~6s_4 &+~ ~2s_5 &+~ ~1s_1 &+~ ~0s_2 &= &~+ 10
\\[2pt]
+~ ~4s_3 &+~ ~1s_4 &+~ ~1s_5 &+~ ~0s_1 &+~ ~1s_2 &= &~+ 20
\\[2pt]
-~ 12s_3 &-~ 18s_4 &-~ 10s_5 &+~ ~0s_1 &+~ ~0s_2 &= &+~ ~0 &-~ ~w
\end{matrix}
\]
Aber dann ist die duale Aufgabe nicht mehr die "negative Transposition" von der primalen Aufgabe, und du musst sehen, ob du damit zurechtkommst.
|
Profil
|
rocaflex
Junior
Dabei seit: 10.02.2022
Mitteilungen: 5
| Beitrag No.5, vom Themenstarter, eingetragen 2022-02-14
|
vielen dank!!
Das hat mir sehr geholfen!
|
Profil
|
| rocaflex hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
