Hausarbeit Operations Research · PDF fileHausarbeit Operations Research - Der Simplex-Algorithmus - Eingereicht von: Christoph Böhm MatrikelNr.: 10014637 Am Anger 30a 91365 Weilersbach

Hausarbeit Operations Research

- Der Simplex-Algorithmus -

Eingereicht von:

Christoph Böhm

MatrikelNr.: 10014637

Am Anger 30a 91365 Weilersbach (0163) 26 09 738

[email protected]

vorgelegt bei:

Dipl.- Stat. Adriane Sommer

Fachhochschule Südwestfalen

Sommersemester 2008

Weilersbach, den 14.08.08

II

Inhaltsverzeichnis

1. EINLEITUNG ................................................................................................ - 1 -

2. DARSTELLUNG DES SIMPLEX-ALGORITHMUS ................................... - 2 -

2.1. Einordnung im Gesamtgebiet des Operations Research ....................................................... - 2 -

2.2. Theoretische Grundlagen des Simplex-Algorithmus .............................................................. - 2 -

2.3. Komplexität ................................................................................................................................... - 3 -

3. MATHEMATISCHES LÖSUNGSVERFAHREN ........................................ - 4 -

3.1. Prozess der Lösungsermittlung .................................................................................................. - 4 -

3.2. Das Standard-Maximum-Problem ............................................................................................. - 6 -

3.2.1. Darstellung des Ausgangsproblems ...................................................................................... - 6 - 3.2.2. Begriff des Standard-Maximum-Problems .......................................................................... - 7 - 3.2.3. Rechnerische Ermittlung des Optimums............................................................................. - 7 - 3.2.4. Interpretation des Gesamttableaus ..................................................................................... - 11 -

3.3. Modifikation des Standard-Maximum-Problems .................................................................. - 11 -

3.3.1. „Größer Gleich“ Ungleichungen als Restriktionen ......................................................... - 11 - 3.3.2. Gleichungen als Restriktion ................................................................................................. - 13 -

3.4. Minimierungs-Problem .............................................................................................................. - 16 -

3.5. Optimalitätskriterium ................................................................................................................. - 16 -

4. ANWENDUNG DES SIMPLEX-ALGORITHMUS IN DER PRAXIS ..... - 17 -

5. RESÜMEE .................................................................................................... - 18 -

6. ANHANG ........................................................................................................ - 1 -

Begriffsdefinition ......................................................................................................................................... - 1 -

Anhang: Simplex Tableau 1 - Umrechnung ............................................................................................ - 2 -

Anhang: Simplex Tableau 10 ..................................................................................................................... - 2 -

Anhang: Simplex Tableau 11 ..................................................................................................................... - 2 -

- 1 -

1. Einleitung

Die Komplexität von Unternehmensentscheidungen hat sich in der Industrie über die

letzten 50 Jahre hinweg wesentlich gesteigert. Dabei sind Manager häufig gefordert aus

einer sehr großen Anzahl von Alternativen diejenige auszuwählen, die dem Unternehmen

zukünftig den größten Erfolg verschaffen wird. Um die große Anzahl an Restriktionen und

Abhängigkeiten der einzelnen Entscheidungen erfassbar zu machen hat der Simplex-

Algorithmus als ein Verfahren zur rechnerischen Lösung linearer Programme eine

herausragende Bedeutung in der Unternehmensplanung.

Der Simplex-Algorithmus wurde 1947 von George Dantzig entwickelt und konnte sich

seitdem als wichtigstes und gebräuchlichstes rechnerisches Lösungsverfahren für lineare

Systeme mit beliebig vielen Variablen profilieren.1

So nennt Zimmermann2 beispielhaft den Einsatz des Simplex-Algorithmus in der

Produktionsprogrammplanung bei Vorliegen von Kapazitätsbeschränkungen,

Verschnittminimierung bei der Produktion von Gütern,

Mischungsoptimierung - beispielsweise in der Lebensmittelindustrie zur Erreichung

geforderter Eigenschaften.

Vor allem in der Informationstechnologie, wo der Simplex-Algorithmus heute in vielen

Standardsoftwarelösungen integriert ist, ermöglich er auch ohne entsprechende

Sachkenntnisse auf sehr schnellem Weg optimale Lösungen für betriebswirtschaftliche

Probleme.3 So verwendet die Firma SAP in ihrem Modul SCM (Supply Chain

Management) diese Methode zur Optimierung von Logistiknetzwerken und zur

Beschaffungsplanung.4

Ziel dieser Hausarbeit ist es die Idee des Simplex-Algorithmus darzustellen, anhand eines

Beispiels zu erläutern und eine Interpretation der ermittelten Ergebnisse vorzunehmen.

Es sollen deshalb in Kapitel 2 die theoretischen Eigenschaften des Algorithmus geklärt

werden um anschließend in Kapitel 3 auf den Prozess der Lösungsermittlung theoretisch

sowie anhand eines Beispiels einzugehen. Hier wird zuerst das Standard-Maximum

Problem näher betrachtet während danach in Kapitel 3.3 sowie 3.4 auf einzelne

Sonderprobleme eingegangen wird.

1 Vgl. Friedrich, A, Lineare Optimierung – Probleme und Lösungen aus Wirtschaft und Technik, S. 30ff.

2 Zimmermann, W., Operations Research, 1990, S. 48.

3 Zimmermann, W., Operations Research, 1990, S. 65 sowie http://www.ilog.com/ als Standardpaket zum

Durchführen von Optimierungsaufgaben.

4 SAP Deutschlang AG: http://www.sap.com/germany/media/50062625.pdf, Seite 13 Zugriff am 03.07.08.

- 2 -

2. Darstellung des Simplex-Algorithmus

2.1. Einordnung im Gesamtgebiet des Operations Research

Die Simplex-Methode ist ein Verfahren aus dem Bereich der linearen Optimierung zur

rechnerischen Lösung von in Normalform (in der Literatur auch Standardform genannt)

vorliegenden Ausgangsproblemen.5 Unter linearer Optimierung versteht man die

Optimierung – das heißt die Maximierung oder Minimierung – einer linearen Funktion, der

so genannten Zielfunktion, deren Variablen einem System von linearen Ungleichungen

oder Gleichungen, den so genannten Restriktionen, genügen müssen.6

Zur rechnerischen Lösung von linearen Optimierungsaufgaben hat sich eine große Anzahl

an Verfahren entwickelt, wobei das hieraus bekannteste und gebräuchlichste das

