1

2

Stochastische Optimierung

Mehrzieloptimierung

Netzwerkoptimierung

Ganzzahlige und kombinatorische Optimierung

Dynamische Optimierung

Nichtlineare Optimierung

Lineare Optimierung

Teilgebiet des Operations Research

*

*

*

Simulations- und Warteschlangenmodelle

3

Typische Problemstellungen des Operations Research

Wie optimiere ich bei beschränkter Faktoreinsatzmenge und mehreren Outputs meinen Gewinn?

- Produktionsplanung:

- Transport:Welches Lager beliefert welchen Kunden mit welcher Menge?

- Netzwerk:

- Tourenplanung:

Welches ist der kürzeste / kostenminimalste Weg durch das Netzwerk?

Wie erreiche ich auf kürzestem Weg in kürzester Zeit meine Kunden?

- Zuordnung: Welche Bewerber soll ich auf welche Stelle setzten?

- Verschnitt: Wie wähle ich mein Schnittmuster, so dass möglichst wenig Verschnitt entsteht?

4

Was ist Optimierung?

Verfahren zur Realisierung bestimmter Ziele bei rationellster Ausnutzung der gegebenen Möglichkeiten.

5

BedeutungLineare Optimierung (1)

Die Entwicklung der linearen Optimierung ist (nach Einschätzung vieler Fachleute) der wichtigste Beitrag der Mathematik des 20. Jahrhunderts zur Lösung praktischer Fragestellungen in Industrie und Wirtschaft.

6

Kantorovitsch (1939): erste Optimierung eines Betriebs-planungproblems, Methode der Auflösungsmultiplikatoren

Praktische Bedürfnisse führten zur Entwicklung:

Hitchcock (1941): Formuliert das Transportproblem und gibt eine Lösungsmethode an, die dem Simplexverfahren ähnelt.

Dantzig (1947): Entwicklung des Simplexverfahrensfür Planungsprobleme der amerikanischen Luftwaffe.

(1947) wird mittels Simplexverfahren die preiswerteste Kombination an Nahrungsmittel errechnet, die allen täglichen Ernährungs-

anforderungen der US Feld GI's gerecht wird.

7

Praktische Bedürfnisse führten zur Entwicklung

2. Weltkrieg: Optimierung des Einsatzes von Flugzeugen und Flakgeschützen der Armeen Großbritanniens und der USA unter Aufwand-Nutzen Aspekt

in den Jahren 1948/49 wurden die Transportpläne bei der Luftbrücke in Berlin weitgehend durch die Methoden der mathematischen Optimierung bestimmt.

8

Praktische Bedürfnisse führten zur Entwicklung:

Die Lineare Optimierung findet seit den 60ern wiederholt Verwendung

• in der Mineralölindustrie,

• bei Mischungsproblemen (Futtermittel),

• bei der Optimierung innerbetrieblicher Materialflüsse

• bei Umladeproblemen usw.

9

Beispiel-Medienauswahl (media selection)

Die Marketing-Abteilung einer größeren Firma hat ein

bestimmtes Werbebudget zur Verfügung, um eine

Werbeaktion für ein neues Produkt auszuarbeiten. Es

stehen der Abteilung Daten über die Kosten einer

Werbeart und ihr statistischer Erfolg zur Verfügung.

Der Werbeerfolg ( Ertrag ) soll maximiert werden.

10

Modell-Medienauswahl

Medium

Potentielle Kunden/

Reklame

Werbe-

kosten

max. Anzahl von

Werbeschaltungen/

Monat

1. TV-tags 1000 1500 15

2. TV-abends 2000 3000 10

3. Tageszeitung 1500 400 25

4. Wochenzeit. 2500 1000 4

5. Radio 300 100 30

Ges.: xi - Anzahl der Werbeschaltungen pro Monat für Medium i, i = 1,2,...,5 so, dass

30000100x 1000x400x 3000x1500x 54321

30x ,4x ,25x ,10x ,15x 54321

