Lineare Optimierung am Beispiel des optimalen Produktionsprogramms


Die folgende Darstellung ergänzt und erweitert das Kapitel „5.4.3 Optimales Produktionsprogramm“ aus dem Werk „Schmolke/Deitermann; Industrielles Rechnungswesen – IKR“. Sie kann auch ohne Rückgriff auf das genannte Buch als Unterstützung bei der Lösung linearer Optimierungsprobleme genutzt werden.
 
Lineare Optimierungsprobleme sind dadurch gekennzeichnet, 

  • dass sie auf einem linearen (Un-)Gleichungssystem beruhen, das eine bestimmte Lösungsmenge umschließt,
  • dass sie zu ihrer Lösung eine Zielfunktion benötigt, über die das angestrebte Optimum gefunden werden kann.
1. Welche optimalen Mengen von G1 und G2 lassen sich unter den obigen Bedingungen herstellen?
2. Wie hoch ist der Gesamtdeckungsbeitrag im Optimum?

Im obigen Beispiel ist aus den Arbeitsgängen und den Kapazitätsbegrenzungen das (Un-)Gleichungssystem zu bilden. Aus den Stückdeckungsbeiträgen lässt sich die Zielbedingung formulieren.Für die Lösung des Systems werden im Folgenden drei Varianten vorgestellt:

  • Grafische Lösung (1.)
  • Lösung durch Schnittpunktberechnung (2.)
  • Mathematische Lösung mithilfe der Simplex-Methode (3.).

1. Grafische Lösung


Um eine grafische Lösung zu ermöglichen, ist im obigen Beispiel das Produktionsprogramm auf zwei Gerätetypen (G1, G2) beschränkt (entsprechend der beiden Achsen x1 und x2 im Koordinatensystem). Die Herstellungsmenge von G1 wird mit x1 bezeichnet, die Herstel-lungsmenge von G2 mit x2
 
Die grafische Lösung ergibt sich aus folgenden Überlegungen: 
 
  • Zulässige Lösungen gelten nur für x1 ≥ 0 und x2 ≥ 0, d. h. im Koordinatensystem mit der waagerechten Achse (Abszisse) x1 und der senkrechten Achse (Ordinate) x2 liegen Lö-sungen nur im 1. Quadranten (Nichtnegativbedingung)
  • Die Lösungsmenge wird innerhalb des 1. Quadranten nach oben durch ein Gleichungssystem begrenzt, das sich aus den Produktionsangaben erstellen lässt (Restriktionsbedingungen). Die gesuchte Lösung liegt also in einem Schnittpunkt der Randgleichungen. 
  • Aus den Stückdeckungsbeiträgen wird eine Zielfunktion gebildet, mit deren Hilfe sich entlang der Randgleichungen die optimale Lösung bestimmen lässt (Zielbedingung).
 
Die Lösung vollzieht sich in folgenden Schritten:

1.1 Bildung eines Ungleichungssystem
 
Um die gesamte Lösungsmenge zu erfassen, ist zunächst aus den im Beispiel gemachten Aussagen ein Ungleichungssystem zu erstellen:
1.2 Bildung der Randgleichungen

Das Ungleichungssystem (≦) schließt die Gleichungen (=) als Randbedingungen mit ein. Die Gleichungen bilden das unten angegebene Gleichungssystem, das die zulässigen optimalen Lösungen enthält.
Zur grafischen Darstellung ist es hilfreich, die Restriktionsgleichungen nach x2 umzustellen, und sie damit in die Funktionsform zu bringen:
1.3 Darstellung der Randgleichungen im Koordinatensystem

Die linearen Randgleichungen S, B und M lassen sich aus ihren jeweiligen Schnittpunkten mit der x1-Achse und der x2-Achse konstruieren:
1.4 Darstellung des Lösungsfeldes (Lösungsmenge)
 
Alle zulässigen Lösungen unter den Bedingungen des Ungleichungssystems (siehe 1.1) liegen im ersten Quadranten unterhalb der Randgleichungen und auf den Randgleichungen. Das Lösungsfeld ist begrenzt 
 
• durch die x1-Achse für x1 ≥ 0 
• durch die x2-Achse mit x2 ≥ 0 
• nach oben durch die Verbindungslinie der Punkte C – F – E – D.
 
1.5 Graphische Ermittlung des Optimums
 
