Der Simplex Algorithmus leicht gemacht!

Operations Research (Lineare Optimierung)


Fachbuch, 2012

43 Seiten


Leseprobe

Inhalt

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

Optimierung allgemein

1. Das allgemeine Vorgehen, bevor der Algorithmus durchlaufen wird
1.1 Die Entscheidungsvariablen
1.2 Die Nebenbedingungen und die Zielfunktion "F"
1.2.1 ≤ Bedingungen
1.2.2 ≥ Bedingungen
1.2.3 Gleichungen als Nebenbedingungen
1.2.4 Besondere Nebenbedingungen
1.2.5 Die Zielfunktion "F"
1.3 Die Normalform

2. Primale und duale Iterationen
2.1 Der primale Simplex Algorithmus
2.2 Der duale Simplex Algorithmus

3. Probleme bei der Lösungsfindung
3.1 Primale Degeneration
3.2 Duale Degeneration
3.3 Unlösbarkeit und unendlich viele Lösungen

4. Neue Nebenbedingungen & Sensitivitätsanalyse
4.1 Einfügen einer neuen Nebenbedingung
4.2 Die Schattenpreise und die reduzierten Kosten
4.3 Wie weit darf sich „bi“ ändern bis sich die Basis ändert?
4.4 Wie weit darf sich „cj“ ändern, bis sich die Basis ändert?

5. Mehrfachzielsetzung
5.1 Lexikographische Zielhierarchie
5.2 Nebenziele als Nebenbedingung
5.3 Die Gewichtung der Ziele

6. Konklusion
6.1 Praxisrelevanz
6.2 Wann werden welche Iterationen benutzt?

Literaturverzeichnis

Anhang 1:

Anhang 2:

Anhang 3:

Anhang 4:

Anhang 6

Anhang 7

Abbildungsverzeichnis

Abbildung 1: primale Degeneration.

Abbildung 2: Kapazitätsänderung

Abbildung 3: Iterationsvorschrift

Tabellenverzeichnis

Tabelle 1: Starttableau des primalen Simplex Algorithmus

Tabelle 2: zweite Basislösung

Tabelle 3: Optimaltableau

Tabelle 4: Nährwerte

Tabelle 5: Starttableau des dualen Simplex Algorithmus

Tabelle 6: Optimaltableau des dualen Simplex Algorithmus

Tabelle 7: Tableau mit neuer Nebenbedingung

Tabelle 8: Optimaltableau mit neuer Nebenbedingung

Tabelle 9: Opportunitätskosten

Tabelle 10: Optimaltableau

Tabelle 11: Optimaltableau mit gewichteten Zielen

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Optimierung allgemein

Viele ökonomische Fragestellungen beschäftigen sich mit der Suche nach einer optimalen Lösung. Bereits in der Schule wird die Kurvendiskussion gelehrt, bei der es zum Teil um die Ermittlung von lokalen und globalen Extrema geht. In der Wirtschaftswissenschaft ermittelt sich z.B. der Preis eines Monopolisten in Abhängigkeit der Preis-Absatz-Funktion durch den Cournotschen Punkt1, welcher das Gewinnmaximum darstellt. Dies gilt allerdings nur für Monopole. Wesentlich mehr Unternehmen befinden sich im Wettbewerb. Hier ermittelt sich der Preis nicht in Abhängigkeit der Preis-Absatz-Funktion, sondern bestimmt sich durch das Marktgleichgewicht, wodurch das Unternehmen keinen oder kaum Einfluss ausüben kann.

Hinweis 1: Natürlich gibt es durch die Differenzierung (durch Marketinginstrumente) von anderen Unternehmen einen gewissen Spielraum (monopolistischer Bereich), der für den Preis ausgenutzt werden kann.2

Viele Unternehmen stehen deswegen vor der Frage, wie genau sie z. B. ihren Gewinn erhöhen können. Diese Gewinnsteigerung bewirkt sich natürlich nicht nur über die Festsetzung des optimalen Preises, sondern auch über viele andere Faktoren, denn der Gewinn besteht ja auch aus den Kosten und der abgesetzten Menge.

