Simplex Algorithmus JavaScript.js
- Author:
- hawe
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 x1,x2 ... xn und s1 .. sn 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 si (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
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 | | |
| |