Ungleichungen mit Maximierungsziel Darstellung im Pivotverfahren

09.05.2012, 16:41

Stephili

Ungleichungen mit Maximierungsziel Darstellung im Pivotverfahren

Meine Frage:
Hallo, studiere im 2. Semester -nach den Kindern- mein Abi ist also schon ca. 15 Jahre her. Deshalb brauche ich Hilfe bei einem Übungsblatt zu Ungleichungen. Habe mich einigermaßen durch den Gauß-Algorithmus und Pivot gekämpft. Nun habe ich als nächsten Punkt die Ungleichungen und eine erste Aufgabe, deren Zusammenhang und Lösungsansatz ich noch nicht kenne:
Aufgabe 19. (1) z=30*x1 +25*x2 --> max
(2) x1/120 +x2/60 <_ 1
x2 <_ 50
2*x1 +3*x2 <_ 200
2*x1 + x2 <_ 160
(3) x1 >_ 0
x2 >_ 0

Meine Ideen:
im 1. Schritt müsste ich wissen, ob die () Aufgaben zusammengehören oder einzeln zu betrachten sind.
Ich hab jetzt so angefangen:
x1 x2
I 1/120 2/60 <_ 1
II 2 <_ 50
III 2 3 <_ 200
IV 2 1 <_160
z 30 25 ---> max

wie macht man weiter?

09.05.2012, 20:24

Stephili

Auf diesen Beitrag antworten »

z=30*x1 +25*x2 --> max

1/120______ 1/60______1________0________1
__0_________1________0________1 _______50
2___________3________0________0______200
2___________1________0________0______160
-30________-25________0________o________o

Die Matrix (Pivot) müsste somit richtig sein, hoffe ich - und die Aufgabe 19 gehört mit (Nr.) zusammen.
Jetzt habe ich die Frage: Wie fange ich in der 1. Zeile an? Ich habe gelesen, mit dem höchsten Wert teilen?

10.05.2012, 06:24

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich habe mal das Simplextableau aufgestellt. Die Zielfunktion ist hier in der zweiten Zeile. Wie der Name des Tableaus vermuten lässt würde ich den Simplex-Algorithmus durchführen.
In der Regel nimmt man die negativen Werte der Zielfunktion. Dadurch wird der Zielfunktionswert im Laufe des Simplex-Algorithmus positiv (hoffentlich maximal).

$\begin{eqnarray*} \begin{tabular}{|c|c|c|c|c|c|}\hline $x_1$ &$x_2$&$x_3$&$x_4$ &$x_5$ &$RS$ \\ \hline -30 & -25 &0 &0 &0 &0 \\ \hline \textcolor{blue}{1/120} & \textcolor{green}{1/60} &1 &0 &0 & 1 \\ \hline 2 & 3 &0 & 1 &0 &200 \\ \hline \textcolor{red}{2} & 1 &0 &0 &1 & 160 \\ \hline \end{tabular} \end{eqnarray*}$

Um das günstigste Pivotelement zu finden schaut man sich erst mal das die Zeile der Zielfunktion an. Hier haben wir -30 und -25 stehen. Man wählt die Spalte mit dem niedrigsten negativen Wert. Hier also -30. Da wir jetzt die Pivotspalte haben brauchen wir noch die Pivotzeile. Da teilt man jeweils die Werte der rechten Seite (RS) durch die Werte in der jeweiligen Pivospalte (1:1/120; 200:2; 160:2)=(120;100;80)

Jetzt ist die Zeile Pivotzeile, bei der als Ergebnis der kleinste positive Wert herauskommt. Hier ist das 80. Also ist das Pivotelement = 2. Ich habe sie schon mal oben rot eingefärbt.

Jetzt fängt man an zu rechnen. Ich mach 3 Beispiele.

Pivozeile: Alle Elemente in der Pivotzeile werden durch den Wert des Pivotelement (hier: 2) geteilt. Auch das Pivotelement selber, das wird somit 1.

Pivotspalte: Es werden alle Elemente 0 außer des Pivotelement selber.