De facto wollen Unternehmen eine unter gegebenen Umständen optimale Lösung finden. Ein Instrument, welches unter der Annahme der Linearität (von Nebenbedingungen und Zielfunktion) eine annehmbare Lösung finden kann ist der Simplex Algorithmus.

Ein Algorithmus ist eine exakte Methode, welche eine genaue Lösung findet.

Es handelt sich bei dem Simplex Algorithmus (SA) um keine Annäherungsmethode, obwohl die benutzten Nebenbedingungen und die Zielfunktion oft nur als Linear approximiert werden.

Zur Beschreibung des Vorgehens müssen zwischendurch immer wieder einige Begrifflichkeiten geklärt werden.

Es wird unterschieden zwischen dem primalen und dem dualen Simplex Algorithmus.3 Zunächst soll die grundlegende Vorbereitung in zwei Schritten erläutert werden, um danach die beiden Arten des Simplex Algorithmus anhand eines produktions- Optimierungsproblems sowie eines Mischungsproblems zu erläutern. Die einzelnen Rechenschritte (Iterationen) und Grafiken finden sich im Anhang. Im letzten Teil wird dann auf die Sensitivitätsanalyse und Mehrfachzielsetzung umfassend eingegangen.

1. Das allgemeine Vorgehen, bevor der Algorithmus durchlaufen wird

Der erste Schritt ist die Findung der Entscheidungsvariablen. Die Anzahl der Entscheidungsvariablen n gibt die Anzahl der Dimensionen des Vektorraums Rn des konvexen Polyeders wieder. Ein konvexes Polyeder ist die Menge aller konvexen Linearkombinationen endlich vieler Punkte im Rn.4

Ein Beispiel: Ein Unternehmen identifiziert die Anzahl der unterschiedlichen Produkte als Entscheidungsvariablen. Wenn das Unternehmen drei Produkte herstellen und absetzen kann, so ist ein R3, also ein drei dimensionaler Vektorraum gegeben.

1.1 Die Entscheidungsvariablen

Entscheidungsvariablen oder Strukturvariablen5 sind die Veränderlichen, deren Menge unter sonst konstanten Bedingungen optimiert werden sollen. Hierbei kann es sich z. B. um Mengen absatzfähiger Produkte, um Inhaltsstoffe von Nahrungsmitteln, um Liefermengen bei Logistikproblemen oder um Wahrscheinlichkeiten gemischter Strategien bei Matrixspielen der Spieltheorie handeln.

Warum ist aber die Findung der relevanten Entscheidungsvariablen so wichtig?

Hierzu ein kleines Beispiel:

Eine Öl-Raffinerie kann aus drei verschiedenen Rohölsorten a, b, c drei verschiedene Benzinsorten 1, 2, 3 herstellen, wobei jede Sorte Benzin alle drei Ölsorten beinhaltet.5 Wie sind hier die Entscheidungsvariablen zu definieren?

Die Antwort auf diese Frage ist mit einem eine kleinen Trick verbunden, der darin besteht, so zu tun, als ob es sich nicht um drei, sondern um neun Ölsorten handle. Rohölsorte "a" ist zwar in Benzin 1, 2 und 3 vorhanden, doch legt man nun fest, dass es jetzt drei unterschiedliche Sorten "a" und zwar a1, a2 und a3 gibt. Insgesamt ergeben sich dadurch neun Entscheidungsvariablen.

Es ist also nicht selbstverständlich die Entscheidungsvariablen von Anfang an zu kennen und es lohnt sich kurz darüber nachzudenken.

Der zweite Schritt zur Vorbereitung ist die richtige Festlegung der Nebenbedingungen und der Zielfunktion, was meiner Meinung nach der schwerste ist.

1.2 Die Nebenbedingungen und die Zielfunktion "F"

