Grundlagen der anwendungsorientierten Optimierungstheorie mit Standardsoftware

II. Inhaltsverzeichnis

I. Summary

II. Inhaltsverzeichnis

III. Abbildungsverzeichnis

IV. Tabellenverzeichnis

V. Abkürzungsverzeichnis

VI. Symbolverzeichnis

VII. Verzeichnis der Anhänge

1. Einführung lineare Optimierung / Operations Research
1.1. Ursprung der linearen Optimierung
1.2. Relevanz linearer Optimierungsmodelle in der Betriebswirtschaftslehre und Wirtschaftsinformatik
1.3. Zielsetzung des Untersuchungsgegenstandes der Arbeit anhand ausgewählter Optimierungsmodelle

2. Grundlagen der linearen Optimierung
2.1. Standardmodelle linearer Optimierungsproblemstellungen
2.1.1. Begriffsdefinitionen
2.1.2. Bewertung und Einordnung grundlegender LP-Modelle
2.1.3. Anwendungsorientierte Modellierungstechniken
2.2. Grafische Interpretation von linearen Optimierungsmodellen
2.2.1. LP-Modell eines 2-dimensionalen Optimierungsproblems
2.2.2. Die typische Form des zulässigen Bereichs: der konvexe Polyeder
2.2.3. Untersuchung des ersten und zweiten Optimalitätskriterium und deren Einschränkungen
2.2.3.1. LP-Modelle ohne zulässige Lösung
2.2.3.2. Unbeschränkte LP-Modelle
2.2.3.3. Mehrdeutige Optimallösungen
2.2.3.4. Degenerierte Optimallösungen

3. Der Simplex-Algorithmus zur Lösung linearer Optimierungsmodelle
3.1. Grundlagen des Simplex-Algorithmus
3.2. Überführung des LP-Modells in das LP-Standardformat
3.3. Die Iteration des Simplex-Algorithmus zur optimalen Lösung des LP- Modells
3.3.1. Erste Iteration im Simplex-Algorithmus
3.3.2. Zweite Iteration im Simplex-Algorithmus

4. Erweiterung des Grundmodells
4.1. Nichtlineare Optimierung
4.2. Ganzzahlige Optimierung
4.3. Sensitivitätsanalyse im LP-Kontext

5. Standardsoftware zur Lösung von LP-Modellen
5.1. Aufstellung ausgesuchter Softwarelösungen zur Lösung von LP-Modellen
5.1.1. Bewertung standardisierter Softwarelösungen im DSS-Umfeld
5.1.2. Qualitätsbeurteilung von Standardsoftwareprodukten
5.1.3. Auswahl der Standardsoftware und der Arbeitsumgebung
5.2. Lösung linearer, nicht-linearer und ganzzahliger LP-Modell mittels Standardsoftware
5.2.1. EXCEL-SOLVER für lineare LP-Modelle
5.2.2. Entwicklung der Sensitivitätsanalyse mittels Spreadsheet
5.2.3. Darstellung nicht-linearer Modelle mittels Spreadsheet
5.2.4. Darstellung ganzzahliger LP-Modelle mittels Spreadsheet
5.2.5. WHAT’S BEST als Erweiterung des Tabellenkalkulationsumfelds
5.2.6. LP-Lösungsansätze in LINGO
5.3. Implementierung anwendungsorientierter Systemerweiterungen im Standardumfeld
5.3.1. Export einer CSV-Datei aus EXCEL
5.3.2. Export einer modifizierbaren ASCII-Datei aus EXCEL
5.3.3. Erstellung eines webbasierten interaktiven Spreadsheets
5.3.4. Fortgeschrittene Analysefunktionen im Spreadsheet
5.3.5. Erstellen einer Datenbanktabelle aus EXCEL

6. Zusammenfassende Bewertung der anwendungsorientierten Optimierungstheorie

VIII. Anhang 1: Simplex-Algorithmus in C

IX. Anhang 2: CVS-Datei erstellen

X. Anhang 3: Modifizierbare ASCII-Datei erzeugen

XI. Anhang 4: Access-Datenbanktabelle aus Excel erzeugen

XII. Literaturverzeichnis

I. Summary

Im Jahr 2006 war der Verfasser Angestellter eines Unternehmens, welches Photo- voltaik-Anlagen plante, verkaufte und installierte. Die Photovoltaikmodule werden mittels Aluminiumstangen, die in der Standardlänge von 6 Metern ab Werkfertigung ausgeliefert werden, am Dach befestigt. Natürlich hatte jedes Dach seine eigenen Abmessungen, die Stangenlänge von 6 Metern blieb jedoch konstant. Bei der Kon- fektion der Aluminiumstangen fiel dem Montageteam der stetig wachsende Materi- albestand - der sogenannten „Verschnitt“ - auf, welcher keinen weiteren Nutzen darstellte. So entstand folgende Frage: ausgehend von einer veränderbaren linea- ren Größe (Dach) mit der Berücksichtigung der Konstante (6 Meter Stange) sollte der kleinste Verschnitt für jede Installationsfläche neu berechnet werden. Die Idee eines Tabellenkalkulations-Mastersheets, welches die Aufgabe übernehmen sollte, wurde geboren. Forciert wurde die Frage des kleinsten Verschnitts durch die dama- lige Preiserhöhungen im Rohstoffhandel und die Motivation der Mitarbeiter, diese Aufgabe mathematisch zu lösen. Nach umfangreichen Online-Recherchen stieß das Team, welchem der Verfasser beiwohnte, auf das Thema „Lineare Optimie- rung“. Der logisch nachvollziehbare und zugleich interessanteste Aspekt dieses Themas war die Übertragbarkeit der Lösungsansätze in beliebige Bereiche des Geschäftslebens, da viele Systeme in linearen Beziehungen zueinander stehen, wie beispielsweise LKW-Beladungen, Kosten- und Ertragsfunktionen, Lagerhal- tungsoptimierung, Wegstreckenplanungen.

