LPL - Linear Programming LanguageLPL... · 26.04.2004 LPL-Einführung 7 Fachbereich Wirtschaftswissenschaften BWL insb. Quant. Meth., Prof. Dr. D. Ohse Besonderheiten der SET-Definition

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



Agenda (0)

1. Grundelemente eines Modells2. Erstellung eines LPL-Programms3. Beispiel "kommune.LPL"4. Verbindung zum Optimierer XA



Agenda (1)




Grundelemente eines Modells

• MODEL• SET• PARAMETER• VARIABLE• CONSTRAINT• MAXIMIZE• END•



MODEL-Sektion

• MODEL Kommune;

• Ein Kommentar kann eingefügt werden, indem er in (*Text*) hinter dem Semikolon eingefügt wird.

• MODEL kommune; (*Beispiel*)



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*)



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 *)



PARAMETER-Sektion

• In dieser Sektion werden alle Daten symbolisch definiert. Es können durch die „gleich Zuweisung“ unmittelbar folgend die Datenwerte zugewiesen werden.



PARAMETER-Definition 1

• Syntax:

– name1 = wert1; (* Einzelwert *)– name2 {Indexmenge} = [wert1 wert2 .. ];

• Mehrfachindizierte Parameter:

– name{i-menge1,j-menge2} = Wertzuweisung;



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.

•



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 ];



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.



VARIABLE 1

• Syntax:

– name1; (* Einzelvariable *)– name2 {i}; (* Einfach indizierte V. *)– name3 {i,j}; (* Mehrfach indizierte V. *)



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!



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.



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



CONSTRAINT-Sektion

• Dieser Teil enthält die Nebenbedingungen des Modells und die Definition der Zielfunktion.

• Nebenbedingung:

– name: funktional = rechte Seite;

• Zielfunktion:

– zielname: funktional;



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



Beispiele von NB-Namen

• nebenbedingung:• flaeche {i}:• lowerbounds {i,j | untergrenze}:• gewinn



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.



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];



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;



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;



END-Sektion

• Jedes Programm wird beschlossen durch:

– END

• (ohne Semikolon!)



Agenda (2)




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



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)



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



Agenda (4)




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



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



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%



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 | ----------------------------------------



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 | --------------------------------------

Documents

LPL - Linear Programming LanguageLPL... · 26.04.2004 LPL-Einführung 7 Fachbereich Wirtschaftswissenschaften BWL insb. Quant. Meth., Prof. Dr. D. Ohse Besonderheiten der SET-Definition