Bei den Nebenbedingungen handelt es sich oft um Kapazitätsbeschränkungen oder Mindestanforderungen in Form von Ungleichungen oder manchmal auch Gleichungen. Eine Nebenbedingung schränkt die Optimierung der Zielfunktion ein. Denn es kann meistens nicht einfach davon ausgegangen werden, dass die Zielfunktion einfach unbegrenzt gesteigert werden kann. Kein Unternehmen kann ohne auf Absatzschranken, Produktionskapazitäten oder finanzielle Mittel zu achten einfach unendlich viel herstellen, um dadurch den Gewinn ins unendliche zu erhöhen. Ergo müssen immer gewisse Nebenbedingungen beachtet werden.

Der einfachste Weg um die Aufstellung von Nebenbedingungen zu erklären ist anhand von Beispielen. Im Folgenden sollen die wichtigsten Arten von Nebenbedingungen jeweils anhand eines Beispiels geklärt werden.

1.2.1 ≤ Bedingungen

Ein Unternehmen stellt zwei Guter x1 und x2 her und hat ein Lager in von 100 m3. die Lagerung von x1 benötigt 0,5 m3 und die von x2 1,5 m3.

Die Nebenbedingung lautet somit: 0,5x1 + 1,5x2 ≤ 100 weil höchstens 100 m3 aufgebraucht werden können. Das Ungleichungszeichen ≤ kann also mit höchstens übersetzt werden.

1.2.2 ≥ Bedingungen

Ein Unternehmen stellt zwei Guter x1 und x2 her und möchte einen Mindestabsatz von 30 Teilen, egal ob Gut eins oder Gut zwei realisieren.

Die Nebenbedingung lautet somit: x1 + x2 ≥ 30

weil mindestens 30 Teile abgesetzt werden sollen. Das Ungleichungszeichen ≥ kann also mit mindestens übersetzt werden.

1.2.3 Gleichungen als Nebenbedingungen

Wenn eine Gleichung als Nebenbedingung gegeben ist, z. B. weil die Summe der Gewichtungen von Wertpapieren in einem Portfolio genau eins sein soll, so werden aus der Gleichung einfach zwei Ungleichungen gemacht.6

Gegeben sei: 2x = 4

somit wird die Gleichung ausgewechselt durch 2x ≤ 4 und 2x ≥ 4.

Wenn 2x einerseits größer gleich vier aber andererseits auch gleichzeitig kleiner gleich vier sein soll, so bleibt nur „gleich vier“ als einziger zulässiger Wert übrig.

1.2.4 Besondere Nebenbedingungen

Es gibt einige Nebenbedingungen, die besonderer Überlegung bedürfen. Hier sollen kurz zwei davon anhand jeweils eines Beispiels erläutert werden.

Ein Unternehmen kann zwei Güter herstellen x1 und x2. Entweder können 8 Mengeneinheiten von x1 oder 3 Mengeneinheiten von x2 hergestellt werden. Jede Linearkombination ist zulässig.

Die Nebenbedingung lautet hier: ⅛ x1 + ⅓ x2 ≤ 1

Sobald von x1 = 8 Mengeneinheiten hergestellt werden, wird der Quotient ⅛ x1 zu eins und die Kapazität ist ausgeschöpft. Gleiches gilt analog bei ⅓ x2.

Eine Brauerei habe Bier mit 5 % Alkohol (x1) und Orangensaft (x2) mit ca. 0,5 %. Sie möchte ein Getränk mit höchstens 3 % Alkohol mischen.7

Jetzt darf nicht der Fehler gemacht werden, den Alkoholanteil für eine absolute Größe zu halten. Denn dann würde die Nebenbedingung lauten: 5x1 + 0,5 x2 ≤ 3. Es wird schnell klar, dass bei einer Mischung aus zwei Getränken mit maximal 5 % Alkohol niemals mehr als 5 % herauskommen kann. Deswegen wird bei Mischungsproblemen mit relativen Anteilsangaben noch durch die Summe der betroffenen Entscheidungsvariablen geteilt.

Hierbei ist es unmöglich, mehr als 3 % Alkoholanteil zu erhalten.

Nebenbedingungen schränken zumindest meistens den Bereich der Zielfunktion ein. Doch wie wird eine korrekte Zielfunktion, die ja optimiert werden soll, aufgestellt?

1.2.5 Die Zielfunktion "F"

