Management Science: Simplexverfahren

Im betriebswirtschaftlichen Kontext müssen in aller Regel Zielfunktionen optimiert werden. So werden etwa ein Gewinn oder ein Umsatz maximiert und Kosten minimiert. Das Anhängsel "-wirtschaft" weist daraufhin, dass mit knappen Ressourcen ein optimales Ergebnis erzielt werden soll. Die Zielfunktion soll also maximiert werden, obwohl ein ganzer Zoo von gemeinen Beschränkungen darauf wartet, dem Optimierer die Zunge zu zeigen.

Betrachten wir ein einfaches Beispiel:

Eine Produktionsstätte für biologischen Heimwerkerbedarf hat noch Kapazität übrig, und zwar 140 Liter Hartwachs und 40 Liter Leinöl. Es sollen damit Poliermittel produziert werden, nämlich Möbelpolitur und Bodenpolitur. Eine Dose Möbelpolitur benötigt unter anderem 4 Liter Hartwachs und 2 Liter Leinöl, und eine Dose Bodenpolitur entsprechend 5 Liter Hartwachs und 1 Liter Leinöl. Vom Bodenpflegemittel sollen vorerst nur maximal 25 Dosen angeboten werden. Für eine Dose Möbelpolitur werden ein Preis von 5 €, für die Bodenpolitur 4 € erzielt. Wir bezeichnen $x_1$ als die Menge des produzierten Möbelpflegemittels und $x_2$ als die Menge des produzierten Bodenpflegemittels.

	Möbelpflegemittel (Dose)	Bodenpflegemittel (Dose)	Beschränkung
	x1	x2
Hartwachs (l)	4	5	140
Leinöl (l)	2	1	40
Max. Angebot	-	25	25 für x2
Preis (€)	5	4

Wir fassen nun die Gegebenheiten formal zusammen. Unser Ziel ist es, den Umsatz zu maximieren. Wir erhalten die also die Zielfunktion und die Beschränkungen oder Restriktionen oder Nebenbedingungen:

Zielfunktion:Z = $5\cdot x_1+4\cdot x_2\to max$

Restriktionen:

• H: $4\cdot x_1+5\cdot x_2\le 140$
• L: $2\cdot x_1+1\cdot x_2\le 40$
• A: $x_2\le 25$

Nichtnegativitätsbedingungen:

$x_1;x_2\ge 0$

Wir haben noch die so genannten Nichtnegativitätsbedingungen dazugefügt, denn wir wollen ja keine negativen Produktionsmengen.

Man nennt diese Art der Konstellation das Standard-Maximum-Problem.

Grafische Lösung

Wir wollen zunächst einmal das Problem grafisch lösen. Dazu tragen wir die Ziefunktion und die Ungleichungen in ein Koordinatensystem ein. $x_1$ soll als Abszisse ("x-Achse") und $x_2$ als Ordinate ("y-Achse") abgetragen werden. Wir lösen die Ungleichungen nach $x_2$ auf:

Restriktionen:

• H: $x_2\le \frac{140}{5}-\frac{4\cdot x_1}{5}=28-\frac{4}{5}\cdot x_1$
• L: $x_2\le 40-2\cdot x_1$
• A: $x_2\le 25$. Hier ergibt sich eine waagerechte Gerade an der Stelle $x_2=25$.

Die Zielfunktion ist der Umsatz U. Wir haben also

$5\cdot x_1+4\cdot x_2=U$

und $x_2=\frac{U}{4}-\frac{5}{4}\cdot x_1$

Da die Zielfunktion maximiert werden soll, ist natürlich U zunächst nicht bekannt. Man kann aber aus der obigen Gleichung ersehen, dass die Steigung für alle Umsätze $-\frac{5}{4}$ ist. Zur Veranschaulichung können wir einen bestimmten Umsatz festlegen und dann eine Gerade skizzieren. Hier wurde ein Umsatz von 160 € vorgegeben. Wir erhalten so eine Funktion $x_2=\frac{160}{4}-\frac{5}{4}\cdot x_1=40-1,25\cdot x_1.$

Die Restriktionsungleichungen werden zunächst als Gleichungen eingetragen. $\le$ ist so aufzufassen, dass die Fläche unter der jeweiligen Geraden die Lösungsmenge der Ungleichung darstellt.