In das Koordinatensystem wird die Zielgleichung 16x1 + 28x2 = Z für Z = 0, also für das denkbar schlechteste Ergebnis, eingezeichnet. 
 
Für Z = 0 gilt:

   16x1 + 28x2 = 0 
↔ 28x2 = 16x1 
↔    x2 = –4/7x1 (grüner Ursprungsgraph, parallel verschoben)
 
Für Z = 0 geht der Zielgraph mit der Steigung m = –4/7 durch den Ursprung. Anschließend wird dieser Graph parallel bis zum äußersten Punkt des Lösungsfelds verschoben; in der Regel ist das der Schnittpunkt zweier Graphen. Die Koordinaten dieses Schnittpunktes stellen die optimale Lösung dar.
 
Aus dem grafischen Bild lässt sich die optimale Lösung im Punkt F ablesen.
  
x1 = 200 
x2 = 350 
F (200; 350)
 
Die optimale Lösung besagt, dass von Gehäuse G1 200 Stück herzustellen sind und von G2 350 Stück. 
 
Der Deckungsbeitrag (DB) beläuft sich im Optimum auf: 
DB = (16,00 € ⦁ 200 Stück) + (28,00 € ⦁ 350 Stück) = 13.000,00 €
 
Die wirtschaftliche Interpretation der graphischen Lösung besagt, dass das Optimum im Schnittpunkt der beiden Graphen B und M liegt, d. h., die beiden Arbeitsgänge Biegen (B) und Montieren (M) sind die für die Lösung einschränkenden Bedingungen. Der dritte Arbeitsgang Stanzen (S) verfügt über genügend freie Kapazität.
 
Sollte die Zielgerade parallel zu einer der Randgeraden verlaufen, so lässt sich keine eindeu-tige optimale Lösung feststellen; es gibt dann eine Vielzahl gleichwertiger Lösungen, die alle von einer einzigen Restriktion begrenzt werden.

2. Lösung durch Schnittpunktberechnung


Zur obigen Lösung kann man auch kommen, wenn die Schnittpunkte der einzelnen Graphen untereinander sowie die Schnittpunkte der Graphen mit der x1-Achse und der x2-Achse nach und nach berechnet werden. Hierbei ist zu prüfen, ob der jeweilige Schnittpunkt innerhalb der Lösungsmenge liegt und in welchem zulässigen Schnittpunkt sich der größte Wert für den Deckungsbeitrag ergibt:
Aus der obigen grafischen Darstellung ist ersichtlich, dass es insgesamt neun Schnittpunkte gibt, davon sechs Schnittpunkte der Graphen mit den Achsen (A, B, C, D, G, H) und drei Schnittpunkte der Graphen untereinander (E, F, I). Folgende Schnittpunkte der Graphen mit den Achsen liegen oberhalb der Lösungsmenge, gehören also nicht zur Lösung: (A, B, G, H), ebenso der Schnittpunkt I. Unter den verbleibenden Schnittpunkten (C, D, E, F) ist der optimale Wert zu berechnen. 
 
Für den Schnittpunkt C gilt z. B. x1 = 0. Der Wert 0 für x1 in die zweite Gleichung eingesetzt, führt zu x2 = 450. Das Zielergebnis (DB) errechnet sich dann:
 
(16 ⦁ 0) + (28 ⦁ 450) = 12.600
 
Nach dieser Rechnung werden die übrigen zur Lösungsmenge gehörenden Schnittpunkte untersucht. Der optimale Wert ergibt sich, wenn von Gehäuse G1 200 Stück und von Gehäuse G2 350 Stück produziert und verkauft werden; der Deckungsbeitrag hat bei diesen Mengen einen Wert von 13.000,00 €. 
 
Interpretation der Lösung:
 
Die optimale Lösung findet sich im Schnittpunkt F der beiden Gleichungen
 
x2 = -0,75x1 + 500 
x2 = -0,5x1 + 450
 
Die zu diesen Gleichungen gehörenden Restriktionen werden voll ausgenutzt:
 
B 15x1 + 30x2 = 13.500 ⇒ (15 ⦁ 200) + (30 ⦁ 350) = 13.500
M 30x1 + 40x2 = 19.500 ⇒ (30 ⦁ 200) + (40 ⦁ 350) = 20.000
 
Die einschränkende Bedingung (Restriktionsbedingung) S   24x1 + 20x2 = 14.400 (in Funktionsform geschrieben x2 = –1,2x1 + 720) verfügt über hinreichende Kapazität und beeinflusst daher nicht die Lösung. 

