[b][icon]/images/ggb/toolbar/mode_viewinfrontof.png[/icon][url=https://docs.google.com/spreadsheets/d/1gKxW9G7O550szURpzJLdSpxtVAfJFrt6kjItLmlyh_g/edit?usp=sharing]Grundlagen (Google Tab - Video)[br][/url][/b][url=https://www.geogebra.org/m/k3ngusuy][icon]/images/ggb/toolbar/mode_zoomin.png[/icon]Kommentiertes Aufgabenbeispiel[/url][br][br][b]Simplex-Standard-Tableau[/b][br]Maximiere Zielfunktion Z(x) mit NB<=b [br]- in Starttableau -Z(x) negativ in unterer Zeile.[br][color=#666666][size=85]Strukturvariablen oder Nichtbasisvasiablen x[sub]1[/sub],x[sub]2[/sub] ... x[sub]n[/sub] und s[sub]1[/sub] .. s[sub]n[/sub] die Basisvariablen[br]Gleichungssystem, beginnend mit den Nebenbedingungen [b]f(x)<= b[/b] (Ungleichungen f(x) >= b ggf. "Umdrehen zu" (-1)f(x) <= -b), ergänzt durch die Basisvariablen s[sub]i[/sub] (Schlupfvariablen) zu einer Gleichung. Letzte Zeile die Zielfunktion (negative Vorzeichen der Koeffizienten)![/size][/color][br]siehe [url=https://ggbm.at/Dnv36wMy]Simplex Algorithmus MAX Programm[/url][br][br]Minimiere Duales Programm Zielfunktion Z(x) mit NB>=b [br]- in Starttableau -b(x) negativ in unterer Zeile.[br][color=#666666][size=85]Überführung in ein duales Programm das mit dem Max-Simplex-Algorithmus bearbeitet werden kann. [br]Die Nebenbedingungen von Min Systemen müssen auf die Form[b] f(x) ≥ b[/b][/size][/color][color=#666666] gebracht werden. [br]Daten-Matrix, die transponiert wird (tausche Zeilen/Spalten). [br]Einfügen von Basis/Schlupfvariablen zum einem Max Programm transformieren. [/color][br]siehe [url=https://ggbm.at/nh4JwT7a]'Simplex Algorithmus Dual Min 2 Max[/url]'[br][br][color=#cc0000]If Inputbox cripples input - please use Tableau X Eingabe-Matrix - coefficients of LP as array[/color][br][br]Eigene Angaben zur Pivotwahl in PivotZeile/PivotSpalte [br][br][url=https://www.geogebra.org/m/mddHVdbM]Grafische Lösung bei 2 Variablen[/url][math]\longrightarrow[/math][br][br]Quellen[br][color=#444444][size=85]Aufgabe angelehnt an[br]http://www.aunda-net.de/homepage/schule/simplex/beispiel/beispiel.html[br]Simplex-Algorithmus[br]http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/A_blau/Simplex_Dokumentation.pdf[br]http://statistik.wu-wien.ac.at/~leydold/MOK/HTML/node145.html[br]http://www.unet.univie.ac.at/~a0025537/php/Abschnitt1/Mathe/fb_menue.html[br]https://www.zweigmedia.com/RealWorld/tutorialsf4/frames4_4.html[br][url=http://www.dma.ufv.br/maxima/index.php]wxMaxima on line[math]\nearrow[/math] load("simplex");[/url][br][/size][/color]

Pivotschritte (Algorithmus-Script.js)[br][list=1][*]wähle als Pivotspalte immer die Spalte mit dem kleinsten Eintrag in der Zielfunktionszeile.[br][/*][*]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.[br][/*][*]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![br][/*][/list][table][tr][td][size=85]maximize_lp([br]20*x1+15*x2+7*x3,[[br]x1-2*x2<=30,[br]3*x1+x2-5*x3<=47,[br]3*x2+x3=20,[br]x3<=5[br]]),numer;[br][556.6666666666666,[br][x3=5,x2=5.0,x1=22.33333333333333][br][br]1,-2,0,30; 3,1,-5,47; 0,3,1,20; 0,0,1,5; 20,15,7,0[br][size=85][color=#1155cc][Eingabe als Tableau X eintragen][br][Standard Programm für X erstellen][/color][/size][br][/size][/td][td][math]X=\left(\begin{array}{rrrrrrr}1&-2&0&1&0&0&30\\3&1&-5&0&1&0&47\\0&3&1&0&0&0&20\\0&0&1&0&0&1&5\\-20&-15&-7&0&0&0&0\\\end{array}\right)[/math][br][size=85][color=#1155cc][Simplex Schritt auf Matrix X ausführen][/color][/size][br]...[br][math]X=\left(\begin{array}{rrrrrrr}0&0&0&1&-0.333&-2.445&17.663\\1&0&0&0&0.333&1.778&\textcolor{red}{22.337}\\0&1&0&0&0&-0.333&\textcolor{red}{5}\\0&0&1&0&0&1&\textcolor{red}{5}\\0&0&0&0&6.667&37.555&\textcolor{red}{556.663}\\\end{array}\right)[/math][br][/td][/tr][/table] [br][math] \textcolor{blue}{\rule{10cm}{.4pt}}[/math]

[br][size=85][table][tr][td]minimize_lp([br]6*x1+2*x2-x3,[[br]2*x1+x2+x3[color=#cc0000][b]<=[/b][/color]60,[br]2*x1+x2-2*x3>=40,[br]2*x2+x3[color=#cc0000][b]<=[/b][/color]25[br]][br]), nonegative_lp=true, numer;[br][107.5,[br][x3=0,[br] x2=12.5,[br] x1=13.75]][br][br]-2,-1,-1,-60 ; 2,1,-2,40 ; 0,-2,-1, -25;6,2,-1,0[br][color=#1155cc][Eingabe als Tableau X eintragen][/color][br][br][br][br][/td][td][math]X=\left(\begin{array}{rrrr}-2&-1&-1&-60\\2&1&-2&40\\0&-2&-1&-25\\6&2&-1&0\\\end{array}\right)[/math][br][color=#1155cc][Duales Programm für Tableau X erstellen][/color][br][br][math]X=\left(\begin{array}{rrrrrrr}-2&2&0&1&0&0&6\\-1&1&-2&0&1&0&2\\-1&-2&-1&0&0&1&-1\\60&-40&25&0&0&0&0\\\end{array}\right) [/math][br][color=#1155cc][Simplex Schritt auf Matrix X ausführen][/color][br] ....[br][math]X=\left(\begin{array}{rrrrrrr}0&0&1&0.25&-0.5&0&0.5\\-1&1&0&0.5&0&0&3\\-3&0&0&1.25&-0.5&1&5.5\\20&0&0&\textcolor{red}{13.75}&\textcolor{red}{12.5}&\textcolor{red}{0}&\textcolor{red}{107.5}\\ \;&\;&\;&x_1&x_2&x_3&min\\\end{array}\right)[/math][br][/td][/tr][/table][/size][br][math] \textcolor{red}{\rule{10cm}{.4pt}}[/math][br]Weitere Beispiele sind in der Tabellen-Ansicht hinterlegt.

[table][tr][td][size=85]maximize_lp([br]-2*x1-2*x2-6*x3, [[br]-2*x1+2*x2 <= 20,[br]-2*x1+2*x3 <= [color=#0000ff]-24[/color], [br]2*x1-2*x2-3*x3 <= 16,[br]-4*x1+2*x2-2*x3 <=[color=#0000ff] -4[/color][br]])[br],[size=85]nonegative_lp=true;[/size] [br][-32,[x3=0,x2=4,x1=12][/size]][br]...[br][size=85]Zulassen neg. Koeffizienten[br][/size][size=85],[size=85]nonegative_lp=false; [/size] [/size][br][size=85][16,[x3=-6,x2=4,x1=6]][/size][br][br][size=85]-2, 2, 0, 20; -2, 0, 2, -24; 2, -2, -2, 16; -4, 2, -2, -4; -2, -2, -6, 0 [/size][br][size=85][[color=#3c78d8]Eingabe[/color][color=#ffffff]_[/color][color=#3c78d8]als[/color][color=#ffffff]_[/color][color=#3c78d8]Tableau[/color][color=#ffffff]_[/color][color=#3c78d8]X[/color][color=#ffffff]_[/color][color=#3c78d8]eintragen[/color]][/size][br][br][size=85]Die Zielfunktion (alle Koeffizieten positiv) und die [br]NB 2 und 4 (rechte Seite negatv) eignet sich nicht für einen [br]primalen Simplex. [br][/size][size=85][size=85][color=#1155cc][Standard Programm für Tableau X erstellen][/color][/size][/size][br][br][/td][td][size=85]Pivot-Spalte:= Berechne jede Spalte c[sub]j[/sub]/a[sub]zj[/sub], indem du jedes Element aus der Zielfunktionszeile durch das jeweilige Element in der Pivotzeile teilst [br]([size=85]Zielfunktion[size=85][size=85]/Pivot-Zeile[/size][/size][/size]). [br]Pivot-Spalte ist die Spalte mit dem größten, negativen Quotienten. [/size][br][math]X=\left(\begin{array}{rrrrrrrr}-2&2&0&1&0&0&0&20\\\minus\textcircled{2}&0&2&0&1&0&0&-24\\2&-2&-2&0&0&1&0&16\\-4&2&-2&0&0&0&1&-4\\2&2&6&0&0&0&0&0\\\end{array}\right)[br][/math][br][size=85]Pivotsuche:[size=85][b] PivotZeile=2[/b] kleinster negativer Koeffizent in b-Spalte. [/size] [br][b]PivotSpalte=1[/b] einstellen und [br][[color=#3c78d8]Simplex-Schritt ausführen[/color]] [/size][br][math]X=\left(\begin{array}{rrrrrrrr}0&2&-2&1&-1&0&0&44\\1&0&-1&0&\frac{-1}{2}&0&0&12\\0&\minus\textcircled{2}&0&0&1&1&0&-8\\0&2&-6&0&-2&0&1&44\\0&2&8&0&1&0&0&-24\\\end{array}\right)[/math][br][size=85]Pivotsuche: [size=85][b]PivotZeile=3[/b] [size=85][size=85]kleinster negativer Koeffizent in b-Spalte. [/size] [/size][/size][br] [b]PivotSpalte=2[/b] einstellen[br][[color=#3c78d8]Simplex-Schritt ausführen[/color]] [/size][br][math]X=\left(\begin{array}{rrrrrrrr}0&0&-2&1&0&1&0&36\\\textcolor{red}{1}&0&-1&0&\frac{-1}{2}&0&0&\textcolor{red}{12}\\0&\textcolor{red}{1}&0&0&\frac{-1}{2}&\frac{-1}{2}&0&\textcolor{red}{4}\\0&0&-6&0&-1&1&1&36\\0&0&8&0&2&1&0&-32\\\end{array}\right)[/math][br][size=85]Rechte Seite alles positiv, es kann mit dem Standard-Max-Programm weiter verfahren werden - wenn nötig[/size][size=85] (hier sind wir fertig, da alle Koeffizenten der Zielfunktion positiv!)[/size][br][/td][/tr][/table]

[table][tr][td][size=85]maximize_lp([br]2*x+3*y+z,[[br]x + y + z <= 40, [br]2*x + y - z [color=#cc0000][b]>=[/b][/color] 10, [br]-y + z [b][color=#cc0000]>=[/color][/b] 10 ][br]),no_negativ_lp=true;[br][70,[z=20,y=10,x=10]][br][br]1,1,1,40;2,1,-1,10;0,-1,1,10;2,3,1,0[br][[color=#3c78d8]Eingabe[/color][color=#ffffff]_[/color][color=#3c78d8]als[/color][color=#ffffff]_[/color][color=#3c78d8]Tableau[/color][color=#ffffff]_[/color][color=#3c78d8]X[/color][color=#ffffff]_[/color][color=#3c78d8]eintragen[/color]][br][br][/size][size=85]Mit dem Standard-Programm nicht lösbar. [br]Führe[color=#cc0000] negative Schlupfvariablen[/color] für die beiden nicht Standard Nebenbedingungen ein. [br][/size][size=85]Und führe für diese Zeilen mit neg. Schlupfvariablen die in folgenden[br]Schitten beschriebene Pivotbehandlung durch.[/size][br][br][br][br][br][/td][td][size=85][br][math]X=\left(\begin{array}{rrrrrrr}1&1&1&1&0&0&40\\\textcircled{2}&1&-1&0&\textcolor{red}{-1}&0&10\\0&-1&1&0&0&\textcolor{red}{-1}&10\\-2&-3&-1&0&0&0&0\\\end{array}\right) [/math][br]Pivotsuche: [b]PivotSpalte=1[/b] ist größte positive Zahl in der ersten Zeile der neg. Schlupfvariablen. [b]PivotZeile=2[/b] wie im Standard-Verfahren. Einstellen und [br][[color=#3c78d8]Simplex-Schritt ausführen[/color]] [br][math]X=\left(\begin{array}{rrrrrrr}0&0.5&1.5&1&0.5&0&35\\1&0.5&-0.5&0&-0.5&0&5\\0&-1&\textcircled{1}&0&0&-1&10\\0&-2&-2&0&-1&0&10\\\end{array}\right)[/math][br]Pivotsuche: [b]PivotSpalte=3[/b] ist größte positive Zahl in der zweiten Zeile der neg. Schlupfvariablen. [b]PivotZeile=3[/b] wie im Standard-Verfahren. Einstellen und [br][[color=#3c78d8]Simplex-Schritt ausführen[/color]] [br][math]X=\left(\begin{array}{rrrrrrr}0&2&0&1&0.5&1.5&20\\1&0&0&0&-0.5&-0.5&10\\0&-1&1&0&0&-1&10\\0&-4&0&0&-1&-2&30\\\end{array}\right)[/math][br]Weiter im Standard-Verfahren [[color=#1155Cc]Simplex-Schritt ausführen[/color]] [br][math]X=\left(\begin{array}{rrrrrrr}0&1&0&0.5&0.25&0.75&\textcolor{red}{10}\\1&0&0&0&-0.5&-0.5&\textcolor{red}{10}\\0&0&1&0.5&0.25&-0.25&\textcolor{red}{20}\\0&0&0&2&0&1&\textcolor{red}{70}\\\end{array}\right)[/math][br][/size][/td][/tr][/table]Im Eingabefeld der Startversion ist[br]Maximize p = -x1+2x2 [br]subject to x2 + x4 >= 4,-5x1+4x2+2x3 + 6x4 >= 15,-3x1 +2x2+x3+3x4<=8,2x1-x2-2x4 = -5 [br]hinterlegt - das Progamm kann mit dem hier beschriebenen Verfahren (z.B.S4Z2,S1Z1) gelöst werden:[br]siehe [url=https://www.zweigmedia.com/simplex/simplex.php?lang=en]Zweigmedia für Alternativen[/url][math]\nearrow[/math]...

[br]NB 2,3 erhalten eine negative Schlupfvariable und die Zielfunktion wird positiv ins Start-Tableau eingetragen[table][tr][td][size=85]minimize_lp(2*x+y+2*z,[ [br] x + 5*y + z <= 100,[br] x + 2*y + z >=50,[br] 2*x + 4*y + z >=80][br]), nonegative_lp=true;[br][size=85][50,[z=50/3,y=50/3,x=0]][/size] [br][br]Da die Minimierung von [size=85]2*x+y+2*z[/size] gleichbedeutend [br]mit der Maximierung von -[size=85]2*x-y-2*z[/size] ist, können wir [br]das obige Problem behandeln, indem, wir die [br]Zielfunktion positiv verwenden [br](also nicht wie beim Maximieren negativ eintragen).[br][br]Bei diesem Problem handelt es sich um ein [br]Maximierungsproblem mit gemischten [br]Einschränkungen,[br]d.h. die Schlupfvariablen der betroffenen NB [br]sind negativ einzusetzen und zuerst unter [br]Vorgabe der Pivots im Standardprogramm[br]zu behandeln.[br][br][br][/size][/td][td][size=85]1,5,1,100; 1,2,1,50; 2,4,1,80; 2,1,2,0[br][[color=#1155Cc]Eingabe als Tableau X eintragen[/color]][/size][br][size=85][[color=#1155Cc]Standardprogramm für Tableau X erstellen[/color]][/size][br][size=85]Schlupfvariablen ändern[/size][br][math]X = \left(\begin{array}{rrrrrrr}1&5&1&1&0&0&100\\1&2&1&0&-1&0&50\\2&4&1&0&0&-1&80\\2&1&2&0&0&0&0\\\end{array}\right)[/math][br][size=85]PivotZeile=3 Pivotspalte=2[/size][br][size=85][[color=#1155Cc]Simplex Schritt auf Matrix X ausführen[/color]][/size][br][math]X = \left(\begin{array}{rrrrrrr}-1.5&0&-0.25&1&0&1.25&0\\0&0&0.5&0&-1&0.5&10\\0.5&1&0.25&0&0&-0.25&20\\1.5&0&1.75&0&0&0.25&-20\\\end{array}\right)[/math][br][size=85]PivotZeile=2 Pivotspalte=3[/size][br][size=85][[color=#1155Cc]Simplex Schritt auf Matrix X ausführen[/color]][/size][br][math]X = \left(\begin{array}{rrrrrrr}-1.5&0&0&1&-0.5&1.5&5\\0&0&1&0&-2&1&20\\0.5&1&0&0&0.5&-0.5&15\\1.5&0&0&0&3.5&-1.5&-55\\\end{array}\right)[/math][br][size=85][[color=#1155Cc]Simplex Schritt auf Matrix X ausführen[/color]][/size][br][math]X = \left(\begin{array}{rrrrrrr}-1&0&0&0.667&-0.333&1&3.333\\1&0&\textcolor{red}{1}&-0.667&-1.667&0&\textcolor{red}{16.667}\\0&\textcolor{red}{1}&0&0.333&0.333&0&\textcolor{red}{16.667}\\0&0&0&1&3&0&-50\\\end{array}\right)[/math][br][/td][/tr][/table]

[i][size=85]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. [br]Raffinerie 2 kostet 25.000 Dollar pro Tag und kann 300 Barrel hochwertiges Öl, 400 Barrel Öl und 400 Barrel [/size][size=85][size=85]Öl mittlere Qualität[/size] und 500 Barrel minderwertiges Öl pro Tag produzieren.[br]Das Unternehmen hat Aufträge über insgesamt 25.000 Barrel hochwertiges Öl, 27.000 Barrel [size=85]Öl mittlere Qualität[/size] und 30.000 Barrel minderwertiges Öl. Kosten (Produktionstage) minimieren um den Auftrag zu erfüllen.[/size][/i][br][size=85]Minimize C= 20000*x1+25000*x2[br]Subject to: 400*x1+300*x2 >= 25000, 300*x1+400*x2 >= 27000, 200*x1+500*x2 >= 30000 x[sub]i[/sub] >= 0[br]400,300, 25000; 300,400,27000; 200,500,30000; 20000,25000,0[br][br]Minimize C= 12*x1+4*x2+2*x3[br]Subject to: -6*x1+3*x2 >= 9, 2*x1-2*x2-6*x3 <= -4, x[sub]i[/sub] >= 0[br]-6,3,0,9 ; -2,2,6,4 ; 12,4,2,0[br][br]Minimize C = 425*x1 + 525*x2 + 475*x3 + 500*x4 [br]Subject to: x1 + x2 <= 120, x3 + x4 <= 250, x1 + x3 >= 200, x2 + x4 >= 150, x[sub]i[/sub] >= 0[br]-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[/size]

Übersicht über Lagermengen, Mengenbedarf A1, A2, A3 und Transportkosten[br][br][table][tr][td]Lagermenge[/td][td][/td][td]Lager 1 (90 t)[/td][td][/td][td][/td][td][/td][/tr][tr][td]Transportkosten L1[br]Bedarf:[br]Transportkosten L2[/td][td]35 €[br]A1 (80 t)[br]15 €[/td][td]30 €[br] A2 (40 t)[br]20€[/td][td]20 €[br]A3 (45 t)[br]25 €[/td][td][/td][td][/td][/tr][tr][td]Lagermenge[/td][td][/td][td]Lager 2 (75 t)[/td][td][br][/td][td][/td][td][br][/td][/tr][/table][br][size=85]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[/size][br][table][tr][td][size=85]minimize_lp([br]35*x1+30*x2+20*x3+15*x4+20*x5+25*x6, [[br]x1+x4>80,[br]+x2+x5>=40,[br]+x3+x6>=45,[br](x1+x2+x3)<90,[br](x4+x5+x6)<=75[br]]), nonegative_lp=true;[br][3400,[x6=0,x3=45,x5=0,x2=40,x4=75,x1=5]][br][br][br][br][br][br][br][br][br][br][br][br][br][br][/size][/td][td][color=#1155Cc][size=85][Eingabe als Tableau X eintragen[/size][/color]] [br][math]\left(\begin{array}{rrrrrrr}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\\\end{array}\right)[/math][br][br][color=#1155Cc][size=85][Duales Programm für Tableau X erstellen][/size][/color][br][math]\left(\begin{array}{rrrrrrrrrrrr}1&0&0&-1&0&1&0&0&0&0&0&35\\0&1&0&-1&0&0&1&0&0&0&0&30\\0&0&1&-1&0&0&0&1&0&0&0&20\\1&0&0&0&-1&0&0&0&1&0&0&15\\0&1&0&0&-1&0&0&0&0&1&0&20\\0&0&1&0&-1&0&0&0&0&0&1&25\\-80&-40&-45&90&75&0&0&0&0&0&0&0\\\end{array}\right)[/math][br]...[br]...[br][color=#1155Cc][size=85][Simplex Schritt auf Matrix ausführen][/size][/color][br][math]\left(\begin{array}{rrrrrrrrrrrr}0&0&0&0&0&1&-1&0&-1&1&0&10\\0&0&0&-1&1&1&0&0&-1&0&0&20\\0&0&1&-1&0&0&0&1&0&0&0&20\\1&0&0&-1&0&1&0&0&0&0&0&35\\0&1&0&-1&0&0&1&0&0&0&0&30\\0&0&0&0&0&1&0&-1&-1&0&1&25\\0&0&0&0&0&5&40&45&75&0&0&3400\\\;&\;&\;&\;&\;&x_1&x_2&x_3&x_4&x_5&x_6&min \\\end{array}\right)[/math][br][/td][/tr][/table]

[br][table][tr][td]Erzeugnis[/td][br][td]Deckungsbeitrag je Stück (EUR)[/td][br][td]geplante, absetzbare Stückzahl[/td][/tr][br][tr][br][td]A[/td][br][td]8,40[/td][br][td]150.000[/td][/tr][br][tr][br][td]B[/td][br][td]6,60[/td][br][td]200.000[/td][/tr][br][tr][br][td]C[/td][br][td]10,80[/td][br][td]120.000[/td][/tr][/table][br]Die fixen Gesamtkosten betragen 180.000,- EUR.[br][br]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.[br][br]Bestimmen Sie unter den gennanten Bedingungen das optimale Produktionsprogramm und berechnen Sie das Betriebsergebnis[br][br][size=85][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][/size][br][table][tr][td][size=85]maximize_lp([br]8.4*a + 6.6*b + 10.8*c - 180000, [[br]a<=150000,[br]b<=200000,[br]c<=120000,[br]2.4*a + 1.5*b + 1.8*c <= 12400*60[br]]), nonegative_lp=true;[br][3234000.0,[c=120000,b=200000.0,a=95000.0]][br][br][br][/size][/td][td][size=85]X-Tableau[/size][br][math]\left(\begin{array}{rrrr}1&0&0&150000\\0&1&0&200000\\0&0&1&120000\\2.4&1.5&1.8&744000\\8.4&6.6&10.8&180000\\\end{array}\right)[/math][br][br][color=#1155Cc][size=85][Standard Programm für X-Tableau erstellen][/size][/color][br][math]\left(\begin{array}{rrrrrrrr}1&0&0&1&0&0&0&150000\\0&1&0&0&1&0&0&200000\\0&0&1&0&0&1&0&120000\\2.4&1.5&1.8&0&0&0&1&744000\\-8.4&-6.6&-10.8&0&0&0&0&-180000\\\end{array}\right)[/math][br][/td][td][/td][/tr][/table]

[table][tr][td][1,2,1,3; 2,-1,3,4; 2,3,4,0][br][size=85]minimize_lp([br] 2*x+3*y+4*z,[ [br] x + 2*y + z >= 3,[br] 2*x - y + 3*z >=4][br]), nonegative_lp=true;[br][28/5,[z=0,y=2/5,x=11/5]][/size][/td][td][br][br][br][br][br][br][/td][td][/td][/tr][/table][br][table][tr][td]Minimieren mit dem Standard-Programm[/td][td]Minimieren mit dem dualen Programm[/td][td][/td][/tr][tr][td][math]m1 \, := \, \left(\begin{array}{rrrrrr}1&2&1&1&0&3\\2&-1&3&0&1&4\\2&3&4&0&0&0\\\end{array}\right)[/math][br][size=85]Pivotzeile 2/ Pivotspalte 1[/size][/td][td][math]m1 \, := \, \left(\begin{array}{rrrrrr}1&2&1&0&0&2\\2&-1&0&1&0&3\\1&3&0&0&1&4\\-3&-4&0&0&0&0\\\end{array}\right)[/math][br][/td][td][/td][/tr][tr][td][math]m2 \, := \, \left(\begin{array}{rrrrrr}0&\frac{5}{2}&-\frac{1}{2}&1&-\frac{1}{2}&1\\1&-\frac{1}{2}&\frac{3}{2}&0&\frac{1}{2}&2\\0&4&1&0&-1&-4\\\end{array}\right)[/math][br][size=85]Pivotzeile 1/ Pivotspalte 2[/size][br][/td][td][math]m2 \, := \, \left(\begin{array}{rrrrrr}\frac{1}{2}&1&\frac{1}{2}&0&0&1\\\frac{5}{2}&0&\frac{1}{2}&1&0&4\\-\frac{1}{2}&0&-\frac{3}{2}&0&1&1\\-1&0&2&0&0&4\\\end{array}\right)[/math][br][/td][td][/td][/tr][tr][td][math]X \, := \, \left(\begin{array}{rrrrrr}0&\textcolor{red}{1}&-\frac{1}{5}&\frac{2}{5}&-\frac{1}{5}&\textcolor{red}{\frac{2}{5}}\\\textcolor{red}{1}&0&\frac{7}{5}&\frac{1}{5}&\frac{2}{5}&\textcolor{red}{\frac{11}{5}}\\0&0&\frac{9}{5}&-\frac{8}{5}&-\frac{1}{5}&-\frac{28}{5}\\\end{array}\right)[/math][br][/td][td][math]X \, := \, \left(\begin{array}{rrrrrr}0&\textcolor{red}{1}&\frac{2}{5}&-\frac{1}{5}&0&\textcolor{red}{\frac{1}{5}}\\\textcolor{red}{1}&0&\frac{1}{5}&\frac{2}{5}&0&\textcolor{red}{\frac{8}{5}}\\0&0&-\frac{7}{5}&\frac{1}{5}&1&\frac{9}{5}\\0&0&\frac{11}{5}&\frac{2}{5}&0&\frac{28}{5}\\\end{array}\right)[/math][br][/td][td][/td][/tr][/table][br][br][table][tr][td]Minmieren mit Standardprogramm[/td][td]und NB als Gleichungen[/td][/tr][tr][td][size=85]minimize_lp([br]6*x1 +x2 + 5*x3 + 4*x4 + 22*x5 + 3*x6, [[br]5*x3 + 2*x4 + 2*x5 +x6 = 32,[br]x2 +x3 + 3*x4 + 2*x5 = 40,[br]x1 + 2*x3 -x4 + 2*x5 = 15[br]]), [br]nonegative_lp=true;[/size][/td][td][size=85][394/5,[x1=11/5,x2=168/5,x3=32/5,x6=0,x5=0,x4=0]][/size][br][br][size=85]Zielfunktion positiv eintragen[br]Schlupfvariable = 0 setzen[/size][br][math]\left(\begin{array}{rrrrrrrrrr}0&0&5&2&2&1&0&0&0&32\\0&1&1&3&2&0&0&0&0&40\\1&0&2&-1&2&0&0&0&0&15\\6&1&5&4&22&3&0&0&0&0\\\end{array}\right)[/math][/td][/tr][tr][td]Geänderte Zeilen der Schlupf-[br]variablen abarbeiten[br]Pivotzeile 1/Pivotspalte 3[br][br][/td][td][math]\left(\begin{array}{rrrrrrrrrr}0&0&1&0.4&0.4&0.2&0&0&0&6.4\\0&1&0&2.6&1.6&-0.2&0&0&0&33.6\\1&0&0&-1.8&1.2&-0.4&0&0&0&2.2\\6&1&0&2&20&2&0&0&0&-32\\\end{array}\right)[/math] [br][/td][/tr][tr][td]Pivotzeile 2/Pivotspalte 4[br][/td][td][math]\left(\begin{array}{rrrrrrrrrr}0&-0.15&1&0&0.15&0.23&0&0&0&1.23\\0&0.38&0&1&0.62&-0.08&0&0&0&12.92\\1&0.69&0&0&2.31&-0.54&0&0&0&25.46\\6&0.23&0&0&18.77&2.15&0&0&0&-57.85\\\end{array}\right)[/math][/td][/tr][tr][td]Pivotzeile 3/Pivotspalte 5[/td][td][math]\left(\begin{array}{rrrrrrrrrr}-0.07&-0.2&1&0&0&0.27&0&0&0&-0.47\\-0.27&0.2&0&1&0&0.07&0&0&0&6.13\\0.43&0.3&0&0&1&-0.23&0&0&0&11.03\\-2.13&-5.4&0&0&0&6.53&0&0&0&-264.93\\\end{array}\right)[/math][/td][/tr][tr][td]Standardverfahren bis[br]Zielfunktion positiv[br][/td][td][math]\left(\begin{array}{rrrrrrrrrr}-0.33&0&1&1&0&0.33&0&0&0&5.67\\-1.33&1&0&5&0&0.33&0&0&0&30.67\\0.83&0&0&-1.5&1&-0.33&0&0&0&1.83\\-9.33&0&0&27&0&8.33&0&0&0&-99.33\\\end{array}\right)[/math][/td][/tr][tr][br] [td]X[/td][br] [td][math]\left(\begin{array}{rrrrrrrrrr}0&0&\textcolor{red}{1}&0.4&0.4&0.2&0&0&0&\textcolor{red}{6.4}\\0&\textcolor{red}{1}&0&2.6&1.6&-0.2&0&0&0&\textcolor{red}{33.6}\\\textcolor{red}{1}&0&0&-1.8&1.2&-0.4&0&0&0&\textcolor{red}{2.2}\\0&0&0&10.2&11.2&4.6&0&0&0&-78.8\\\end{array}\right)[/math][/td][br][/tr][br][/table]

Ein Papierfabrikant stellt Papierrollen mit einer Standardbreite von 105 cm und einer Länge von L cm her. Es liegen folgende Aufträge vor:[br]- 100 Rollen 25 cm breit,[br]- 124 Rollen 30 cm breit,[br]- 80 Rollen 35 cm breit.[br]Für die Aufträge werden Standardrollen zerschnitten. [br]Ziel ist die Minimierung der Schnittverluste.[br][br][i]Excel Solver[/i][br][math]\begin{array}{|r|r|r|r|r|r|r|r|r|r|}[br]\hline Längen & Anzahl & Schnittmuster & 105 & 105 & 105 & 105 & 105 & 105 & 105\\[br]\hline 25 & 100 & 100 & 4 & 3 & 1 & 0 & 0 & 0 & 1 \\[br]\hline 30 & 124 & 124 & 0 & 1 & 1 & 2 & 1 & 0 & 0 \\[br]\hline 35 & 80 & 80 & 0 & 0 & 1 & 1 & 2 & 3 & 2 \\[br]\hline &\; & \textcolor{red}{95} & \textcolor{red}{0} & \textcolor{red}{39} & \textcolor{red}{3} & \textcolor{red}{29} & \textcolor{red}{24} & 0 & 0 \\[br]\hline Waste & & & 5 & 0 & 15 & 10 & 5 & 0 & 10 \\[br]\hline {4 5 5} & & & 5 & 0 & 0 & 320 & 120 & 0 & 0\\[br]\hline [br]\end{array}[/math][br][br][size=85]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 [/size][br]Eingabe-Tableau[br][math]X=\left(\begin{array}{rrrrrrrr}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\\\end{array}\right)[/math][br][br]Duales Programm für Tableau X erstellen[br][math]\left(\begin{array}{rrrrrrrrrrr}4&0&0&1&0&0&0&0&0&0&5\\3&1&0&0&1&0&0&0&0&0&0\\1&1&1&0&0&1&0&0&0&0&15\\0&2&1&0&0&0&1&0&0&0&10\\0&1&2&0&0&0&0&1&0&0&5\\0&0&3&0&0&0&0&0&1&0&0\\1&0&2&0&0&0&0&0&0&1&10\\-100&-124&-80&0&0&0&0&0&0&0&0\\\end{array}\right)[/math][br][br][math]\left(\begin{array}{rrrrrrrrrrr}0&0&0&1&-1.231&0&0.615&0&0&-0.308&8.077\\1&0&0&0&0.308&0&-0.154&0&0&0.077&-0.769\\0&0&0&0&-0.231&1&-0.385&0&0&-0.308&8.077\\0&1&0&0&0.077&0&0.462&0&0&-0.231&2.308\\0&0&0&0&0.231&0&-0.615&1&0&-0.692&-8.077\\0&0&0&0&0.462&0&-0.231&0&1&-1.385&-16.154\\0&0&1&0&-0.154&0&0.077&0&0&0.462&5.385\\0&0&0&0&28&0&48&0&0&16&640\\\;&\;&\;&x_1&x_2&x_3&x_4&x_5&x_6&x_7&min \\\end{array}\right)[/math][br][br]Erreicht nicht das Ergebnis des Solvers braucht aber weniger Standard-Rollen (92)![br][br][url=http://www.dma.ufv.br/maxima/index.php?c=t30xi6uowodtrjn1n3lfu&n=10]wxMaxima[/url][math]\nearrow[/math][br][i]load("simplex");[br]minimize_lp([br] x1*5+x3*15+x4*10+x5*5+x7*10,[br][ x3 + x4+2*x5+3*x6+2*x7 = 80, [br] x2+x3+2*x4 +x5 = 125,[br]4*x1+3*x2+x3+x = 100,[br]x6=10,[br]x5=1,[br]x7=0[br]]),nonegative_lp=true, numer;[/i][br][505.0,[x1=4.0,x2=28,x7=0,x6=10,x5=1,x4=48,x3=0]][br]x6, x5, x7 schrittweise in mehreren Durchläufen festgelegt![br]