Nach erster Sichtung der Fachliteratur sind die entscheidenden Hinweise zur Not- wendigkeit einer ernsthaften Auseinandersetzung mit dem Thema aufgetaucht, da beispielsweise: „ [ … ] beim Leser der Eindruck [erweckt wird], dass die mathemati- sche Optimierung eher nur für große Firmen und Unternehmen geeignet ist. Tat- sächlich wird die Optimierung häufiger in großen als in kleinen und mittelst ä ndi- schen Firmen angewendet. Dies hat zum Teil damit zu tun, dass letzteren die Mög- lichkeit der Optimierung nicht klar sind oder die Kenntnisse, das Personal und eventuell der passende akademische Hintergrund nicht zur Verf ü gung stehen. “

(Kallrath, 2002, S.51). Verstärkt wird dieser Eindruck weiterhin durch die Feststel- lung, dass das Thema „Lineare Optimierung“ im deutschsprachigen Raum eine eher untergeordnete Rolle in der Wirtschaftsinformatik und der Betriebswirtschafts- lehre darstellt: „ Die dabei zu ü berwindenden Schwierigkeiten [der mathematischen Optimierung] sind einerseits technischer Natur (Schnittstellenthematik mit allen

möglichen Systembr ü chen, oftmals auch über Firmengrenzen hinweg), aber in noch größerem Maße menschlicher Natur, da es im deutschsprachigen Raum, im Gegensatz zum angels ä chsischen beispielsweise, bislang keinen richtigen Durch- bruch für OR Methoden und mathematische Optimierung gab. “ (Kallrath, 2002, S.51).

Die benötigte Standardsoftware ist verfügbar und ausgereift, so dass im Zuge dieser Diplomarbeit ein möglichst anwendungsorientierter Ansatz, der sich vorrangig um die softwareseitige Implementierung zur Darlegung der Optimierungstheorie mit dem Schwerpunkt der linearen Optimierung bemüht, verfolgt werden soll.

III. Abbildungsverzeichnis

Abbildung 1: Modellbildung nach Gohout

Abbildung 2: Modellierung nach Suhl & Mellouli

Abbildung 3: grafische Darstellung eines 2-dimensionalen LP-Modells

Abbildung 4: konvexer/nicht-konvexer Polyeder

Abbildung 5: globales/lokales Maximum

Abbildung 6: Zahlenstrahl ohne Schnittmenge

Abbildung 7: Unbeschränktes LP-Modell

Abbildung 8: Mehrdeutiges LP-Modell

Abbildung 9: Degeneriertes LP-Modell

Abbildung 10: Basis- und Nichtbasisvariablen

Abbildung 11: Transfer der Schlupfvariablen

Abbildung 12: Auswahl der Pivotvariable und Pivotspalte

Abbildung 13: Auswahl der Pivotspalte und der Pivotzeile

Abbildung 14: Auswahl der Pivotspalte und Pivotzeile, Teil 2

Abbildung 15: tabellarische Lösung des Simplex-Algorithmus

Abbildung 16: Chancen und Risiken von Standardsoftware