Bei Zielfunktionen des SA handelt es sich um homogene Funktionen. Das bedeutet, sie haben keine Konstante. Folgendes Beispiel zeigt die Aufstellung einer Zielfunktion:

Ein Unternehmen hat das Ziel8 seinen Gewinn zu maximieren. Zwei Produkte x1 und x2 werden produziert. Der Stückumsatz (Preis) für x1 sei 10 € und der für x2 sei 15 €. Die variablen Kosten für x1 seien 5 € und die für x2 8 €. Die Fixkosten betragen 200 €.

Die Gewinnfunktion sieht folgendermaßen aus:

Da die Fixkosten sowieso bezahlt werden müssen, auch wenn die Produktion komplett heruntergefahren wird, kann man diese weglassen.

Die Zielfunktion F (x1, x2) lautet dann: F (x1, x2) = 5x1 + 7x2

Um ein Optimierungsproblem lösen zu können, muss es zunächst auf Normalform gebracht werden, von wo aus dann direkt die Simplexmethode angewandt werden kann.

1.3 Die Normalform

Bisher ist festzuhalten, dass ein Optimierungsproblem aus Nebenbedingungen und einer Zielfunktion „F“ besteht. Um die Normalform zu erreichen müssen alle Nebenbedingungen zu ≤-Bedingungen umgewandelt werden, indem die ≥-Bedingungen mit minus eins multipliziert werden, was alle Vorzeichen und das ≥ in ein ≤ ändert. Wenn die Zielfunktion ein Minimierungsproblem ist, so wird diese, multipliziert mit minus eins, zu einem Maximierungsproblem.9

Bei der Simplexmethode müssen allerdings, um das lineare Optimierungsproblem lösen zu können aus den Ungleichungen erst einmal Gleichungen gebildet werden. Aus einer Ungleichung ergibt sich eine Gleichung, indem eine so genannte Schlupfvariable hinzufügt wird, welche die Differenz zwischen der rechten und linken Seite der Gleichung sozusagen auffängt (ausgleicht).10

Beispiel:

2x ≤ 8; wenn für x = 2 eingefügt wird, so ist die Ungleichung erfüllt. Wird nun eine Schlupfvariable (u) hinzugefügt: 2x + u = 8, so ergibt sich eine Gleichung. Wenn nun eine zwei für x eingesetzt wird, fängt (u) den Rest auf. Die Schlupfvariable (u) hätte dann den Wert vier. Die Normalform sieht folgendermaßen aus:

Zielfunktion:

F(x1, x2, ..., xn-1, xn) = ∑nj=1 cj * xj => max!

wobei beispielsweise cj der Nutzenkoeffizient und xj die Entscheidungsvariable des Produktes j ist. Unter den Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

Beispielsweise ist hier aij der Verbrauch der Kapazität eines Produktes j an der Maschine i, ui ist die Schlupfvariable und bi die Kapazität der Maschine i.

Darüber hinaus komme die Nichtnegativitätsbedingung xj ≥ 0 zum Tragen, denn negative Mengen sind nicht sinnvoll.

Nachdem die Zielfunktion und die Nebenbedingungen aufgestellt sind, ist der nächste Schritt die Berechnung. Der SA kann zur Erleichterung mit einem so genannten Simplextableau, oder auch ohne dieses durchgeführt werden.

2. Primale und duale Iterationen

Entweder kann ohne Tableau gerechnet werden, indem anfangs die Strukturvariablen xj und bi die Schlupfvariablen ui erklären. Sprich, die Schlupfvariablen befinden sich nun in der Basis. Danach wird die Variable, die den größten Nutzenzuwachs für die Zielfunktion bringt genommen und geschaut, wie groß diese Variable maximal sein darf, bis die Basisvariablen gerade zu null werden. Das wird erreicht, indem die Konstante jeder einzelnen Nebenbedingung durch den jeweiligen Koeffizienten der Variable, die ja den größten Zuwachs an Nutzen bringt, geteilt wird. Der dabei entstehende Quotient nennt sich Charakteristischer Quotient11 (CQ) wovon der kleinste zu wählen ist, da dieser die härteste Restriktion darstellt. Die Basisvariable, die den kleinsten CQ hat, wird zu der Variable hin, die in der Zielfunktion den größten Nutzen bringt, aufgelöst und in alle anderen Basisvariablen, sowie die Zielfunktion eingesetzt. Hierdurch entsteht die zweite zulässige Basislösung, bei der nun die in der Zielfunktion zuvor nützlichste Variable in die Basis aufgenommen wurde.12 Die Nichtbasisvariablen werden gleich Null gesetzt und die Konstanten stellen die Lösungen dar. Diese Iterationen sind weiter durchzuführen, bis alle Werte in der Zielfunktion < 0 sind, denn dann ist die optimale Lösung gegeben.

