Aufgabenkatalog PDF

Preview

Summary

Aufgabenkatalog sommersemester 18/19...

Description

Technische Universität Berlin Fakultät VII (Wirtschaft & Management) Fachgebiet Wirtschafts- und Infrastrukturpolitik (WIP)

Aufgabenkatalog Operations Research – Grundlagen

Verfasser: OR Team Wintersemester 2018/19

Version 12.5 - Oktober 2018

Verzeichnisse

Inhaltsübersicht 1 Einführung und Übersicht..........................................................................................

1

2 Lineare Optimierung...................................................................................................

2

3 Graphentheorie........................................................................................................... 24 4 Ganzzahlige Optimierung........................................................................................... 39 5 Effizienzananalyse...................................................................................................... 44 6 GAMS .......................................................................................................................... 47

Seite ii

Verzeichnisse

Inhaltsverzeichnis 1 Einführung und Übersicht..........................................................................................

1

2 Lineare Optimierung...................................................................................................

2

2.1 Einführung in die lineare Programmierung ............................................................ 2.2 Lineare Programmierung: Grundlagen .................................................................. 2.3 Matrizen ...............................................................................................................

2 2 3

2.4 Konvexität............................................................................................................. 2.5 Modellbildung: Der Whisky-Importeur....................................................................

3 3

2.6 Modellbildung: Die Personalplanung ..................................................................... 2.7 Modellbildung: Die Stahlhütte in Eisenhüttenstadt .................................................

4 4

2.8 Modellbildung: Oriana in der Colgatefabrik ............................................................ 2.9 Modellbildung: Studentenfutter.............................................................................. 2.10 Modellbildung: Erdgas-Problematik.......................................................................

5 6 7

2.11 Einführung in die graphische Lösung .................................................................... 2.12 Graphische Lösung ..............................................................................................

8 8

2.13 Simplex-Algorithmus............................................................................................. 9 2.14 Primaler Simplex .................................................................................................. 10 2.15 Dualer Simplex ..................................................................................................... 11 2.16 Dualer und Primaler Simplex................................................................................. 11 2.17 Der Eisenwarenproduzent..................................................................................... 12 2.18 Der Viehzuchtbetrieb ............................................................................................ 12 2.19 Der Nährstoffpillenhersteller.................................................................................. 13 2.20 Dualitätssätze....................................................................................................... 13 2.21 Begriffsdefinitionen............................................................................................... 13 2.22 Dualproblem I ....................................................................................................... 14 2.23 Dualproblem II ...................................................................................................... 14 2.24 Oriana baut Lithium-Ionen-Batterien ..................................................................... 15 2.25 Sensitivitätsanalyse .............................................................................................. 16 2.26 Die Hamburger Wollfabrik ..................................................................................... 17 2.27 Komplementärer Schlupf I..................................................................................... 18 2.28 Komplementärer Schlupf II.................................................................................... 18 2.29 Sonderfälle I ......................................................................................................... 19 2.30 Sonderfälle II ........................................................................................................ 19 2.31 Sonderfall: Redundanz ......................................................................................... 20 2.32 Kürzeste Wege ..................................................................................................... 20 2.33 Minimale Spannbäume ......................................................................................... 21 2.34 Travelling Salesman Problem................................................................................ 21 2.35 Graphentheoretische Probleme als LP .................................................................. 22 3 Graphentheorie........................................................................................................... 24 3.1 Minimale Spannbäume ......................................................................................... 24 3.2 Kruskal-Algorithmus: Der befreundete Busunternehmer ........................................ 24 3.3 Kruskal-Algorithmus: Lok um Lok.......................................................................... 25

Seite iii