Abbildung 17: Microsoft Office - Marktführer im Bereich Office-Anwendungen (entnommen aus http://de.statista.com/statistik/daten/studie/77226/umfrage/internetnutzer-- -verbreitung-von-office-software-in-deutschland/; Stand: 16.02.2010)

Abbildung 18: What’s Best im EXCEL-Kontext

Abbildung 19: Aufstellen des LP-Modells im Spreadsheet

Abbildung 20: funktionale Abhängigkeiten der Zellen im Spreadsheet

Abbildung 21: EXCEL-SOLVER

Abbildung 22: Dialogfester „SOLVER Options“ im EXCEL-SOLVER

Abbildung 23: EXCEL-SOLVER starten

Abbildung 24: Die EXCEL-SOLVER Einzelschritte als Szenario aufzeichnen

Abbildung 25: Dialogfenster „SOLVER Results“

Abbildung 26: Ergebnisbericht EXCEL-SOLVER

Abbildung 27: Lösung des LP-Modells mithilfe des EXCEL-SOLVERS

Abbildung 28: Auswahl der Sensitivitätsanalyse im EXCEL-SOLVER

Abbildung 29: Sensitivitätsanalyse des EXCEL-SOLVERS

Abbildung 30: nicht-lineare Funktion f (x)

Abbildung 31: EXCEL-Ergebnisse für x=2 und x=3,5

Abbildung 32: Aufstellung eines ganzzahligen LP-Modells im Spreadsheet

Abbildung 32: funktionale Abhängigkeiten im Spreadsheet (2)

Abbildung 33: Angabe der Ganzzahligkeit innerhalb des EXCEL-SOLVERS

Abbildung 34: ganzzahliges LP-Modell im EXCEL-SOLVER

Abbildung 35: Lösung des ganzzahligen LP-Modells mithilfe des EXCEL-SOLVERS

Abbildung 36: Aufstellung des LP-Modells mit EXCEL (2)

Abbildung 37: funktionale Abhängigkeiten im Spreadsheet (3)

Abbildung 38: WHAT’S BEST - Auswahl der Variablen des LP-Modells

Abbildung 39: Auswahl der Variablen mit WHAT’S BEST

Abbildung 40: Auswahl des Zielfunktionswertes in WHAT’S BEST

Abbildung 41: Auswahl der Beschränkungen in WHAT’S BEST

Abbildung 42: Lösung des LP-Modells mit WHAT’S BEST

Abbildung 43: lineares LP-Modell in LINGO

Abbildung 44: Lösung des LP-Modells mittels LINGO

Abbildung 45: exportiertes MPS-Format in LINGO

Abbildung 46: Export einer CSV-Datei aus dem Tabellenkalkulationsumfeld

Abbildung 47: Erstellung einer modifizierbaren ASCII-Datei aus dem

Tabellenkalkulationsumfeld

Abbildung 48: Speichern eines interaktiven Spreadsheets

Abbildung 49: Darstellung des interaktiven Spreadsheets im Browser

Abbildung 50: Auswahl des Datenbanksystems

Abbildung 51: Auswahl der Spalten im Datenbanksystem

Abbildung 52: Auswahl der relationalen Datenbanktabellen mit QUERY

Abbildung 53: Auswahl der Ausgabe des QUERY-Assistenen

Abbildung 54: Erster Schritt des OLAP-Cube-Assistenten

Abbildung 55: Zweiter Schritt des OLAP-Cube-Assistenten

Abbildung 56: Dritter Schritt des OLAP-Cube-Assistenten

Abbildung 57: Pivottabelle in EXCEL

Abbildung 58: Auswahl des ADOX-Objekts im VBA-Editor

Abbildung 59: Der ADOX-Objektkatalog

Abbildung 60: Anlegen einer ACCESS-Datenbanktabelle aus EXCEL

IV. Tabellenverzeichnis

Tabelle 1: Modellierungstechnik

Tabelle 2: ganzzahliger Wert/binärer Wert

Tabelle 3: Standardsoftware/Eigenentwicklung

V. Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

VI. Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

VII. Verzeichnis der Anhänge

VIII. Anhang 1: Simplex-Algorithmus in C

IX. Anhang 2: CVS-Datei erstellen

X. Anhang 3: Modifizierbare ASCII-Datei erzeugen

XI. Anhang 4: Access-Datenbanktabelle aus Excel erzeugen

1. Einführung lineare Optimierung / Operations Research

Einführend wird in diesem Kapitel die geschichtliche Entwicklung des Operations Research (OR) dargestellt. Im Weiteren werden die Notwendigkeit der linearen Optimierung in der Betriebswirtschaftslehre und Wirtschaftsinformatik, sowie die Abgrenzung des Untersuchungsobjekts dieser Arbeit, aufgezeigt.

1.1. Ursprung der linearen Optimierung

Entscheidungsträger sind oft mit Problemen der Zuordnung von knappen Ressour- cen konfrontiert: ein Manager des operativen Geschäfts möchte den Produktions- plan finden, welcher sein Output unter Geschichtspunkten des Deckungsbeitrages maximiert, ein Marketingmanager interessiert sich möglicherweise für eine Marke- tingkampagne, die seine Zielgruppe mit maximaler Streuung erreicht, ohne das vorgesehene Budget zu überschreiten. Diese Fragestellungen können Mittels linea- rer Optimierung gelöst werden. Die linearen Optimierung (engl. Linear Program- ming, LP) ist eine Methode für die Lösung von Optimierungsproblemen (Suhl & Mellouli, 2005, S.8). Eingebettet ist LP in das wirtschaftswissenschaftliche Fach OR, welches sich mit der Analyse von komplexen Problemstellungen im Rahmen eines Planungsprozesses zum Zweck der Vorbereitung von möglichst optimalen Entscheidungen beschäftigt (Domschke & Drexl, 2002, S.1). Der Ursprung dieses Begriffs liegt in den Jahren 1937 bis 1939 in England. Mit OR wurde eine Gruppe von Wissenschaftlern der englischen Armee bezeichnet, die die Aufgabe hatten die operationale Nutzung des Radarsystems durchzuführen (Zimmermann, 1992, S. 5). Folgendes Zitat verweist dabei auf die Mühe einer genauen Abgrenzung und Defi- nition von OR: „ Eine Abgrenzung dessen, was zum Operations Research geh ö rt und was nicht, ist in einem pr ä zisen Sinne kaum m ö glich. Dies gilt sowohl in inhalt- licher wie in methodischer Hinsicht. “ (Kathöfer & Müller-Funk, 2005, S.12). Für OR ist ein sehr breiter, interdisziplinärer Standpunkt charakteristisch. Typischerweise umfasst eine OR-Aufgabenstellung Experten aus den Gebieten der Volks- und Be- triebswirtschaft, der Mathematik, der Statistik und Wahrscheinlichkeitstheorie, so- wie der Informatik und Technik. Grundsätzlich kann festgehalten werden, dass der Einsatz von quantitativen¹ Methoden zur Entscheidungsfindung zentrales Thema des OR ist.

Die Idee der optimalen Entscheidungsfindung wurde weiterentwickelt von G.B. Dantzig, indem ein iteratives Verfahren in jedem Schritt eines Gleichungssystems gelöst wird und die jeweilig optimale Lösung alle Restriktionen des linearen Sys- tems vollständig ausschöpft - der Simplexalgorithmus (Dantzig, 1949, S.339-347) auf welchen noch detailliert eingegangen werden wird. Weiterhin wird eine Untertei- lung zwischen deterministischen und stochastischen Modellen in der gesichteten Literatur unterschieden. Bei deterministischen Modellen werden alle Parameter des Modells als fest vorgegeben vorausgesetzt, bei stochastischen Modellen wird vor- ausgesetzt, dass zumindest ein Parameter vom Zufall abhängt (Domschke & Drexl, 2007, S.6). Im weiteren Verlauf der Arbeit wird stets ein deterministisches Modell unterstellt.

1.2. Relevanz linearer Optimierungsmodelle in der Betriebswirtschafts- lehre und Wirtschaftsinformatik

„ Wichtige Voraussetzung f ü r die Anwendung von OR ist die Verf ü gbarkeit der er forderlichen Daten “ ( Domschke & Drexl, 2007, S.10).

Lineare Optimierungssysteme bilden aus Praxissicht die wichtigste Methode um betriebliche Anwendungssysteme effizient zu gestalten (Suhl & Mellouli, 2006, S.17). Der grundsätzlichen Überlegung der Betriebswirtschaftslehre die Kosten niedrig zu halten um mit limitierten Ressourcen umgehen zu können, führt die Op- timierungstheorie zu ihrer Bedeutung: eine eher konservative Schätzung von 3-4% Ersparnissen auf Kostenseite kann bei hochvolumigen Produktionskosten bzw. Verbundproduktionsnetzwerken zu erheblichen Effizienzsteigerungen führen (Kall- rath, 2002, S.31). Durch moderne EDV-Systeme ist eine lückenlose Betriebsdaten- erfassung möglich, welche die Methode der linearen Optimierung voraussetzt. Mo- derne Anwendungen finden sich im Dienstleistungsbereich, wie beispielsweise der Einsatz von spezieller LP-Software zur Besatzungsplanung von Fluglinien (Suhl & Mellouli, 2006, S. 22) sowie klassische betriebswirtschaftliche Fragen wie die Mi- nimierung der Stückkosten oder die Ermittlung des optimalen Produktionspro- gramms². „ Lineare Optimierungsprobleme sind in zweifacher Hinsicht von gro ß er Bedeutung. Zum einem lassen sich viele wirtschaftliche und technische Fragestel- lungen ( … ) modellieren; zum anderen stehen f ü r derartige Aufgabenstellungen eine leistungsf ä hige Theorie und effiziente Verfahren zur Verf ü gung. “ (Neumann & Morlock, 2002, S.13).

1.3. Zielsetzung des Untersuchungsgegenstandes der Arbeit anhand ausgewählter Optimierungsmodelle

Zentraler Gegenstand der Untersuchung der vorliegenden Arbeit ist die lineare Op- timierung, nachfolgend als LP-Modell bezeichnet, und dessen anwendungsorien- tierte Lösung. Im zweiten Teil der Arbeit werden anhand eines Rechenbeispieles die Begriffe und der grundlegende Aufbau von LP-Modellen geklärt. Der dritte Teil der Arbeit beschreibt die Untersuchung des Simplex-Algorithmus und dessen Lö- sungsschema. Der vierte Teil der Arbeit beschäftigt sich mit gängigen Randgebie- ten des zuvor vorgestellten Grundmodells. Den fünfte Teil der Arbeit bildet die an- wendungsorientierte Darstellung und Lösung von LP-Modellen mittels Standard- software - der Kern der vorliegenden Arbeit. Hierbei wird detailliert auf verschiede- ne Lösungsansätze mit gängiger Software sowie spezieller LP-Software eingegan- gen. Abgeschlossen wird die Arbeit mit Eigenentwicklungen des Autors zum Aus- bau der Software-Standardumgebung. Die konkrete Abgrenzung des Themenge- bietes wird in dem jeweiligen Kapitel einzeln vorgenommen.

Zur Erstellung dieser Arbeit hat der Verfasser auf die Methodik der Literaturrecherche und der Webrecherche zurückgegriffen. Aufgrund der interdisziplinären Natur des Themas, bestand der Bedarf an einem breiten Spektrum von Fachbüchern, was sich am Umfang und der heterogenen Zusammensetzung des Literaturverzeichnisses ablesen lässt.

2. Grundlagen der linearen Optimierung

Das zweite Kapitel der Arbeit befasst sich eingehend mit der Darlegung des grundsätzlichen Aufbaus von linearen Modellen. Ein Modell ist ganz allgemein eine vereinfachte Abbildung der Realität unter Erhaltung der inhaltlichen Struktur (Gohout, 2007, S.3). Nach den fachspezifischen Begriffsdefinitionen und Modellierungstechniken wird anhand eines Rechenbeispiels ein zweidimensionales LP-Modell vorgestellt und dessen zulässiger Lösungsbereich näher untersucht.

2.1. Standardmodelle linearer Optimierungsproblemstellungen

LP-Modelle gelten unter drei Voraussetzungen:

1.) Lineare Abh ä ngigkeit der Zielfunktion