Simplexverfahren ist.7

2.2. Theoretische Grundlagen des Simplex-Algorithmus

Der Begriff Simplex-Algorithmus lässt sich aus der Bezeichnung der Lösungsmenge des zu

lösenden Problems ableiten. Hiernach ist die Menge der zulässigen Lösungen eines linearen

Programms durch ein konvexes Polyeder darstellbar, der auch als n-dimensionaler Simplex

bezeichnet wird. Unter einem Polyeder versteht man einen Körper, der ausschließlich von

geraden Flächen begrenzt wird.8

Nach dem Hauptsatz der linearen Optimierung kann nun bewiesen werden, dass ein

Maximum oder Minimum, falls vorhanden, immer in einem, oder sofern mehrere

Lösungen vorliegen, in mehreren Eckpunkten des Polyeders gefunden werden kann.9

Zur Ermittlung eines gesuchten Optimums ermöglicht das Simplexverfahren ausgehend

von einem Startpunkt in einem Iterationsverfahren den jeweils nächst besseren Eckpunkt

des Polyeders zu bestimmen. Dieser Schritt wird solange wiederholt bis eine optimale

Lösung, falls vorhanden, ermittelt wurde. Andererseits gibt es auch Probleme, dessen

Lösung unbeschränkt beziehungsweise nicht zulässig ist.10

5 Grötschel, M., Lineare Optimierung, 2002, S. 111.



8 Schick, C., Lineares Optimieren, 1975, S. 80 – 82.

9 Grötschel, M: Lineare Optimierung, 2002, S. 111.


- 3 -

2.3. Komplexität

Das Simplexverfahren zählt zu den erprobtesten Verfahren des Operations Research und

erweist sich in der Praxis als sehr schnell. Bei einer Vielzahl an Problemen konnte gezeigt

werden, dass es vielen anderen vergleichbaren Methoden überlegen ist.11 Hier gilt als

Faustregel, dass die Laufzeit des Simplexverfahrens weitgehend linear von der Anzahl der

Restriktionen und sogar geringer als linear mit der Anzahl der Variablen ansteigt.12

Ein weiterer großer Vorteil des Simplexverfahrens ist dessen Fähigkeit bei einer leichten

Veränderung des Ausgangsproblems, beispielsweise beim Hinzufügen einer zusätzlichen

Restriktion, die vorhandene Lösung als Ausgangspunkt zu nutzen. Somit kann mit einer im

Vergleich zum Ausgangsproblem sehr geringen Anzahl an Iterationen die neue optimale

Lösung ermittelt werden.13

Im Gegensatz zu den empirischen Ergebnissen aus der Praxis über den niedrigen

durchschnittlichen Rechenaufwand konnten Mathematiker Optimierungsprobleme

erstellen, bei dem der Simplex-Algorithmus sich als sehr langsam erweist. So konnten Klee

und Minty 1972 ein Beispiel konstruieren, bei dem der von Danzig ursprünglich

entwickelte Algorithmus eine exponentielle Laufzeit aufweist. 14 In diesem Fall wird der

Simplex-Algorithmus alle möglichen Eckpunkte des zulässigen Bereichs absuchen bevor

die optimale Lösung erreicht wird.15 Dieses Verhalten des Algorithmus stellt das

schlechtmöglichste Laufzeitverhalten dar. Jedoch sind solche Beispiele immer als

Ausnahmen zu sehen.

11 Neumann, K. / Morlock K., Operations Research, München, Carl Hanser Verlag, 2002, S. 160.

12 Neumann, K. / Morlock K., Operations Research, München, Carl Hanser Verlag, 2002, S. 160.


14 Klee, V. / Minty, G.J.: How good is the simplex algorithm? In: O. Shisha (Hrsg.), Inequalities, Academic

Press, S. 159 – 175.

15 Dempe, S. /Schreier H., Operations Research, 2006, S. 66-67 und S. 346 ff.

- 4 -

3. Mathematisches Lösungsverfahren

3.1. Prozess der Lösungsermittlung

Der Simplex-Algorithmus löst lineare Optimierungsaufgaben, welche in Normalform

vorliegen. Unter einer Normalform16 versteht man ein lineares Gleichungssystem der

Form:

(1) c1x1 + c2x2 + … + cnxn Max lineare Zielfunktion

(2) a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2 Restriktionen

am1x1 + am2x2 + … + amnxn = bm

(3) x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0 Nichtnegativitätsbedingungen

Mit i = {1,…,m} wird die Zeilenindexmenge beschrieben, mit j = {1,…,n} die

Spaltenindexmenge.

xj Strukturvariablen

cj Koeffizienten der Zielfunktion

aij Koeffizienten der Beschränkungen

bi Rechte Seite der Beschränkungen

Meistens liegt aber eine gegebene lineare Optimierungsaufgabe nicht in Normalform vor.

Jedoch kann gezeigt werden, dass alle linearen Programme, die diese Voraussetzungen

nicht erfüllen, auf solche zurückgeführt werden können. Damit der Simplex-Algorithmus

universell für alle Probleme der linearen Optimierung einsetzbar.17 In den nachfolgenden

Kapiteln 3.2.3, 3.3 sowie 3.4 wird neben der Ermittlung zur Lösung einer in Normalform

vorliegenden Optimierungsaufgabe auch ein Schwerpunkt auf die Transformation eines

Ausgangsproblems zur Normalform gelegt.

Für das Gleichungssystem in Normalform, so die Annahme, gilt, dass m < n ist und es

damit unterbestimmt ist. 18 Es ist damit nicht möglich eine eindeutige Lösung mit Hilfe des

Gauß’schen Eliminationsverfahrens zu ermitteln.19 Um trotzdem, sofern existierend, eine

eindeutige Lösung zu bestimmen, werden wie im Verlauf dieser Hausarbeit gezeigt wird,

gezielt einzelne Variablen genullt, um das lineare Optimierungsproblem lösen zu können.

Liegt das lineare Programm in Normalform vor, so muss in einem ersten Schritt ein

Einstiegspunkt für den Simplex-Algorithmus, das heißt eine erste Basislösung gefunden

werden, von dem aus die iterative Optimierung starten kann. Unter einer Basislösung

16 Schick, C., Lineares Optimieren, 1975, S. 102.

17Grötschel, M: Lineare Optimierung, 2002, S. 113.



- 5 -

versteht man eine zulässige Lösung der Zielfunktion, die sowohl die Nichtnegativitäts- als

auch die Restriktionsbedingungen erfüllt.

