Simplex Algorithmus JavaScript.js

Author:
hawe

Maximize LP - Minimize LP (duales Max Problem)

Toolbar ImageGrundlagen (Google Tab - Video) Toolbar ImageKommentiertes 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)
  1. wähle als Pivotspalte immer die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile.
  2. 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.
  3. 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).
  4. 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.

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 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
LagermengeLager 1 (90 t)
Transportkosten L1 Bedarf: Transportkosten L235 € A1 (80 t) 15 €30 € A2 (40 t) 20€20 € A3 (45 t) 25 €
LagermengeLager 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

ErzeugnisDeckungsbeitrag je Stück (EUR)geplante, absetzbare Stückzahl
A8,40150.000
B6,60200.000
C10,80120.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-ProgrammMinimieren mit dem dualen Programm
 Pivotzeile 2/ Pivotspalte 1 
Pivotzeile 1/ Pivotspalte 2 

Minmieren mit Standardprogrammund NB als Gleichungen
minimize_lp( 6*x1 +x2 + 5*x3 + 4*x4 + 22*x5 + 3*x6, [ 5*x3 + 2*x4 + 2*x5 +x6 = 32, x2 +x3 + 3*x4 + 2*x5 = 40, x1 + 2*x3 -x4 + 2*x5 = 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

Lineare Optimierung von der grafischen zur rechnerischen Lösung (Simplex-Algorithmus)