Modellieren mit AMPL - Discrete Mathematics · 2007-04-27 · Uberblick AMPL - Algebraic modeling language for mathematical programming Algebraische Schreibweise eine linearen Programms:

Modellieren mit AMPL

Elisabeth Gassner

Mathematische Modelle in den Wirtschaftswissenschaften

Prof. R. E. Burkard

27. April 2007

E. Gassner (Mathematische Modelle) AMPL 27. April 2007 1 / 21

Uberblick

AMPL - Algebraic modeling language for mathematical programmingAlgebraische Schreibweise eine linearen Programms:

minx

n∑

j=1

cjxj

s.t.n∑

j=1

aijxj ≤ bi i = 1, . . . ,m

xj ≥ 0 j = 1, . . . , n

Ziel: Ubergabe eines Modells und der Daten an einen Solver und Ausgabeeiner Optimallosung.


Uberblick

Eigenschaften von AMPL:

AMPL ist eine Modelliersparche, die es ermoglicht, einOptimierungsmodell in kompakter Form darzustellen.

AMPL lost das Optimierungsproblem nicht selbst sondern ubergibt eseinem Solver (z.B. CPLEX, minos, etc.)

Das Modell und die Daten sind getrennt (file.mod, file.dat)

Das Modellfile enthalt Deklaration der Datenparameter und Variablen,die Zielfunktion und die Nebenbedingungen.

Das Datenfile enthalt die aktuellen Werte der Parameter.


Uberblick

Verfugbarkeit:

Freie Studentenversion von AMPL aufhttp://www.ampl.com/DOWNLOADS/index.html

Online-Version

In der Windows-Version wird Solver mit zip-file mitgeliefert, furUnix/Linux muss CPLEX getrennt downgeloadet werden.


Beispiel 1: Produktionsplanung

Eine Stahlfabrik muss den Produktionsplan fur eine Wochezusammenstellen. Die Fabrik kann Produkt A oder Produkt B herstellen.Die Produkte werden in folgenden Raten gefertigt:

Tonnen pro Stunde: Produkt A 200Produkt B 140

Der Verkaufspreis betragt

Profit pro Tonne: Produkt A 25Produkt B 30

Aufgrund von Kapazitatsbeschrankungen mussen folgende Grenzeneingehalten werden:

Maximal in Tonnen: Produkt A 6000Produkt B 4000

Wieviel Tonnen von Produkt A und B sollen produziert werden, wenn 40Arbeitsstunden zur Verfugung stehen und als Ziel der gesamteVerkaufserlos maximiert werden soll?


Beispiel 1: Produktionsplanung (Fs.)

Entscheidungsvariablen:xA (Tonnen von Produkt A), xB (Tonnen von Produkt B)

max 25xA + 30xB

s.t.1

200xA +

1

140xB ≤ 40

0 ≤ xA ≤ 6000

0 ≤ xB ≤ 4000



Trennung von Modell und Daten!

production.mod

set PROD; #Produkte

param rate {PROD} >0; #Produktionsrate fur jedes Produkt

param profit {PROD}; #Profit pro Tonne fur jedes Produkt

param schranke {PROD}; #obere Schranke fur jedes Produkt

param arbeitszeit; #Arbeitsstunden pro Woche

var menge {PROD}; #Produktionsmenge fur jedes Produkt

maximize Gesamtprofit: sum {p in PROD} profit[p] * menge[p];

subject to Zeit:

sum {p in PROD} (1/rate[p]) * menge[p] <= arbeitszeit;

subject to Schranken {p in PROD}: menge[p] <= schranke[p];



production.dat

set PROD := ProduktA ProduktB;

param arbeitszeit := 40;

param: rate profit schranke :=

ProduktA 200 25 6000

ProduktB 140 30 4000;



production.run

model production.mod;

data production.dat;

option solver cplex; #option solver cplexamp;

solve;

display menge;


Starten von AMPL

Starten von AMPLWindows:

MS-DOS Fenster:

Doppelklick auf ampl.exe ⇒ MS-DOS Fenster offnet sich mit ampl:

Scrolling-Window Utility:

Doppelklick auf sw.exe ⇒ Fenster offnet sich mit sw: ⇒ sw: ampl ⇒

ampl:

Linux/Unix: Konsole ampl

Losen eines Optimierungsproblems mit AMPLinclude filename.run;

Beenden von AMPL mit quit;


Output von AMPL

ILOG AMPL 9.100, licensed to ’’university-graz’’.

AMPL Version 20021038 (Linux 2.4.9-e.24smp)

ILOG CPLEX 9.100, licensed to ’’university-graz’’, options:

e m b q

CPLEX 9.1.0: optimal solution; objective 192000

0 dual simplex iterations (0 in phase I)

menge [*] :=

ProduktA 6000

ProduktB 1400

;


Die Modelldatei (1)

Definition von Mengen, Parametern und Variablen

Mengen:set MENGENNAME;

