Simplex Algorithmus JavaScript.js

Author:hawe

Topic:Optimization Problems, Linear Equations, Linear Programming or Linear Optimization

Maximize LP - Minimize LP (duales Max Problem)

Grundlagen (Google Tab - Video) Kommentiertes Aufgabenbeispiel Simplex-Standard-Tableau Maximiere Zielfunktion Z(x) mit NB<=b - in Starttableau -Z(x) negativ in unterer Zeile. Strukturvariablen oder Nichtbasisvasiablen x₁,x₂ ... x_n und s₁ .. s_n die Basisvariablen Gleichungssystem, beginnend mit den Nebenbedingungen f(x)<= b (Ungleichungen f(x) >= b ggf. "Umdrehen zu" (-1)f(x) <= -b), ergänzt durch die Basisvariablen s_i (Schlupfvariablen) zu einer Gleichung. Letzte Zeile die Zielfunktion (negative Vorzeichen der Koeffizienten)! siehe Simplex Algorithmus MAX Programm Minimiere Duales Programm Zielfunktion Z(x) mit NB>=b - in Starttableau -b(x) negativ in unterer Zeile. Überführung in ein duales Programm das mit dem Max-Simplex-Algorithmus bearbeitet werden kann. Die Nebenbedingungen von Min Systemen müssen auf die Form f(x) ≥ b gebracht werden. Daten-Matrix, die transponiert wird (tausche Zeilen/Spalten). Einfügen von Basis/Schlupfvariablen zum einem Max Programm transformieren. siehe 'Simplex Algorithmus Dual Min 2 Max' If Inputbox cripples input - please use Tableau X Eingabe-Matrix - coefficients of LP as array Eigene Angaben zur Pivotwahl in PivotZeile/PivotSpalte Grafische Lösung bei 2 Variablen

Quellen Aufgabe angelehnt an http://www.aunda-net.de/homepage/schule/simplex/beispiel/beispiel.html Simplex-Algorithmus http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/A_blau/Simplex_Dokumentation.pdf http://statistik.wu-wien.ac.at/~leydold/MOK/HTML/node145.html http://www.unet.univie.ac.at/~a0025537/php/Abschnitt1/Mathe/fb_menue.html https://www.zweigmedia.com/RealWorld/tutorialsf4/frames4_4.html wxMaxima on line

load("simplex");

Anwendung Standard Programm MAX

Pivotschritte (Algorithmus-Script.js)

wähle als Pivotspalte immer die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile.
bilde die Quotienten aus den Konstanten in der Spalte ganz rechts und den entsprechenden Einträgen in der Pivotspalte. Die Zeile mit dem kleinsten nichtnegativen Quotienten wählen wir als Pivotzeile. Das Element in der Pivotspalte und Pivotzeile heißt Pivotelement.
dividiere die Pivotzeile durch das Pivotelement und subtrahieren von jeder anderen Zeile ein geeignetes Vielfaches der Pivotzeile sodaß die entsprechenden Komponenten in der Pivotspalte gleich 0 werden ( Pivotschritt).
Stopp - alle Koeffizienten der Zielfunktion sind positiv!

maximize_lp( 20*x1+15*x2+7*x3,[ x1-2*x2<=30, 3*x1+x2-5*x3<=47, 3*x2+x3=20, x3<=5 ]),numer; [556.6666666666666, [x3=5,x2=5.0,x1=22.33333333333333] 1,-2,0,30; 3,1,-5,47; 0,3,1,20; 0,0,1,5; 20,15,7,0 [Eingabe als Tableau X eintragen] [Standard Programm für X erstellen]

[Simplex Schritt auf Matrix X ausführen] ...

Anwendung Duales Programm MIN

minimize_lp( 6*x1+2*x2-x3,[ 2*x1+x2+x3<=60, 2*x1+x2-2*x3>=40, 2*x2+x3<=25 ] ), nonegative_lp=true, numer; [107.5, [x3=0, x2=12.5, x1=13.75]] -2,-1,-1,-60 ; 2,1,-2,40 ; 0,-2,-1, -25;6,2,-1,0 [Eingabe als Tableau X eintragen]

[Duales Programm für Tableau X erstellen]

[Simplex Schritt auf Matrix X ausführen] ....

Weitere Beispiele sind in der Tabellen-Ansicht hinterlegt.

Dualer Simplex bei Nebenbedingungen mit negativer rechter Seite

maximize_lp( -2*x1-2*x2-6*x3, [ -2*x1+2*x2 <= 20, -2*x1+2*x3 <= -24, 2*x1-2*x2-3*x3 <= 16, -4*x1+2*x2-2*x3 <= -4 ]) ,nonegative_lp=true; [-32,[x3=0,x2=4,x1=12]] ... Zulassen neg. Koeffizienten ,nonegative_lp=false; [16,[x3=-6,x2=4,x1=6]] -2, 2, 0, 20; -2, 0, 2, -24; 2, -2, -2, 16; -4, 2, -2, -4; -2, -2, -6, 0 [Eingabe_als_Tableau_X_eintragen] Die Zielfunktion (alle Koeffizieten positiv) und die NB 2 und 4 (rechte Seite negatv) eignet sich nicht für einen primalen Simplex. [Standard Programm für Tableau X erstellen]

Pivot-Spalte:= Berechne jede Spalte c_j/a_zj, indem du jedes Element aus der Zielfunktionszeile durch das jeweilige Element in der Pivotzeile teilst (Zielfunktion/Pivot-Zeile). Pivot-Spalte ist die Spalte mit dem größten, negativen Quotienten.

Pivotsuche: PivotZeile=2 kleinster negativer Koeffizent in b-Spalte. PivotSpalte=1 einstellen und [Simplex-Schritt ausführen]

Pivotsuche: PivotZeile=3 kleinster negativer Koeffizent in b-Spalte. PivotSpalte=2 einstellen [Simplex-Schritt ausführen]

Rechte Seite alles positiv, es kann mit dem Standard-Max-Programm weiter verfahren werden - wenn nötig (hier sind wir fertig, da alle Koeffizenten der Zielfunktion positiv!)

Anwendung nonegative Max Programm

maximize_lp( 2*x+3*y+z,[ x + y + z <= 40, 2*x + y - z >= 10, -y + z >= 10 ] ),no_negativ_lp=true; [70,[z=20,y=10,x=10]] 1,1,1,40;2,1,-1,10;0,-1,1,10;2,3,1,0 [Eingabe_als_Tableau_X_eintragen] Mit dem Standard-Programm nicht lösbar. Führe negative Schlupfvariablen für die beiden nicht Standard Nebenbedingungen ein. Und führe für diese Zeilen mit neg. Schlupfvariablen die in folgenden Schitten beschriebene Pivotbehandlung durch.

Pivotsuche: PivotSpalte=1 ist größte positive Zahl in der ersten Zeile der neg. Schlupfvariablen. PivotZeile=2 wie im Standard-Verfahren. Einstellen und [Simplex-Schritt ausführen]

Pivotsuche: PivotSpalte=3 ist größte positive Zahl in der zweiten Zeile der neg. Schlupfvariablen. PivotZeile=3 wie im Standard-Verfahren. Einstellen und [Simplex-Schritt ausführen]

Weiter im Standard-Verfahren [Simplex-Schritt ausführen]

Im Eingabefeld der Startversion ist Maximize p = -x1+2x2 subject to x2 + x4 >= 4,-5x1+4x2+2x3 + 6x4 >= 15,-3x1 +2x2+x3+3x4<=8,2x1-x2-2x4 = -5 hinterlegt - das Progamm kann mit dem hier beschriebenen Verfahren (z.B.S4Z2,S1Z1) gelöst werden: siehe Zweigmedia für Alternativen

...

Converting a Minimzation Problem to a Maximization Problem

NB 2,3 erhalten eine negative Schlupfvariable und die Zielfunktion wird positiv ins Start-Tableau eingetragen

minimize_lp(2*x+y+2*z,[ x + 5*y + z <= 100, x + 2*y + z >=50, 2*x + 4*y + z >=80] ), nonegative_lp=true; [50,[z=50/3,y=50/3,x=0]] Da die Minimierung von 2*x+y+2*z gleichbedeutend mit der Maximierung von -2*x-y-2*z ist, können wir das obige Problem behandeln, indem, wir die Zielfunktion positiv verwenden (also nicht wie beim Maximieren negativ eintragen). Bei diesem Problem handelt es sich um ein Maximierungsproblem mit gemischten Einschränkungen, d.h. die Schlupfvariablen der betroffenen NB sind negativ einzusetzen und zuerst unter Vorgabe der Pivots im Standardprogramm zu behandeln.

1,5,1,100; 1,2,1,50; 2,4,1,80; 2,1,2,0 [Eingabe als Tableau X eintragen] [Standardprogramm für Tableau X erstellen] Schlupfvariablen ändern

PivotZeile=3 Pivotspalte=2 [Simplex Schritt auf Matrix X ausführen]

PivotZeile=2 Pivotspalte=3 [Simplex Schritt auf Matrix X ausführen]

[Simplex Schritt auf Matrix X ausführen]

Minimize Problems

Eine kleine Erdölgesellschaft besitzt zwei Raffinerien. Raffinerie 1 kostet $20.000 pro Tag, sie kann 400 Barrel hochwertiges Öl und 300 Barrel Öl mittlere Qualität produzieren und 200 Barrel minderwertiges Öl pro Tag. Raffinerie 2 kostet 25.000 Dollar pro Tag und kann 300 Barrel hochwertiges Öl, 400 Barrel Öl und 400 Barrel Öl mittlere Qualität und 500 Barrel minderwertiges Öl pro Tag produzieren. Das Unternehmen hat Aufträge über insgesamt 25.000 Barrel hochwertiges Öl, 27.000 Barrel Öl mittlere Qualität und 30.000 Barrel minderwertiges Öl. Kosten (Produktionstage) minimieren um den Auftrag zu erfüllen. Minimize C= 20000*x1+25000*x2 Subject to: 400*x1+300*x2 >= 25000, 300*x1+400*x2 >= 27000, 200*x1+500*x2 >= 30000 x_i >= 0 400,300, 25000; 300,400,27000; 200,500,30000; 20000,25000,0 Minimize C= 12*x1+4*x2+2*x3 Subject to: -6*x1+3*x2 >= 9, 2*x1-2*x2-6*x3 <= -4, x_i >= 0 -6,3,0,9 ; -2,2,6,4 ; 12,4,2,0 Minimize C = 425*x1 + 525*x2 + 475*x3 + 500*x4 Subject to: x1 + x2 <= 120, x3 + x4 <= 250, x1 + x3 >= 200, x2 + x4 >= 150, x_i >= 0 -1,-1,0,0,-120 ; 0,0,-1,-1,-250 ; 1,0,1,0,200 ; 0,1,0,1,150 ; 425,525,475,500,0

Lagerkosten minimieren

Übersicht über Lagermengen, Mengenbedarf A1, A2, A3 und Transportkosten

Lagermenge		Lager 1 (90 t)
Transportkosten L1 Bedarf: Transportkosten L2	35 € A1 (80 t) 15 €	30 € A2 (40 t) 20€	20 € A3 (45 t) 25 €
Lagermenge		Lager 2 (75 t)

1,0,0,1,0,0,80; 0,1,0,0,1,0,40; 0,0,1,0,0,1,45; -1,-1,-1,0,0,0,-90; 0,0,0,-1,-1,-1,-75; 35,30,20,15,20,25,0

minimize_lp( 35*x1+30*x2+20*x3+15*x4+20*x5+25*x6, [ x1+x4>80, +x2+x5>=40, +x3+x6>=45, (x1+x2+x3)<90, (x4+x5+x6)<=75 ]), nonegative_lp=true; [3400,[x6=0,x3=45,x5=0,x2=40,x4=75,x1=5]]

[Eingabe als Tableau X eintragen]

[Duales Programm für Tableau X erstellen]

... ... [Simplex Schritt auf Matrix ausführen]

Beispiel mit Konstante in Gewinnfunktion

Erzeugnis	Deckungsbeitrag je Stück (EUR)	geplante, absetzbare Stückzahl
A	8,40	150.000
B	6,60	200.000
C	10,80	120.000

Die fixen Gesamtkosten betragen 180.000,- EUR. Die Produkte werden in Serie auf getrennten Anlagen gefertigt; durchlaufen gemeinsam eine Kontroll-, Prüf- und Verpackungsabteilung, die mit 12.400 Stunden belastet werden kann. Für das Produkt A werden 2,4 Minuten/Stück, für B 1,5 Minuten/Stück und für C 1,8 Minuten/Stück verbraucht. Bestimmen Sie unter den gennanten Bedingungen das optimale Produktionsprogramm und berechnen Sie das Betriebsergebnis [1,0,0,150000; 0,1,0,200000; 0,0,1,120000; 2.4,1.5,1.8,12400*60; 8.4,6.6,10.8,180000]

maximize_lp( 8.4*a + 6.6*b + 10.8*c - 180000, [ a<=150000, b<=200000, c<=120000, 2.4*a + 1.5*b + 1.8*c <= 12400*60 ]), nonegative_lp=true; [3234000.0,[c=120000,b=200000.0,a=95000.0]]

X-Tableau

[Standard Programm für X-Tableau erstellen]

[1,2,1,3; 2,-1,3,4; 2,3,4,0] minimize_lp( 2*x+3*y+4*z,[ x + 2*y + z >= 3, 2*x - y + 3*z >=4] ), nonegative_lp=true; [28/5,[z=0,y=2/5,x=11/5]]

Minimieren mit dem Standard-Programm	Minimieren mit dem dualen Programm
Pivotzeile 2/ Pivotspalte 1
Pivotzeile 1/ Pivotspalte 2

Minmieren mit Standardprogramm	und NB als Gleichungen
minimize_lp( 6x1 +x2 + 5x3 + 4x4 + 22x5 + 3x6, [ 5x3 + 2x4 + 2x5 +x6 = 32, x2 +x3 + 3x4 + 2x5 = 40, x1 + 2x3 -x4 + 2x5 = 15 ]), nonegative_lp=true;	[394/5,[x1=11/5,x2=168/5,x3=32/5,x6=0,x5=0,x4=0]] Zielfunktion positiv eintragen Schlupfvariable = 0 setzen
Geänderte Zeilen der Schlupf- variablen abarbeiten Pivotzeile 1/Pivotspalte 3
Pivotzeile 2/Pivotspalte 4
Pivotzeile 3/Pivotspalte 5
Standardverfahren bis Zielfunktion positiv
X

Zuschnitt-Problem - min integer programm

Ein Papierfabrikant stellt Papierrollen mit einer Standardbreite von 105 cm und einer Länge von L cm her. Es liegen folgende Aufträge vor: - 100 Rollen 25 cm breit, - 124 Rollen 30 cm breit, - 80 Rollen 35 cm breit. Für die Aufträge werden Standardrollen zerschnitten. Ziel ist die Minimierung der Schnittverluste. Excel Solver

4, 3, 1, 0, 0, 0, 1, 100; 0, 1, 1, 2, 1, 0, 0, 124; 0, 0, 1, 1, 2, 3, 2, 80; 5, 0, 15, 10, 5, 0, 10,0 Eingabe-Tableau

Duales Programm für Tableau X erstellen

Erreicht nicht das Ergebnis des Solvers braucht aber weniger Standard-Rollen (92)! wxMaxima

load("simplex"); minimize_lp( x1*5+x3*15+x4*10+x5*5+x7*10, [ x3 + x4+2*x5+3*x6+2*x7 = 80, x2+x3+2*x4 +x5 = 125, 4*x1+3*x2+x3+x = 100, x6=10, x5=1, x7=0 ]),nonegative_lp=true, numer; [505.0,[x1=4.0,x2=28,x7=0,x6=10,x5=1,x4=48,x3=0]] x6, x5, x7 schrittweise in mehreren Durchläufen festgelegt!