Von diesem Startpunkt aus ist es dann Ziel, eine Basislösung zu finden, welche einen

maximalen Wert der Zielfunktion erreicht. Ob dieser Zustand erreicht wurde ist an der

Zielfunktion zu erkennen. Weißt diese noch negative Koeffizienten auf, so ist klar, dass

eine weitere Optimierung möglich ist. Dies wird erreicht indem die zugehörige Variable in

die Basis aufgenommen wird. 20

Bei der Auswahl der zu überführenden Nichtbasisvariable können verschiedene Strategien

verfolgt werden. In dieser Arbeit wird aus Vereinfachungsgründen das Element

ausgewählt, das den größten negativen Koeffizient in der Zielfunktion aufweist. Das

theoretische Problem hierbei ist, dass die Restriktionen bei der Auswahl unbeachtet

bleiben, wobei diese einen wesentlichen Beitrag auf die Wirksamkeit des

Optimierungsschrittes haben können. Andere Strategien versuchen deshalb zuerst den

größten Fortschritt zu berechnen (bezeichnet in der Literatur als „Größte-Fortschritt-

Regel“).21

Ergebnis der Optimierung ist dann ein ermitteltes Optimum beziehungsweise die

Feststellung, dass die Lösung unbeschränkt oder unlösbar ist.

Folgende Übersicht soll die verschiedenen Phasen der Lösungsermittlung noch einmal

verdeutlichen:

Gegebene

lineare

Optimierungsaufgabe

NormalformOptimale Lösung

oder keine Lösung

Iterative

OptimierungTransformation

Darstellung 1: Abbildung in Anlehnung an Dempe, 2006, S. 20

20 Schick, C., Lineares Optimieren, 1975, S. 120.


- 6 -

3.2. Das Standard-Maximum-Problem

3.2.1. Darstellung des Ausgangsproblems

Zur Abhandlung und Verdeutlichung des Simplex-Algorithmus wird im nachfolgenden ein

Beispiel aus der Produktionsplanung aufgegriffen und dies unter Verwendung des Simplex-

Algorithmus optimal gelöst. 22

Für einen Kleinbetrieb ist das gewinnmaximale Produktionsprogramm zu ermitteln. Es

können die Artikel 1 und 2 mit einem Gewinn von g1 = 500 € und g2 = 800 € gefertigt

werden.

Die zur Produktion vorhandenen Kapazitäten sind jedoch beschränkt. In der Produktion

stehen nur die zwei Maschinen A und B zur Verfügung sowie eine beschränkte Anzahl an

Mitarbeitern in der Montageabteilung. Die technischen Daten sind in folgender Tabelle

aufgelistet:

Artikel Kapazität pro Tag 1 ≙ x1 2 ≙ x2

Maschine A Maschine B Montageabteilung

5 Stunden 1 Stunde 6 Stunden

2 Stunden 5 Stunden 6 Stunden

24 Stunden 24 Stunden 36 Stunden

Gewinn pro Stück 500 € 800 €

Tabelle Verbrauch und Kapazitäten

Die 36 Stunden Kapazität in der Montageabteilung bedeuten, dass alle Mitarbeiter

zusammen diese Anzahl an Stunden pro Tag arbeiten. Die mathematische Formulierung

des Problems lautet:

Lineare Zielfunktion

Z = 500x1 + 800x2 Zielfunktion (kurz Z) Max!

Lineare Restriktionen

(1) 5x1 + 2x2 ≤ 24 (2) x1 + 5x2 ≤ 24 (3) 6x1 + 6x2 ≤ 36

Nichtnegativitätsbedingungen

(4) x1 ≥ 0 (5) x2 ≥ 0

Gesucht ist nun die Anzahl an Produkten 1 und 2, die gefertigt werden müssen, um den Gewinn des Unternehmens pro Tag zu optimieren.

22 Beispiel in Anlehnung an Zimmermann, W., Operations Research, 1990, S. 49f.

- 7 -

3.2.2. Begriff des Standard-Maximum-Problems

Bei dem vorliegenden Problem handelt es sich um ein Standard-Maximum-Problem.

Hierunter versteht man ein lineares Optimierungsprogramm der Form

(1) c1x1 + c2x2 + … + cnxn Max

(2) a11x1 + a12x2 + … + a1nxn ≤ b1

a21x1 + a22x2 + … + a2nxn ≤ b2

am1x1 + am2x2 + … + amnxn ≤ bm

(3) x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0

Wie an den ≤ Zeichen in den Restriktionen ersichtlich ist, liegen solche Probleme nicht in

Normalform vor. Zur Überführung werden Schlupfvariablen y1,…,yn eingeführt, um die

vorliegenden linearen Restriktionsungleichungen in Gleichungen zu überführen. Die

Schlupfvariablen fungieren damit als Puffer zwischen b1,…,bn und den linken Seiten der

Ungleichungen. Sie nehmen die Differenz des Betrags zwischen den zwei Seiten auf. Auch

für diese speziellen Variablen muss die Nichtnegativitätsbedingung gelten. In der linearen

Zielfunktion werden die Schlupfvariablen mit null multipliziert, da natürlich die Werte

dieser keine Auswirkungen auf die Zielfunktion haben sollen.23

3.2.3. Rechnerische Ermittlung des Optimums

Ausgangspunkt für das Simplexverfahren sind die Restriktionen. Wie bereits aufgezeigt,

können durch das Hinzufügen von Schlupfvariablen aus den bestehenden Ungleichungen

Gleichungen erstellt werden.

(1) 5x1 + 2x2 +y1 = 24

(2) x1 + 5x2 +y2 = 24

(3) 6x1 + 6x2 +y3 = 36

Möchte man hier eine Interpretation der Schlupfvariablen vornehmen, so können diese als

Leerlaufzeit interpretiert werden, also der Differenz der verfügbaren und der für die

Produktion der Produkte 1 und 2 benötigten Kapazitäten auf der linken Seite des

Gleichheitszeichens.24 Der nächste Schritt besteht in der Umstellung der Zielfunktion Z

nach null sodass diese anschließend lautet:

Z - 500x1 - 800x2 = 0.

Die vorhandenen Funktionen werden mit Ausnahme der Nichtnegativitätsbedingungen in

ein sogenanntes Simplex Tableau übernommen, wobei fehlende Koeffizienten der

einzelnen Funktionen durch eine null gekennzeichnet werden.


24 Sturm, M., Wirtschaftsmathematik Lerneinheit 2, 2002, S. 18.