Die Zielfunktion, die maximiert oder minimiert werden soll, ist zwingend linear abhängig von den Variabeln des LP-Modells, es dürfen keine nichtlinearen

Therme wie beispielsweise oder [Abbildung in dieser Leseprobe nicht enthalten] in der Zielfunktion enthalten sein (Suhl & Mellouli, 2005, S. 31).

2.) Beschr ä nkungen

Der Lösungsraum des LP-Modells kann durch Gleichungs- oder Ungleichungs- therme beschrieben werden, die vom Typ ≤ , ≥ oder = sind. Analog zur Ziel- funktion ist hier ebenfalls eine lineare Abhängigkeit zwingend vorausgesetzt.

3.) Stetige Variablen

Die Variablen können innerhalb des Lösungsraums beliebige reelle Werte annehmen, die in der Menge reeller Zahlen IR+ enthalten sind³.

Die Variablen werden durch mathematische Gesetze verbunden. Das dabei kon- struierte Gebilde wird als mathematisches Modell bezeichnet (Nieswandt, 1994, S.17).

2.1.1. Begriffsdefinitionen

Bevor ein LP-Modell aufgestellt werden kann, müssen die unter 2.1 eingeführten Voraussetzungen mathematisch näher definiert werden.

Die Zielfunktion wird im Rahmen dieser Arbeit als Einzelfunktion⁴ bewertet und hat die Gestalt

Abbildung in dieser Leseprobe nicht enthalten

Die Beschränkungen eines LP-Modells liegen als Gleichungen oder Ungleichungen vor. Die linke Seite stellt die Linearkombinationen der Variablen dar, wohingegen die rechte Seite eine reelle Konstante (die Ober-/bzw. Untergrenze im Lösungsraum, hier b) bildet. Die Beschränkungen werden formuliert als

Abbildung in dieser Leseprobe nicht enthalten

wobei die Anzahl der Beschränkungen mit m bezeichnet wird (Suhl & Mellouli, 2006, S.33).

Die Variablen des LP-Modells stellen im mathematischen Sinne den möglichen Entscheidungsfreiraum dar. Die allgemeine Formulierung dieser Variablen liefert folgende Definition:

Abbildung in dieser Leseprobe nicht enthalten

n Variablen haben demnach jeweils die (reelle) Untergrenze l j und die korrespon- dierende Obergrenze u. Sind die Variablen unbeschränkt nach oben oder unten, j entsprechen die dazugehörigen Grenzen gleich ∞ bzw. - ∞ (Suhl & Mellouli, 2006, S.32).

2.1.2. Bewertung und Einordnung grundlegender LP-Modelle

Die intuitive Interpretation von linearen Modellen führt zu der Annahme dass sich LP-Modelle an betriebswirtschaftlichen Themen, wie der Maximierung des Ge- winns, vorrangig anwenden lassen. Die Autoren Koop und Moock demonstrieren am konkreten Fall die optimale Ventilsteuerung in Verbrennungsmotoren, deren Ziel die Entwicklung eines computergestützten Verfahrens zur Berechung ruckfreier Nocken⁵ war (Koop & Moock, S.165). Somit lassen sich neben betriebswirtschaftli- chen auch technisch anspruchsvolle Fragestellungen näher untersuchen. Unter dieser Betrachtungsweise wird im nachfolgenden Teil der Arbeit die grundlegende Modellierungstechnik von LP-Modellen vorgestellt, mit deren Hilfe konkrete Prob- lemstellungen aus der Praxis in ein gültiges LP-Modell überführt werden können.

