Google Classroom
GeoGebraGeoGebra Classroom

Simplex Algorithmus MAX Programm

Toolbar ImageGrundlagen (Google Tab - Video) X Vorgabe der Strukturvariablen oder Nichtbasisvasiablen x1,x2 und x3 .. x7 die Basisvariablen (ggf. ändern oder ergänzen). Zeile 3/4 enthalten Funktionen für einen Simplex-Schritt Tablo, Gleichungssystem, beginnend mit den Nebenbedingungen f(x)<= b. Ungleichungen f(x) >= b ggf. "Umdrehen zu" (-1)f(x) <= -b , ergänzt durch die Basisvariablen xi (Schlupfvariablen) zu einer Gleichung. Zum Abschluß die Zielfunktion (negative Vorzeichen der Koeffizienten)! Aus Tablo erzeuge ich das Ausgangstabelau für den 1. Simplex-Schritt, Start (Zeile $9). Ziel ist es durch Umformung der Start-Tableaus in der Zeile der Zielfunktion (Zeile n) ausschließlich positive Werte zu erzeugen. Zeile 10/11/16 enthalten Funktionen für einen Simplex-Schritt 9: A1:=Start Tableau A1 zuweisen Einen Simplex-Schritt berechnen durch die Anwendung der Simplex-Schritt-Funktionen
Schritt-Berechnung Schritt-FunktionAnwendung auf A1
1:PivotspaltePs=PivotSpalte(Ai) 12: PivotSpalte(A1)
2: Quotient Vektor b/Ai(Pivotspalte)PB=PivotB(Ai, Ps)13: PivotB(A1, $12)
3:PivotzeilePz=PivotZeile(PB) 14: PivotZeile($13)
4:Pivot-Zeilen-Element aus AiPe=Pivotelement(Ai,Pz,Ps)15: Pivotelement(A1, $14, $12)
5:Nächstes TableauNxTableau(Ai, Pz, Ps, Pe)17: A2:=NxTableau(A1, $14, $12, $15)
17: A2 Simplextabelle nach der 1. Umformung Zeile 18..22: Ps=PivotSpalte(Ai) > PB=PivotB(Ai, Ps) > Pz=PivotZeile(PB) > Pe=Pivotelement(Ai,Pz,Ps) > NxTableau(Ai, Pz, Ps, Pe) 22: A3 Simplextabelle nach der 2. Umformung Zeile 24..28:  Ps=PivotSpalte(Ai) > PB=PivotB(Ai, Ps) > Pz=PivotZeile(PB) > Pe=Pivotelement(Ai,Pz,Ps) > NxTableau(Ai, Pz, Ps, Pe) 28: A4 Simplextabelle nach der 3. Umformung ggf. wären weitere Schrittfolgen nach dem vorgegebenen Muster zu ergänzen... Um beim Errechnen der Quotienten (PivotB ) keine undefinierten Werte zu erzeugen setzte ich 10^15 als Dummy-Wert bei der Minimumsuche ein. Toolbar ImageZur JavaScript Umsetzung des Simplex-Algorithmus

SimplexAlgorithmusMAXfAi.ggb

Vom Start-Tableau zum Schlußtableau
Vom Start-Tableau zum Schlußtableau
Im Schlußtableau ist der maximale Wert für die Zielfunktion in der B-Spalte (max=180) abzulesen. Die x1=20 und x2=60 Werte stehen ebenfalls in der B-Spalte in den Zeilen, in denen die x1, x2 Koeffizienten durch die Umformungen verschoben wurden. Beispiel entnommen https://sites.google.com/site/simplexverfahren/begriffe-von-a-bis-z für ausführlichen Kommentierung des Algorithmus siehe dort.  maximize_lp(40*x1+20*x2,[ 20*x1+7*x2<=1400, 7*x1+10*x2<=1600, 8*x1+2*x2<=500, x1<=50, x2<=150] ), nonegative_lp=true; [556000/151,[x2=22200/151,x1=2800/151]] Übung: http://www.fernstudium-wiwi.de/simplextableau-umformung-fuer-dummies/ Tablo:={ 20*x1+7*x2+x_3=1400, 7*x1+10*x2+x_4=1600, 8*x1+2*x2+x_5=500, x1+x_6=50, x2+x_7=150, -40*x1-20*x2=0} Tablo:={x1+x3+x_4=8, x1+x2+x_5=7, x1+2 x2+ x_6=12, -3*x1-2*x2-2 x3=0}

Das lineare Programm des Applet erweitern (weiteres Simplex-Tableau hinzufügen)

Das lineare Programm des Applet erweitern (weiteres Simplex-Tableau hinzufügen)
Neues Programm eingeben und ein weiteres Tableau hinzufügen
Beispiel PivotSpl=1, PivotZle=2, Pivot {1, 0.4, 0.2, 0, 0.2, 0, 100} PivotSpl=3, PivotZle=1, Pivot {0, 1.26, 1, 0.19, (-0.11), 0, 92.59}

Lösungsraum mit den Ergebnissen der Simplex Tableaus

Lösungsraum mit den Ergebnissen der Simplex Tableaus
Start S0, Tableau S1 und S2

Beispiel

3 Produkte werden auf 3 Maschinen M1, M2 und M3 hergestellt. Die Belegungszeiten der Produkte auf der Maschine  M1 betragen 2 Minuten für P1, 4 Minuten für P2 und 3 Minuten für P3; M1 besitzt eine freie Kapazität von 1.050 Minuten. Alle Produkte belegen die Maschine M2 mit je einer Minute; die Kapazität dieser Maschine beträgt noch 450 Minuten. Auf der dritten Maschine M3 kann nur P2 gefertigt werden; sie besitzt noch eine Kapazität von 150 Minuten. Die Belegungszeit von P2 auf M3 beträgt 1 Minute. Der Deckungsbeitrag je Stück der 3 Produkte beträgt 50 € , 80 € bzw. 60 €. a) Welche Stückzahlen sind jeweils herzustellen, damit der Gesamtdeckungsbeitrag maximal wird? b) Wie groß ist der optimale Gesamtdeckungsbeitrag und wie hoch sind die freien Kapazitäten der drei Maschinen im Optimum? Anwendung der Google Tab Toolbar ImageGrundlagen (Google Tab - Video)
Image