3. Mathematische Lösung mithilfe der Simplex-Methode


Die mathematische Lösung geht vom ursprünglichen Ungleichungssystem aus:
Um das Restriktionssystem in ein Gleichungssystem zu überführen, werden in jede Ungleichung sog. Schlupfvariable si (= Hilfsvariable) eingefügt, die positiv und so groß gewählt werden, dass Gleichungen entstehen:
In die Zielbedingung wird für Z die Lösungsvariable x0 eingefügt. Die Zielgleichung lautet dann:
Die Einfügung der Schlupfvariablen si und der Lösungsvariablen x0 hat den Zweck, eine Ausgangslösung zu erhalten, in der die Schlupfvariablen s1, s2, s3 als Lösungsvariable eingesetzt werden. Das obige Gleichungssystem hat die Lösung:
In diesem Gleichungssystem hat z. B. die Schlupfvariable s1 den Wert 14.400, d. h., in der Ausgangslösung werden 14.400 Minuten nicht genutzt, oder anders ausgedrückt: Die verfügbare Kapazität wird überhaupt nicht genutzt. Die übrigen Schlupfvariablen geben an, dass auch bei ihnen nicht genutzte Kapazitäten vorliegen. Die gesuchten Variablen x1, x2 nehmen in der Ausgangslösung den Wert 0 an. Entsprechend ist der Zielwert x0 ebenfalls gleich 0.

Zur Lösung des Gleichungssystems wird das sog. Simplextableau verwendet. Es ist eine Tabelle, die für jede Variable eine Spalte – zusätzlich eine „Wert“-Spalte – aufweist. In die Kopfzeile werden alle Variablen eingetragen. Rechts steht der Lösungswert (= Wert). In die nachfolgenden Zeilen sind alle Gleichungen des obigen Systems mit ihren Koeffizienten ein-zutragen. Leerzellen werden durch 0 aufgefüllt. Es ergibt sich die folgende Ausgangslösung:
Formales Kennzeichen für die Ausgangslösung ist, dass x0 und jedes si eine eigene Spalte bilden, in der jeweils einmal der Koeffizient 1 vorkommt und alle anderen Werte der Spalte die Größe 0 annehmen: s1 hat die Lösung in der Gleichung S, s2 in der Gleichung B, s3 in der Gleichung M und x0 in der Gleichung Z. 
 
Eine verbesserte Lösung ergibt sich, wenn man in diesem Ausgangssystem die Lösungsvariablen von si nach xi umschlüsselt, also die Lösungsvariable x1 oder x2 mit dem Koeffizienten 1 in die Lösung hereinholt. Das gesamte Gleichungssystem ist dann so umzuschlüsseln, dass an allen anderen Stellen der gewählten Spalte 0 steht. Für das zielgerichtete Umschlüsseln gelten folgende Regeln:
 
  • Das Umschlüsseln folgt – um im obigen grafischen Bild zu bleiben – schrittweise der Umrandung des Lösungsfeldes, ausgehend vom Ursprung des Koordinatenkreuzes (mit x1 = 0 und x2 = 0), und „tastet“ sich mathematisch von Schnittpunkt zu Schnittpunkt vor.
  • Um dabei zielgerichtet den größten Zielwert anzusteuern, wird in der Zielgleichung dieje-nige Spalte gewählt, in der der absolut größte (= kleinste negative) Koeffizient steht. In der obigen Tabelle ist das die Spalte x2 mit dem Koeffizienten –28. Dieser Koeffizient sorgt dafür, dass von vornherein der größtmögliche Zielwert angesteuert wird.
  • Die Wahl der Spalte x2 sagt noch nicht, in welcher der Gleichungen S, B oder M der Koeffizient 1 und an allen anderen Stellen dieser Spalte 0 stehen muss. Für die Auswahl der entsprechenden Gleichung (= Zeile) folgt man dem Kriterium des Engpasses und wählt diejenige Zeile aus, bei der der Quotient aus „Wert dividiert durch Koeffizienten“ am kleinsten ist:
    • Für die Gleichung S ergibt sich ein Quotient von 14.400 : 20 = 720.
    • Für die Gleichung B ergibt sich ein Quotient von 13.500 : 30 = 450.
    • Für die Gleichung M ergibt sich ein Quotient von 19.500 : 40 = 487,50.
  • Solange in der Zielgleichung Z unter den Lösungsvariablen xi negative Koeffizienten auf-treten, ist die optimale Lösung noch nicht erreicht.
 