- 8 -

Die Nichtnegativitätsbedingungen werden nicht erfasst und müssen implizit bei jedem

Optimierungsschritt überprüft werden.

Z x1 x2 y1 y2 y3 bi

1,00 -500,00 -800,00 0,00 0,00 0,00 0,00

0,00 5,00 2,00 1,00 0,00 0,00 24,00

0,00 1,00 5,00 0,00 1,00 0,00 24,00

0,00 6,00 6,00 0,00 0,00 1,00 36,00

Darstellung 2: Simplex Tableau

Bei linearen Problemen, die dem Standard-Maximum-Problem entsprechen kann durch

Gleichsetzung der Entscheidungsvariablen mit Null eine erste zulässige Basislösung

gefunden werden.

Entscheidungsvariablen sind diejenigen veränderlichen Variablen, deren Wert in

Abhängigkeit von der Zielfunktion optimal zu bestimmen ist, in unserem Fallbeispiel also

x1 sowie x2.

Diese gefundene Basislösung entspricht bei graphischer Darstellung dem Ursprung des

Koordinatensystems. Die Basisvariablen y1, y2 und y3 zeichnen sich dadurch aus, dass sie in

genau einer einzigen Zeile des Tableaus auftreten. Möchte man die gefundene Lösung

beispielhaft an Restriktion 2 verdeutlichen so kann folgende Gleichung abgelesen werden.

0Z + 1x1 + 5x2 + 0 y1 +1y2+ 0 y3 = 24

Da x1 sowie x2 aufgrund ihres Status als Nichtbasisvariable der Wert Null zugewiesen wird,

kann die Funktion zusammengefasst werden zu

y2 = 24

Dies bedeutet, dass 24 Stunden freie Kapazitäten auf der Maschine 2 verfügbar sind.

Ähnliches kann für alle anderen Restriktionen ermittelt werden.

Da die gefundene Basislösung eine Einstellung der Produktion bedeuten würde, ist

praktisch bereits ersichtlich, dass eine optimale Lösung noch nicht erreicht wurde. Dies

lässt sich zusätzlich an den negativen Nichtbasisvariablen-Koeffizienten in der Zielfunktion

ablesen, welche aufzeigen, dass eine weitere Optimierung möglich ist und damit der

Gewinn durch die Produktion der Produkte 1 oder 2 steigen wird.25 Besonders das

Produkt 2 mit einem zusätzlichen Gewinn von 800 € pro Stück sollte unter Beachtung der

Restriktionen in höchstmöglicher Stückzahl produziert werden. Damit wird die Spalte der

Variable x2 als Pivotspalte ausgewählt um sie zu einer Basisvariable zu überführen.26



Zielfunktion

Restriktion

1.

2.

3.

- 9 -

Unter einer Pivotspalte, in der Literatur auch Austauschspalte genannt, versteht man jene

Spalte in einem Simplex Tableau, welche ausgewählt wird, um sie zu einer Basisvariablen zu

überführen.27

Die maximale Produktionsmenge kann ermittelt werden, indem alle einzelnen

Restriktionsgleichungen wieder als Ungleichungen aufgefasst werden und auch x2 weiterhin

mit Null gleichgesetzt wird. Dann ergibt sich:

2 x2 ≤ 24 x2 ≤ 12 Stück

5 x2 ≤ 24 x2 ≤ 4,8 Stück

6 x2 ≤ 36 x2 ≤ 6,0 Stück

Damit stellt die Maschine 2 mit nur 4,8 Stück produzierbaren Einheiten einen Engpass dar.

Die Zelle des Schnittpunkts aus der Pivotspalte und der ermittelten Pivotzeile ergibt dann

anschließend das Pivotelement. Die Auswahl des niedrigsten Engpasses garantiert, dass das

Tableau nach Durchführung der Optimierung nicht aus dem zulässigen Lösungsbereich

fällt.28

Die unten dargestellte Tabelle fasst die Ergebnisse zusammen. Die Spalte qi dient der

Ermittlung des Pivotelements, indem wie oben beschrieben die Spalte bi durch die

Pivotspalte geteilt wird. Die grün hinterlegte Spalte verdeutlicht das gefundene

Pivotelement.29

Nichtbasisvariablen Basisvariablen

Z x1 x2 y1 y2 y3 bi qi

1,00 -500,00 -800,00 0,00 0,00 0,00 0,00

0,00 5,00 2,00 1,00 0,00 0,00 24,00 24 / 2 = 12

0,00 1,00 5,00 0,00 1,00 0,00 24,00 24 / 5 = 4,8

0,00 6,00 6,00 0,00 0,00 1,00 36,00 36 / 6 = 6,0

Simplex Tableau 1

Zu beachten ist bei der Ermittlung der Pivotzeile, dass Restriktionen, dessen Engpasswert

kleiner oder gleich null ist, nicht in die Auswahl zur Pivotzeile genommen werden dürfen.

Dies würde bei der noch zu erläuternden Umrechnung zur Basisvariable zu einem Verstoß

gegen die Nichtnegativitätsbedingungen führen und damit zu einer unzulässigen

Basislösung.30


28 Josef Leydold: http://statmath.wu-wien.ac.at/~leydold/MOK/HTML/node159.html, Zugriff am

05.08.08.



Engpass

Pivotspalte

- 10 -

Um dieses Tableau in eine neue Basislösung zu überführen, muss die Pivotspalte so

umgerechnet werden, dass sie als Basisvariable auftritt.31

Hierzu muss die Pivotzeile im ersten Schritt komplett durch das Pivotelement geteilt

werden. Anschließend wird von der so ermittelten Zeile ein entsprechendes Vielfaches der

anderen Zeilen addiert beziehungsweise subtrahiert32, so dass ein Einheitsspaltenvektor in

der Pivotspalte entsteht.33

Durch die Anwendung der oben genannten Vorgehensweise entsteht folgende zweite

Tabelle. Die detailierte Umrechnung des Simplex Tableau 1 befindet sich im Anhang.


Z x1 y2 x2 y1 y3 bi qi

1,00 -340,00 160,00 0,00 0,00 0,00 3840,00

0,00 4,60 -0,40 0,00 1,00 0,00 14,40 14,40 /4,60 = 3,13

0,00 0,20 0,20 1,00 0,00 0,00 4,80 4,80 / 0,20 = 24,0

0,00 4,80 -1,20 0,00 0,00 1,00 7,20 7,20 / 4,80 = 1,50

Simplex Tableau 2