Wie sieht nun das gesamte realisierbare Produktionsprogramm aus? Überlegen wir:

Wollen wir das Wertepaar $(x_1;x_2)=(2;26)$ produzieren, werden die Restriktionen L und H erfüllt, aber es können nur maximal 25 Einheiten von $x_2$ verkauft werden. Also kommt diese Kombination nicht in Frage. Ebenso kann $(22;10)$ nicht realisiert werden, weil hier nicht genügend Leinöl zur Verfügung steht. Also können nur die Schnittmengen der Restriktionen realisiert werden. Die Nichtnegativitätsbedingen begrenzen die Lösungsmenge von unten. In der zweiten Grafik ist die zulässige Lösungsmenge durch ein Polygon dargestellt.

Wie ermittelt man nun das Optimum? In der dritten Grafik sind alternative Umsatzgeraden dargestellt. Betrachten wir die Gerade des Umsatzes 100. Alle Punkte auf der Geraden entsprechen einem Umsatz von 100 €. Wählen wir beispielsweise den Punkt $(10;12)$ Innerhalb der zulässigen Lösungen können wir $x_1$ und $x_2$ noch erhöhen, also den Umsatz steigern. Das Optimum liegt auf der Umsatzgerade, die gerade noch das Polygon berührt. Die optimale Produktionsmenge liegt also im Punkt $(10;20)$ und entspricht einem Umsatz von $10\cdot 5+20\cdot 4=130$.

Simplexalgorithmus

Das obige Beispiel ist klein und überschaubar, allerdings leider wenig realitätsnah. Zwei zu produzierende Güter ermöglichen eine grafische Lösung. Bei mehr als zwei Gütern versagt diese einfache Methode. Wir wollen nun eine analytische Lösungsmöglichkeit ins Visier nehmen, den Simplexalgorithmus. Um das System verarbeitbar zu machen, müssen zunächst die Ungleichungen der Restriktionen in Gleichungen überführt werden. Zu diesem Zweck führen wir so genannte Schlupfvariablen y ein:

Restriktionen:

• H: $4\cdot x_1+5\cdot x_2+y_1=140$
• L: $2\cdot x_1+1\cdot x_2+y_2=40$
• A: $x_2+y_3=25$

$y_1$ gibt beispielsweise an, wieviel Hartwachs bei vorgegebenem$x_1$ und $x_2$ noch verfügbar ist.

Für die konkrete Berechnung des Standardmaximierungsproblem müssen wir noch bei der Zielfunktion alle Variablen auf die linke Seite bringen, so dass sich ergibt

$Z-5\cdot x_1-4\cdot x_2=0.$

Nun sieht unser Optimierungsproblem so aus:

Zielfunktion: $Z\to max$ mit $Z-5\cdot x_1-4\cdot x_2=0.$

Restriktionen:

• H: $4\cdot x_1+5\cdot x_2+y_1=140$
• L: $2\cdot x_1+1\cdot x_2+y_2=40$
• A: $x_2+y_3=25$

Nichtnegativitätsbedingungen:

$x_1;x_2;y_1;y_2;y_3\ge 0$

bzw. genauer

Zielfunktion: $Z\to max$ mit $Z-5\cdot x_1-4\cdot x_2-0\cdot y_1-0\cdot y_2-0\cdot y_3=0.$

Restriktionen:

• H: $4\cdot x_1+5\cdot x_2+1\cdot y_1+0\cdot y_2+0\cdot y_3=140$
• L: $2\cdot x_1+1\cdot x_2+0\cdot y_1+1\cdot y_2+0\cdot y_3=40$
• A: $0\cdot x_1+1\cdot x_2+0\cdot y_1+0\cdot y_2+1\cdot y_3=25$

Nichtnegativitätsbedingungen:

$x_1;x_2;y_1;y_2;y_3\ge 0$

Im Wesentlichen reduziert sich das Problem auf ein lineares Gleichungssystem. Wir benötigen hier die Kenntnisse aus dem Kapitel Matrizen. Also wollen wir uns zunächst mal um eine formale Darstellung des obigen Simplexproblems bemühen:

Zielfunktion: $Z\to max$ mit $Z-c_1\cdot x_1-c_2\cdot x_2-c_3\cdot y_1-c_4\cdot y_2-c_5\cdot y_3$.