Nicht-Pivot-Zeile-Element und Nicht-Pivot-Spalte-Element: Ich nehme beispielhaft die 1/60 in der Spalte von $\begin{eqnarray*} x_2 \end{eqnarray*}$ . Jetzt muss man in die Pivotspalte schauen ( $\begin{eqnarray*} x_1 \end{eqnarray*}$ ). Hier sieht man, dass der Wert des Pivotelements 240-mal größer ist, als der Wert der in der Zeile der 1. Nebenbedingung steht $\begin{eqnarray*} \textcolor{blue}{blau} \end{eqnarray*}$ (1/120:2)=1/240.
Also nimmt man die Zeile mit der 1. Nebenbedingung und zieht davon das 1/240-stel der Pivozeile ab. Man rechnet in dem Beispiel: 1/60-1/240=3/240=1/80.
Alle anderen Zellen werden vom Prinzip genauso berechnet, auch die Zielfunktion (außer Pivotzeile und Pivotspalte). Beachtet werden müssen unbedingt die Vorzeichen!!!!!
Die -10 in der Tabelle unten berechnen sich wie folgt: (-30:2)=-15.
Und dann -25-(-15)=-25+15=-10

$\begin{eqnarray*} \begin{tabular}{|c|c|c|c|c|c|}\hline $x_1$ &$x_2$&$x_3$&$x_4$ &$x_5$ &$RS$ \\ \hline 0 & -10 & & & & 2400 \\ \hline 0 & 1/80 & & & & \\ \hline 0 & & & & & \\ \hline 1 & 1/2 &0 &0 &1/2 & 80 \\ \hline \end{tabular} \end{eqnarray*}$

Du kannst ja mal versuchen die anderen Zellen zu berechnen.

Ich habe noch einen Link, wo es sehr gut erklärt ist: hier.

Wenn du noch Fragen hast oder Zwischenergebnisse bitte melden.

Mit freundlichen Grüßen.

10.05.2012, 14:26

Stephili

Auf diesen Beitrag antworten »

Hallo! Super eklärt!!!!! Vielen Dank!!!! Bin ganz glücklich!!!! Jetzt verstehe ich endlich die Erklärungen, die ich sonst so im www gefunden habe besser Freude

Dennoch habe ich eine Frage:
http://www.youtube.com/watch?v=Kck8LTOdNq4
nach diesem Video muss ich folgendermaßen vorgehen:

Den Wert aus der Pivotspalte + oder - und * den Wert aus der Pivotzeile.
Dann komme ich auch auf die 2400 aber leider nicht auf die -10

Was habe ich den jetzt falsch verstanden?
Gruß und Danke!!!

10.05.2012, 15:20

Kasen75

Auf diesen Beitrag antworten »

Hallo,

habe mir das Video mal kurz angesehen. Scheint kein Ton zu haben. Jedenfalls habe ich mal die 6 im Ausgangstableau genommen $\begin{eqnarray*} (s_1, x_2) \end{eqnarray*}$ . Pivotelement hat den Wert 2. Wert in der Pivozspalte $\begin{eqnarray*} (s_1, x_1) \end{eqnarray*}$ ist 8. Wert in der Pivozeile ist 1,5 $\begin{eqnarray*} (s_1 , x_2) \end{eqnarray*}$ .

Die 8 ist viermal so groß wie die 2. Jetzt nimmt man die 6 und zieht das Vierfache der 1,5 ab. Und heraus kommt 0.

Andere Zahl $\begin{eqnarray*} (s_3, x_3): 1,5 - 2*0,5=0,5 \end{eqnarray*}$
noch ne andere Zahl: -30 in der Zielfunktion: $\begin{eqnarray*} -30 - (-30)*1,5=-30+45=15 \end{eqnarray*}$

Bei deinem Beispiel war der Faktor $\begin{eqnarray*} 1/240 \end{eqnarray*}$ . Also $\begin{eqnarray*} 1/60-1/240 *1 = 4/240-1/240 *1=3/240=1/80 \end{eqnarray*}$

Zitat:

