Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Lineare Optimierung mit Simplex Verfahren

Lineare Optimierung mit Simplex Verfahren

Universität / Fachhochschule

Matrizenrechnung

Tags: Lineare Optimierung, Matrizenrechnung, Simplex Verfahren

DonHup46 aktiv_icon

17:51 Uhr, 10.07.2012

Hallo, ich bin neu hier und habe folgendes Problem: Ich schreibe am Donnerstag eine Klausur in Wirtschaftsmathematik und bekomme diese Aufgabe einfach nicht raus. Zur Information, ich befinde mich momentan im BWL-Grundstudium.

Die Aufgabe lautet:

Gegeben sei das folgende Standard-Maximum-Problem:

G = 10 x 1 + 2 x 2 >

Max.

3 x 1 + x 2 \leq 45

x 1 + 2 x 2 \leq 40

x 1, x 2 \geq 0

Führen Sie die lineare Optimierung mit dem Simplex-Verfahren durch und quantifizieren
Sie dabei

x 1, x 2

und

G

für das Gewinnmaximum. Gibt es im Gewinnmaximum freie
Kapazitäten, ggf. welche und in welcher Höhe ?

Ich hoffe mir kann jemand helfen

!!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Mathe-Steve aktiv_icon

18:07 Uhr, 10.07.2012

Hallo,
wo ist denn Dein Problem dabei? Schlupfvariablen ergänzen, Starttableau aufstellen, Pivotelement bestimmen, Basiswechsel durchführen und dann die Antworten auf die Fragen ablesen.
Gruß
Stephan

DonHup46 aktiv_icon

18:25 Uhr, 10.07.2012

Wir haben im Unterricht leider nur sehr wenig über Matrizen durchgenommen, aber es wird vorausgesetzt, dass wir es können.
Ich habe diese Aufgaben mit dem Simplex-Verfahren im Abi bereits durchgenommen und konnte sie auch gut. Nur habe ich leider alles wieder vergessen und habe die alten Unterlagen nicht mehr.

Diese Aufgabe ist eine alte Prüfungsaufgabe und könnte so wieder dran kommen.
Ich versuche mich gerade durch haufenweise Interneterklärungen zum Simplex-Verfahren durchzukämpfen und muss sagen, mein Kopf raucht und es will einfach nicht mehr Klick machen, obwohl ich es schon konnte

: (

Also ich würde so anfangen:

3 x 1 + x 2 + x 3 = 45

x 1 + 2 x 2 + x 4 = 40

Aber dann weiß ich nicht mehr weiter, wie ich das mit dem Pivat-Element mache !? Ich schaue gerade, ob mich Interneterklärungen weiterbringen.

Mathe-Steve aktiv_icon

19:01 Uhr, 10.07.2012

So, hier die Lösung zm Simplexverfahren.
Kannst du jetzt alle Fragestellungen beantworten?

DonHup46 aktiv_icon

20:34 Uhr, 10.07.2012

Vielen Dank für deine Antwort und deine Mühe

!!

Dank dir wird mir so langsam einiges klarer. Das obere Tableau (auch das mit dem Pivot-Element) habe ich jetzt verstanden.

Beim unteren Tableau ist mir noch manches unklar. Ich schaue jetzt mal, ob ich es von alleine herausbekomme, was mir noch unklar ist.

Falls nicht, würde ich mich nochmal an dich wenden.

DonHup46 aktiv_icon

21:50 Uhr, 10.07.2012

Durch deine Hilfe in Verbindung mit der unteren Erklärung auf dieser Homepage
www2.htw-dresden.de~mvoigt/wing-ab7.pdf )
habe ich jetzt endlich fast alles verstanden

Kannst du mir vielleicht noch diese 4 Fragen beantworten, dann müsste mir alles klar sein :

1)

Wie bist du im unteren Tableau auf

L 2 = 25

gekommen ??

2)

Wie errechnet sich der Gmax

(150)

3)

Bedeutet das Endergebnis (siehe Frage), dass es im Gewinnmaximum freie Kapazitäten
von

15

"Stück" gibt ??

4)

Warum bekommt am Ende für

x 2

kein Ergebnis heraus