Restriktionen:

• $a_{11}\cdot x_1+a_{12}\cdot x_2+a_{13}\cdot y_1+a_{14}\cdot y_2+a_{15}\cdot y_3=b_1$
• $a_{21}\cdot x_1+a_{22}\cdot x_2+a_{23}\cdot y_1+a_{24}\cdot y_2+a_{25}\cdot y_3=b_2$
• $a_{31}\cdot x_2+a_{32}\cdot x_2+a_{33}\cdot y_1+a_{34}\cdot y_2+a_{35}\cdot y_3=b_3$.

Nichtnegativitätsbedingungen:

$x_1;x_2;y_1;y_2;y_3\ge 0$

Wir haben m = 3 Restriktionen und n+m Variablen $x$ und $y$. Wir fassen nun die $x_j$ und $y_i$ zu einem Spaltenvektor $\underset{\_}{x}$ mit (n+m) = 5 Elementen, die Restriktionen $b_i$ zum Vektor $\underset{\_}{b}$ mit m=3 Elementen und die $a_{ij}$ zur m×(n+m)-Koeffizienten-Matrix $\underset{\_}{A}$ zusammen. Zusätzlich werden noch die Koeffizienten der Zielfunktion zum Vektor $\underset{\_}{c}$ zusammengefasst.

Wir erhalten nun das Simplexproblem in Matrizenschreibweise als

Zielfunktion: ${\underset{\_}{c}}^T\cdot \underset{\_}{x}\to max$

Restriktionsgleichungen:

$\underset{\_}{A}\cdot \underset{\_}{x}=\underset{\_}{b}$

Nichtnegativitätsbedingungen:

$\underset{\_}{x}\ge \underset{\_}{0}$,

Wir werden in aller Regel eine große Koeffizientenmatrix $\underset{\_}{A}$ haben und sie wird meistens singulär sein, d.h. man kann sie nicht invertieren.

Das Simplex-Verfahren sucht die Ecken des Polytops ab, bis die optimale Lösung gefunden wird

Wir haben gesehen, dass in dem Beispiel mit zwei Gütern die Restriktionen, die ja lineare Gleichungen darstellen, ein Vieleck darstellen. Im höherdimensionalen Fall, wenn also mehr als zwei Güter im Optimierungsmodell sind, erhält man ein mehrdimensionales Vieleck, also ein so genanntes Polytop oder auch Simplex genannt. Die recht gelungene Grafik stellt einen Simplex in der dritten Dimension dar.

Wir werden nun anhand unseres Beispiels den Simplexalgorithmus durchrechnen. Die Schritte werden kommentiert. Die Vorgehensweise ist folgende: Ausgehend von einer Anfangslösung werden die Ecken des Polygons in Bezug auf ihr Optimierungspotenzial untersucht. Es werden zuerst die Ecken untersucht, die den größten Beitrag zur Zielfunktion leisten und deren Restriktionen am schärfsten sind.

Simplexalgorithmus

Die Ausgangslösung entspricht dem Gleichungssystem mit der Koeffizientenmatrix wie oben angegeben. Für die praktische Berechnung - etwa mit Hilfe des Tableaus - wird nun noch die Zielfunktion mit $\underset{\_}{A}$ zur Matrix ${\underset{\_}{A}}_c$ zusammengefasst, und zwar folgendermaßen:

${\underset{\_}{A}}_c=\left(\begin{array}{cc}\underset{\_}{A}& \underset{\_}{o}\\ {\underset{\_}{c}}^T& 1\end{array}\right)$,

mit $\underset{\_}{o}$ als Spaltenvektor der Ordnung m, und den Restriktionen fügen wir entsprechend noch die Null als aktuellem Wert der Zielfunktion bei,

${\underset{\_}{b}}_c=\left(\begin{array}{c}\underset{\_}{b}\\ 0\end{array}\right)$.

Mit unserem Beispiel sieht das so aus:

$\left(\begin{array}{cccccc}4& 5& 1& 0& 0& 0\\ 2& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ -5& -4& 0& 0& 0& 1\end{array}\right)\cdot \left(\begin{array}{c}{x}_1\\ x_2\\ y_1\\ y_2\\ y_3\\ Z\end{array}\right)=\left(\begin{array}{c}140\\ 40\\ 25\\ 0\end{array}\right).$