2.1.3. Anwendungsorientierte Modellierungstechniken

„ Drei Aspekte sind charakteristisch für das OR, nämlich die Quantifizierung eines Problems, das Optimalit ätsstreben und die Modellierung. “ (Gohout, 2007, S.3).

Die Modellbildung überführt allgemein ein reales Problem in ein formales Problem. Die fachspezifische Einigkeit der Modellierung stellte sich als unscharf dargestellt in der gesichteten Literatur dar. So unterscheiden die Autoren Domschke und Drexl eine weitreichende Modellierungstechnik, die in der folgenden Tabelle zusammen- fassend dargestellt ist:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Modellbildung nach Gohout (Gohout, 2007, S.4)

Ein vereinfachter Ansatz ist bei Kallrath knapp formuliert: „ In der Modellbildung wird das Problem [LP-Modell] in Objekte, Variablen, Zielfunktion und Nebenbedin- gungen strukturiert. “ (Kallrath, 2002, S.33). Dieser Ansatz Kallraths wird im Hinblick auf den anwendungsorientierten Fokus der Arbeit weiter verfolgt, denn: „ Sobald die Indizes strukturiert und eingef ü hrt sind, folgen die Variablen, Nebenbedingungen und die Zielfunktion nahezu automatisch. Danach stellt sich die Frage, wie man das Modell einem Rechner zug ä nglich macht. “ (Kallrath, 2002, S.33). Einen weiteren Modellierungsvorschlag der als anwendungsorientiert betrachtet werden darf, und den geforderten Zugang Kallraths zu einem Rechner ermöglicht, liefern die Autoren Suhl und Mellouli:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Modellierung nach Suhl & Mellouli (Suhl & Mellouli, 2007, S. 78)

Die softwareseitige Implementierung dieser Modellierungstechnik ergänzt den ver- einfachten Ansatz von Kallrath nach Meinung des Verfassers aus Praxissicht her- vorragend. Unter 5.2 wird diese Modellierungskombination der beiden Autoren an- gewandt.

2.2. Grafische Interpretation von linearen Optimierungsmodellen

Die nachfolgenden drei Unterpunkte stellen, ausgehend von 2.1, die grafische Lö- sung eines 2-dimensionalen LP-Modells dar. Das weitere Verständnis der Lösung von LP-Modellen wird durch die anschauliche Darstellung erleichtert - und begrün- det gleichzeitig den Übergang zur Lösung mittels Simplex-Algorithmus in 3.1 und dessen Notwendigkeit.

2.2.1. LP-Modell eines 2-dimensionalen Optimierungsproblems

Um die grundlegende Idee eines LP-Modells darzustellen wird hier folgendes Beispiel aufgestellt:

Ein Unternehmen produziert zwei Arten von Aluminiumstangen A1 und A2 mit ei- nem Deckungsbeitrag (DB) von 4,00 € für A1 und 3,00 € für A2. Der Typ A1 benö- tigt die zweifache Zeit bei seiner Herstellung im Vergleich zu Typ A2. Falls nur A2 Typen hergestellt werden würden, könnte das Unternehmen 2.000 Stangen pro Tag produzieren. Der Aluminiumproduzent kann aber maximal Rohmaterial für 1.600 Stangen pro Tag (für A1 und A2) zur Verfügung stellen. Für Typ A1 und Typ A2 werden verschiedene Stangendurchmesser verwendet, so dass täglich 800 Stangen für Typ A1 und 1.400 für Typ A2 bereitgestellt werden können. Die Optimierungsaufgabe lautet: Wie viele Stangen von Typ A1 und A2 müssen produziert werden, um den maximal möglichen Gesamtdeckungsbeitrag zu erzielen?

Hierbei handelt es sich um ein LP-Modell mit zwei Variablen, A1 und A2. Dieses Modell ist 2-dimensional und lässt sich rein grafisch lösen, wie an späterer Stelle dargestellt. „ Wenn das lineare Optimierungsmodell nur zwei Variablen beinhaltet, entsprechen die Restriktionen Geraden in der Ebene den definieren somit als zu- l ä ssigen Bereich einen zweidimensionalen Polyeder [ … ]. Wenn wir die Variablen auf beide Achsen projizieren, k ö nnen wir ein zweidimensionales Modell grafisch [ … ] l ö sen. “ (Suhl & Mellouli, 2007, S.33). Die Anzahl der linearen Kombinationen endlicher Punkte der beiden Variablen A1 und A2 wird als konvexes Polyeder be- zeichnet (Domschke & Drexl, 2007, S. 19). Auf diesen Umstand wird näher unter 2.2.2 eingegangen.

Die Angabe der Daten wird nach (1) - (3) zusammengefasst (siehe S.5): Entscheidungsvariablen

Abbildung in dieser Leseprobe nicht enthalten^{7 6}

Nach den Autoren Suhl und Mellouli kann vereinfacht ein solches LP-Modell grafisch dargestellt werden, nachdem die drei Schritte

1.) Bestimmung des zulässigen Bereichs (Einzeichnen des zulässigen Bereichs

(a) und (b), die Variablen, und der sogenannten Randgeraden (c) und (d)).

2.) Richtung der Zielfunktion (setzte z auf eine Konstante)

3.) Optimum bestimmen (paralleles Verschieben der Geraden z bis zur optima- len Ecke des zulässigen Bereichs) durchgeführt wurden (Suhl & Mellouli, 2007, S.35 ff). Die nachfolgende Zeichnung im Koordinatenkreuz ist anhand der Kleinbuchstaben eindeutig zuzuordnen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: grafische Darstellung eines 2-dimensionalen LP-Modells

Im 2-dimensionalen Rahmen des LP-Modells wird durch Parallelverschiebung der Zielfunktion (gestrichelte Linie) entlang des konvexen Polyeders (schwarz einge- rahmt) zum Punkt der optimalen Lösung geschritten (hier groß Z). Damit ist die op- timale Lösung des LP-Modells derjenige Punkt im Koordinatenkreuz, welcher am weitesten vom Ursprung entfernt liegt, sich aber dennoch innerhalb des gültigen Lösungsraumes befindet (Horngren et al., 2001, S.398). Lösungen die den gleichen Wert beinhalten, werden im 2-dimensionalen Raum als Isogewinngeraden be- zeichnet (Suhl & Mellouli, 2007, S.35).