Hinweis 2: Die erste Basislösung ergibt sich durch Nullsetzen der Nichtbasisvariablen direkt am Anfang, hierbei stellt der "übrige" Schlupf die Basislösung dar.

Es kann aber auch mit Tableau vorgegangen werden, was im Folgenden an zwei Beispielen gezeigt wird. Das obige Vorgehen sollte zunächst einige grundlegende Begrifflichkeiten klären.

2.1 Der primale Simplex Algorithmus

Folgendes Optimierungsproblem ist gegeben:

Das Simplex-Tableau wird nach den Vorgaben von 1. 3 aufgebaut. Hierzu wird eine erweiterte Koeffizientenmatrix aus der Koeffizientenmatrix (A) der Strukturvariablen, einer Einheitsmatrix (I) aus den Schlupfvariablen, sowie einem Vektor (b) aus den Konstanten aufgestellt. Es handelt sich um eine (m *(n + m + 1)) Matrix, wobei m die Anzahl der linearen (unabhängigen) Nebenbedingungen und n die Anzahl der Variablen ist. Plus eins entsteht wegen dem Konstantenvektor b.

[...]


1 Operatives Marketing-Instrumente der Marketingpraxis Anne Jacobi S. 154

2 Operatives Marketing-Instrumente der Marketingpraxis Anne Jacobi S. 157

3 vgl. Einführung in Operations Research von Domschke und Drexel 8. Auflage S. 24 u. 26

4 vgl. Einführung in Operations Research von Domschke und Drexel 8. Auflage S. 19

5 vgl. Einführung in Operations Research von Domschke und Drexel 8. Auflage S. 17

6 In Anlehnung an das Skript Operations Research von Prof. Dr. Reimpell S. 50

7 vgl. Einführung in Operations Research von Domschke und Drexel 8. Auflage S. 17

8 In Anlehnung an das Skript Operations Research von Prof. Dr. Reimpell S. 50

9 Ziele müssen eigentlich immer operationalisiert sein, dies wird hier der Einfachheit halber vernachlässigt.

10 In Anlehnung an Einführung in Operations Research von Domschke und Drexel 8. Auflage S. 17

11 Mathematik anschaulich dargestellt für Studierende der Wirtschaftswissenschaft von Peter Dörsam 15. Auflage S. 135

12 Entspricht dem Vorgehen von Strategische Spiele für Einsteiger von Alexander Mahlmann 1. Auflage 2007 S. 23-25

Ende der Leseprobe aus 43 Seiten

Details

Titel
Der Simplex Algorithmus leicht gemacht!
Untertitel
Operations Research (Lineare Optimierung)
Autor
Jahr
2012
Seiten
43
Katalognummer
V199030
ISBN (eBook)
9783656254508
ISBN (Buch)
9783656255956
Dateigröße
839 KB
Sprache
Deutsch
Schlagworte
Simplex Algorithmus, Lineare Optimierung, Simplex, dual, primal, degenneration, Sensitivitätsanalyse, Operations Research, OR, Normalform, Konvexes Polyeder, Optimierung, Vektorraum, Mischungsproblem, Mischproblem, Simplexalgorithmus, einfach erklärt
Arbeit zitieren
Bachelor of Arts Frank Raulf (Autor), 2012, Der Simplex Algorithmus leicht gemacht!, München, GRIN Verlag, https://www.grin.com/document/199030

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Der Simplex Algorithmus leicht gemacht!



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden