simplex algorithmus drei phasen methode

19.02.2007, 13:46

alena1981

simplex algorithmus drei phasen methode

Hi
die überschrift sagt eigentlich schon alles. ich kann den simplex algorithmus in der 1. phase, und in der 2. phase auch wohl so grade noch, aber jetzt wollen die in meinem mathe skript dass ich so'n problem mit der drei-phasen-methode löse und ich weiß nicht mehr weiter ...
für schnelle rückantwort bin ich dankbar, hab nämlich übermorgen klausur Augenzwinkern

thanks, alena

19.02.2007, 15:04

Auf diesen Beitrag antworten »

Verschoben

Ich weiß ja nicht, wie es anderen geht, aber von einer Drei-Phasen-Methode im Zusammenhang mit dem Simplex-Algorithmus habe ich noch nie was gehört. Den normalen Simplex-Algorithmus teilt man ja bisweilen in zwei Phasen ein:

1.Bestimmen einer "zulässigen" Lösung bzw. Startlösung, d.h. eine, die überhaupt erstmal den Nebenbedingungen genügt.

2.Bestimmen der Optimallösung

Aber zu deiner Drei-Phasen-Methode solltest du noch ein paar Erläuterungen liefern, oder zumindest einen Link woher das stammt.

20.02.2007, 13:56

alena1981

Auf diesen Beitrag antworten »

simplex drei phasen
hab dann gestern mal den ganzen nachmittag mich durch diverse unterlagen gekämpft und folgendes herausgefunden:

die dritte phase des simplex algorithmus, die braucht man dann wenn bei den nebenbedingungen nicht alle x >= 0 sein müssen sondern eins oder mehrere x = 0, dann muss man in phase 1 die nebenbedingungen so ändern, dass da steht x>=0 und x<=0 und dann macht man weiter ...
oder man braucht das auch, wenn als zielfunktion da steht fi(x) = x_4, dann setzt man x_4 = u_4 - v_4 und nimmt das als zielfunktion, das ist dann auch in phase 1,

und wenn man das abgehandelt hat, macht man glaub ich normal weiter ...

wie würdest du das denn lösen, wenn da folgende aufgabe steht:

Maximiere fi (x) = -3x_1 + x_2 - 2x_4 unter den nebenbedingungen x_4 element aus den reellen zahlen, x_1, x_2, x_3 >= 0 und Ax<=b mit A = $\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & -1 \\ -1 & 0 & 1 & 1 \\ -2 & 1 & -2 & 0 \\ -1 &1 & -1 & 0 \end{pmatrix} \end{eqnarray*}$ und b = $\begin{eqnarray*} \begin{pmatrix} 1 \\ 2 \\ 1 \\ 9 \end{pmatrix} \end{eqnarray*}$

so ich hoffe das ist jetzt so lesbar, und danke für die mühe,
ach übrigens, tut mir leid daß ich gestern nicht mehr geantwortet hab, ich hab zuhause kein Internet, deshalb geht das bei mir nicht so lange mit surfen, bis gleich, Alena

20.02.2007, 16:10

alena1981

Auf diesen Beitrag antworten »

RE: simplex drei phasen
hm. ich würd mich ehrlich gesagt ganz gerne nach sonstiges von hochschulmathematik verschieben - da sind irgendwie mehr beiträge zu simplex usw. - ich wieiß nur leider nicht wie ...

Hallo? Ist hier jemand? Komme mir hier allmählich ein wenig verlassen vor?
Ich brauch auch bloß mal eben die erklärung wie das mit den drei phasen des simplex algorithmus geht... genaueres s. vorher ...

danke, Alena unglücklich

20.02.2007, 16:35

Auf diesen Beitrag antworten »

Zitat:

Original von alena1981
dann setzt man x_4 = u_4 - v_4

So kenne ich das auch: Wenn man an $\begin{eqnarray*} x_4 \end{eqnarray*}$ keine Nichtnegativitätsbedingung stellt, dann ersetzt man diese Variable im Modell eben einfach als Differenz zweier neuer, diesmal nichtnegativer Variablen $\begin{eqnarray*} u_4 \end{eqnarray*}$ und $\begin{eqnarray*} v_4 \end{eqnarray*}$ .

Dass man dies gleich als neue Phase titulieren muss, nun ja, Geschmackssache.

Aber was ist jetzt das Problem? Ersetzen und dann mit dem normalen Verfahren loslegen. In deinem Beispiel ist es doch besonders einfach, da ergibt sich dann der zulässige Bereich

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & -1 & 1\\ -1 & 0 & 1 & 1 & -1\\ -2 & 1 & -2 & 0 & 0\\ -1 &1 & -1 & 0 & 0\end{pmatrix} \cdot \begin{pmatrix} x_1\\ x_2\\ x_3\\ u_4\\ v_4\end{pmatrix} \leq \begin{pmatrix} 1 \\ 2 \\ 1 \\ 9 \end{pmatrix} \end{eqnarray*}$

und eine zulässige Lösung findet man wegen des nichtnegativen Vektors rechts auch sofort, nämlich einfach den Nullvektor. Also kann man sofort zur Optimierungsphase übergehen.

P.S.: Das Thema ist in Numerik sehr gut aufgehoben, ich habe es ja erst dahin geschoben!

20.02.2007, 16:57

alena1981

Auf diesen Beitrag antworten »

immer noch nicht so richtig
ja okay. meinetwegen, das mit dem
$\begin{eqnarray*} x_4 \end{eqnarray*}$
mag ja noch angehen,
hab mir dazu ne andere beispielaufgabe angesehen, aber die ist noch ekliger:
Minimiere $\begin{eqnarray*} fi \end{eqnarray*}$ (X) = $\begin{eqnarray*} x_4 \end{eqnarray*}$ u.d.N.
$\begin{eqnarray*} x_1, x_2, x_3 >= 0 und x_4 \in Menge der reellen Zahlen -x_2 + x_3 - x_4 >= -4 -3x_3 - x_4 >= -8 -x_2 + x_3 = 3 x_1 + 3x_2 - x_3 = -2 x_1 + 3x_2 - 2X_3 >= -6 \end{eqnarray*}$

davon kann ich ja wohl noch die Nebenbedingungen umformen auf <= 0

aber bei mir ist so eine komische Lösung vorgegeben, zum Beispiel werden neben den Schlupfvariablen
$\begin{eqnarray*} x_5 bis x_8 \end{eqnarray*}$
noch so komische künstliche Variablen eingeführt, die nennen sich dann
$\begin{eqnarray*} y_8 und y_9 \end{eqnarray*}$ , davon haben wir genauso viele wie wir Gleichungen haben, warum auch immer, und ich hab keine Ahnung wofür die gut sein sollen,

hast du da vllt eine Idee, was das soll?

thanks, Alena

20.02.2007, 17:28

alena1981

Auf diesen Beitrag antworten »

RE: immer noch nicht so richtig
hey ich hatte gerade einen geistesblitz

sag mal, kann das sein, dass ich entweder diese künstlichen Variablen einführe oder die Nebenbedingung irgendwas = eine Konstante aufteile in >= oder <= ??

also einmal schreibe ich dafür zwei nebenbedingungen mit eigenen Schlupfvariablen auf
oder ich schreib in dem normalen tableau unter die zeilen mit den schlupfvariablen einfach die gleichung mit dem normalen = Zeichen und dann ganz ohne schlupfvariable, weil das ja schon = ist ??

alena

Neue Frage »

Antworten »

simplex algorithmus drei phasen methode

Verwandte Themen