Die Anzahl der A1-Aluminiumstangen sollte demnach bei 400, die der A2- Aluminiumstangen bei 1200 Stück liegen - der maximale (und somit auch optimale) Wert des Deckungsbeitrags liegt bei 5200 Euro.

2.2.2. Die typische Form des zulässigen Bereichs: der konvexe Polyeder

Wie in (2) auf Seite 5 ersichtlich, setzen LP-Modelle lineare Abhängigkeiten voraus. Daraus lässt sich die allgemeine Annahme des konvexen Lösungsbereichs ablei- ten, da nicht zusammenhängende Lösungsbereiche immer eine Fallunterscheidung erfordern. Konvex bedeutet, dass auch linear interpolierte Werte⁸ zulässig sind, also alle Werte aus IR+ innerhalb der Grenzen von (3), ebenfalls auf Seite 5, ste- hen.

Die grafische Darstellung veranschaulicht diesen Zusammenhang kompakt:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: konvexer/nicht-konvexer Polyeder

Der konvexe Lösungsbereich jedes linearen Modells ist somit eindeutig durch seine Ecken festgelegt. Diese Ecken sind über zugeordnete Gleichungssysteme näher zu untersuchen, was unter 3.1 näher erläutert ist. Im konvexen Polyeder ist das Maxi- mum (oder Minimum) immer als globales Maximum⁹ zu finden, wohingegen lokale Maxima zwar ebenfalls zulässige Lösungen darstellen, allerdings das LP-Modell nicht vollständig ausschöpfen. Folgende Darstellung erfasst diesen Umstand knapp:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: globales/lokales Maximum

Weist das LP-Modell ein globales Maximum auf, so existiert keine zulässige Lö- sung die einen besseren Zielfunktionswert aufweist. „ Eine lineare Funktion F, die auf einem konvexen Polyeder X definiert ist, nimmt ihr Optimum in mindestens ei- nem Eckpunkt des Polyeders an. “ (Donschke & Drexl, 2007, S.20). Dies gilt für Maximierungsprobleme, wie die Ermittlung des maximalen Deckungsbeitrags eines Produktionsprogramms. Soll hingegen ein Minimierungsproblem gelöst werden, wie die Ermittlung der niedrigsten Kosten eines Produktionsprogramms, gilt: „ Durch Multiplizieren der Zielfunktion mit (-1) kann ein Maximierungsproblem zu einem Minimierungsproblem umgewandelt werden und umgekehrt. Das Multiplizieren ei- ner ≤ − Restriktion (beide Seiten) mit (-1) ergibt eine dazu ä quivalente ≥ − Restrikti- on und umgekehrt. “ (Suhl & Mellouli, 2007, S. 38). Weiterhin sprechen die Autoren Domschke und Drexl in diesem Zusammenhang auch von Dualität - ein Minimie- rungsproblem kann durch o.g. Umformung in ein Maximierungsproblem transferiert werden und vice versa (Domschke & Drexl, 2007, S.31).

2.2.3. Untersuchung des ersten und zweiten Optimalitätskriterium und deren Einschränkungen

Die Darstellung eines 2-dimensionalen LP-Modells unter 2.2.1 begrenzt durch zwei Geraden (a und b) den Bereich der Randgeraden (c und d) und stellt somit den gültigen Lösungsbereich dar. Sollten jedoch n-dimensionale Beschränkungen im LP-Modell gelten, so: „ [ … ] ist die Anzahl der Variablen gr öß er als drei, dann wird der zul ä ssige Bereich durch ebene Fl ä chen begrenzt. “ (Corsten, el al., 2005, S.21). Dies begründet das erste Optimalitätskriterium: Die optimale Lösung eines LP- Modells befindet sich stets in einer Ecke des zulässigen Bereichs (wie in Abbildung 3). „ Man kann beweisen, dass, falls ein LP-Modell genau eine optimale L ö sung besitzt, sich diese in einer Ecke des zul ä ssigen Polyeders befindet. “ (Suhl & Mellouli, 2007, S.44).

Das zweite Optimalitätskriterium setzt direkt an diesem Zusammenhang an: „Als zweites Optimalitätskriterium gilt „ [...] dass eine Ecke dann optimal ist, wenn s ä mtli- che zu ihr entlang von Kanten zu erreichende benachbarte Ecken schlechtere (oder gleiche) Zielfunktionswerte aufweisen. “ (Corsten, et al., 2005, S.22). Die ein- schlägige Fachliteratur geht, ähnlich der Unschärfe der Modellierung unter 2.1.3, abweichend bei der Beschreibung von Ausnahmefällen von LP-Modellen vor. Im Folgenden werden einige ausgesuchte LP-Modelle vorgestellt, die oben genannte Modelle teilweise einschränken und die wesentlichen Punkte nach den Autoren Suhl & Mellouli beschreiben.

2.2.3.1. LP-Modelle ohne zulässige Lösung

Ein LP-Modell, dessen Schnittmenge der Ebenen leer ist, besitzt keine gültige Lösung. Betrachtet man beispielsweise die beiden Gleichungen:

Abbildung in dieser Leseprobe nicht enthalten

so ist es den Beschränkungen nicht möglich, eine gemeinsame Schnittmenge zu bilden. Folgende Abbildung liefert dazu die Darstellung auf dem Zahlenstrahl:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Zahlenstrahl ohne Schnittmenge

2.2.3.2. Unbeschränkte LP-Modelle

Falls durch Parallelverschiebung die Zielfunktion (vgl. Abbildung 3) unendlich weit nach oben verschoben werden kann, verbessert dies die Zielfunktion grenzenlos. Unter einem solchem Umstand ist es nicht möglich eine Zielfunktion mit einem op- timalen Ergebnis zu ermitteln. Der zugehörige Lösungsbereich eines solchen LP- Modells hat, dargestellt in einem einfachen Koordinatenkreuz, folgende Gestalt:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Unbeschränktes LP-Modell

