Simplex-Methode

in Teilgebiet der Wirtschaftswissenschaften, die Unternehmensforschung (Operations Research) beschäftigt sich mit der Anwendung mathematischer Methoden auf die Lösung wirtschaftlicher Entscheidungsprobleme. Dabei wird das Realproblem in ein mathematisches Ausgangsmodell transformiert. Im Falle der linearen Programmierung (Optimierung) geschieht dies in Form von linearen Ungleichungen (a₁ x₁+a₂x₂+...+a_nx_n <= b bzw. >= b) , welche die Zielfunktion (z. B. Gewinnmaximierung) und die Restriktionen (z. B. Maschinenkapazität) repräsentieren.
      Bei Ungleichungen mit nur zwei Variablen bietet sich eine graphische Lösungsmethode an. Bei mehr als zwei Variablen bedient man sich sehr oft der Simplex Methode. Dabei wird die gesuchte Optimallösung iterativ, d.h. in mehreren Schritten ermittelt. Die Koeffizienten der Ungleichungen werden dabei in Tabellenform (Simplex-Tableau) geschrieben. Auf die Koeffizienten werden dann Zeilenoperationen (wie in der Matrizenrechnung) angewendet.
      Und da sowas stets stinklangweilig und mühsam ist, halsen wir das einfach unseren Computer auf. Entweder man besorgt sich eine geeignete Software, oder man schreibt sich selbst ein Tool (in Klammern gesagt: Das untenstehende Beispiel in JavaScript soll lediglich als Demonstration dienen und stellt keineswegs ein vollständiges Anwendungsprogramm dar ;-).
Das Beispiel:
Folgende Ungleichungen liegen vor:
Restriktionen:
2x₁+x₂<=200,
x₁+x₂<=120,
x₁+3x₂<=240,
x₁>=0, x₂>=0 (Nichtnegativitätsbedingung).
Aus den Ungleichungen machen wir Gleichungen:
2x₁+x₂+y₁=200,
x₁+x₂+y₂=120,
x₁+3x₂+y₃=240,
y_i sind sogenannte Schlupfvariablen und stellen die nicht ausgenutzte Kapazität dar.
Gewinnfunktion:
G=2x₁+3x₂ Umformen: -2x₁-3x₂+G=0
Die Koeffizienten in das Tableau einsetzen und los gehts:
(Achtung: "Neue Runde" drücken. Danach erscheint ein Fenster, welches anzeigt, ob die optimale Lösung schon gefunden wurde.)

Nach zwei Runden hat man in diesem Beispiel die optimale Lösung für das Produktionsprogramm gefunden. Man stelle also von Gut x1 60 und von x2 60 Stück her und erzielt dabei einen Gewinn (G) von 300. (halt, nie die Dimension vergessen, also sagen wir 300 Euro). y1 = 20 stellt eine ungenutzte Kapazität der 1.Maschine dar. Die Werte in der letzten Zeile der Spalte y2 u. y3 (1,5 u. 0.5) sind die Opportunitätskosten (Schattenpreise).

2. Beispiel zum Ausprobieren: Ein Unternehemn möchte kurzfristig seinen Deckungsbeitrag, langfristig seinen Gewinn maximieren. Analyse der variablen Kosten sowie Kapazitäten der jeweiligen Kostenstellen ergeben folgende Restriktionen:
1x₁+1x₂<=120
2x₁+4x₂<=300
6x₁+2x₂<=360
Marktpreise und Fixkostenblock ergeben folgende Gewinnfunktion:
G=8000x₁+5000x₂-400000
Wie lautet das optimale Produktionsprogramm?
Antwort:
Folgende Koeffizienten in obiges Tableau eintragen:
1,1,1,0,0,0,120
2,4,0,1,0,0,300
6,2,0,0,1,0,360
-8000,-5000,0,0,0,1,-400000
Auf Button drücken und rechnen lassen!
Ergebnis:
x1=42, x2=54, G(max)=206000(Euro,Dm,...)
Nichtausnutzung=24 Stck. ergibt
24*100/120=20% Leerkapazität und
((120-24)/120)*100=80% Auslastungsgrad von Kostenstelle-3

Für ein besseres Programm bediene man sich z.B. Java; biete am Programmstart eine Eingabemaske an, um die Anzahl der Variablen und Ungleichungen abzufragen; daraufhin wird ein dementsprechendes Tableau generiert. Den Code für die Zeilenoperationen kann man fast 1:1 aus dem JavaScript-Beispiel übernehmen; (vorher den "hartcodierten" Kram ersetzen). Das ganze vielleicht noch mit ein paar Funktionen zur Sensitivitätsanalyse usw. garnieren. Fertig ist das eigene Programm.
Schema: Realproblem - mathematische Formulierung des Problems (die halbe Miete) - Algorithmus entwerfen - Programm schreiben - (Fehler suchen :(  )