Bei Überprüfung der Zielfunktion auf Optimalität ist feststellbar, dass noch kein optimales

Ergebnis erreicht wurde, da der Koeffizient von x1 weiterhin negativ ist und damit als

Pivotspalte zu einer Basisvariable überführt werden muss. Auch hier ist ähnlich wie im

ersten Tableau die Pivotzeile beziehungsweise der Engpass zu ermitteln und aus dem

Schnittpunkt der Pivotzeile mit der Pivotspalte das Pivotelement festzulegen. Das

Pivotelement ist im vorliegenden Fall der Wert 4,80, der im Simplex Tableau 2 grün

unterlegt dargestellt ist. Durch weitere Optimierung erhält man anschließend folgendes

Tableau:


Z y2 y3 y1 x1 x2 bi qi

1,00 75,00 70,83 0,00 0,00 0,00 4350,00

0,00 0,75 -0,96 1,00 0,00 0,00 7,50

0,00 0,25 -0,04 0,00 0,00 1,00 4,50

0,00 -0,25 0,21 0,00 1,00 0,00 1,50

Simplex Tableau 3




- 11 -

Da im vorliegenden Fall für alle Variablen der Zielfunktion ein positiver Wert erreicht wird,

ist die Optimalitätsbedingung erfüllt und die Zielfunktion hat unter Einhaltung der

Restriktionsbedingungen einen maximalen Wert erreicht. 34

3.2.4. Interpretation des Gesamttableaus

Aus dem Simplex Tableau 3 können vielfältige Rückschlüsse gezogen werden. Wichtige

Kennzahlen sind grün im Tableau unterlegt. Der maximale Gewinn beträgt im

vorliegenden Fall 4350 € und wird bei einer täglichen Produktion von 1,5 Stück von

Produkt 1 sowie 4,5 Stück von Produkt 2 erwirtschaftet. Dieses Ergebnis kann an den

Basisvariablen x1 sowie x2 abgelesen werden, indem die Zeile mit dem Wert Eins gesucht

und dann der zugehörige Wert bi abgelesen wird.35

Die Basisvariable y1 lässt erkennen, dass auf Maschine A noch 7,5 Stunden freie Kapazität

zur Verfügung stehen, die nicht genutzt werden.

Neben dieser Grundinterpretation können aber noch weitere Interpretationen

vorgenommen werden. Die in der Zielfunktion bestehenden Koeffizienten der

Nichtbasisvariablen können als Opportunitätskosten der nicht gefertigten Produkte oder

der bis zur Kapazitätsgrenze genutzten Produktionsfaktoren interpretiert werden.36 Diese

Opportunitätskosten bedeuten folgendes:

Für jede Stunde Mindereinsatz der Maschine B (Spalte y2) geht der Gewinn um 75 €

zurück, beziehungsweise für jede zusätzliche Einsatzstunde der Maschine steigt der

Gewinn um eben diesen Betrag. Ähnliches gilt für die Montagegruppe (Spalte y3). Für jede

nicht gearbeitete Stunde entgehen dem Unternehmen 70,83 € Gewinn.37

Durch die Interpretation kann das Simplex Tableau als Entscheidungsgrundlage dienen

und helfen, eine Aussage darüber zu treffen, ob eine Ausweitung der Produktion sinnvoll

ist oder nicht. Sollten im vorliegenden Fall exemplarisch die Kosten für Überstunden an

Maschine 1 geringer als 75 € sein, kann somit eine Produktionsausweitung empfohlen

werden.

3.3. Modifikation des Standard-Maximum-Problems

3.3.1. „Größer Gleich“ Ungleichungen als Restriktionen

Das in Kapitel 3.2 beschriebene Verfahren zur Überführung eines Standard-Maximum-

Problems kann nur solange angewandt werden, wie die Restriktionen alle ≤ Zeichen





- 12 -

aufweisen. Bereits problematisch ist das Vorliegen eines Problems mit einer ≥ Restriktion.

Zwar kann durch Multiplikation der betroffenen Restriktion mit -1 das ≥ zu einem ≤

umgedreht werden,38 jedoch weißt anschließend die betroffene Zeile einen negativen Wert

auf und verstößt damit gegen die Nichtnegativitätsbedingung. Um trotzdem zu einer

zulässigen Basislösung zu gelangen muss die bisher als Basisvariable geführte negative

Variable aus dem Tableau in eine Nichtbasisvariable überführt werden, was in einer

vorgelagerten Phase geschehen muss. 39

Zu beachten ist, dass falls in der Pivotzeile tatsächlich nur positive Nichtbasis-Variablen

auftreten, keine Lösung für das Problem gefunden werden kann und der Simplex-

Algorithmus beendet ist.40

Das in Kapitel 3.2.1 dargestellte Ausgangsproblem soll zur Verdeutlichung des Vorgehens

dienen.

Neben den bereits vorgestellten Restriktionen soll nun gelten, dass von Produkt 1 und 2

aufgrund von Kundenverpflichtungen zusammen mindestens 3 Stück pro Tag produziert

werden sollen. Die hieraus zu berücksichtigende Restriktion

x1 + x2 ≥ 3.

kann durch Multiplikation mit -1 in eine Kleiner-Gleich-Beziehung überführt werden. Eine

weitere Schlupfvariable y4 wird eingeführt um eine der Normalform entsprechende

Gleichung zu erhalten:

-x1 - x2 + y4 = -3

Das Ausgangstableau lautet damit


Z x1 x2 y1 y2 y3 y4 bi qi

1,00 -500,00 -800,00 0,00 0,00 0,00 0,00 0,00

0,00 5,00 2,00 1,00 0,00 0,00 0,00 24,00

0,00 1,00 5,00 0,00 ,00 0,00 0,00 24,00

0,00 6,00 6,00 0,00 0,00 1,00 0,00 36,00

0,00 -1,00 -1,00 0,00 0,00 0,00 1,00 -3,00

Simplex Tableau 4

Im Ausgangstableau kann in den grün hinterlegten Feldern der Verstoß gegen die

Nichtnegativitätsbedingung erkannt werden. Die Schlupfvariable y4 weist einen negativen

Wert auf. Die ermittelte Lösung ist damit nicht zulässig. Um dieses Problem zu beheben

38 Dempe, S. /Schreier H., Operations Research, 2006, S. 18.



neue Restriktion

- 13 -

muss eine Phase vor der eigentlichen Optimierung geschaltet werden. Zu Beginn muss zur

Überführung das negative Pivotelement x2 ausgewählt werden.