2.2.3.3. Mehrdeutige Optimallösungen

Falls durch Parallelverschiebung der Zielfunktion ein paralleler Verlauf einer Beschränkung deckungsgleich auftritt, so entspricht die Beschränkung in unendlich vielen Punkten der Zielfunktion in den Optima.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Mehrdeutiges LP-Modell

2.2.3.4. Degenerierte Optimallösungen

Die Autoren Suhl & Mellouli sprechen von einer degenerierten¹⁰ Lösung wenn „ [ … ] die Ecke[..] aber (zuf ä llig) noch durch eine weitere Gerade gekreuzt wird, hat man redundante Informationen zur Bestimmung der optimalen L ö sung “ (Suhl & Mellouli, 2007, S.38). Eine knappe Darstellung soll hier ebenfalls den Sachverhalt näher veranschaulichen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9: Degeneriertes LP-Modell

3. Der Simplex-Algorithmus zur Lösung linearer Optimie- rungsmodelle

Die nachfolgenden vier Unterpunkte beschreiben die bekannteste und gängigste Lösungsform von LP-Modellen: den Simplex-Algorithmus. „ Er [Der Simplex- Algorithmus, Anm. des Verfassers] wird zumeist G.B. Dantzig zugeschrieben, der die Vorgehensweise im Jahre 1947 ver ö ffentlichte. Erste Arbeiten dazu stammen jedoch von dem russischen Mathematiker L.V. Kantorovich aus dem Jahre 1939. “

(Domschke & Drexl, 2007, S. 21). Damit stellt der Simplex-Algorithmus sowohl den Grundstein als auch den State-of-the-Art Lösungsalgorithmus des OR dar¹¹. „ Die Anwendbarkeit der Simplex-Methode ist in den ca. letzten 50 Jahren parallel mit der Entwicklung der Computertechnologie gestiegen. “ (Suhl & Mellouli, 2007, S.43).

3.1. Grundlagen des Simplex-Algorithmus

„ Eine lineare Funktion F, die auf einem konvexen Polyeder X definiert ist, nimmt ihr Optimum in mindestens einem Eckpunkt des Polyeders an “ (Domschke & Drexl, 2007, S.20).

Wie unter 2.2 beschrieben, lassen sich 2-dimensionale LP-Modelle „zu Fuß“, per Parallelverschiebung der Zielfunktion innerhalb des zulässigen Lösungsbereichs, lösen. Dieses simple Lösungsverfahren versagt im n-dimensionalen¹² LP-Modell: „ Die Berechnung aller Eckpunkte und das Aussortieren des kleinsten Wertes der dazugeh ö rigen Zielfunktion zur Ermittlung des Minimums oder des gr öß ten zur Er- mittlung des Maximums ist bei n-dimensionalen Problemen in der Regel zeitlich kaum zu leisten. “ (Brehler, 1998, S. 41). Da jedes gültige LP-Modell einen aufge- spannten Polyeder mit n-dimensionierten Ecken darstellen kann, setzt der Simplex- Algorithmus¹³ an diesem Umstand an: die zentrale Idee des Simplex-Algorithmus besteht in der Untersuchung eben dieser (gültigen) Ecklösungen des Polyeders. Diese Ecklösungen des LP-Modells werden nacheinander und iterativ untersucht um festzustellen, ob sich der Wert der Zielfunktion verbessert bzw. nicht ver- schlechtert (Suhl & Mellouli, 2007, S.44). Lösungen die den gleichen Wert beinhal- ten werden im n-dimensionalen Raum als Isogewinn-Hyperebenen bezeichnet (Suhl & Mellouli, 2007, S.35). Der so ermittelte Zielfunktionswert stellt das Optimum des LP-Modells dar (vgl. Abbildung 3). Zurückzuführen ist diese Vorgehensweise auf die Gauß’sche Eliminationsregel, welche auf der elementaren Umformung ei- nes linearen Gleichungssystems beruht. Diese Umformung ändert zwar das Glei- chungssystem, verändert aber die Lösung des Gleichungssystems nicht. Die Lö- sung kann durch sukzessive Elimination der Unbekannten bestimmt werden (Opitz, 2004, S.203). Auf die Gauß’sche Eliminationsregel wird näher unter 3.2.2 einge- gangen.

Somit stellt der Simplex-Algorithmus ein iteratives Verfahren zur exakten Lösung eines LP-Modells mit beliebig vielen Variablen dar.

3.2. Überführung des LP-Modells in das LP-Standardformat

Um ein einheitliches Format zur Lösung von LP-Modellen zu erhalten, wird das LP- Modell in das Standardformat transformiert. Das Standardformat fordert die Über- führung aller Ungleichungen zu Gleichungen und eine höhere Anzahl an Spalten (Variablen) als Zeilen (Beschränkungen) im Gleichungssystem. Hätte das Glei- chungssystem mehr Spalten als Zeilen wäre es unterdeterminiert - es hätte mehr als eine mögliche Lösung.

Als Vorbereitung zur Durchführung des Simplex-Algorithmus ist man mit mehr Spalten als Zeilen in der Lage, Spalten auszuwählen, mit denen man die verblei- benden Spalten unter Berücksichtigung der Beschränkungen ausdrücken kann (Suhl & Mellouli, 2007, S.45 ff). Um die konkrete Funktionsweise des Simplex- Algorithmus darzustellen, wird im Folgenden das Beispiel aus 2.2.1 herangezogen:

Abbildung in dieser Leseprobe nicht enthalten

