Simplexalgorithmus < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
wir müssen in der Klausur Aufgaben mit den Simplexalgorithmus lösen und das Maximum der Zielfunktion unter einer Nebenbedingung bestimmen.
Ich vestehe ja noch wie man durch die Pivotspalte und die Pivotzeile zu dem Pivotelement komme, aber wie ich dann weitermachen soll bin ich total überfragt...
Wenn mir jemand mal ein System fürs pivotisieren verraten könnte wäre ich super dankbar.
LG Trinity
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:43 Mo 06.02.2006 | | Autor: | piet.t |
Hallo Trinity,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
da die Darstellungsformen des Simplex-Algorithmus doch recht verschieden sind (Tableaus, Gleichungen,???) wäre es vielleicht gut, wenn Du noch eine kleine Aufgabe posten könntest und an der mal zeigst, wie weit Du schon kommst. Dann können wir Dein Problem genauer eingrenzen und die Erklärung auch in der passenden Notation bringen.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:09 Di 07.02.2006 | | Autor: | Trinity_R |
Hi,
ich verstech hier in diesem Beispiel nicht wie man genau beim pivotisieren vor geht. Ich weiß nur, dass ich mir in meiner ersten matrix, bei X1 und X2 den größten Wert (=4) suchen muss und der dann vorerst meine Pivotzahl ist.
Aber was dann kommt hab ich nicht so wirklich verstanden.
W1 3 4 1 0 0 48 12
W2 3 2 0 1 0 36 18
W3 3 0 0 0 1 27 -
Z -1 -1 0 0 0 0 -
X2 3 4 1 0 0 48
W2 1,5 0 -0,5 1 0 12
W3 3 0 0 0 1 27
Z -0,25 0 0,25 0 0 12
.....
ist leider etwas verzerrt, sollte eigentlich schön untereinander stehen.
LG Trinity
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:34 Di 07.02.2006 | | Autor: | piet.t |
Hallo Trinity,
> Hi,
> ich verstech hier in diesem Beispiel nicht wie man genau beim pivotisieren
> vor geht. Ich weiß nur, dass ich mir in meiner ersten matrix, bei X1 und X2
> den größten Wert (=4) suchen muss und der dann vorerst meine
> Pivotzahl ist.
...nicht ganz. Das bestimmen der Pivot-Zahl hat immer zwei Schritte:
1. muss man sich eine passende Pivot-Spalte suchen. Dazu sucht man in der letzten Zeile (Zielfunktion) i.a. den Eintrag mit passendem Vorzeichen (positiv bei einem Maximierungsproblem, negativ bei einem Minimierungsproblem) und dem gößten Betrag. Das Vorzeichen muss passen, der Betrag ist nice to have.
Anschließend sucht man noch eine zugehörige pivot-Zeile. dazu betrachtet man für jede Zeile mit positivem Eintrag r in der pivot-Spalte das Verhältnis s/r, wobei s die Zahl in der rechten Spalte der entsprechenden Zeile ist.
Die Zeile mit dem kleinsten s/r wird unsere pivot-Zeile.
> Aber was dann kommt hab ich nicht so wirklich verstanden.
>
>
> W1 3 4 1 0 0 48 12
> W2 3 2 0 1 0 36 18
> W3 3 0 0 0 1 27 -
> Z -1 -1 0 0 0 0 -
>
Hier ist also willkürlich die zweite Spalte als pivot-Spalte gewählt (die erste wäre wohl genauso gut), s/r ist in der ganz rechten Spalte ergänzt, man sieht also, dass die erste Zeile die pivot-Zeile wird.
>
> X2 3 4 1 0 0 48
> W2 1,5 0 -0,5 1 0 12
> W3 3 0 0 0 1 27
> Z -0,25 0 0,25 0 0 12
>
> .....
Hier hat man eigentlich nur für alle nicht-pivot-Zeilen die Einträge in der pivot-Spalte durch elementare Zeilenumfomrungen auf 0 gebracht.
z.B. wird zur zweiten Zeile -0,5 mal die erste Zeile addiert.
In der LP-Sprechweise erfolgt hier ein Basiswechsel: die Variable der Pivot-Zeile (hier also W1) verlässt die Basis, die Variable der Pivot-Spalte (also X2) tritt in die Basis ein.
Von diesem Punkt kann man eigentlich gleich in die nächste Iteration gehen, also wieder pivot-Spalte und -Zeile bestimmen usw.
Will man am Ende die Werte der Variablen direkt ablesen muss man noch darauf achten, dass in den Spalten der Basisvariablen nur eine 1 stehen darf - ggf. muss man die entsprechende Zeile also noch passend multiplizieren.
Gruß
piet
|
|
|
|