Verzeichnisse 3.4 Kruskal-Algorithmus: Internet in der Lausitz .......................................................... 26 3.5 Greedy- und Dijkstra-Algorithmus in ungerichteten Graphen.................................. 26 3.6 Dijkstra-Algorithmus.............................................................................................. 27 3.7 Dijkstra mit neuen Kantengewichten ..................................................................... 28 3.8 Dijkstra-Algorithmus: Der Wanderer ...................................................................... 29 3.9 Dijkstra-Algorithmus: Oriana goes Volta ................................................................ 30 3.10 Dijkstra-Algorithmus: Oriana kauft ein ................................................................... 31 3.11 Adjazenz- und Inzidenzmatrix: Das Bus- und Bahnnetz Tegel ............................... 31 3.12 Bellman-Ford-Algorithmus I .................................................................................. 32 3.13 Bellman-Ford-Algorithmus mit Tree-Matrix ............................................................ 33 3.14 Bellman-Ford-Algorithmus II ................................................................................. 33 3.15 Dynamische Optimierung...................................................................................... 34 3.16 Dynamische Optimierung: Großbaustellen ............................................................ 35 3.17 Dynamische Optimierung: Nahverkehr in Stockholm ............................................. 35 3.18 Lagerhaltung ........................................................................................................ 36 3.19 Lagerhaltung: Fertigungsauftrag ........................................................................... 36 3.20 Lagerhaltung von Kupfersulfat .............................................................................. 37 3.21 Yen-Algorithmus ................................................................................................... 37 3.22 Yen-Algorithmus: Castortransport nach Bayern ..................................................... 37 4 Ganzzahlige Optimierung........................................................................................... 39 4.1 Einführung............................................................................................................ 39 4.2 Branch-and-Bound-Algorithmus: Die Raffinerie in Karlsruhe.................................. 39 4.3 Branch-and-Bound-Algorithmus: Die Raffinerie in Karlsruhe 2.0 ............................ 39 4.4 Branch-and-Bound-Algorithmus I .......................................................................... 40 4.5 Branch-and-Bound-Algorithmus II ......................................................................... 40 4.6 Branch-and-Bound-Algorithmus III ........................................................................ 41 4.7 Binäre Variablen: Bei IKEA ................................................................................... 41 4.8 Binäre Variablen: Oriana beim Süßigkeiten-Wettbewerb in NYC ............................ 42 4.9 Rucksackproblem: Oriana geht aufs Festival......................................................... 42 5 Effizienzananalyse...................................................................................................... 44 5.1 DEA ..................................................................................................................... 44 5.2 Kosten und Allokationseffizienz im Mehrproduktfall ............................................... 44 5.3 Produktion von Solarpanelen ................................................................................ 45 6 GAMS .......................................................................................................................... 47 6.1 Übungsaufgaben .................................................................................................. 47 6.2 GAMS: Erdgas-Problematik .................................................................................. 47 6.3 GAMS: Der Viehzuchtbetrieb ................................................................................ 48

Seite iv

Einführung und Übersicht

1 Einführung und Übersicht

„Geburtsstunde“ der OR

Quelle: Winfried Mönch: Entscheidungsschlacht „Invasion“ 1944, Franz Steiner Verlag, 2001, S. 142

Landung in der Normandie:

Quelle: http://www.ambafrance-de.org/70-Jahre-D-day-Feierlichkeiten-zur letzter Zugriff am 04.07.2018

Seite 1

Lineare Optimierung

2 Lineare Optimierung 2.1 Einführung in die lineare Programmierung a) Was versteht man unter einem LP? b) Wie sieht die „Allgemeine Form“ eines LP aus? c) Was sind Schlupf- und Strukturvariablen? d) Nehmen Sie Stellung zu den folgenden Aussagen: • Ein LP besitzt genau eine optimale Basislösung. • Ein LP besitzt keine optimale Basislösung. • Ein LP besitzt unendlich viele optimale Basislösungen. • Ein LP besitzt genau zwei optimale Basislösungen. • Ein LP besitzt genau 734.982.726 optimale Basislösungen.

2.2 Lineare Programmierung: Grundlagen Gegeben seien folgende Aussagen zur Linearen Programmierung. Entscheiden Sie, ob die Aussagen richtig oder falsch sind. 1. Ein LP mit unbeschränktem Zulässigkeitsbereich kann eine optimale Basislösung haben. 2. Ein LP kann genau eine optimale Basislösung besitzen. 3. Ein optimaler Zielfunktionswert kann einen negativen Wert annehmen. 4. Eckpunkte des zulässigen Bereichs werden auch optimale Basislösung genannt. 5. Die Vereinigung von zwei konvexen Flächen ist auch konvex. 6. f ( x ) = 3x2 + 4x + 3 ist eine konvexe Funktion. 7. f ( x ) = tan( x ); x ∈] − 8. max z =

√

Π ; 0] 2

ist eine konvexe Funkion.

7x1 + 15 x2 + 8 3 x3 − 4 könnte eine Zielfunktion eines Linearen Programms sein.

9. f ( x ) = sin ( x ); x ∈ [0; Π] ist eine konvexe Funktion. 10. Der zulässige Bereich eines LPs ist immer konvex.

Seite 2

Lineare Optimierung

2.3 Matrizen a) Gegeben ist das folgende LP in Matrizenschreibweise. Übertragen Sie es in die Standardform.

max z = c T x s.t.

Ax = b xj ≥ 0

0 1 3 B C 0 0 1 1 B C B 2C 3 0 1 0 0 9 B C B B C C B C B B C C c = B 0C ; A = B 1 1 0 1 0 C ; b = B 6C B C @ @ A A B C B 0C 1 −4 0 0 1 1 @ A 0 b) Wie nennt man die Eckpunkte des Lösungsraums?