3.1 Erste Umschlüsselung
 
Der kleinste Wert lautet 450; er steht in der Gleichung B. Also ist im Schnittpunkt der Spalte x2 und der Zeile B an die Stelle des Koeffizienten 30 der Koeffizient 1 zu setzen; dies ge-schieht dadurch, dass die ganze Gleichung B durch 30 dividiert wird. Die folgende Tabelle zeigt die neue Gleichung B‘: 
Damit x2 eine Lösung des Systems wird, dürfen oberhalb und unterhalb der Gleichung B in der Spalte x2 nur Nullen stehen. Das wird erreicht, indem man die neue Gleichung B‘ nach und nach mit den Koeffizienten der übrigen Gleichungen in der Spalte x2 multipliziert und die so erhaltenen erweiterten Gleichungen B‘ von den übrigen Gleichungen S und M subtrahiert bzw. zur Gleichung Z addiert.

Nebenrechnungen zur Umschlüsselung:

Um in der Gleichung S in der Spalte x2 eine Null zu setzen, wird die neue Gleichung B‘ mit 20 multipliziert und von S subtrahiert; es ergibt sich die neue Gleichung S‘. Sie wird in die unten stehende Tabelle eingesetzt:
Auf entsprechende Weise werden die anderen Gleichungen umgeschlüsselt:
In dieser Lösung weist x2 = 450 auf die verbesserte Lösung hin. Die Variable x1 hat den Wert 0 (sie ist nicht in der Lösung enthalten). Der Zielwert beträgt x0 = 12.600. Die Schlupfvariablen s1 und s3 zeigen weiterhin ungenutzte Kapazitäten an.
 
Im Vergleich mit dem grafischen Bild entspricht diese Lösung dem Punkt C der grafischen Darstellung. 

3.2 Zweite Umschlüsselung
 
Die optimale Lösung ist noch nicht gefunden. Kennzeichen dafür ist der negative Wert von –2 in der Zielgleichung Z‘ bei x1. Unter Anwendung der obigen Regeln wird nochmals eine Umschlüsselung vorgenommen, sodass in der Spalte x1 in der Gleichung M‘ eine 1 steht, wie die folgende Quotientenbildung verdeutlicht:
 
  • Für die Gleichung S‘ ergibt sich ein Quotient von 5.400 : 14 = 385,714. 
  • Die Gleichung B‘ wird nicht erneut umgeschlüsselt. Sie hat in der Zielgleichung den Wert 0. Eine Verbesserung ist hier also nicht zu erreichen. 
  • Für die Gleichung M‘ ergibt sich ein Quotient von 2.000 : 10 = 200.
 
Der kleinste Wert lautet 200; er steht in der Gleichung M‘. Also ist im Schnittpunkt der Spalte x1 und der Zeile M‘ an die Stelle des Koeffizienten 10 der Koeffizient 1 zu setzen. Es ergibt sich die neue Zeile M‘‘, die in die unten stehende Tabelle eingetragen wird: 
Nebenrechnungen zur Umschlüsselung:
Die Umschlüsselung ergibt die folgende abschließende Tabelle:
3.3 Optimales Ergebnis

(1) In der Zielgleichung Z‘‘ der obigen (blauen) Tabelle befindet sich unter den Lösungsvariablen x1 und x2 kein von 0 verschiedener Wert.
(2) In der Zielgleichung findet sich kein negativer Wert.
(3) Eine weitere Lösungsvariable xi ist nicht vorhanden.
Das sind die Kennzeichen dafür, dass die optimale Lösung erreicht ist. Sie lautet:
Von Gehäuse G1 sind also 200 Stück zu produzieren, von Gehäuse G2 350 Stück. Die beiden Arbeitsgänge B (Biegen) und M (Montieren) stellen mit ihren monatlichen Arbeitsstunden den Engpass für die Produktion dar. Die hier verfügbaren Arbeitsstunden werden voll aufgebraucht. Die Schlupfvariable s1 = 2.600 tritt ebenfalls in der Lösung auf. Sie weist auf eine nicht genutzte Kapazität im Arbeitsgang „Stanzen“ hin, die für die optimale Lösung nicht benötigt wird. 
 
Wirtschaftlich bedeutet die Lösung, dass die Ressourcen der Arbeitsgänge „Biegen“ und „Montieren“ voll ausgeschöpft werden, während der Arbeitsgang „Stanzen“ noch freie Kapazitäten hat. Hieraus ergibt sich die Aufgabe, entweder die Arbeitsstunden dieses Arbeitsganges zu reduzieren oder – bei Ausdehnung der Produktion – die Arbeitsstunden der übrigen Arbeitsgänge zu erhöhen.
 
Der unter den Bedingungen der Aufgabe maximale Deckungsbeitrag beläuft sich auf 13.000,00 €.
 
Im grafischen Bild entspricht die Lösung dem Schnittpunkt F der beiden Randgleichungen
 
B x2 = - 0,5x1   + 450 (blauer Graph)
M x2 = - 0,75x1 + 500 (roter Graph).

4. Übungsaufgabe mit Lösungen


 
4.1 Ungleichungssystem

Lösung

Die obigen einschränkenden Bedingungen lassen sich mathematisch zu folgendem Unglei-chungssystem (≦) formulieren, das alle zulässigen Lösungen enthält. Die Mengen von P1 sind mit der Variablen x1, die Mengen von P2 mit der Variablen x2 belegt. Der gesuchte Deckungsbeitrag wird als zu maximierender Zielwert Z formuliert:
4.2 Gleichungssystem

Das Ungleichungssystem (≦) schließt die Gleichungen (=) als Randbedingungen mit ein. Die Gleichungen bilden das unten angegebene Gleichungssystem, das die zulässigen optimalen Lösungen enthält. Das nach x2 umgestellte Gleichungssystem ist im Koordinatensystem mit x2 auf der (senkrechten) Ordinatenachse und mit x1 auf der (waagerechten) Abszissenachse grafisch darstellbar.

I.    3x1 + 2x2 = 360 ↔ x2 = -1,5x1 + 180
II.   2x1 + 6²/³x2 = 400 ↔ x2 = -0,3x1 + 60
III.  4x2 = 160 ↔ x= +40
Z     5x1 + 8x2 ⇒ max. ↔ x2 = -5/8x1 (max.)
 
4.3 Grafische Lösung über obige Randgleichungen
Im 1. Quadranten entsteht ein Lösungsfeld, das durch die x1-Achse und die x2-Achse sowie durch die Randgleichungen I, II, III begrenzt ist und in dem alle zulässigen Lösungen liegen. Die optimale Lösung ergibt sich, wenn man die Zielfunktion (Z) x2 = -5/8x1 durch den Ursprung des Koordinatensystems zeichnet und parallel bis zum Rand des Lösungsfeldes verschiebt. Das Optimum (= Ausbringungsmengen mit dem höchst möglichen Deckungsbeitrag) lässt sich dann im Schnittpunkt der beiden Gleichungen I und II ablesen. Die Gleichung III (Bedingung III) ist für die Lösung nicht erforderlich (= freie Kapazität!).
 
I = II:   -1,5x1 + 180 = -0,3x1 + 60
↔    1,2x1  =  120
↔         x1  =  100    
            x2  =    30
Der maximale Deckungsbeitrag beträgt dann 
 = (5 ⦁100) + (8 ⦁ 30)    =  740

4.4 Lösung durch Schnittpunktberechnung
Aus der obigen grafischen Darstellung ist ersichtlich, dass es insgesamt acht Schnittpunkte gibt, davon fünf Schnittpunkte der Graphen mit den Achsen (A, D, E, F, G) und drei Schnittpunkte der Graphen untereinander (B, C, H). Folgende Schnittpunkte der Graphen mit den Achsen liegen oberhalb der Lösungsmenge, gehören also nicht zur Lösung: (E. F, G, H). Unter den verbleibenden Schnittpunkten (A, B, C, D) ist der optimale Wert zu berechnen. 
 
Für den Schnittpunkt A gilt z. B. x1 = 0. Der Wert 0 für x1 in die zweite Gleichung eingesetzt, führt zu x2 = 40. Das Zielergebnis (DB) errechnet sich dann:
 
(5 ⦁ 0) + (8 ⦁ 40) = 320
 
Nach dieser Rechnung werden die übrigen zur Lösungsmenge gehörenden Schnittpunkte untersucht. Der optimale Wert ergibt sich, wenn von Produkt P1 100 Stück und von Produkt P2 30 Stück produziert und verkauft werden; der Deckungsbeitrag hat bei diesen Mengen einen Wert von 740,00 €. 