Das entspricht dem Gleichungssystem

Restriktionen:

H: $4\cdot x_1+5\cdot x_2+1\cdot y_1+0\cdot y_2+0\cdot y_3+0\cdot Z=140$

L: $2\cdot x_1+1\cdot x_2++0\cdot y_1+1\cdot y_2+0\cdot y_3+0\cdot Z=40$

A: $0\cdot x_1+1\cdot x_2+0\cdot y_1+0\cdot y_2+1\cdot y_3+0\cdot Z=25$

Z: $-5\cdot x_1+-4\cdot x_2+0\cdot y_1+0\cdot y_2+0\cdot y_3+1\cdot Z=0$

Was bedeutet das nun? Wir haben 6 Variablen und 4 Gleichungen. Erinnern wir uns an die Basislösungen im kanonischen System: Wenn es mehr Variablen als Gleichungen gibt, können wir einen Teil der Variablen mit Hilfe der anderen ausdrücken. Wir erhalten eine Basislösung. Die spezielle Basislösung ergibt sich, wenn man letztere Variablen Null setzt. Wir stellen die Gleichungen um,

$y_1=140-4\cdot x_1-5\cdot x_2$

$y_2=40-2\cdot x_1-x_2$

$y_3=25-x_2$

$Z=5\cdot x_1+4\cdot x_2$,

und setzen Null:

$x_1=0$ $x_2=0$: Es wird noch nichts produziert.

$y_1=140$: Es sind noch 140 l Hartwachs vorhanden.

$y_2=40$: Es sind noch 40 l Leinöl vorhanden.

$y_3=25$: Es ist noch nichts verkauft worden.

$Z=0$. Der Umsatz ist noch Null.

Im Polygon entspricht das dem Koordinatenursprung. Das System ist ohne Zweifel verbesserungsfähig. Wir wollen händisch weiterrechnen. Hier empfiehlt sich die Verwendung eines Tableaus:

Wir starten mit der Anfangslösung:

         x1   x2  y1  y2  y3   Z |  b
H |y1|    4    5   1   0   0   0 | 140       
L |y2|    2    1   0   1   0   0 |  40  
A |y3|    0    1   0   0   1   0 |  25     
---------------------------------------- 
Z |      -5   -4   0   0   0   1 |   0

Wir erkennen in der Mitte die Matrix $A_c$. Ganz links ist die Legende der Zeile. Es folgt dann der Name der Variable, die in der Basislösung ist, hier die drei y-Variablen. In der Zeile sind zur Information die Bezeichnungen der Spalten angegeben.

Wie können wir das System verbessern? Betrachten wir die Zeile Z. Als Gleichung ausgedrückt ergibt sich $Z=5x_1+4x_2$. Das Gut 1 trägt mit einem Preis von 5 € am meisten zum Umsatz bei, ist also am attraktivsten.

Wieviel können wir maximal davon herstellen? Für eine Dose Möbelpolitur brauchen wir 4 l Hartwachs und 2 l Leinöl. Bei 140 l Hartwachs können also maximal 140/4 = 35 Dosen hergestellt werden. Bei 40 l Leinöl sind es maximal 40/2 = 20 Dosen. Also ist Leinöl die strengere Restriktion, wir visieren zunächst 20 Dosen Möbelpolitur an. Man ermittelt im Tableau die Engpässe so, dass ganz rechts in der Spalte q die Elemente der Spalte b zeilenweise durch die Elemente der Spalte $x_1$ dividiert werden.

         x1   x2  y1  y2  y3   Z |  b  | q
H |y1|    4    5   1   0   0   0 | 140 | 140/4=35       
L |y2|    2    1   0   1   0   0 |  40 |  40/2=20  
A |y3|    0    1   0   0   1   0 |  25 |  -     
---------------------------------------- 
Z |      -5   -4   0   0   0   1 |   0 |

