26.04.2004 LPL-Einführung 1
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
• LPL - Linear ProgrammingLanguage
• Ein Matrix-Generator
• Tony Hürlimann
26.04.2004 LPL-Einführung 2
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Agenda (0)
1. Grundelemente eines Modells2. Erstellung eines LPL-Programms3. Beispiel "kommune.LPL"4. Verbindung zum Optimierer XA
26.04.2004 LPL-Einführung 3
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Agenda (1)
1. Grundelemente eines Modells2. Erstellung eines LPL-Programms3. Beispiel "kommune.LPL"4. Verbindung zum Optimierer XA
26.04.2004 LPL-Einführung 4
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Grundelemente eines Modells
• MODEL• SET• PARAMETER• VARIABLE• CONSTRAINT• MAXIMIZE• END•
26.04.2004 LPL-Einführung 5
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
MODEL-Sektion
• MODEL Kommune;
• Ein Kommentar kann eingefügt werden, indem er in (*Text*) hinter dem Semikolon eingefügt wird.
• MODEL kommune; (*Beispiel*)
26.04.2004 LPL-Einführung 6
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
SET-Sektion
•• SET i = /1 2 3/;• j = /1:3/;
– (*In dieser Sektion werden die Indexmengen definiert, und es können sofort die Werte zugeordnet werden*)
26.04.2004 LPL-Einführung 7
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Besonderheiten der SET-Definition• Der Index wird intern als Zahl verarbeitet. Da er als Zahlenwert wenig
aussagekräftig ist, kann man einen sog. ALIAS-Name vergeben, der hinter dem Index durch Punkt getrennt angefügt wird:
–Index.Alias
• Kommentar kann wieder hinter dem Semikolon in (* Kommentar *) eingefügt werden:
–i = / 1.alias1 2.alias2 3.alias3 /; (* Kommentar *)
• Beispiel:–j = / 1.K1 2.K2 3.K3 /; (* Kommunen *)–i = / 1.ZU 2.BA 3.HI /; (* Pflanzsorten *)
26.04.2004 LPL-Einführung 8
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PARAMETER-Sektion
• In dieser Sektion werden alle Daten symbolisch definiert. Es können durch die „gleich Zuweisung“ unmittelbar folgend die Datenwerte zugewiesen werden.
26.04.2004 LPL-Einführung 9
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PARAMETER-Definition 1
• Syntax:
– name1 = wert1; (* Einzelwert *)– name2 {Indexmenge} = [wert1 wert2 .. ];
• Mehrfachindizierte Parameter:
– name{i-menge1,j-menge2} = Wertzuweisung;
26.04.2004 LPL-Einführung 10
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PARAMETER-Definition 2
• Wertzuweisung:• name {i,j} =
• /: 1 2 3 :• 1 w11 w12 w13• 2 w21 w22 w23• 3 w31 w32 w33/; (* Text *)
• Fall der Name nicht aussagekräftig genug ist, kann man einen (* Kommentar *) anfügen.
•
26.04.2004 LPL-Einführung 11
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PARAMETER
- land {j} = [ 400 600 300];• untergrenze {i,j} =• /: 1 2 3 :• 1 . 50 . • 2 . . 60• 3 75 . . /;• obergrenze {i,j} =• /: 1 2 3 :• 1 . 100 100 • 2 . 250 120• 3 . . . /;• wasser {j} = [ 900 800 375 ];• quote {i} = [ 600 500 325 ]; • faktor {j} = [ 1 1.05 1.1 ];• ertrag {i} = [ 400 290 150 ];
26.04.2004 LPL-Einführung 12
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
VARIABLE-Sektion
• In dieser Sektion werden die Variablen definiert. • Gleichzeitig kann man zwischen kontinuierlichen und
ganzzahligen Variablen unterscheiden.• Schließlich kann man sinnvolle Namen konstruieren.
26.04.2004 LPL-Einführung 13
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
VARIABLE 1
• Syntax:
– name1; (* Einzelvariable *)– name2 {i}; (* Einfach indizierte V. *)– name3 {i,j}; (* Mehrfach indizierte V. *)
26.04.2004 LPL-Einführung 14
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
VARIABLE 2
• Es ist sinnvoll, den Variablen mnemotechnische Namen zu geben.
• Die Namen können laut LPL-Syntax fast beliebig lang sein; sie müssen mit einem Buchstaben beginnen.
• Wichtig: Der anschließende Optimierer XA unterscheidet nur Namen der Länge mit 8 Zeichen!
26.04.2004 LPL-Einführung 15
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
VARIABLE-Definition 1
• Der Name der Variablen wird durch einen String nach der Definition und vor dem Semikolon gebildet:
– variablenname 'string';
• Ein String 'string' = 'za1a2' besteht aus:– z = eine Zahl, die angibt, wie viele der ersten
z Buchstaben des Variablennamensverwendet werden.
– a1 und a2 sind die ALIAS der Indizes 1 und 2 ersetzt.
26.04.2004 LPL-Einführung 16
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
VARIABLE-Definition 2
• Die Variablen des Beispiels:
• anbau {i,j};• Jetzt würden i bzw. j durch die Indizes der Mengen i und
j ersetzt.• Unter Benutzung der ALIAS:
• anbau {i,j} '4a1a2';• Jetzt würden i bzw. j durch die ALIAS der Mengen i und j
ersetzt:• anbaZUK1 → Anbau von Zucker in Komm.K1
26.04.2004 LPL-Einführung 17
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
CONSTRAINT-Sektion
• Dieser Teil enthält die Nebenbedingungen des Modells und die Definition der Zielfunktion.
• Nebenbedingung:
– name: funktional = rechte Seite;
• Zielfunktion:
– zielname: funktional;
26.04.2004 LPL-Einführung 18
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
CONSTRAINT-Definition: name
• Einzelname: name:• einfach indizierter Name: name {i}:• mehrfach indiz. Name: name {i,j}:• bedingter Name: name {i | log. Beding.}:
– log. Bedingung: i<=10; i>4: i<>5;– name{i,j | name2} →→→→ nur falls name2 ungleich dem
Default-Wert
26.04.2004 LPL-Einführung 19
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Beispiele von NB-Namen
• nebenbedingung:• flaeche {i}:• lowerbounds {i,j | untergrenze}:• gewinn
26.04.2004 LPL-Einführung 20
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
CONSTRAINT-Definition: funktional
• Ein Funktional ist ein nach den Regeln der Arithmetik aufgebauter Ausdruck.
• Operatoren: +, -, *, SUM{i}• Indizes sind in eckige Klammern zu setzen, wenn sie
keine Mengen sind.
26.04.2004 LPL-Einführung 21
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Beispiele für Funktionale
• lbound {i,j}: anbau[i,j]<=ugrenze[i,j];• flaeche{i}: SUM{i} anbau[i,j]<=land{j};• kont{j}: SUM{i} verbrauch[i]*anbau[i,j] <= wasser
{j};• gewinn: SUM{i,j} ertrag[i]*anbau[i,j];
26.04.2004 LPL-Einführung 22
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Alternative Formulierungen
• lbound {i,j}: anbau[i,j] <= ugrenze[i,j];! lbound {i,j}: anbau <= ugrenze;
• flaeche {j}: SUM{i} anbau <= land;! flaeche {i}: SUM{i} anbau[i,j] <= land{j};
• kont {j}: SUM{i} verbrauch[i] * anbau[i,j] <= wasser[j];! kont {j}: SUM{i} verbrauch * anbau <= wasser;
26.04.2004 LPL-Einführung 23
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Zielfunktion
• Die Zielfunktion ist ein Funktional ohne rechte Seite:
– gewinn: SUM{i,j} ertrag * anbau;
• Die Optimierungsrichtung wird durch MAXIMIZE bzw. MINIMIZE bestimmt:
– MAXIMIZE gewinn;
26.04.2004 LPL-Einführung 24
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
END-Sektion
• Jedes Programm wird beschlossen durch:
– END
• (ohne Semikolon!)
26.04.2004 LPL-Einführung 25
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Agenda (2)
1. Grundelemente eines Modells2. Erstellung eines LPL-Programms3. Beispiel "kommune.LPL"4. Verbindung zum Optimierer XA
26.04.2004 LPL-Einführung 26
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Das Problem
Pflanzsorte i Wasserverbrauch vi [1.000 m3/ha]
Nettoertrag ei [ME/ha] Maxfläche si [ha]
Zuckerrüben 3 400 600 Baumwolle 2 290 500
Hirse 1 150 325
Kibbuz j Fläche fj [ha] Wassermenge wj [1.000 m3] Wasserfaktor mj
1 400 900 1,00 2 600 800 1,05 3 300 375 1,10
26.04.2004 LPL-Einführung 27
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Das algebraische Modell
Sortenfläche: x s für alle Pflanzsorten iij ij
≤∑
Wasserkontingent: m v x w für alle Kibbuzim jj i ij ji
⋅ ⋅ ≤∑
Anbaufläche: x f für alle Kibbuzim jij ji
≤∑
Ertrag: z e xi ijji
= ⋅∑∑
Ziel Maximiere z
Anbaurelation 12: 1
1
2 2
ii
ii
xf
x f=
∑∑
(Kibbuz 2: Kibbuz 3)
Anbaurelation 23: 2
2
3 3
ii
ii
xf
x f=
∑∑
(Kibbuz 2: Kibbuz 3)
26.04.2004 LPL-Einführung 28
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Das LPL-ModellMODEL Kommune; SET i = /1.ZU 2.BA 3.HI/; (*Pflanzsorten*) j = /1.K1 2.K2 3.K3/; (*Kommunen*) PARAMETER land{j} = [ 400 600 300 ]; untergrenze{i,j} = /: 1 2 3 : 1 . 50 . 2 . . 60 3 75 . . /; obergrenze{i,j} = /: 1 2 3 : 1 . 100 100 2 . 250 120 3 . . . /; wasser{j} = [ 900 800 375 ]; quote{i} = [600 500 325 ]; verbrauch{i} = [ 3 2 1 ]; faktor{j} = [ 1 1.05 1.1 ]; ertrag{i} = [ 400 290 150 ]; VARIABLE anbau{i,j} '3a1a2'; CONSTRAINT lowerbounds{i,j | untergrenze} '4a1a2': anbau >= untergrenze; upperbounds{i,j | obergrenze} '4a1a2': anbau <= obergrenze; flaeche{j} '6a1': SUM{i} anbau[i,j] <= land; kontingent{j} '6a1': SUM{i} verbrauch*faktor[j]*anbau[i,j] <= wasser; grenze{i} '6a1': SUM{j} anbau[i,j] <= quote; A12: land[2]*(SUM{i} anbau[i,1]) = land[1]*(SUM{i} anbau[i,2]); A23: land[3]*(SUM{i} anbau[i,2]) = land[2]*(SUM{i} anbau[i,3]); gewinn: SUM{i,j} ertrag[i] * anbau[i,j]; MAXIMIZE gewinn; END
26.04.2004 LPL-Einführung 29
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Agenda (4)
1. Grundelemente eines Modells2. Erstellung eines LPL-Programms3. Beispiel "kommune.LPL"4. Verbindung zum Optimierer XA
26.04.2004 LPL-Einführung 30
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
Der Optimierer XA
• Mächtiges LP/IP-Softwareprodukt für PC • Jim Byer, Sunset Software Technology• Wird automatisch von LPL aufgerufen• Verkürzte Ausgabe des Ergebnisses in der Datei
$$$.SOL• Komplette Ausgabe des Ergebnisses in der Datei
$$$.PRN
26.04.2004 LPL-Einführung 31
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
SOL-Datei
"MPSXNAME","$$$ ","Tue Apr 06 09:36:39 2004","MAX" 11, 9,256208.6908, 10 "anbZUK1 ", 214.05680, 400.00000, 0.00000,"IN ","anbBAK1 ", 290.00000,"(NB) ", -0.00000 "anbZUK2 ", 50.00000, 400.00000, -135.15152,"LOWER","(NB) ", -0.00000,"(RS) ", 535.15152 "anbZUK3 ", 2.05824, 400.00000, 0.00000,"IN ","kontinK3", 9.33333,"anbBAK3 ", 523.88889 "anbBAK1 ", 0.00000, 290.00000, -110.00000,"LOWER","(NB) ", -0.00000,"(RS) ", 400.00000 "anbBAK2 ", 228.31956, 290.00000, 0.00000,"IN ","anbZUK2 ", 207.40741,"grenzeHI", 579.16667 "anbBAK3 ", 120.00000, 290.00000, 67.57576,"UPPER","(RS) ", 222.42424,"(NB) ", -0.00000 "anbHIK1 ", 75.00000, 150.00000, -355.15152,"LOWER","(NB) ", -0.00000,"(RS) ", 505.15152 "anbHIK2 ", 155.26564, 150.00000, 0.00000,"IN ","grenzeHI", 5.41667,"anbZUK2 ", 645.55556 "anbHIK3 ", 94.73436, 150.00000, 0.00000,"IN ","grenzeHI", -235.55556,"anbBAK3 ", 335.83333 "flaechK1", 289.05680, 400.00000, 0.00000,"IN ","LE","(RS) ", 289.05680,"(NB) ", -0.00000 "flaechK2", 433.58520, 600.00000, 0.00000,"IN ","LE","(RS) ", 433.58520,"(NB) ", -0.00000 "flaechK3", 216.79260, 300.00000, 0.00000,"IN ","LE","(RS) ", 216.79260,"(NB) ", -0.00000 "kontinK1", 717.17041, 900.00000, 0.00000,"IN ","LE","(RS) ", 717.17041,"(NB) ", -0.00000 "kontinK2", 800.00000, 800.00000, 233.47763,"UPPER","LE","anbHIK3 ", 435.27273,"anbZUK3 ", 823.77273 "kontinK3", 375.00000, 375.00000, 161.43251,"UPPER","LE","anbZUK3 ", 370.01905,"anbZUK3 ", 612.01905 "grenzeZU", 266.11505, 600.00000, 0.00000,"IN ","LE","(RS) ", 266.11505,"(NB) ", -0.00000 "grenzeBA", 348.31956, 500.00000, 0.00000,"IN ","LE","(RS) ", 348.31956,"(NB) ", -0.00000 "grenzeHI", 325.00000, 325.00000, 105.15152,"UPPER","LE","anbBAK2 ", 265.37879,"anbZUK3 ", 347.64069 "A12 ", 0.00000, 0.00000, 0.66667,"LOWER","EQ","anbZUK1 ",-128434.081,"kontinK1",36565.91893 "A23 ", 0.00000, 0.00000, 0.22121,"LOWER","EQ","anbZUK3 ",-3396.10390,"anbHIK3 ",52103.89610
26.04.2004 LPL-Einführung 32
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PRN-Datei (Statistik)
STATISTICS - FILE: $$$ TITLE: MPSXNAME Tue Apr 06 09:36:39 2004 xa VERSION 10.0 Intel Extended-DOS x86 USABLE MEMORY 7,605K BYTES VARIABLES 9 MAXIMUM 50,000 3 LOWER, 0 FIXED, 4 UPPER, 0 FREE CONSTRAINTS 11 MAXIMUM 10,000 0 GE, 2 EQ, 9 LE, 0 NULL/FREE, 0 RANGED. CAPACITY USED BY CATEGORY- 0.0% VARIABLE, 0.1% CONSTRAINT, 48 NON-ZEROS, WORK 778,338 MAXIMIZATION. MPS FORMAT- OBJECTIVE: gew RHS: ..rhs RANGE: ? BOUND: Bounds O P T I M A L S O L U T I O N ---> OBJECTIVE 256208.6908 SOLVE TIME 00:00:00 ITER 10 MEMORY USED 0.0%
26.04.2004 LPL-Einführung 33
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PRN-Datei (Variablen)
File: $$$ Tue Apr 06 09:36:39 2004 Page 1 SOLUTION (Maximized): 256208.6908 MPSXNAME ------------------------------------------------------------------------------- | Variable | Activity | Cost | Variable | Activity | Cost | ------------------------------------------------------------------------------- I anbZUK1 214.05680 400.00000 | anbZUK2 50.00000 400.00000 | | REDUCED COST 0.00000 | REDUCED COST -135.15152 | ------------------------------------------------------------------------------- I anbZUK3 2.05824 400.00000 | anbBAK1 0.00000 290.00000 | | REDUCED COST 0.00000 | REDUCED COST -110.00000 | ------------------------------------------------------------------------------- I anbBAK2 228.31956 290.00000 U anbBAK3 120.00000 290.00000 | | REDUCED COST 0.00000 | REDUCED COST 67.57576 | ------------------------------------------------------------------------------- | anbHIK1 75.00000 150.00000 I anbHIK2 155.26564 150.00000 | | REDUCED COST -355.15152 | REDUCED COST 0.00000 | ------------------------------------------------------------------------------- I anbHIK3 94.73436 150.00000 | | REDUCED COST 0.00000 | ----------------------------------------
26.04.2004 LPL-Einführung 34
Fachbereich WirtschaftswissenschaftenBWL insb. Quant. Meth., Prof. Dr. D. Ohse
PRN-Datei (Nebenbedingungen)File: $$$ Tue Apr 06 09:36:39 2004 Page 2 CONSTRAINTS: MPSXNAME --------------------------------------------------------------------------- |Constraint| Activity | RHS |Constraint| Activity | RHS | --------------------------------------------------------------------------- I flaechK1 289.05680 < 400.00000 I flaechK2 433.58520 < 600.00000 | | DUAL VALUE 0.00000 | DUAL VALUE 0.00000 | --------------------------------------------------------------------------- I flaechK3 216.79260 < 300.00000 I kontinK1 717.17041 < 900.00000 | | DUAL VALUE 0.00000 | DUAL VALUE 0.00000 | --------------------------------------------------------------------------- | kontinK2 800.00000 < 800.00000 | kontinK3 375.00000 < 375.00000 | | DUAL VALUE 233.47763 | DUAL VALUE 161.43251 | --------------------------------------------------------------------------- I grenzeZU 266.11505 < 600.00000 I grenzeBA 348.31956 < 500.00000 | | DUAL VALUE 0.00000 | DUAL VALUE 0.00000 | --------------------------------------------------------------------------- | grenzeHI 325.00000 < 325.00000 | A12 0.00000 = 0.00000 | | DUAL VALUE 105.15152 | DUAL VALUE 0.66667 | --------------------------------------------------------------------------- | A23 0.00000 = 0.00000 | | DUAL VALUE 0.22121 | --------------------------------------