2.4 Konvexität a) Wie ist Konvexität definiert (für Mengen und Funktionen)? b) Ist der Schnitt von konvexen Mengen konvex? c) Ist die Vereinigung von konvexen Mengen konvex? d) Weshalb ist Konvexität für Lineare Programme wichtig? e) Ist der US Bundesstaat Colorado auf einer Landkarte konvex?

2.5 Modellbildung: Der Whisky-Importeur Ein Whisky-Importeur versorgt zwar einen unbegrenzten Markt mit seine Ware, aber durch Importbeschränkungen werden seine monatlichen Einkaufsmengen folgendermaßen begrenzt: • Sir Roses: Höchstens 2.000 Liter zu 35 EUR • Highland Wind: Höchstens 2.500 Liter zu 25 EUR • Old Frenzy: Höchstens 1.200 Liter zu 20 EUR Daraus stellt er drei Mischungen Crested Ten (Mischung A), Jameson (Mischung B) und Paddy (Mischung C) her, die er zu 34 EUR, 28,50 EUR bzw. 22,50 EUR pro Liter verkauft. Die Zusammensetzung der Mischungen ist: Seite 3

Lineare Optimierung • A: Wenigstens 60% Sir Roses und höchstens 20% Old Frenzy • B: Wenigstens 15% Sir Roses und höchstens 60% Old Frenzy • C: Höchstens 50% Old Frenzy Stellen Sie ein Modell auf, um hinsichtlich der Gewinnmaximierung die optimalen Produktionsmengen und Zusammensetzungen der drei Mischungen bestimmen zu können.

2.6 Modellbildung: Die Personalplanung In einem Unternehmen mit Schichtbetrieb besteht folgender Mindestbedarf an Personal: • von 0 bis 4 Uhr: 3 Personen • von 4 bis 8 Uhr: 8 Personen • von 8 bis 12 Uhr: 10 Personen • von 12 bis 16 Uhr: 8 Personen • von 16 bis 20 Uhr: 14 Personen • von 20 bis 24 Uhr: 5 Personen Der Arbeitsbeginn ist jeweils um 0, 4, 8, 12, 16 bzw. 20 Uhr. Die Arbeitszeit beträgt stets 8 Stunden hintereinander. Formulieren Sie das dazugehörige Optimierungsmodell für das Problem, einen Einsatzplan mit minimalem Gesamtpersonalbedarf aufzustellen.

2.7 Modellbildung: Die Stahlhütte in Eisenhüttenstadt Ein Metallproduzent stellt Stahlrohre mit einem Standardlänge von 105 cm und einem Durchmesser von D cm her. Die Kunden verlangen jedoch Rohre mit geringerer Länge (aber demselben Durchmesser D). Es liegen folgende Aufträge vor: • Auftrag 1: 100 Rohre mit Länge 25 cm • Auftrag 2: 80 Rohre mit Länge 35 cm Zur Erledigung der Aufträge werden Standardrohre zerschnitten. Der Fabrikant kann z.B. aus einem Stahlrohr mit Standardlänge zwei Rohre von je 35 cm Länge und ein Rohr von 25 cm Länge schneiden. Das ergibt einen Schnittverlust von 10 cm. Ziel des Fabrikanten ist die Minimierung der Schnittverluste für die vorliegenden Aufträge. Formulieren Sie dieses Problem als Optimierungsproblem.

Seite 4

Lineare Optimierung Hinweis: Derzeit liegen keine Rohrstücke der Länge 25 cm oder 35 cm vor. Wenn zusätzlich Rohre der Länge 25 cm oder 35 cm geschnitten werden, können diese zu einem späteren Zeitpunkt verkauft werden. Die Stücke zählen folglich nicht als Verschnitt!