4.5 Mathematische Lösung über Simplextableau mit Schlupfvariablen s1, s2, s3

Durch die Einfügung von sog. Schlupfvariablen s1, s2 und s3 wird das Ungleichungssystem [vgl. 1] in ein Gleichungssystem überführt. 
Die Zielgleichung lautet 5x1 + 8x2 = x
 
I    3x1 + 2x2 + s1 = 360
II   2x1 + 6²/³x+ s2 = 400
III  4x+ s3 = 160
Z x0 – 5x1 – 8x2 = 0.
 
Das Gleichungssystem lässt sich übersichtlich in folgender Tabelle darstellen, in der die Kopfzeile die Variablen enthält und in jeder Spalte die zugehörigen Koeffizienten stehen. Die nicht belegten Positionen werden auf null gesetzt; die Spalte „b“ benennt die rechten Terme der Gleichungen (= Werte).
Im obigen Gleichungssystem weisen die Spalten s1, s2 und s3 die Lösungen des Systems aus. Zu erkennen ist eine Lösung daran, dass in der betreffenden Spalte in einer Zeile eine 1 und in allen anderen Zeilen 0 steht. Der zugehörige Lösungswert lässt sich in der Spalte „b“ ablesen. In der obigen Ausgangstabelle heißt die Lösung:
 
s1 = 360
s2 = 400
s3  = 160
x1 = 0
x2 = 0
x0 = 0
 
Diesem Gleichungssystem liegt die ungünstigste Lösung zugrunde. Da x1 und x2 nicht in der Lösung enthalten sind, bedeutet das, dass weder von P1 noch von P2 Produkte hergestellt werden. Dementsprechend ist der Deckungsbeitrag x0 = 0. 
 
Wirtschaftlich ist diese Situation so zu deuten, dass überhaupt nicht produziert wird. 
 
Durch Umschlüsselung des Systems von den Schlupfvariablen s1, s2 oder s3 auf die Lösungsvariablen x1 bzw. x2 lässt sich die Lösung verbessern. Bei der Umschlüsselung sind folgende Regeln zu beachten (Simplex-Methode):
 
a) In der Zielgleichung Z wird der absolut größte Wert (–8 für die Variable x2; blaues Feld in obiger Tabelle) ausgewählt; er führt nach der Umschlüsselung zum relativ größten Deckungsbeitrag. In diesem ersten Schritt wird nur das Produkt P2 hergestellt.
 
b) Solange in der Zielgleichung negative Werte auftreten, ist die optimale Lösung nicht erreicht.
 
c) Mit der Festlegung auf den größten Wert wird x2 Lösungsvariable. In welcher Gleichung die Lösungsvariable mit dem Wert 1 steht, entscheidet sich nach der kleinsten Größe b in den drei Gleichungen I bis III
 
I: 360 : 2 = 180
II: 400 : 6²/³ = 60
III: 160 : 4 = 40
 
 
a) Umschlüsselung:
 
x2 wird Lösungsvariable in der Gleichung III und verdrängt hier die Schlupfvariable s3. Alle anderen Variablen der gleichen Spalte x2 müssen durch Umschlüsselung auf null gesetzt werden. Dies geschieht schrittweise wie folgt:
 
  • Gleichung III in der obigen Tabelle dividiert durch 4 ergibt die neue Gleichung III in der folgenden (umgeschlüsselten) Tabelle (s. grüne Zeile in der umgeschlüsselten Tabelle). 
  • Neue Gleichung III multipliziert mit (–2) und addiert zur Gleichung I aus obiger Tabelle ergibt die neue Gleichung I, bei der in der Spalte x2 der Wert 0 steht (s. folgende umgeschlüsselte Tabelle; gelbe Zeile):
  • Neue Gleichung III multipliziert mit (–6 2/3) und addiert zur Gleichung II der obigen Tabelle ergibt die neue Gleichung II, bei der in der Spalte x2 der Wert 0 steht (s. folgende um-geschlüsselte Tabelle; orange Zeile):
  • Neue Gleichung III multipliziert mit 8 und addiert zur Gleichung Z der obigen Tabelle ergibt die neue Gleichung Z, bei der in der Spalte x2 der Wert 0 steht (s. folgende umge-schlüsselte Tabelle; lila Zeile):