Da sowohl x1 als auch x2 einen negativen Wert enthalten ist das Auswählen des

Pivotelements hierbei frei.41 Anschließend kann das Tableau passend umgerechnet werden.


Z x1 y4 x2 y1 y2 y3 bi qi

1,00 300,00 -800,00 0,00 0,00 0,00 0,00 2400,00

0,00 3,00 2,00 0,00 1,00 0,00 0,00 18,00 9,00

0,00 -4,00 5,00 0,00 0,00 1,00 0,00 9,00 1,80

0,00 0,00 6,00 0,00 0,00 0,00 1,00 18,00 3,00

0,00 1,00 -1,00 1,00 0,00 0,00 0,00 3,00 -3,00

Simplex Tableau 5

Das Ergebnis dieser Umrechnung ist ein in Normalform befindliches Ausgangstableau,

dass nun wie gewohnt optimiert werden kann, so dass nach Durchführung der

Optimierung folgendes Tableau für das optimierte Produktionsprogramm vorliegt

(Zwischenschritt siehe Simplex Tableau 10 im Anhang).


Z y2 y3 x1 x2 y1 y4 bi qi

1,00 75,00 70,83 0,00 0,00 0,00 0,00 4350,00

0,00 0,75 -0,96 0,00 0,00 1,00 0,00 7,50

0,00 0,00 0,17 0,00 0,00 0,00 1,00 3,00

0,00 -0,25 0,21 1,00 0,00 0,00 0,00 1,50

0,00 0,25 -0,04 0,00 1,00 0,00 0,00 4,50

Simplex Tableau 6

Das Ergebnis des optimalen Tableaus empfiehlt nun 1,5 Stück von Produkt 1 sowie 4,5

Stück von Produkt 2. Trotzdem werden die Kapazitäten nicht voll ausgenutzt. Auf

Maschine 1 stehen noch insgesamt 7,5 Stunden freie Kapazitäten zur Verfügung.

3.3.2. Gleichungen als Restriktion

Liegen anstelle der Ungleichungen in den Restriktionen Gleichungen vor, so muss auch

hier die Optimierung solange zurückgestellt werden bis eine erste zulässige Basislösung

ermittelt wird. Durch die Einführung einer zusätzlichen Schlupfvariable in der Restriktion

kann eine solche Basislösung gefunden werden.42 Diese Vorgehensweise macht Sinn, da sie

nachdem die Variable zur Nichtbasisvariable überführt wurde, anschließend mit einem



- 14 -

Sperrvermerk versehen wird um zu verhindern, dass diese wieder als Basisvariable

eingeführt wird.

Durch die Umwandlung zur Nichtbasisvariable wird erreicht, dass die Schlupfvariable Null

wird und damit die Gleichung erfüllt ist.43

Dem eigentlichen Simplex-Algorithmus muss damit wiederum eine weitere Phase

vorgeschaltet werden, in dem die mit einem Sperrvermerk versehenen Variablen als

Pivotzeilen bestimmt werden. Die Behandlung der einzelnen Zeilen bei vorliegen mehrerer

mit Sperrvermerk versehenen Variablen ist vollkommen beliebig. Als zugehörige Pivot-

spalte ist eine beliebige Nichtbasisvariable wählbar, sofern die Nichtbasisvariable ≠ 0 ist. 44

Das Verfahren soll wieder an dem unter Punkt 3.2.1 dargestellten Ausgangsproblem

dargestellt werden.

Hierbei soll ein dritter Artikel in das Produktionsprogramm aufgenommen werden. Bei

einem Gewinn von 100 € pro Stück wird eine Fertigungszeit von je 3 Stunden auf

Maschine A benötigt. Abgesehen von einer Einheit des Artikels 1 kann der Artikel 3 nur

zusammen mit dem Artikel 1 verkauft werden. Es ist damit eine zusätzliche

Restriktionsgleichung der Form x1 = 1 + x3 einzuführen, die nach Umstellung in die Form

x1 - x3 = 1 als Restriktion in das vorliegende Gleichungssystem einfließen wird:

(1) 5x1 + 2x2 +3x3 ≤ 24 (2) x1 + 5x2 ≤ 24 (3) 6x1 + 6x2 ≤ 36 (4) x1 - x3 = 1

Wiederrum zum Simplex Tableau überführt ergibt sich folgende Darstellung:


Z x1 x2 x3 y1 y2 y3 y4(g) bi

1,00 -500,00 -800,00 -100,00 0,00 0,00 0,00 0,00 0,00

0,00 5,00 2,00 3,00 1,00 0,00 0,00 0,00 24,00

0,00 1,00 5,00 0,00 0,00 1,00 0,00 0,00 24,00

0,00 6,00 6,00 0,00 0,00 0,00 1,00 0,00 36,00

0,00 1,00 0,00 -1,00 0,00 0,00 0,00 1,00 1,00

Simplex Tableau 7

Die Variable y4 wird mit einem kleinen g für gesperrt gekennzeichnet. Die neu hinzugefügte

Restriktion wird gleichzeitig zur Pivotzeile und als zugehörige Pivotspalte wird

anschließend x1 ausgewählt. Durch Umrechnung wird die Variable y4 zur

Nichtbasisvariablen transformiert und damit das Simplex Tableau zu einer zulässigen

Basislösung überführt.



neue Restriktion

- 15 -


Z x2 x3 y4(g) x1 y1 y2 y3 bi

1,00 -800,00 -600,00 500,00 0,00 0,00 0,00 0,00 500,00

0,00 2,00 8,00 -5,00 0,00 1,00 0,00 0,00 19,00 9,50

0,00 5,00 1,00 -1,00 0,00 0,00 1,00 0,00 23,00 4,60

0,00 6,00 6,00 -6,00 0,00 0,00 0,00 1,00 30,00 5,00

0,00 0,00 -1,00 1,00 1,00 0,00 0,00 0,00 1,00 -- / --

Simplex Tableau 8

Nachdem diese Form erreicht wurde kann wie gewohnt mit der Optimierung begonnen

werden. Auf Darstellung des Zwischenschrittes zur Optimierung des Simplex Tableaus

wird an dieser Stelle verzichtet, sodass direkt die optimierte Lösung dargestellt wird. Im

Anhang (Simplex Tableau 11) kann der fehlende Schritt jedoch nachgeschlagen werden.

Simplex Tableau 9

Wie an der oberen Lösung erkannt werden kann weißt die Nichtbasisvariable y4 im Simplex