2.8 Modellbildung: Oriana in der Colgatefabrik Oriana plant nach ihrem erfolgreich abgeschlossenen Studium ihre theoretischen Kenntnisse praktisch anzuwenden. Seit ihrer Kindheit träumt sie davon, in einer Zahnpastafabrik zu arbeiten und nun wurde ihr die Möglichkeit geboten ein Projekt zu leiten, bei der es um drei neue Zahnpastavarianten geht: Colgate Total (75ml Packung), Dentagard (100 ml Packung) und Advanced White (150ml Packung). Alle drei Produkte werden auf einer integrierten Fertigungseinheit erzeugt, die am Tag 7 Stunden zur Verfügung steht; der Planungszeitraum beträgt 15 Tage. Pro Stunde können 800 Tuben Colgate Total, 450 Tuben Dentagard oder 100 Tuben Advanced White hergestellt werden. Die Umrüstzeit ist aufgrund der innovativen Technologie vernachlässigbar. Darüber hinaus wird der chemische Grundstoff in jeder Tube zu einem anderen Anteil vermischt. Für den Planungszeitraum stehen 1500 Kilogramm zur Verfügung. Je Tube Colgate Total werden 150 Gramm, je Tube Dentagard 100 Gramm und je Tube Advanced White 80 Gramm von diesem chemischen Stoff benötigt. Neben diesem chemischen Grundstoff wird bei Colgate Total und Dentagard noch ein künstlicher Geschmacksstoff verwendet. Hiervon stehen 700 Kilogramm in den 15 Tagen zur Verfügung. Colgate Total enthält 10 Gramm je Tube und Dentagard 2 Gramm je Tube. In der Zahnpasta Advanced White wird außerdem eine Spezialzutat gegen Karies verwendet, von der pro Tube 15 Gramm benötigt werden. Im Planungszeitraum ist der Einsatz von bis zu 1000 kg der Spezialzutat möglich. Aufgrund vertraglicher Bedingungen muss die Absatzmenge von Advanced White mindestens 1500 und darf nicht mehr als 5000 betragen. Da Oriana eine ökonomisch veranlagte Person ist und will, dass das Projekt erfolgreich ist, möchte sie den Umsatz maximieren. Colgate Total wird für 5,59 EUR, Dentagard für 1,64 EUR und Advanced White für 9,17 EUR je Tube verkauft. Erstellen sie ein Modell, das Oriana helfen wird, die optimale Produktionsmenge zu bestimmen. Verwenden Sie dazu bitte folgende Strukturvariablen: xtotal – Anzahl der produzierten Tuben von Colgate Total xdenta – Anzahl der produzierten Tuben von Dentagard xwhite – Anzahl der produzierten Tuben von Advanced White

Seite 5

Lineare Optimierung

2.9 Modellbildung: Studentenfutter Das Berliner Start-Up "GreenToGo" spezialisiert sich bei seinem Sortiment auf Snackangebote aus ökologisch kontrolliertem Anbau und fairem Handel. Seit neuestem bietet das Unternehmen seinen Kunden auch Studentenfutter an. Für den Wochenmarkt werden hierfür Nuss-Variationen zusammengestellt. "GreenToGo" bietet 3 verschiedene Varianten an, die als Basis eine Grundmischung von Nüssen haben. Die drei verschiedenen Varianten "classic", "classic-mini" und "fit-mix" unterscheiden sich durch die Größe und Zugabe weiterer Zutaten. "classic" und "classic-mini" weisen dasselbe Mischverhältnis auf, wobei 15% Cashewkerne und 30% Sultaninen neben der Basismischung enthalten sind. Eine Packung "classic-mini" enthält 50g, während die Packungen "classic" und "fit-mix" 100g beinhalten. Letzteres enthält im Vergleich zu den "classic"-Varianten keine Sultaninen, dafür 20g Cashewkerne und 10g Walnüsse. Die Basis-Nussmischung kann das Start-Up aus seinem Lager unbegrenzt zu einem vernachlässigbar kleinen Preisaufwand beziehen. Walnüsse und Sultaninen können in beliebiger Menge aus der Nachbar-Manufaktur einkauft werden, wobei der Preis für 1 kg Walnüsse 30 EUR beträgt und der Preis für 1 kg Sultaninen bei 5 EUR liegt. Aufgrund von schweren Stürmen im Honduras konnte bei der letzten Lieferung nicht die ganze Bestellung geliefert werden, weswegen lediglich 1,2 kg Cashewkerne für die Verarbeitung zur Verfügung stehen. Um den CO2-Fußabdruck des jungen Unternehmens möglichst klein zu halten, wird bei der Verpackung recyclebares Material verwendet. Trotzdem fallen bei einer 50g-Verpackung 4g CO2e und bei einer 100g-Verpackung 6 g CO2e an. "GreenToGo" hat sich als persönliches Ziel gesetzt, nicht über die 450g-CO2e-Obergrenze hinaus zu produzieren. Aus Erfahrung wissen die Unternehmer, dass sich die kleinen und gesunden Packungen besser verkaufen lassen. Aus diesem Grund sollen mindestens 40 Packungen "classic-mini" und 30 Packungen "fit-mix" zum Verkauf angeboten werden. Auf dem Wochenmarkt werden die Variationen "classic-mini", "classic" und "fit-mix" zu den Preisen 2 EUR, 3 EUR und 3,5 EUR verkauft. Erstellen Sie ein Modell, das den jungen Gründern hilft, die optimale Produktionsmenge zu bestimmen, um den Gewinn zu maximieren.

Seite 6

Lineare Optimierung

2.10 Modellbildung: Erdgas-Problematik Deutschland besitzt eine jährliche Nachfrage von Gas in Höhe v...