Zweiphasenverfahren < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zweiphasenmethode |
Hallo,
ich muss die Zweiphasenmethode(Simplex-Algorithmus) kennen und sie auch anwenden können.
kann mir jemand eine gute internetseite empfehlen??
ich habe absolut nichts gefunden,
Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:45 Fr 03.04.2009 | | Autor: | barsch |
Hi,
eine Internetseite kann ich dir auch nicht nennen. Aus eigener Erfahrung weiß ich, dass - sofern man überhaupt etwas findet - dies alles sehr dürftig ist.
Ich habe momentan leider nicht viel Zeit. Aber vielleicht kann dir jemand weiterhelfen, wenn du eine konkrete Aufgabe stellst.
Ein paar Sätze, die mir spontan zur 2-Phasenmethode einfallen.
Um die Phase 2, also den eigentlichen Simplexalgorithmus, auf dein lineares Problem der Art
min [mm] c^{T}x [/mm] unter $Ax=b$, [mm] x\ge{0} [/mm] wobei [mm] A\in\IR^{mxn} [/mm] mit $m<n$ anwenden zu können, musst du bereits eine zulässige Basislösung mit Basis B kennen. Genau da triffst du dann auf das Phase 1 Problem. Du musst sogenannte künstliche Variablen einführen - nennen wir sie [mm] y_i [/mm] $i=1,...,m$.
Das Phase 1 Problem sieht dann wie folgt aus:
[mm] min\summe_{i=n+1}^{n+m}y_i [/mm] unter $Ax+y=b$, [mm] x,y\ge{0}. [/mm] Phase 1 - Problem
Ohne Einschränkung sei [mm] b\ge{0} [/mm] - ansonsten musst du die betroffene Restriktion mit $(-1)$ multiplizieren.
Eine zulässige Basislösung für das Phase 1 Problem erhälst du, indem du [mm] z=\vektor{x \\ y} [/mm] mit $x=0$ und [mm] y=b\ge{0} [/mm] (deswegen musstest du darauf achten, dass [mm] b\ge{0} [/mm] gilt) setzt. $z$ ist zulässige Basislösung zur Basis [mm] B=\{n+1,...,n+m\}. [/mm] Entsprechend gilt für die Nichtbasis [mm] N=\{1,...,n\}.
[/mm]
Jetzt musst du den Simplexalgorithmus auf das Phase 1 Problem anwenden.
Simplex bekommst du hin? Der steht sicher in deinem Skript.
Du erhälst dann eine optimale Basislösung [mm] z^{\*}=\vektor{x^{\*} \\ y^{\*}} [/mm] zur Basis [mm] $B^{\*}$.
[/mm]
Jetzt gibt es zwei Möglichkeiten:
1) [mm] \summe_{i=n+1}^{n+m}y_i>0 [/mm] , dann ist die Menge (der Polyeder = zulässige Menge eines linearen Programms)
[mm] P=\{x\in\IR^n|Ax=b,x\ge{0}\}=\emptyset. [/mm] Für das Programm min [mm] c^{T}x [/mm] unter $Ax=b$, [mm] x\ge{0} [/mm] existiert also keine zulässige Basislösung.
2) [mm] \summe_{i=n+1}^{n+m}y_i=0\gdw{y_i=0},i=n+1,...,m.
[/mm]
Jetzt musst du wieder 2 Fälle unterscheiden:
$i)$ [mm] B^{\*}\cap{\{n+1,...,n+m\}}=\emptyset [/mm] - bedeutet: Es befinden sich keine künstlichen Variablen [mm] y_i [/mm] in der Basis. Dann startest du den Simplex zu dem Problem min [mm] c^{T}x [/mm] unter $Ax=b$, [mm] x\ge{0} [/mm] mit [mm] $x=x^{\*}$ [/mm] und Basis [mm] $B^{\*}$.
[/mm]
$ii)$ [mm] B^{\*}\cap{\{n+1,...,n+m\}}=\{x_{i_0},..,x_{i_n}\} [/mm] wobei [mm] n\ge{0}. [/mm] Es befinden sich also noch künstliche Variablen in der Basis. Die kannst du jedoch nach und nach aus der Basis entfernen - denn: Da für alle [mm] y_i=0 [/mm] $i=n+1,...,n+m$, handelt es sich um eine degenerierte Ecke.
![[kopfkratz2]](/images/smileys/kopfkratz2.gif "[kopfkratz2]") Sind wohl doch mehr als nur ein bis zwei Sätze (Fast schon eine Antwort  ) geworden.
Ich hoffe, es hilft dir bei deinem Problem weiter.
MfG barsch
|
|
|
| |
|
erledigt!!
habs raus!!danke:)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:53 Fr 03.04.2009 | | Autor: | max3000 |
Von mir gibts nur nen Buchtipp ;)
Jarre/Stoer: Optimierung (Springer 2004)
Mit dem Buch hab ichs verstanden, nachdem ich in der Vorlesung immer wieder daran gescheitert bin.
|
|
|
| |
|
hej!
vielen dank euch zwei!!!:) ich versuch es selbst und wenn es nicht klappt,schreib ich die aufgabe hier rein
|
|
|
| |
|
| Aufgabe | Untersuchen Sie mit Hilfe des Zweiphasenverfahrens, ob der Zulässigkeitsbereich [mm] X=\{x\in\IR^n _+| A\vec{x}=\vec{b}\} [/mm] nicht leer ist und berechnen SIe ggf eine nicht ausgeartete zulässige Basislösung.
[mm] A=\pmat{ -1 & 1 & -1 & 1 & 0 \\ 2 & -3 & 1 & 1 & 0 \\ 2 & 1 & 1 & -1 & 1 } [/mm]
[mm] \vec{b}= \vektor{1 \\ 1 \\ 2} [/mm] |
nunja...keine ahnung,wie ich da anfangen soll...leider ist unser skript nicht hilfreich....
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:39 Sa 04.04.2009 | | Autor: | barsch |
Hi,
gehen wir doch einmal so vor, wie in meinem ersten Thread beschrieben. Wir müssen zuerst das Phase 1 Problem aufstellen.
> Untersuchen Sie mit Hilfe des Zweiphasenverfahrens, ob der
> Zulässigkeitsbereich [mm]X=\{x\in\IR^n _+| A\vec{x}=\vec{b}\}[/mm]
> nicht leer ist und berechnen SIe ggf eine nicht ausgeartete
> zulässige Basislösung.
>
> [mm]A=\pmat{ -1 & 1 & -1 & 1 & 0 \\ 2 & -3 & 1 & 1 & 0 \\ 2 & 1 & 1 & -1 & 1}[/mm]
>
> [mm]\vec{b}= \vektor{1 \\ 1 \\ 2}[/mm]
> nunja...keine ahnung,wie ich
> da anfangen soll...leider ist unser skript nicht
> hilfreich....
Wir müssen künstliche Variablen einführen, nämlich: [mm] y_1,y_2 [/mm] und [mm] y_3. [/mm] Wir erhalten folgende Matrix:
[mm] \overline{\red{A}}=\pmat{ -1 & 1 & -1 & 1 & 0 & 1 & 0 & 0 \\ 2 & -3 & 1 & 1 & 0 & 0 & 1 & 0\\ 2 & 1 & 1 & -1 & 1 & 0 & 0 & 1 }
[/mm]
Unser Vektor z der die Entscheidungsvariablen [mm] x_i, [/mm] $i=1,2,3,4$ und die künstlichen Variablen [mm] y_1,y_2,y_3 [/mm] enthält:
[mm] \red{z}=\vektor{x_1 \\ x_2 \\ x_3 \\ x_4\\ y_1\\ y_2\\ y_3}\ge{0}
[/mm]
Insgesamt erhälst du das Phase 1 Problem:
min [mm] {y_1+y_2+y_3}
[/mm]
unter [mm] \overline{\red{A}}\red{z}=b, \red{z}\ge{0}
[/mm]
Jetzt wendest du auf dieses Problem den Simplexalgorithmus an.
Überlege: Wie wählst du eine zulässige Basislösung für den ersten Schritt? (Tipp: Siehe auch hier meinen ersten Thread)
Wenn du eine optimale Basislösung [mm] z^{\*} [/mm] für das Phase 1 Problem gefunden hast, liest du erneut den ersten Thread und überlegst, was für die optimale Basislösung des Phase 1 Problems gelten muss, damit [mm] X=\{x\in\IR^n _+| A\vec{x}=\vec{b}\} [/mm] nicht leer ist!
MfG barsch
|
|
|
| |
|
@ barsch:vielen dank :)
ich bin jetzt zur 1.Basislösung gekommen.
wenn ich nun den simplex anwende,weiß ich nicht so recht,wie ich nun vorgehen soll. ich weiß,wie man das macht....aber ich habe keine konkreten zahlen für Z(x),also x1-y3 in der 1.Zeile,daher weiß ich nicht,wie ich nun pivotieren muss. mein ziel ist es ja immer,dass [mm] b\ge [/mm] 0 und auch [mm] x1-y3\ge [/mm] 0.
aber wie funktioniert es hier?
|
|
|
| |
|
ich verstehe diese Fallunterscheidung nicht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:39 So 05.04.2009 | | Autor: | barsch |
Hallo,
> .
> ich verstehe diese Fallunterscheidung nicht...
die Fallunterscheidung ist erst interessant, wenn du eine optimale Basislösung für das Phase 1 Problem hast. Und deiner Mitteilung (direkt vor deiner letzten Frage) entnehme ich, dass es bereits hier Probleme gibt.
Ich verstehe dich aber nicht ganz. Ich habe es eben mal ![[]](/images/popup.gif) hier >>> [mm] \blue{\text{Start im Browser}} [/mm] berechnen lassen. Hier wurde mir als optimale Basislösung [mm] z^T=(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8)^T=(0,0,0,1,3,0,0,0)^T [/mm] zur Basis [mm] B^{\*}=\{2,4,5\} [/mm] angegeben, wobei [mm] y_1=x_6,y_2:=x_7,y_3:=x_8.
[/mm]
Jetzt tritt also der folgende Fall ein:
> 2) $ [mm] \summe_{i=n+1}^{n+m}y_i=0\gdw{y_i=0},i=n+1,...,m. [/mm] $
In diesem Falle, habe ich eben die Notation [mm] y_1,y_2 [/mm] und [mm] y_3 [/mm] und nicht [mm] y_6,y_7 [/mm] und [mm] y_8 [/mm] verwendet.
> Jetzt musst du wieder 2 Fälle unterscheiden:
Hier musst du Fall 1 verwenden - Warum(?)
> $ i) $ $ [mm] B^{\*}\cap{\{n+1,...,n+m\}}=\emptyset [/mm] $ - bedeutet: Es befinden sich keine künstlichen Variablen $ [mm] y_i [/mm] $ in der Basis. Dann startest du den Simplex zu dem Problem min $ [mm] c^{T}x [/mm] $ unter $ Ax=b $, $ [mm] x\ge{0} [/mm] $ mit $ [mm] x=x^{\*} [/mm] $ und Basis $ [mm] B^{\*} [/mm] $.
Das oben verlinkte Programm zeigt dir auch die einzelnen Tableaus an - damit kann ich jetzt weniger anfangen, weil wir nie diese Tableau-Schreibweise benutzt haben; aber vielleicht hilft's dir. Achso, kleiner Hinweis: Das Programm geht standardmäßig davon aus, dass es sich um ein Maximierungsproblem handelt - also umstellen
Noch ein Hinweis: Die Angaben für [mm] y_1, y_2 [/mm] und [mm] y_3 [/mm] in dem Programm sind die Schattenpreise! Also nicht verwechseln.
MfG barsch
|
|
|
|