Tableau 9 auch im optimalen Zustand einen negativen Wert in der Zielfunktion auf. Trotz

dieses Umstands ist das an dieser Stelle vorliegende Ergebnis optimal, da ja die Variable y4

als gesperrt gekennzeichnet ist.

Nichtbasisvariable Basisvariablen

Z y2 y3 y4 x1 x2 x3 y1 bi

1,00 50,00 91,67 -100,00 0,00 0,00 0,00 0,00 4400,00

0,00 1,50 -1,58 3,00 0,00 0,00 0,00 1,00 6,00

0,00 0,25 -0,04 0,00 0,00 1,00 0,00 0,00 4,50

0,00 -0,25 0,21 -1,00 0,00 0,00 1,00 0,00 0,50

0,00 -0,25 0,21 0,00 1,00 0,00 0,00 0,00 1,50

- 16 -

3.4. Minimierungs-Problem

Auch bei der Minimierung eines linearen Programms besteht die grundlegende Frage wie

man dieses Problem in die für die Anwendung des Simplexverfahrens notwendige

Normalform überführen kann. Hierfür gilt45

Z = Min ↔ (-Z) = Max

Generell kann die Aussage getroffen werden, dass eine lineare Funktion ein Minimum dort

erreicht, wo sie multipliziert mit minus eins ein Maximum hat.46 Bevor der Simplex-

Algorithmus zur Lösung des Problems angewandt werden kann, muss auch hier überprüft

werden, ob die zu optimierende Aufgabe in Normalform vorliegt und die Basislösung

zulässig ist.

Das anschließende Ergebnis kann dann durch Multiplikation mit -1 als Z interpretiert

werden.

3.5. Optimalitätskriterium

Wie in Kapitel 3.2.3 gezeigt wurde, gilt eine Zielfunktion und damit das Tableau als optimal

gelöst, wenn alle Variablen einen positiven Wert einnehmen.

Jedoch kann es immer wieder vorkommen, dass eine unbeschränkte Lösung vorliegt, dass

heißt das Optimum liegt im Unendlichen. Eine unbeschränkte Lösung liegt dann vor, wenn

die Pivotspalte nur negative Werte aufweist.47 Dies würde dazu führen, dass die Lösung bei

steigendem Wert der Basisvariable auch steigen würde und dabei weder die eigentlichen

Nichtnegativitätsbedingungen noch die Restriktionen verletzt werden würden.

45 Sturm, M., Wirtschaftsmathematik Lerneinheit 2, 2002, S. 50f.


47 Fernuniversität Hagen: http://www.fernuni-hagen.de/BWLOR/assets/courses/k00053-9-4.pdf, S. 7

Zugriff 16.07.2008.

- 17 -

4. Anwendung des Simplex-Algorithmus in der Praxis

SAP bietet mit SAP Advanced Planner and Optimizer (kurz SAP APO) ein System, dass

die Planung und Optimierungsaufgaben im Rahmen des Supply Chain Management

übernimmt. Zur Verdeutlichung des Simplex-Algorithmus wird im Nachfolgenden eine

Optimierung mithilfe des Supply Network Planning Optimizer (SNP optimizer)

dargestellt.48

Ziel des SNP optimizer ist es, anhand einer Zielfunktion, die zum Beispiel aus Transport-,

Produktions-, Lager- und Umschlagskosten besteht, eine Logistikkette so aufeinander

abzustimmen, dass die Minimalkostenkombination hieraus entsteht.

Das bei der Optimierung in SAP zugrundeliegenden Modell bietet die Möglichkeit, so

genannte Softconstraints zu definieren, also Restriktionen die nicht unter allen Umständen

zu berücksichtigen sind. Verletzungen werden genau dann hingenommen wenn dies billiger

ist als sie einzuhalten. Damit wird eine Priorisierung einzelner Aspekte des zu

optimierenden Modells möglich. So kann eine sehr schnelle Lieferung dadurch gefördert

werden, dass entsprechend hohe Verzugskosten kalkuliert werden.49

Datenbasis

Bestellung vornehmenLineares Modell erzeugen

Optimization Solver

Lösungskonsistenz überprüfen und Optimallösung ermitteln

Daten erfassen

Ausgangsmodell Optimiertes Modell

Aktualisierte Bestellungen

Darstellung 3 nach Bartsch, H / Teufel T: Supply Chain Management mit SAP APO

Das oben dargestellte Modell zeigt den Ablauf einer Optimierung mit Hilfe von SAP auf.

Die entsprechende Zusammenstellung der Elemente der Lieferkette wird im Anschluss

automatisiert von APO vorgeschlagen.

Ausgewählt werden kann das Verfahren des primären oder dualen Simplexverfahren

beziehungsweiße das Innere Punkt Verfahren zur Lösung des Modells.50

48 Bartsch, H. / Teufel T., Supply Chain Management mit SAP, 2002, S. 318.



- 18 -

5. Resümee

Der hier vorgestellte Algorithmus zeigt die von Dantzig geschaffenen Grundlagen zur

Lösung linearer Probleme auf. Dieser wird auch als primale Simplexmethode bezeichnet,

da zu jeder Simplexlösung auch eine duale Lösung ermittelt werden kann, die im

Wesentlichen auf dem Tausch von Spalten und Zeilen beruht.

In der Mathematik haben sich optimierte Verfahren zum Originalverfahren von 1947

entwickelt. Als moderner Vertreter des Simplexverfahrens ist, aufgrund seiner schnelleren

Rechenzeit, das revidierte Simplexverfahren, dass sich die Eigenschaft zu nutze macht, dass

trotz des Vorhandenseins einer großen Anzahl von Restriktionen nur ein gewisser

Prozentsatz hieraus verwendet wird. Eine weitere Optimierung stellt die LU-Zerlegung dar,

die das als Matrix dargestellte Ausgangsproblem in eine untere und obere Dreiecksmatrix

unterteilt. Sie macht sich zu nutzen, dass anschließend viele Gleichungssysteme mit

derselben Matrix, aber unterschiedlichen rechten Seiten effizient gelöst werden können.51

Bei der Anwendung des Simplexverfahrens in der Praxis muss jedoch immer berücksichtigt

werden, dass hierfür eine Reihe von Annahmen getroffen werden müssen, um das Problem

in Gleichungs- beziehungsweise Ungleichungsform zu bringen. Einzelne technische oder

wirtschaftliche Aspekte können in einem solchen mathematischen Modell oft nicht

ausreichend beschrieben werden. Es entstehen Abweichungen von der realen