Wir befassen uns also mit der Spalte $x_1$, der Pivotspalte, mit der zweiten Zeile L, der Pivotzeile. Das Element im Schnittpunkt, also 2, ist das Pivotelement. Nun suchen wir die entsprechende Ecke des Polygons auf. Wir bringen die Produktion von $x_1=20$ in das System ein, d.h. die Variable $x_1$ wird in die Basislösung eingebracht, also auf Eins gesetzt. Dafür wird $y_1$ aus der Basislösung entfernt, d.h. diese Variable wird 0 gesetzt. Die restlichen Elemente der Pivotspalte sollen Null werden. Im Matrizenkalkül wird das mit Hilfe der elementaren Zeilentransformationen erreicht. Wir wandeln also die Pivotspalte in einen Einheitsvektor um und erhalten:

         x1   x2  y1  y2  y3   Z |  b  
H |y1|    0    3   1  -2   0   0 |  60
L |x1|    1    0,5 0   0,5 0   0 |  20 
A |y3|    0    1   0   0   1   0 |  25 
--------------------------------------------- 
Z |       0   -1,5 0   2,5 0   1 | 100

Wir analysieren das Zwischenergebnis: Die Nichtbasisvariablen sind Null:

$x_2=0$ Von $x_2$ wird noch nichts produziert.

$y_2=0$ Es ist kein Leinöl mehr übrig.

Die Einheitsvektoren repräsentieren die Variablen in der Basislösung:

$x_1=20$ Es werden 20 Dosen Möbelpolitur hergestellt.

$y_1=60$ Es sind noch 60 l Hartwachs übrig

$y_3=25$ Das Verkaufskontingent für Bodenpolitur ist noch nicht angetastet.

$Z=100$ Es wird ein Umsatz von 100 € erzielt.

Grafisch befinden wir uns in dem Punkt (20; 0).

Ist das System verbesserungsfähig? Die Gleichung Z ergibt

$Z=100+1,5x_2-2,5y_2$

Gut 2 trägt noch positiv zur Zielfunktion bei. $x_2$ wird also neue Basisvarible. $y_2$ ist unproduktiv und bleibt daher Nichtbasisvariable. Wir ermitteln die Engpässe für $x_2$. Es stellt sich heraus, dass der Engpass bei 20 l Hartwachs liegt.

         x1   x2  y1  y2  y3   Z |  b  | q
H |y1|    0    3   1  -2   0   0 |  60 | 60/3 = 20
L |x1|    1    0,5 0   0,5 0   0 |  20 | 20/0,5 = 40
A |y3|    0    1   0   0   1   0 |  25 | 25/1 = 25
--------------------------------------------- 
Z |       0   -1,5 0   2,5 0   1 | 100

Es wird also $x_2$ Pivotspalte und $a_{12}$ das neue Pivotelement. $x_2$ wird mit elementaren Zeilenumformungen zu einem Einheitsvektor umgeformt:

         x1   x2    y1  y2  y3  Z |  b  
H |x2|    0    1   1/3 -2/3  0  0 |  20
L |x1|    1    0  -1/6  5/6  0  0 |  10
A |y3|    0    0  -1/3  2/3  1  0 |   5
---------------------------------------- 
Z |       0    0   1/2  3/2  0  1 | 130

Wir analysieren das Ergebnis:

Die Nichtbasisvariablen sind Null:

$y_1,y_2=0$ Vom Leinöl und Hartwachs ist nichts mehr übrig.

Variablen in der Basislösung:

$x_1=10$ Es werden nun 10 Dosen Möbelpolitur hergestellt.

$x_2=20$ Es werden 20 Dosen Bodenpolitur hergestellt.

$y_3=5$ Im Verkaufskontingent sind noch 5 Dosen von Gut 2 nicht ausgeschöpft.

Grafisch befinden wir uns in dem Punkt (10; 20).

Ist das System verbesserungsfähig? Die Gleichung Z ergibt

$Z=130-0,5y_1-1,5y_2$.

Da die y-Werte positiv sind, würde jede weitere Änderung die Zielfunktion verringern. Also ist das Optimum erreicht.

Interpretation der Koeffizienten in der Lösung

         x1   x2    y1  y2  y3  Z |  r  
H |x2|    0    1   1/3 -2/3  0  0 |  20
L |x1|    1    0  -1/6  5/6  0  0 |  10
A |y3|    0    0  -1/3  2/3  1  0 |   5
---------------------------------------- 
Z |       0    0   1/2  3/2  0  1 | 130

Wir analysieren das Ergebnis: Die Nichtbasisvariablen sind Null:

$y_1,y_2=0$ Vom Leinöl und Hartwachs ist nichts mehr übrig.