(\frac{5}{3}

sind in Spalte

x 2

ja nicht
negativ, oder liegt es daran dass sich in dieser Spalte

- \frac{1}{3}

befinden) ??

Viele Grüße
Dominik

Mathe-Steve aktiv_icon

22:16 Uhr, 10.07.2012

(1)

Ich habe die erste Zeile des zweiten Tableaus von der zweiten Zeile des ersten Tableaus abgezogen.

(2)

Ich habe die erste Zeile des zweiten Tableaus

10

mal zur vierten Zeile des ersten Tableaus addiert.

(3)

Mit

x_{1} = 15

und

x_{2} = 0

ist die erste Ungleichung

3 x_{1} + x_{2} \leq 45

genau erfüllt (also keine Kapazität frei). Die zweite Ungleichung

x_{1} + 2 x 2 \leq 40

ergibt

15 \leq 40

. Hier haben wir also frie Kapazitäten von

25

Einheiten.

(4)

Der Algorithmus geht solange, bis in der letzen Zeile (der Zielfunktion) kein negativer Wert mehr vorkommt. Alle Variablen, bei denen in der Zielfunktion dann 0 steht haben einen Wert, der in

L

steht. Alle ursprünglichen Variablen mit positiven Ergebnissen sind 0 zu setzen.
Die positiven Werte bei den Schlupfvariablen werden Schattenpreise genannt, denn sie geben an, wie sich die Zielfunktion ändert, wenn man in der entsprechenden Nebenbedingung die Beschränkung um eine Einheit lockert. Wenn man also

3 x_{1} + x_{2} \leq 46

machen könnten, dann könnte man

x_{1}

\frac{1}{3}

erhöhen, was die Zielfunktion um

\frac{10}{3}

verbessern würde. Bei der zweiten Nebenbedingung ist der Schattenpreis

0,

denn die Ungleichung ist ja nicht ausgeschöpft und wenn ich aus

4041

machen würde, würde das daran nichts ändern.

DonHup46 aktiv_icon

22:49 Uhr, 10.07.2012

zu 2. ) Heißt dies, dass die Zahl bzw. der Funktionswert der Pivotzeile immer mal dem
kleinsten Wert in der Zielfunktion (mit positiven Vorzeichen) multipliziert
werden muss, um den Gewinn herauszubekommen ??

Ich frage nur, falls eine andere Aufgabenkonstellation in der Klausur drankommen sollte
und ich dann keine allgemeine Erklärung dafür habe.

DonHup46 aktiv_icon

23:16 Uhr, 10.07.2012

Ich schaue es mir gerade mal an

!!

Den Rechenweg habe ich jetzt auf jeden Fall verstanden, auch deine Antworten 3 und 4. Ob ich allerdings den Sinn genau verstanden habe, das bezweifel ich auch.

Ich werde es mir morgen Mittag nochmal genauer anschauen, da mein Kopf heute Abend leider nicht mehr länger mitmacht