maxx20 x60x40 x90x65)x,...,x,x(z 54321521

0x,x,x,x,x 54321

10xx 21

18000x3000x1500 21

50000x300 x2500x1500 x2000x1000 54321 • mindestens 50.000 Kunden erreicht werden

• höchstens 30.000 € ausgegeben werden

• mindestens in TV 10 Werbebeiträge pro Monat

• aber die Kosten in TV von 18.000 € nicht überschreiten

• und was noch für xi?

• Zielfunktion?

Media-Auswahl

(Anderson, 132)

Werbeerfolg

65

90

40

60

20

11

Lösung-Medienauswahl

Optimale Lösung:

Medium Schaltungen

xi

Kosten

1.TV-tags 10 15.000

2.TV-abends 0 0

3.Tageszeitung 25 10.000

4.Wochenzeit. 2 2.000

5.Radio 30 3.000

Summe 30.000

Kontakte 61500

237020 6040 9065),...,,(:gWerbeerfol 54321521 xxxxxxxxz

12

Beispiel-Portfeuille Wahl

Ein Finanzberater erhält von einem Kunden den Auftrag, einen bestimmten Betrag für einen Zeitraum von n Jahren anzulegen. Der Kunde ist mit m unterschiedlichen Anlageformen einverstanden, deren Bedingungen bekannt sind. Der Ertrag soll maximal werden.

1.2.1. Portfeuille Wahl (Anderson, 139)

Anlagemöglichkeiten:

Investition Rendite % Anlagevolumen = 100.000

AntlanticOil x1 7,3 Anlagestrategien:

Pacific Oil x 2 10,3 keine Anlage von mehr als 50% in einer Branche

Midwest Steel x3 6,4 Staatsanleihen 25% der Investitionen in Stahl

Huber Steel x4 7,5 Investition in Pacific Oil 60% Öl-Investition

Staatsanleihen x5 4,5

13

Diätproblem

Finde die preiswerteste Kombination der Nahrungsmittel, die allen täglichen Ernährungsanforderungen einer Person gerecht wird.

14

Historisches I

Das Diätproblem war eines der ersten Optimierungsprobleme, die in den dreißiger und vierziger Jahren studiert wurden.

Es war der Wunsch der Armee bei Minderung der Kosten, die Ernährungsbedingungen des Feld GI's zu erfüllen.

15

Historisches II

1947 mit der (neuen) Simplexmethode gelöst.

Das mathematische Modell bestand aus 9 Gleichungen mit 77 Unbekannten.

Bei der Auswertung waren 9 Sekretärinnen mit handbetriebenen Tischrechnern 120 Arbeitstage beschäftigt.

optimale Lösung:$ 39,69 für die Tagesverpflegung eines GI

16

Find the cheapest daily selection of food

items from McDonald's that satisfies the

following requirements:

1. Provides 100% of the U.S. RDA of

vitamins A, C, calcium and iron.

2. Supplies at least 55 grams of protein.

3. Contains at most 3 grams of sodium.

4. Obtains at most 30% of its calories from fat

McDonald‘s

(grams) (% of daily req.)

Menu Item PriceCalo-

ries

Cal.

From

Fat

So-

dium

Pro-

tein Vit A

Vit

C

Cal-

ciu

m Iron

Hamburger $0,69 270 90 0,530 12 2 4 15 15

Cheeseburger $0,79 320 130 0,770 15 6 4 15 15

Quarter Pounder $1,79 430 190 0,730 23 2 4 15 25

Quarter Pounder w/ Cheese $1,99 530 270 1,200 28 10 4 15 25

Big Mac $1,99 500 250 0,880 25 6 4 20 25

Source: Bosch, Robert A., "Big Mac Attack," OR/MS Today, 20:4, pp. 30-31.

McDonald's Nutrition Facts, © 1996. McDonalds Corporation.

17

Vitaminanteile

Minimalster

Vitamin mg / Ei mg / Käse mg / Müsli Tagesbedarf

A 2 4 1 16

B 3 2 1 12

Kosten

Ei 0,04 GE / Stück

Käse 0,03 GE / Scheibe

Musli 0,02 GE / Schale

Beispiel Diätproblem

Finde die preiswerteste Kombination der Nahrungsmittel, die den täglichen

Vitaminanforderungen einer Person gerecht wird. (Lösung später)

In einer Pension soll allmorgendlich das Frühstück, bestehend aus Ei,

Käsescheiben und Müsli für den Gast zubereitet werden.

18

genug der Beispiele …

Welche mathematische Modellstrukur

besitzen diese Beispiele ?

Was ist gesucht,

was ist gegeben?

19

Mathematisches Modell der Linearen Optimierung

Bestimmung des Extremwertes einer linearen

Funktion mehrerer beeinflussbarer Größen unter

Berücksichtigung linearer Nebenbedingungen.

max. z = cT x

A x b

x 0

max. Z(x1,x2,...,xn) = c1 x1 + c2x2 +...+ cnxn

a11x1 +...+ a1nxn b1

am1x1 +... + amnxn bm

x1, x2,..., xn 0

20

Zielfunktion : Z = 0,04x1 + 0,03x2 + 0,02x3 min

Entscheidungsvariablen :x1 Anzahl von Eiernx2 Anzahl von Käsescheibenx3 Anzahl Müslischalen

NB : 2x1 + 4x2 + x3 163x1 + 2x2 + x3 12

mathematisches Modell zum DiätproblemKosten

Ei 0,04 GE / Stück

Käse 0,03 GE / Scheibe

Musli 0,02 GE / Schale

Vitaminanteile

Minimalster

Vitamin mg / Ei mg / Käse mg / Müsli Tagesbedarf

A 2 4 1 16

B 3 2 1 12

NNB : x1 0x2 0 x3 0

Ziel: Minimiere Kosten des Frühstücks

21

Allg. Optimierungsaufgabe

= Extremwertaufgabe ohne/mit Nebenbedingungen der Form

;m,...,1j ;n,...,1i 0x,0)x(g)x(fmax iiji

Nichtlineare Optimierung

- keine Einschränkungen

für f und gj

- Spezialverfahren bzw.

Heuristiken

- konvexe / quadratische

Optimierung

Lineare Optimierung

- f und gj sind lineare

. Funktionen

- SimplexAlgorithmus,

Diskrete lineare

Optimierung

- xi G (ganze Zahlen)

bzw. xi (0;1)

- vollständige Enumeration

-Branch&Bund Algorithmus

-Schnittebenenverfahren

Dynamische

Optimierung

- stufenweise

Optimierung

mit Rück-

wärtsrechnung

22

Überblick über Standard-

Solver

EXCEL mit SOLVER

23

Literatur (1)

•Beisel,E.-P.;Mendel,M. : Optimierungsmethoden des Operations Research, Bd. 1: Lineare und ganzzahlige Optimierung. Bd. 2: Nichtlineare und ganzzahlige Optimierung, graphentheoretische Verfahren. Vieweg, Braunschweig-Wiesbaden,

•Bomze I., Grossmann W.: Optimierung - Theorie und Algorithmen, BI-Wissenschaftsverlag,

•Dinkelbach,W.;Lorschneider,U.: Übungsbuch zur Betriebs-wirtschaftslehre - Entscheidungsmodelle und lineare Programmierung. ., R.Oldenbourg Verlag München-Wien,

•Dinkelbach,W. : Entscheidungsmodelle. de Gruyter, Berlin-New York, 1

24

Literatur(2)

•Domschke,W.;Drexl,A. :Operations Research., Springer-Verlag, Berlin u.a.

•Domschke W., Drexl A., Schildt B., Scholl A., Voß S.: Übungsbuch zu Operations Research, Springer, Berlin, Heidelberg, u.a.

•Dürr W., Kleibohm K.: Operations Research, Lineare Modelle und ihre Anwendungen, Hanser, München Wien

•Ellinger T.: Operations Research, Springer, Berlin Heidelberg New York,

•Gal,T.:Grundlagen des Operations Research (3 Bände). 3.Aufl., Springer-Verlag, Berlin u.a.

•Hillier, Liebermann : Operations Research - Einführung

25

Literatur(3)

•Jungnickel D.: Optimierungsmethoden, Eine Einführung, Berlin u.a.,

•Kern,W.: Operations Research., Poeschel, Stuttgart.

•Krabs,W.: Einführung in die lineare und nichtlineare Optimierung für Ingenieure. Teubner, Stuttgart

•Müller-Merbach,H.: Operations Research., Vahlen, München

•Neumann K. und M. Morlock (NM): Operations Research, Hanser Verlag,

•Nieswandt A., Operations Research, Oldenbourg, München Wien,

•ZimmermannH.-J.: Methoden und Modelle des Operations Research. Vieweg, Braunschweig-Wiesbaden

26

Skripte im Internet

unter GOOGLE.com, Stichworte z.B.:

lineare optimierung,

linear programming,

optimierung,

optimization,

simplex methode.