| |
| Autor |
  2-Phasen-Methode |
|
DerSebastian
Ehemals Aktiv 
Dabei seit: 13.12.2003
Mitteilungen: 49
Wohnort: Sachsen-Anhalt
 |  Themenstart: 2004-02-07
|
Lösen sie folgendes LOP mit Hilfe der 2-Phasen-Methode:
x_1+x_2+2*x_3->min
2*x_1+x_2-x_3=1
x_1-x_2+4*x_3=2
3*x_1+x_2+2*x_3<=5
2*x_1-x_2+x_3<=1
x_i>=0, \forall i
Hab leider nicht viel gefunden was die 2-Phasen-Methode eigentlich ist? Kann mir wer nen Tip geben wie man es dementsprechend umformt?
|
 Profil
|
Hume
Senior 
Dabei seit: 11.08.2003
Mitteilungen: 583
Wohnort: Shanghai, China
 | Beitrag No.1, eingetragen 2004-02-09
|
Hallo Sebastian,
als Zwei-Phasen-Methode bezeichnet man die Simplexmethode im allgemeinen Fall.
Die (primale) Simplexmethode zur Lösung linearer Optimierungsaufgaben arbeitet
ja stets mit (primal) zulässigen Basen. Das setzt aber voraus, dass man bereits
am Anfang eine solche kennt.
(Der Basisbegriff ist Dir bekannt? Sonst frag nach.)
Und was, wenn man eine solche nicht kennt? Man kann neue, künstliche Variablen einfügen,
die eine Basis bilden. Um die Aufgabe nicht zu verfälschen, muss man sie anschließend
natürlich wieder entfernen, und das ist genau die erste Phase. Am Ende derselben
sollte man also eine zulässige Basis der eigentlichen Aufgabe kennen oder aber wissen,
dass es eine solche nicht gibt.
Nun konkret. Bringe zunächst Deine Aufgabe in Normalform:
2*x_1+x_2-x_3=1
x_1-x_2+4*x_3=2
3*x_1+x_2+2*x_3+u_1=5
2*x_1-x_2+x_3+u_2=1
x_i>=0, \forall i
u_j>=0, \forall j
Zunächst ist also keine zulässige Basis zu erkennen, u_1 und u_2 können zwar
als Basisvariablen gewählt werden, aber es werden ja vier benötigt.
(Eine Basis ist durch eine Einheitsmatrix in der Systemmatrix gekenntzeichnet.)
Also füge noch zwei künstliche Variablen hinzu:
2*x_1+x_2-x_3+v_1=1
x_1-x_2+4*x_3+v_2=2
3*x_1+x_2+2*x_3+u_1=5
2*x_1-x_2+x_3+u_2=1
x_i>=0, \forall i
u_j>=0, \forall j
v_k>=0, \forall k
Die künstlichen Variablen sollten aber, damit die ursprüngliche Aufgabe da steht,
den Wert Null haben. Das wird zunächst als das Ziel in Phase 1 formuliert:
v_1+v_2 -> min
2*x_1+x_2-x_3+v_1=1
x_1-x_2+4*x_3+v_2=2
3*x_1+x_2+2*x_3+u_1=5
2*x_1-x_2+x_3+u_2=1
x_i>=0, \forall i
u_j>=0, \forall j
v_k>=0, \forall k
Diese Aufgabe kann nun mit Simplexmethode und der Startbasis menge(v_1 ,v_2 ,u_1 ,u_2 )
bearbeitet werden. Als Ende ist folgendes möglich:
(1) Der Optimalwert ist größer als Null. Dann hat die ursprüngliche Aufgabe
keine zulässige Lösung. Fertig.
(2) Der Optimalwert ist Null, dh. die künstlichen Variablen v_1, v_2 sind Null und
könnne (falls sie es nicht ohnehin schon sind) aus der Basis entfernt werden. Was
übrigbleibt, ist eine zulässige Basis für die ursprüngliche Aufgabe, so dass diese
nun ausgehend vom letzten Tableau der Phase 1, aber neuer Zielfunktion,
gelöst werden kann. Das ist dann die sogenannte Phase 2. Fertig.
Hilft Dir das weiter?
Du kannst sicher auch in jedem einigermaßen vernünftigen Skript zur linearen Optimierung
mehr dazu finden.
Viele Grüße,
Hume
|
Profil
|
DerSebastian
Ehemals Aktiv
Dabei seit: 13.12.2003
Mitteilungen: 49
Wohnort: Sachsen-Anhalt
| Beitrag No.2, vom Themenstarter, eingetragen 2004-02-10
|
OK ich denke ich habs so langsam verstanden, danke für die Mühe!
Nur noch eine Frage, wie merke ich mit dem Simplextableau das nicht nur eine Optimle Lösung existiert, sondern mehrere?
|
Profil
|
Hume
Senior
Dabei seit: 11.08.2003
Mitteilungen: 583
Wohnort: Shanghai, China
| Beitrag No.3, eingetragen 2004-02-11
|
Hallo Sebastian,
wenn Du mit dem üblichen Simplextableau arbeitest, lässt sich die Anzahl der
optimalen Basislösungen ziemlich leicht feststellen:
Bekanntlich sind die Optimalitätsindikatoren -- oder reduzierten Kosten, nenn
es wie Du willst -- der Basisvariablen stets Null. Die Optimalitätsindikatoren
der Nichtbasisvariablen sind -- im Falle der Optimalität -- nichtnegativ.
Jede Null, die dort enthalten ist, erzeugt eine neue optimale Basis, dh. die zugehörige
Variable kann wie üblich in die Basis aufgenommen werden und über den Quotiententest
eine Variable bestimmt werden, die die Basis verlässt.
Das geht so oft, wie "zusätzliche", also bei Nichtbasisvariablen stehende, Nullen
in den Optimalitätsindikatoren auftauchen.
Die Gleichung "Anzahl der zusätzlichen Nullen = Anzahl der zusätzlichen
optimalen Bases" bezieht sich aber tatsächlich nur auf die Anzahl der BASEN! Im
Entartungsfall kann zu zwei verschiedenen Basen derselbe Lösungsvektor
gehören.
Viele Grüße,
Hume
|
Profil
|
DerSebastian hat die Antworten auf ihre/seine Frage gesehen.
DerSebastian hat selbst das Ok-Häkchen gesetzt. |
|
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?