Umgeschlüsselte Tabelle
1. Zwischenergebnis:
 
x1 = 0 (ist noch nicht in der Lösung enthalten)
x2 = 40
Zielwert x0 = 320
 
Freie Kapazitäten:
s1 = 280
s2 = 133 1/3
 
Im grafischen Bild bedeutet diese Lösung eine Verschiebung der Zielfunktion entlang der x2-Achse bis zum Schnittpunkt mit der Gleichung III (vgl. Punkt A in der obigen Grafik),
 
Wirtschaftlich bedeutet das erste Zwischenergebnis, dass von Produkt P2 40 Einheiten nur auf der dritten Maschinenanlage produziert werden. P1 wird nicht produziert, die Anlagen I und II haben freie Kapazitäten.
 
b) Umschlüsselung: 
 
Ausgehend von der obigen ersten Lösung ist eine verbesserte Lösung möglich, da in der Zielgleichung noch ein negativer Wert (–5) steht. Der negative Wert weist darauf hin, dass das Optimum nicht erreicht ist. Im nächsten Schritt wird x1 in die Basis geholt (in der zu x1 gehörenden Spalte steht der negative Wert in der Zielgleichung). Nach den zuvor formulierten Regeln wird die Gleichung bestimmt, in der x1 mit dem Wert 1 anzusetzen ist:
 
I: 280 : 3 = 93 1/3
II 133 1/3 : 2 = 66 2/3
 
Der kleinste Wert (66 2/3) steht in der Gleichung II; also wird x1 Lösungsvariable in der Gleichung II und verdrängt hier s2. Alle anderen Variablen der gleichen Spalte x1 müssen durch Umschlüsselung nach dem zuvor gezeigten Verfahren auf null gesetzt werden. Es ergibt sich die folgende Tabelle:
 
c) Zwischenergebnis:
 
x0 = 653 1/3
x1 =   66 2/3
x2 =   40
 
Freie Kapazität:
s1 =   80
 
Im grafischen Bild stellt diese Lösung den Schnittpunkt des Graphen II mit dem Graphen III dar (vgl. Punkt B in der obigen Grafik). 
 
Durch die zweite Umschlüsselung ist das Produktionsergebnis deutlich verbessert worden: Es werden beide Produkte in den Mengeneinheiten 66 2/3 und 40 auf den Maschinenanlagen II und III hergestellt; der Deckungsbeitrag bemisst sich auf 653 1/3 Geldeinheiten. Die Maschinenanlage I hat freie Kapazitäten.
 
 
d) Umschlüsselung: 
 
Die optimale Lösung ist noch nicht erreicht, da die Schlupfvariable s3 in der Zielgleichung mit –13/6 einen negativen Wert aufweist und somit auf eine zu verbessernde Lösung hinweist. In der Spalte s3 ist für die Gleichungen I, II und III diejenige Position zu bestimmen, in der die Schlupfvariable mit dem Wert 1 anzusetzen ist. Die Gleichung II (mit –5/6s3) kommt nicht infrage, da sie wegen ihres negativen Wertes keine Einschränkungen angibt. Es verbleiben die Gleichungen I (mit 2s3) und III (mit 1/4s):
 
I. 80 : 2 = 40
III. 40 : ¼ = 160
 
Für die Umschlüsselung in der Spalte s3 ist aufgrund des kleinsten Wertes die Gleichung I auszuwählen. Es ergibt sich das folgende Tableau: 
e) Endergebnis:
 
x1 = 100 (optimale Produktionsmenge von P1)
x2 =   30 (optimale Produktionsmenge von P2)
x0 = 740 (maximaler Deckungsbeitrag)
 
Freie Kapazität:
s3 = 40
 
Im grafischen Bild stellt diese Lösung den Schnittpunkt des Graphen I mit dem Graphen II dar (vgl. Punkt C in der obigen Grafik). 
 
Wirtschaftlich bedeutet die Lösung, dass die Ressourcen der Maschinen I und II voll ausgeschöpft werden, während die Maschine III noch freie Kapazitäten hat. In dieser Situation werden von P1 100 Mengeneinheiten und von P2 30 Mengeneinheiten produziert. Der Deckungsbeitrag steigt von zuvor 653 1/3 auf 740 Geldeinheiten. Das optimale Ergebnis ist erreicht.
Den vollständigen Artikel können Sie sich hier als PDF-Datei herunterladen.

© Copyright: Westermann Gruppe