Variablen in der Basislösung:

$x_1=10$ Es werden nun 10 l Möbelpolitur hergestellt. $x_2=20$ Es werden 20 l Bodenpolitur hergestellt. $y_3=5$ Im Verkaufskontingent sind noch 5 l von Gut 2 nicht ausgeschöpft.

Grafisch befinden wir uns in dem Punkt (10; 20).

$x_2=20-\frac{1}{3}{y}_1+\frac{2}{3}{y}_2$

$x_1=10+\frac{1}{6}{y}_1-\frac{5}{6}{y}_2$

$y_3=5+\frac{1}{3}{y}_1-\frac{2}{3}{y}_2$

$Z=130-\frac{1}{2}{y}_1-\frac{3}{2}{y}_2$

Setzen wir $y_1=1$. Was passiert jetzt? Es wird ein Liter Hartwachs weniger verbraucht. Wir haben nun $x_2=20-\frac{1}{3}\cdot 1+\frac{2}{3}{y}_2$. Bei unverändertem $y_2=0$ sinkt $x_2$ um 1/3, es kann dann also 1/3 l weniger Bodenpflegemittel hergestellt werden. Stattdessen kann aber 1/6 l Möbelpflegemittel mehr hergestellt werden. Man nennt diese Koeffizienten Substitutionskoeffizienten. Sie geben an, wie sich das Produktionsprogramm ändert, wenn man eine Nichtbasisvariable ceteris paribus verändert (ceteris paribus bedeutet: Alle anderen Variablen bleiben in der Analyse unverändert).

Wenn die Produktion von $x_2$ um 1/3 zurückgeht, wird natürlich die nichtausgenutzte Absatzkapazität um 1/3 erhöht.

Diese Substitutionskoeffizienten können direkt im fertigen Simplextableau abgelesen werden: In der Spalte von $y_1$ finden sich in der entsprechenden Zeile die Auswirkungen auf die betreffende Basisvariable.

Auf die Zielfunktion wirkt sich bei einem Literpreis von 5€ für das erste Gut und 4 € für das zweite Gut die Änderung so aus: $5\cdot \frac{1}{6}-4\cdot \frac{1}{3}=\frac{5}{6}-\frac{8}{6}=-\frac{1}{2}$.

Das findet sich in der Gleichung

$Z=130-\frac{1}{2}{y}_1-\frac{3}{2}{y}_2$

Also bezeichnen die Koeffizienten in der Zielfunktionszeile die Änderung der Zielfunktion, wenn eine Nichtbasisvariable um eine Einheit erhöht wird. Wird also ein Liter Hartwachs weniger verwendet, sinkt Umsatz um 50 Cents, wird ein Liter Leinöl weniger verwendet, sinkt der Umsatz um 1,50 €. Man nennt diese Koeffizienten Schattenpreise oder Opportunitätskosten, denn sie zeigen an, wieviel man verliert, wenn eine Einheit der Nichtbasisvariablen anderweitig investiert wird.

Sensibilitätsanalyse

Als Sensibilitätsanalyse bezeichnet man im Zusammenhang mit dem Simplexalgorithmus die Auswirkung einer Zielfunktionsänderung auf die optimale Lösung.

Wir wollen nun den Preis des Gutes 2 mal ordentlich anheben, und zwar auf 8 Euros. Die Grafik zeigt uns nun, was passiert. Die alte Zielfunktion betrug

$5\cdot x_1+4\cdot x_2=U$, was umgeformt ergab $x_2=\frac{U}{4}-\frac{5}{4}\cdot x_1.$

Die Steigung der Umsatzgeraden betrug

$-\frac{5}{4}=-1,25$

, wie man der Geraden unmittelbar ansieht. Die Umsatzgerade berührte die Ecke (10; 20) als optimale Lösung. Die neue Zielfunktion beträgt nach der Preiserhöhung

$5\cdot x_1+8\cdot x_2=U$

und $x_2=\frac{U}{8}-\frac{5}{8}\cdot x_1$.

Wir sehen, dass sich die Gerade nach oben gedreht hat, ihre Steigung ist gewachsen, sie beträgt jetzt $-\frac{5}{8}=-0,25$. Sie berührt jetzt die Menge der zulässigen Lösungen im Punkt (3,75 und 25). Wir erhalten einen Umsatz von

