Quantitative Methoden der BWL – Lineare Programmierung

Prof. Dr. Steffen FleßaUniversität Greifswald

Gliederung

1. Grundlagen2. Modellierung in LINGO3. Fallstudie 1: Produktionsprogrammplanung4. Komplexere Modelle5. Fallstudie 2: Personaleinsatzplanung6. Ausblick

1. Grundlagen

• Planungs- und Entscheidungmodelle–Optimierende Modelle– Prognostizierende Modelle– Simulationsmodelle

• Arten von Optimierenden Modellen– Infinitesimalrechnung

–Lineare Programmierung– Entscheidungsbaumverfahren– Spielmodelle

Grundmodell der mathematischen Programmierung

• Variablendefinition x Vektor der Strukturvariablen• Zielfunktion

• NebenbedingungenmifürKxf ii ,..,1)(

!)( OptxgZ

Spezialfall: Lineare Programmierung

• Zielfunktion– g(x) als lineare Funktion

• Nebenbedingungen– Alle fi als lineare Funktionen

– Nicht-Negativitäts-Bedingung

!1

MaxxdZn

jjj

mifürKxc i

n

jjij ,..,1

1

Beispiel: Produktionsprogrammplanung

• Inhalt: Festlegung der Menge der zu produzierenden Produkte.

• Krankenhaus: – Festlegung des Fallklassenprogramms – Gebräuchlicher: Leistungsprogrammplanung

Beispiel• Entgelt– Hüftoperation: 1600 € Deckungsbeitrag – Knieoperation: 1000 € Deckungsbeitrag

• Restriktionen– OP-Kapazität: 6 Stunden/Tag – Aufwachraumkapazität: 8 Stunden/Tag

• Spezifischer Bedarf – Hüftoperation: 2 Stunden OP-Kapazität, 2 Stunden

Aufwachraumkapazität– Knieoperation: 1 Stunde OP-Kapazität, 2 Stunden

Aufwachraumkapazität

Optimale Lösung

• Produktionsprogramm – Zwei Hüftoperationen (benötigt 4 Stunden OP-

Kapazität, vier Stunden Aufwachraumkapazität) – Zwei Knieoperationen (benötigt 2 Stunden OP-

Kapazität, 4 Stunden Aufwachraumkapazität) • Deckungsbeitrag:

2*1600 € + 2*1000 € = 5200 €

Charakteristika der Produktionsprogrammplanung

• Ressourcen: gegeben, unveränderlich • Produktionsmöglichkeitsbereich,

Lösungsraum: durch Restriktionen eingeschränkt

• Ziel: Deckungsbeitragsmaximierung • Ergebnis ist die Zahl der zu produzierenden

Einheiten

• Variablendefinition: X1 = Anzahl der KnieoperationenX2 = Anzahl der Hüftoperationen

• Nebenbedingungen 2 X1 + 2 X2 < 8 1 X1 + 2 X2 < 6X1 > 0X2 > 0

• Zielfunktion Z = 1000 X1 + 1600 X2 Max!

Lösung durch Lineare Programmierung

Graphische Lösung

X2

1 2 3 4 5 6

X1

1

2

3

4

1X1+2X2<=6

2X1+2X2<=8

Konvexes Lösungspolyeder

X2

1 2 3 4 5 6

X1

1

2

3

4

1X1+2X2<=6

2X1+2X2<=8

Zielfunktion und Optimierung

X2

1 2 3 4 5 6

X1

1

2

3

4

1X1+2X2<=6

2X1+2X2<=8

Z=1000X1+1600X2

2. Modellierung in LINGO

• Modell:

• Solve

ErgebnisZielfunktionswert

Zahl der Iterationen

Endliche, zulässige Lösung Zielfunktionswert

X1=2X2=2

Zielfunktionswert

Variablen in der Basislösung haben immer „reduced cost“ von 0

Um wie viel würde der Zielfunktionswert sinken, wenn

man die Variable in die Basislösung aufnehmen würde (wenn sie nicht

in der Basislösung ist)

Schlupfvariable: 0: Restriktion voll erfüllt

(links=rechts)>0: ungenutzte Kapazität (Schlupf zwischen linker und rechter Seite)

Schattenpreis: Um wie viel würde der Zielfunktionswert steigen,

wenn man die Kapazität um eine Einheit erhöhen würde.

Fallstudie 1: Produktionsprogrammplanung

• Lösung der Arbeitsaufgabe (Fallstudie 1)– LINGO– Interpretation der Ergebnisse

Ansatz

Solver Status

Ergebnisse

Analyse• Entscheidungsvariable:

– 50 Patienten von Klasse 3– 100 Patienten von Klasse 4 – 25 Patienten von Klasse 7

• Restriktionen:– Pflegetage: 50 unterausgelastet– Labor:0: Engpass– Röntgen: 1000: unterausgelastet– Operationssaal: 0: Engpass– Pflegekräfte:0: Engpass– Ärzte: 4000: unterausgelastet

Analyse

• Variable Value Reduced Cost• X1 0.000000 438.2833• X2 0.000000 866.2750• X3 50.00000 0.000000• X4 100.0000 0.000000• X5 0.000000 1126.700• X6 0.000000 1850.000• X7 25.00000 0.000000• X8 0.000000 515.7000

Analyse:

• Aufgabe: Zwingen Sie das Modell, mindestens einen Patienten mit Fallklasse 1 zu behandeln. Wie verändert sich der Zielfunktionswert?

• dZ= 459710.0 - 459271.7=438,3– Vgl. reduced cost des Ausgangsmodells!

Analyse

• Row Slack or Surplus Dual Price• 1 459710.0 1.000000• 2 50.00000 0.000000• 3 0.000000 39.12750• 4 1000.000 0.000000• 5 0.000000 18.62500• 6 0.000000 0.4776667• 7 4000.000 0.000000

Analyse

• Aufgabe: Sie öffnen den OP eine Minute länger länger. Wie wirkt sich das auf den Zielfunktionswert aus?– OP-Zeit = 9001 min.

• LP: … <=9001• dZ=459728,6 – 459710 = 18,6– Vgl. Schattenpreis!

Komplexere Modelle

• Ganzzahlige Variable (General Integer): 0,1,2,3,…– @GIN(X)

• Binäre Variable (Binary Integer): 0,1– @BIN(X)

• Nicht-Vorzeichenbeschränkte Variable– @FREE(X)

SETS

• Ziel: Zusammenfassung von Objekten zu einer Menge, z.B. indizierte Variable– X={x1, x2, x3, …, xn}

• SET-Section: Wir müssen die Sets definierenSETS:

Set1: attribute;Set2: attribute;

ENDSETS

DATA

• Inhalt: Liste der Konstanten für einzelne Sets• DATA-Section: Definition der Konstanten

DATA:Set1 = S1, S2, …, Sn;Attribut = a1, a2, …, an;

ENDDATA

Summen

• Inhalt: Summierung über alle Elemente einer Menge

• Funktion: @SUM– @SUM(Index(i): c(i)*x(i));

• Voraussetzung: X und c wurden vorher als Set Index definiert, d.h.SETS:Index: c, x;ENDSETS

Personaleinsatzplanung

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 7 Zeit [Stunden]

S1

S2

S3

S4

S5

S8

N

S7

S6 Schi

chte

n

Personaleinsatzplanung

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 7 Zeit [Stunden]

Bedarf bt [Vollkräfte]

1 2 3 4 5 6 7 8 9

Kosten• Schicht Kosten pro Mitarbeiter• 1 1500 €• 2 1000 €• 3 1000 €• 4 1000 €• 5 1000 €• 6 1200 €• 7 1200 €• 8 1500 €• N 1800 €

Einfacher Ansatz

Ergebnis Einfacher Ansatz

Ansatz mit SET

Ansatz mit SET

Summen

• ZIELFUNKTION

Summen

• Nebenbeding- ungen

• #LE#: less or equal to

• #GE#: greater or equal to

Ausblick

• For-Schleifen– For i=1..n – Beispiel: @FOR( Schichten(I): @GIN(X(I)));

• Einbindung von Excel– Eingabe– Ausgabe