Parameter:param PARAMETERNAME >= lb, <= ub;

Indizierter Parameter:param PARAMETERNAME {MENGE} >= lb, <= ub; #oder

param PARAMETERNAME {MENGE1, MENGE2} >= lb, <= ub;

Variablen:var VARIABLENNAME >= lb, <= ub; #oder

var VARIABLENNAME {j in MENGE} >= lb, <= ub; #oder

var VARIABLENNAME {i in MENGE1, j in MENGE2}# optional binary oder integer


Die Modelldatei (2)

Definition der Zielfunktion:maximize/minimize ZIELNAME: Funktion;

Nebenbedingungen:

eine Bedingung:subject to NAME: Restriktion;

mehrere Bedingungen:subject to NAME {j in Menge}: Restriktion;


Die Datendatei

Mengen:set MENGENNAME := M1 M2 M3 M4; #oder

set MENGENNAME := 1 .. 10 by 2;

Parameter:param PARAMETERNAME := 40;

Einfach indizierter Parameter:param PARAMETERNAME:= M1 p1 M2 p2; #einfach indiziert

param: PARAMETERNAME1 PARAMETERNAME2 :=

M1 p1 p2

M2 p3 p4; #mehrere Parameter


Die Datendatei (2)

Mehrfach indizierte Parameter:param PARAMETERNAME:=

[M1,*] N1 a N2 b

[M2,*] N1 c N2 d; #doppelt indiziert

param PARAMETERNAME: N1 N2:=

M1 a b

M2 c d; #einfache Schreibweise

param PARAMETERNAME:=

[A1,*,*] C1 C2 C3

B1 a b c

B2 d e f

[A2,*,*] C1 C2 C3

B1 g h i

B2 j k l; #Parameter mit 3 Indizes


Die Run-Datei

reset;

model DATEINAME.mod;

data DATEINAME.dat;

option solver cplex; #option solver cplexamp;

solve;

display VARIABLE1, VARIABLE2; #Output am Bildschirm

display VARIABLE3 > OUTPUT.txt; #Output in Datei OUTPUT.txt


Einige Grundsatze und Fehlerquellen

Wahlen Sie aussagekraftige Namen. Variablen und Nebenbedingungendurfen nicht den gleichen Namen tragen.

Dokumentieren Sie das Modell. Alles nach dem Symbol # wirdignoriert.

Jede Zeile muss mit Strichpunkt enden.

Jede Variable muss mit var definiert sein.


Beispiel 2: Zuordnungsproblem

Ein Unternehmen besitzt 3 Lager und 4 Fabriken. Die Ressourcen fur dieProduktion in den Fabriken mussen von den Lagern zugeliefert werden. DieLager verfugen uber folgende Kapazitaten

Lager 1: 250, Lager 2: 800, Lager 3: 760

und die Fabriken haben folgenden Bedarf

Fabrik 1: 300, Fabrik 2: 320, Fabrik 3: 800, Fabrik 4: 390

Die Transportkosten pro gelieferter Einheit sind linear von der Distanzabhangig:

Fabrik 1 Fabrik 2 Fabrik 3 Fabrik 4Lager 1 1 2 3 2Lager 2 3 2 4 1Lager 3 2 6 2 5

Bestimmen Sie einen zulassigen Transportplan, der die Gesamtkostenminimiert.



zuordnung.mod

param anzahlfabriken; #Anzahl der Fabriken

param anzahllager; #Anzahl der Lager

set fabriken:=1..anzahlfabriken; #Menge aller Fabriken

set lager:=1..anzahllager; #Menge der Lager

param cost{i in lager, j in fabriken}; #Kosten von Lager i

zu Fabrik j

param kapazitaet {i in lager}; #Kapazitaet von Lager i

param bedarf {j in fabriken}; #Bedarf von Fabrik j

var transport {i in lager, j in fabriken} >=0;

#Transportierte Menge von Lager i zu Fabrik j



zuordnung.mod (Fs.)

minimize Kosten: sum{i in lager, j in fabriken} cost[i,j] *

transport[i,j];

subject to Lagerkapazitaet {i in lager}:sum{j in fabriken} transport[i,j] <= kapazitaet[i];

#Gesamttransport ab Lager i

subject to Fabriksbedarf {j in fabriken}:sum{i in lager} transport[i,j] >= bedarf[j];

#Gesamttransport zu Fabrik j



zuordnung.dat

param anzahlfabriken := 4;

param anzahllager :=3;

param kapazitaet:= 1 250 2 800 3 760;

param bedarf:= 1 300 2 320 3 800 4 390;

param cost: 1 2 3 4 :=

1 1 2 3 2

2 3 2 4 1

3 2 6 2 5;


Documents

Modellieren mit AMPL - Discrete Mathematics · 2007-04-27 · Uberblick AMPL - Algebraic modeling language for mathematical programming Algebraische Schreibweise eine linearen Programms: