Simplex Algorithmus JavaScript.js
- Author:
- hawe
Maximize LP - Minimize LP (duales Max Problem)


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] .... |
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] |
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 xi >= 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, xi >= 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, xi >= 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
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
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) | |
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 |
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 | | |
|