Problemstellung, die sich dann auch auf das Ergebnis des Verfahrens auswirken.

Alleine die in Kapitel 3.2.1 erstellte Zielfunktion geht von einem gleich bleibenden Gewinn

je abgesetztes Stück aus, was in der Praxis als sehr unrealistisch einzuschätzen ist. Eine

mögliche Fixkostendegression wird hierbei zum Beispiel nicht betrachtet.

Doch werden im Operations Research, besonders aus den Themengebieten der

Nichtlinearen Optimierung sowie der Ganzzahlen Optimierungen Lösungswege aufgezeigt,

um solche Probleme zu begegnen.52

51 Grötschel, M., Lineare Optimierung, 2002, S. 169 sowie

Wikipedia: http://de.wikipedia.org/wiki/Simplex-Algorithmus, Zugriff am 02.08.08.

52 Zimmermann, W., Operations Research, 1990, S. 208f.

- 19 -

Literaturverzeichnis

Bartsch, H / Teufel T: Supply Chain Management mit SAP APO – Supply-Chain Modelle mit

dem Advanced Planner and Optimizer, Galileo Verlag, 2002

Dempe, Stephen / Schreier, Heiner: Operations Research – Deterministische Modelle und

Methoden, Wiesbaden, B. G. Teubner Verlag / GWV Fachverlage GmbH, 2006

Friedrich, Alfred: Lineare Optimierung – Probleme und Lösungen aus Wirtschaft und Technik,

Renningen-Malsheim, 2001

Grötschel, M: Lineare Optimierung – Algorithmische Diskrete Mathematik, Technische

Universität Berlin – Institut für Mathematik, 2003

Schick, Karl: Lineares Optimieren, Frankfurt am Main, 1972

Sturm, Manfred: Wirtschaftsmathematik – Lerneinheit 2, Hagen, IfV NRW, 2002

Zimmermann, Werner: Operations Research – Quantitative Methoden zur

Entscheidungsvorbereitung, München, Oldenburg, 1990

I

6. Anhang

Begriffsdefinition

nach Sturm, M., Wirtschaftsmathematik Lerneinheit 2, S.69

Basislösung gegeben ist ein lineare Gleichung mit m Gleichungen und n

Variablen (m>n). Weist man einer beliebigen Auswahl von (m-n)

Variablen (den sogenannten „freien Variablen“) den Wert Null zu,

so erhält man eine eindeutige Lösung für den restlichen n

Variablen. Die Lösung hierzu nennt man Basislösung mit n

Basisvariablen und m-n Nichtbasisvariablen.

Basisvariable siehe Basislösung.

Entscheidungs-

variable

verändlerliche Variable, deren Wert in Abhängigkeit von der

Zielfunktion optimal zu bestimmen ist; stellt die

Handlungsalternative im praktischen Problem dar.

Gesperrte

Schlupfvariable

aus mathematischen Gründen zusätzlich definierte Variable in

Zusammenhang mit einer Gleichung als Nebenbedingung:

Hintergrund ist die Idee das diese Variable einmal zur

Nichtbasisvariable überführt und damit nie mehr ≠ 0 sein kann.

Nebenbedingung Rahmenbedingung, die bei der Optimierung einer Zielfunktion

beachtet werden muss.

Nichtbasisvariable siehe Basislösung.

Nichtnegativitäts-

bedingung

Restriktion, um nicht zuzulassen, dass die Entscheidungsvariablen

oder Schlupfvariablen negativ werden.

Schlupfvariable Variable um eine Ungleichung() in eine Gleichung umzuwandeln.

Zielfunktion Funktion, die in Abhängigkeit vom praktischen Problem die

Zielsetzung des Handelns bestimmt; hierbei ist die Funktion

entweder zu maximieren oder minimieren.

II

Anhang: Simplex Tableau 1 - Umrechnung

Anhang: Simplex Tableau 10

Zur Vervollständigung der Ausarbeitung wird hier der Zwischenschritt zu Kapitel 3.3.1

dargestellt.


Z x 1 y2 x2 y1 y3 y4 bi qi

1,00 -340,00 160,00 0,00 0,00 0,00 0,00 3840,00

0,00 4,60 -0,40 0,00 1,00 0,00 0,00 14,40 3,13

0,00 -0,80 0,20 0,00 0,00 0,00 1,00 1,80 -2,25

0,00 4,80 -1,20 0,00 0,00 1,00 0,00 7,20 1,50

0,00 0,20 0,20 1,00 0,00 0,00 0,00 4,80 24,00

Simplex Tableau 9

Anhang: Simplex Tableau 11

Zur Vervollständigung der Ausarbeitung wird hier der Zwischenschritt zu Kapitel 3.3.2

dargestellt.


Z x3 y2 y4(g) x1 x2 y1 y3 bi

1,00 -440,00 160,00 340,00 0,00 0,00 0,00 0,00 4180,00

0,00 7,60 -0,40 -4,60 0,00 0,00 1,00 0,00 9,80 1,29

0,00 0,20 0,20 -0,20 0,00 1,00 0,00 0,00 4,60 23,00

0,00 4,80 -1,20 -4,80 0,00 0,00 0,00 1,00 2,40 0,50

0,00 -1,00 0,00 1,00 1,00 0,00 0,00 0,00 1,00 -1,00

Simplex Tableau 10


x1 x2 y1 y2 y3 bi

-500 + 800 * 0,2 = -340

-800 + 800 * 1 = 0

0 + 800 * 0 = 0

0 + 800 * 0,2 = 160

0 + 800 * 0 = 0

0 + 800 * 4,8 = 3840

5 - 2 * 0,2 = 4,6

2 - 2 * 1 = 0

1 - 2 * 0 = 1

0 - 2 * 0,2 = -0,4

0 - 2 * 0 = 0

24 - 2 *4,8 = 14,4

1 / 5 = 0,2

5 / 5 = 1

0 / 5 = 0

1 / 5 = 0,2

0 / 5 = 0

24 / 5 = 4,8

6 - 6 * 0,2 = 4,8

6 - 6 * 1 = 0

0 - 6 * 0 = 0

0 - 6 * 0,2 = -1,2

1 - 6 * 0 = 1

36 - 6 * 4,8 = 7,2

Documents

Hausarbeit Operations Research · PDF fileHausarbeit Operations Research - Der Simplex-Algorithmus - Eingereicht von: Christoph Böhm MatrikelNr.: 10014637 Am Anger 30a 91365 Weilersbach