: (

Ich werde mich dann morgen wieder melden

!!!

Aber du hast mich aber mit deinen super Antworten auf jeden Fall einen riesen Schritt nach vorne gebracht.
Dafür vielen Dank

!!!

Gruß
Dominik

DonHup46 aktiv_icon

15:15 Uhr, 11.07.2012

Ich bin die Sache heute nochmal von vorne angegangen und wollte mich bei einer neuen gleichwertigen Aufgabe testen, ob ich es überhaupt voll verstanden habe (siehe hier):

G = 4 x 1 + 3 x 2 \to

Max.

2 x 1 + x 2 \leq 40

x 1 + 2 x 2 \leq 50

Die Aufgabenstellung ist mit der anderen identisch

x 1, x 2 \geq 0

Ergebnis laut meinen Lösungen (leider ohne Rechenweg)

x 1 = 10

x 2 = 20

G = 100

Aber ich kann die Werte "außerhalb" der Pivotspalte bzw. Pivotzeile nicht ausrechnen. Ich weiß nicht wie (daher habe ich die Zellen auf meiner Anlage auch ausgelassen)

!!

Bei deiner ersten Anlage (mit den 2 Tableaus) hast du unten links hingeschrieben
"

+ 10 \cdot I

". Wie kommst du auf die

10

???

Ich hoffe du kannst mir nochmal helfen, damit ich es endlich komplett verstehe

!!

Morgen ist ja schon die Prüfung

: (

Mathe-Steve aktiv_icon

16:52 Uhr, 11.07.2012

Keine Ahnung, was Du da machst - wozu Spaltentauschen?
Außerdem fehlt bei

L

in der Zielfunktionszeile III eine 0.
Due wählst zuerst die Spalte mit der negativsten Zahl in der Zielfunktion.
Dann berechnest Du

\frac{L}{x_{i}}

und wählst die Zeile mit dem kleinsten positiven Wert.
So hast Du die eingekringelte

2

in Zeile 1 Spalte 1 erhalten.
Diese 2 muss zur 1 werden, indem Du die Zeile durch 2 teilst.
Das ergibt

1, 0.5, 0.5, 0, 0,20

Alle anderen Zeilen müssen jetzt eine 0 bekommen in der Pivotspalte, also wo die 1 jetzt steht, also in Spalte 1
Dazu ziehst Du die Pivotzeile, also die Zeile I, einmal von Zeile II ab und addieret sie 4 mal auf Zeile III.
II

0, 1.5, - 0.5, 1, 0, 30

III

0, - 1, 2, 0, 1, 80

Danach geht das Spiel von neuem los.

DonHup46 aktiv_icon

18:05 Uhr, 11.07.2012

Die Erklärung hat mir wirklich weitergeholfen

!!

Dann müsste im nächsten Schritt folgendes rauskommen :

I:

1; 0; \frac{7}{6}; 0; 0; 10

II:

0,1; - \frac{2}{3}; 0; 0; 20

III:

0; 0; \frac{20}{6}; 0; 1; 100

Nur wie komme ich auf die

10

und die

100

(die Zahlen sind aus Lösungen und wurden nicht selbst errechnet) ?? Bitte wenn es geht mit Rechenweg.

Mathe-Steve aktiv_icon

19:00 Uhr, 11.07.2012

Wenn Du meine Erklärungen verstehst, solltest Du versuchen, den nächsten Schritt analog zu rechnen und nicht irgendeine Lösung zu posten, die Du irgendwo abgeschrieben hast.

DonHup46 aktiv_icon

19:16 Uhr, 11.07.2012

Ich habe nur die Endergebnisse

x 1 = 10, x 2 = 20

und

G = 100

.

Ich habe die Matrix selber versucht zu errechnen, bin nur in Spalte

L

nicht auf die Ergebnisse von I und III gekommen, die in meinen Lösungen stehen. Daher habe ich dann die

10

und die

100

ohne Rechenweg in Spalte

L

eingesetzt.

DonHup46 aktiv_icon

19:22 Uhr, 11.07.2012

Mir ist nur noch unklar, wie du auf die Zahl 4 "du addierst sie 4 mal" kommst ??? Wenn das weiß, kann ich wahrscheinlich die anderen Zusammenhänge verstehen.

DonHup46 aktiv_icon

13:19 Uhr, 12.07.2012

Hallo Mathe-Steve,

Prüfung lief ganz gut

!!

Die gleiche Aufgabe kam in der Klausur dran, nur mit anderen Zahlen.

Und ich habe die Aufgabe gestern noch solange geübt, sodass ich sie heute ohne Probleme hinbekommen habe.

Ich hatte ja vorher null komma null Ahnung wie ich so eine Aufgabe lösen kann und hab mich Schritt für Schritt durch Tipps von dir oder Youtube-Videos nach vorne gearbeitet.

Vorallem dieses Video brachte mich das letzte Quäntchen vorwärts, das noch gefehlt hat.
http://www.youtube.com/watch?v=lPm46c1pfvQ&feature=relmfu

Danke für deine Tipps, sie haben mich zumindest teilweise echt weitergebracht.
Jemand wie ich, der null Ahnung hatte, hätte man vielleicht noch die Zusammenhänge genauer erklären müssen, warum (Grund ?? - Allgemeinerung) man beim 2. Tableau II

- I

oder warum man

3 x

III machen muss. Die Zusammenhänge sind mir erst gestern Abend nach langer langer Zeit klar geworden.

Danke für deine Mühe

!!!

Viele Grüße
Dominik Hooper

1017035

1016792

	Status: nicht eingeloggt	Noch nicht registriert?