Diese Darstellung des LP-Modells wird als kanonische Form bezeichnet (Kathöfer & Müller-Funk, 2005, S.79). Um die absolute Differenz zwischen der rechten und der linken Seite der (vormaligen) Ungleichungen abzubilden, werden nichtnegative Schlupfvariablen¹⁴ eingeführt. Die Besonderheit der Nichtnegativitätsbedingung sowohl der Schlupfvariablen [Abbildung in dieser Leseprobe nicht enthalten] als auch der Strukturvariablen¹⁵ [Abbildung in dieser Leseprobe nicht enthalten] beruht auf der Gültigkeit der Anfangslösung: so ist in Abbildung 3 der Startpunkt der Zielfunktion ab dem Koordinatenursprung (0|0) gültig - die Zielfunktion kann durch Parallelverschiebung bis zur optimalen Lösung bewegt werden. Hätten bei- spielsweise die Variablen [Abbildung in dieser Leseprobe nicht enthalten] negative Vorzeichen und damit negative Werte, würde man zunächst nach einer zulässigen Anfangslösung suchen - die sogenann- te Phase 1 des Simplex-Algorithmus - welche die Summe der Unzulässigkeiten minimiert. Dies geschieht durch Maximierung der Werte, welche negative, und so- mit unzulässige Werte beinhalten (Suhl & Mellouli, 2007, S.53). Im weiteren Verlauf der Arbeit wird die Nichtnegativität sowohl der Struktur- als auch der Schlupfvariab- len unterstellt. Weiterhin wird die Obergrenze + ∞ unterstellt. Es ist möglich, expli- zite Ober- und Untergrenzen im Simplex-Algorithmus zu berücksichtigen (Suhl & Mellouli, 2007, S48).

Somit ist das LP-Modell im Standardformat abgebildet. In der gesichteten Literatur wird teilweise von Standardformulierung oder Standardnotation gesprochen (Kall- rath, 2002, S.55). Im weiteren Verlauf der Arbeit wird die Bezeichnung Standard- format beibehalten.

3.3. Die Iteration des Simplex-Algorithmus zur optimalen Lösung des LP-Modells

Der Simplex-Algorithmus startet stets mit den Basisvariablen, die zunächst gleich- gesetzt sind mit den Schlupfvariablen. Die Zielfunktion DBmax wird als eigenstän- dige Zeile mit integriert, und als solche auch behandelt. Die Werte dieser soge-

nannten Ausgangsbasislösung sind direkt ablesbar [Abbildung in dieser Leseprobe nicht enthalten] Dies trifft auf das vollständige Gleichungssystem zu, solange die Nichtbasisvariablen auf Null gesetzt sind, was hierbei unterstellt wird. Folgende Darstellung fasst diesen Sachverhalt zunächst zusammen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 10: Basis- und Nichtbasisvariablen

[...]

---

¹ Als quantitativ wird ein konkreter Zahlenwert betrachtet (Anm. des Verfassers).

² Jedes Produkt mit positivem Deckungsbeitrag trägt zur Deckung der Produktionsfixkosten bei. Produkte mit dem höchsten positiven Deckungsbeitrag werden im Produktionsprogramm ab- steigend sortiert, um im Zustand der Überbeschäftigung die optimale Produktionsreihenfolge festzulegen, da nicht alle Produkte wegen Maschinenüberbelegung/Engpässen produziert wer- den können (Schmolke & Deitermann, 2007, S. 469).

³ Hier wird vorerst der Lösungsraum der positiven reellen Variablen unterstellt, die nachfolgenden Kapitel grenzen diesen Umstand näher ein (Anm. d. Autors).

⁴ LP-Modelle erlauben per Definition nur eine Zielfunktion. Unter anwendungsorientierter Ge- sichtspunkten lassen sich mehrer Zielfunktionen in einen nach Priorität gewichtete Reihenfolge bringen und nacheinander lösen (Suhl & Mellouli, 2006, S. 32).

⁵ Die charakteristischen Eigenschaften jedes Verbrennungsmotors hängen vom Gaswechselvor- gang im Zylinder ab. Der Kraftstoff wird mittels Ventilen in den Zylinder gebracht. Die Steuerung dieser Ventile erfolgt über die sogenannte Nockenwelle (Anm. des Verfassers).

⁶ Typ A1 benötigt die doppelte Herstellzeit (2x1) pro Einheit, Typ A2 nur eine Zeiteinheit (x2) pro Einheit (Anm. des Verfassers).

⁷ X1, X2 sind größer 0, da negative Produktionsmengen sinnlos wären (Anm. des Verfassers).

⁸ Interpolation [lat. „Umgestaltung“, „Veränderung“]; im mathematischen Sinne die näherungswei- se Bestimmung eines Funktionswertes (Anm. des Verfassers).

⁹ Im weiteren Verlauf der Arbeit wird stets ein Maximierungsproblem unterstellt (Anm. des Ver- fassers).

¹⁰ Degeneration [lat. „Rückbildung“, „Entartung“] bedeutet im Sinne des OR dass durch zwei be- liebige Geraden (nicht durch genau zwei Geraden) der Punkt des Optimums bestimmt werden kann. Selbige Degeneration gilt ebenfalls für Abbildung 8 (Anm. des Verfassers).

¹¹ Neben dem Simplex-Algorithmus hat auch das sogenannte Innere-Punkte-Verfahren einen etablierten Platz im OR, da es den aus theoretischer Sicht möglichen exponentiellen Rechen- aufwand der Simplex-Methode umgeht, indem es einen polynominellen Rechenaufwand auf- weist (Fischer et al., 2008, S.402).Auf das Innere-Punkte-Verfahren wird im weiteren Verlauf der Arbeit nicht eingegangen (Anm. des Verfassers).

¹²Als n-dimensionales LP-Modell wird ein LP-Modell mit mehr als 2 Variablen verstanden (Anm. des Verfassers).

¹³ Der Name Simplex ist die Bezeichnung für einen konvexen Polyeder (Domschke & Drexl, 2007, S.21). Weiterhin wird als Algorithmus: „ Ein systematisches deterministisches Verfahren zur Lö - sung eines bestimmten Problems, das durch eine endliche Anzahl von Verfahrensschritten be- schrieben werden kann, wobei jedem Verfahrensschritt eindeutig der nächste Schritt folgt (Kall- rath, 2002, S.266)“ bezeichnet.

¹⁴ Die Schlupfvariablen werden bei einem Maximierungsproblem linksseitig der Gleichung addiert. Läge ein Minimierungsproblem vor, würden Sie linksseitig subtrahiert werden (Marinell, 2001, S.423).

¹⁵ „ Die ursprünglichen Variablen [Abbildung in dieser Leseprobe nicht enthalten] des Problems bezeichnet man als Strukturvariablen “ (Domschke & Drexl, 2007, S.17).