Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | hanke-zaiger |
View: | 122 times |
Download: | 0 times |
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 Knieoperationen
X2 = Anzahl der Hüftoperationen
• Nebenbedingungen 2 X1 + 2 X2 < 8
1 X1 + 2 X2 < 6
X1 > 0
X2 > 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 Sch
ich
ten
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