Den Wert aus der Pivotspalte + oder - und * den Wert aus der Pivotzeile.

Kannst du das mal an einem Beispiel konkretisieren. Dann kann ich es besser nachvollziehen.

Mit freundlichen Grüßen Willkommen

10.05.2012, 21:04

Stephili

Auf diesen Beitrag antworten »

ok - habe jetzt entsprechend gerechnet:

Die Pivotspalte 0 gesetzt, und in der 1. Zeile folgendermaßen gerechnet: -(-30/2)*Pivotzeile usw. also z.B. den Koeffizienten von x2 aus der 3. Zeile 3 -2/2 * 0,5 = 1...

0___-10___0___0___7,5_______2400
0___1/80__0___0___119/240___159 1/3
0___1_____0___0___-1/2______31840
1___1/2___o___0___1/2_________160

ist das so richtig?

10.05.2012, 21:08

Stephili

Auf diesen Beitrag antworten »

10.05.2012, 22:07

Stephili

Auf diesen Beitrag antworten »

ups. mein Tableau ist falsch - ich war ein bissl durcheinander - hab wohl schon zu lange und zu viel gerechnet. unglücklich

Frage: warum hast Du auch die Pivotspalte durch das Pivotelement geteilt - ich dachte man teilt nur die Pivotzeile durch das Pivotelement.

das Tableau nochmal neu:

0; -10; 0; 0; 7 1/2; 2400
0; 1/80; 0; 0; 1/480; 2/3
0; 1/2; 0; 1; -1/2; 40
1; 1/2; 0; 0; 1/2; 160

10.05.2012, 22:08

Kasen75

Auf diesen Beitrag antworten »

Hallo,

das ist mein Ergebnis. Teilweise habe ich andere Ergebnisse.

0___-10___0___0___15_______2400
0___1/80__0___0___-1/240___1/3
0___2_____0___0___-1______40
1___1/2___0___0___1/2_________80

Du hast geschrieben:

Zitat:

x2 aus der 3. Zeile 3 -2/2 * 0,5 = 1...

Das ist die vorhergehende Matrix:

$\begin{eqnarray*} \begin{tabular}{|c|c|c|c|c|c|}\hline $x_1$ &$x_2$&$x_3$&$x_4$ &$x_5$ &$RS$ \\ \hline -30 & -25 &0 &0 &0 &0 \\ \hline \textcolor{blue}{1/120} & \textcolor{green}{1/60} &1 &0 &0 & 1 \\ \hline 2 & 3 &0 & 1 &0 &200 \\ \hline \textcolor{red}{2} & 1 &0 &0 &1 & 160 \\ \hline \end{tabular} \end{eqnarray*}$

Das Pivoelement (2) ist 1 Mal größer als die 2 in der Pivospalte. Also zieht man einfach von der 3 die 1 in der Pivospalte ab.

In gleicher Weise gilt dies für die 200. Aus der 200 wird 40 (200-160).

Da wo du 119/120 raus hast habe ich gerechnet:
0 - 1*1/240 = -1/240
Die Null ist klar. Jetzt schaue ich mir das Verhältnis von dem Pivotelement (2) und dem zwei Zeilen darüberliegenden Element (1/120) an. Das das ist 1:240. Somit muss man rechnen 0-1*1/240=-1/240

Das ist alles eine Frage der Übung. Ein paar Zahlen sind ja schon richtig. Und das ist auf jeden Fall schon mal gut. Freude

Ich würde erst mal versuchen die Zahlen die ich habe nachzuvollziehen. Wenn du dazu Fragen hast, bitte gerne.
Bevor du dann das nächste Tableau berechnest, wäre gut wenn du noch mal postest welches das Pivotelement ist und warum.
Noch ein Tipp: Es kommen bei dieser Aufgabe keine riesigen Zahlen irgendwo raus. Also sowas 31840 sind bei dieser Aufgabe immer falsch. Nur zu Orientierung.

Mit freundlichen Grüßen. Willkommen

Neue Frage »

Antworten »

Ungleichungen mit Maximierungsziel Darstellung im Pivotverfahren

Verwandte Themen