$5\cdot 3,75+8\cdot 25=218,75.$

Hätten wir das alte Produktionsprogramm aufrechterhalten, würden wir lediglich

$5\cdot 10+8\cdot 20=210$ Euros verdienen.

Wir wollen nun die Gerade etwas absenken, etwa mit einem Preis von Gut 2 von 7,5. Als Steigung der Geraden ergibt sich nun $-\frac{5}{7,5}=-\frac{2}{3}-0,67$. Diese Gerade berührt immer noch den Punkt (3,75; 25).

Wir senken weiter bis zu einem Preis p2 von 6,25 Euro. Die Steigung ist nun $-\frac{5}{6,25}=-0,8$. Wir sehen, dass jetzt die Gerade mit der ersten Restrikionsgeraden

$4\cdot x_1+5\cdot x_2\le 140$

zusammenfällt. Wir können also speziell bei diesem Preis alle Kombinationen auf dem zulässigen Abschnitt der Geraden

$U=5\cdot x_1+6,25\cdot x_2$

realisieren. Wenn wir den Preis weiter senken, dreht sich die Gerade noch mehr nach unten und berührt nun wieder den Punkt (10; 20). Das aktuelle optimale Produktionsprogramm ist also abhängig von den Steigungen der Umsatzgeraden und Restriktionsgeraden.

Ablauf des Simplexalgorithmus im Simplextableau

Ausgangsposition

$\begin{array}{cccccccccc}{a}_{11}& a_{12}& \dots & a_{1n}& 1& 0& \dots & 0& 0& b_1\\ a_{21}& a_{22}& \dots & a_{2n}& 0& 1& \dots & 0& 0& b_2\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& b_i\\ a_{m1}& a_{m2}& \dots & a_{mn}& 0& 0& \dots & 1& 0& b_m\\ -c_1& -c_2& \dots & -c_n& 0& 0& \dots & 0& 1& 0\end{array}$

1. Schritt:

1. Es wird zunächst der negative Wert $-c_k$ in der Zielfunktionszeile gesucht, für den $|c_j|$ maximal wird. Diese Spalte k ist die Pivotspalte.
2. Es werden die Engpässe ermittelt als $q_i=b_i/a_{ik}$. Die Zeile r, für die der Quotient minimal wird, ist die neue Pivotzeile. Das Element $a_{rk}$ ist Pivotelement.
3. Die Pivotspalte j wird mit Hilfe der elementaren Zeilenoperationen, die neben allen $a_{ij}$ auch $b_j$ tangieren, in einen Einheitsvektor mit der Eins im Pivotelement umgeformt.
4. Sind keine negativen Koeffizienten der Zielfunktion mehr vorhanden, ist keine weitere Verbesserung des Systems möglich. Falls doch, geht man zum nächsten Schritt über.

Nächster Schritt:

1. Es wird der negative Wert $c_k$ in der Zielfunktionszeile gesucht, für den $|c_j|$ maximal wird. Diese Spalte k ist die Pivotspalte.
2. Es werden die Engpässe ermittelt als $q_i=b_i/a_{ik}$. Die Zeile r, für die der Quotient minimal wird, ist die neue Pivotzeile. Das Element $a_{rk}$ ist Pivotelement.
3. Die Pivotspalte j wird mit Hilfe der elementaren Zeilenoperationen, die neben allen $a_{ij}$ auch $b_j$ tangieren, in einen Einheitsvektor mit der Eins im Pivotelement umgeformt.
4. Sind keine negativen Koeffizienten der Zielfunktion mehr vorhanden, ist keine weitere Verbesserung des Systems möglich. Falls doch, geht man zum nächsten Schritt über.

Bemerkungen:

Eine Variable, deren Spalte k Einheitsvektor ist, befindet sich in der Basislösung. Hier kann das Ergebnis in der Zeile r des Pivotelements direkt abgelesen werden: $x_k=b_r$.

Für Variablen, deren Spalten keine Einheitsvektoren sind, gilt: $x_j=0$.

Bei der Berechnung des Engpasses werden Ergebnisse, die negativ oder Null geworden sind, außer acht gelassen.

Navigation

↓ ??

↑ Lineare Gleichungssysteme

↑↑ Inhaltsverzeichnis Management Science