1 Breve introduzione ad AMPL
Il primo passo per risolvere un problema reale attraverso strumenti matematici consiste nel passare dalla descrizione a parole del problema al modello matema- tico dello stesso. Questo passaggio verr´a ora illustrato in un caso particolare, il
@
@%
%
%J J
Jhhh
@@
%
%
%
% bb b T T T
Z Z Z
%
%
Descrizione a parole del problema
Modello matematico del problema
Figura 1: Il passaggio dalla descrizione a parole al modello matematico.
problema della dieta. La descrizione a parole di tale problema ´e la seguente.
Descrizione a parole Sia dato un insieme P ROD di prodotti ed un insieme SOST di sostanze nutritive. Si sa che in un’unit´a del prodotto j si trova una quantit´a quant unitij della sostanza nutritiva i. Inoltre si sa che il costo di un’unit´a di prodotto j ´e pari a cost unitj. Tenendo conto che una dieta deve contenere una quantit´a minima quant mini di ciascuna sostanza nutritiva, si vuole determinare una dieta che abbia costo minimo.
Da tale descrizione si passa al modello matematico che risulter´a essere un problema di programmazione lineare.
Modello matematico Ad ogni prodotto j si associa una variabile xjindicante la quantit´a di prodotto da inserire nella dieta. L’ obiettivo ´e quello di minimizzare il costo complessivo della dieta, cio´e
min X
j∈P ROD
cost unitj∗ xj. (1)
Inoltre abbiamo i vincoli di dover avere almeno una quantit´a quant mini
di ciascuna sostanza nutritiva, cio´e X
j∈P ROD
quant unitij∗ xj≥ quant mini ∀ i ∈ SOST. (2)
Infine di ogni prodotto dobbiamo avere una quantit´a non negativa, cio´e
xj≥ 0 ∀ j ∈ P ROD. (3)
Quindi il nostro modello matematico ´e il seguente problema di PL
min P
j∈P RODcost unitj∗ xj
P
j∈P RODquant unitij∗ xj≥ quant mini ∀ i ∈ SOST
xj ≥ 0 ∀ j ∈ P ROD
Una volta definito il modello matematico lo si passa ad un risolutore (nel nostro caso, tipicamente, l’algoritmo del simplesso) che restituisce come output una soluzione ottima se questa esiste oppure segnala in quale caso dei due casi di impossibilit´a (problema illimitato o regione ammissibile vuota) ci si trova (vedi Figura 2). Il passaggio dal modello matematico al risolutore non ´e per´o im-
e e
e,,,e e
e D
D D
D , , , , bb
!b
!! T T T
Descrizione a parole Modello
matematico Risolutore (Simplesso)
Soluzioni o segnalazione caso di impossibilita’
Figura 2: Dalla descrizione a parole alla soluzione del problema.
mediato. ´E necessario tradurre questo modello nelle strutture dati che devono essere passate come input al programma risolutore (vedi Figura 3). Ci´o che suc-
Input per il risolutore Modello matematico
su carta
Figura 3: Il modello matematico su carta va tradotto nell’input per il risolutore .
cede nella pratica ´e che ci sono tipicamente grosse differenze tra il modello scritto su carta di un problema di PL e la forma in cui lo stesso modello deve essere passato come input al risolutore e la trasformazione richiede un certo sforzo. Lo scopo del linguaggio AMPL ´e proprio quello di facilitare questo compito. Invece di passare direttamente dal modello su carta all’input per il risolutore, si scrive un modello in linguaggio AMPL che viene poi passato ad un traduttore che si occupa di trasformare il modello scritto in AMPL nell’input per il programma
""""b bb
b
"
"
"
"
bb bb
Modello in
linguaggio AMPL traduttore Input per il risolutore Modello
matematico su carta
Figura 4: Il modello in AMPL traduce il modello su carta e viene a sua volta tradotto nell’input per il risolutore.
risolutore (vedi Figura 4). Il vantaggio di questo passaggio supplementare ´e che AMPL ´e concepito in modo che il modello scritto in AMPL sia molto simile al modello scritto su carta.
Verranno ora introdotte alcune parti fondamentali di AMPL. Le stesse verranno illustrate attraverso l’esempio della dieta mostrato in precedenza. In un model- lo di programmazione lineare (o di programmazione lineare intera) gli elementi fondamentali sono:
Insiemi di indici Nel caso del problema della dieta sono i due insiemi P ROD dei prodotti e SOST delle sostanze nutritive.
Parametri Sono tutte le quantit´a il cui valore ´e noto prima di risolvere il problema. Nel problema della dieta sono i costi unitari cost unitj dei pro- dotti, le quantit´a minime quant minidelle sostanze nutritive e le quantit´a quant unitij di sostanza i in un’unit´a di prodotto j.
Variabili Sono le quantit´a i cui valori devono essere stabiliti attraverso la solu- zione del problema. Nell’esempio sono le variabili xj indicanti le quantit´a di prodotto j.
Vincoli Limitano la scelta delle variabili. Nell’esempio abbiamo i vincoli (2) sulle quantit´a minime di ciascuna sostanza ed i vincoli (3) sulla non negativit´a delle quantit´a di ciascun prodotto.
Obiettivo ´E la quantit´a il cui valore va massimizzato (o minimizzato) sceglien- do opportunamente i valori delle variabili. Nell’esempio si deve minimiz- zare il costo della dieta, ovvero l’obiettivo ´e dato da (1).
Si tratta ora di vedere come questi elementi vengono definiti in linguaggio AMPL.
Insiemi Un insieme T si dichiara semplicemente attraverso la seguente sintassi set T ;
Si noti che questa ´e soltanto la dichiarazione dell’insieme. Da una qualche altra parte, come vedremo, andr´a specificato il contenuto dell’insieme.
Nel nostro esempio avremo le seguenti dichiarazioni set P ROD ;
set SOST ;
Parametri Un parametro a si dichiara nel modo seguente param a ;
Qualora sia noto che il parametro ´e sempre positivo conviene indicarlo esplicitamente nella dichiarazione nel modo seguente
param a > 0 ;
In modo analogo si pu´o specificare che un parametro ´e non negativo (>= 0), negativo (< 0) o non positivo (<= 0). Si pu´o anche specifi- care che un parametro deve avere un valore intero nel modo seguente param a > 0 integer ;
In questo caso il parametro a deve essere un intero positivo.
E possibile anche dichiarare vettori di parametri con indici in un insieme´ T attraverso la seguente dichiarazione
param a{T } ;
Nel caso gli indici siano gli interi da 1 a n si pu´o scrivere param a{1..n} ;
Si possono infine anche dichiarare array bidimensionali con insiemi di in- dici T1 e T2nel modo seguente
param a{T1, T2} ;
Nell’esempio si avranno le seguenti dichiarazioni param cost unit{P ROD} > 0 ;
param quant unit{SOST ,P ROD} >= 0 ; param quant min{SOST } > 0;
Si noti che si richiede che i costi unitari e le quantit´a minime siano stret-
tamente positive, mentre le quantit´a di sostanza in un’unit´a di prodotto devono essere non negative.
Variabili La definizione delle variabili ´e del tutto analoga a quella dei parame- tri. La sola differenza ´e che la parola chiave param viene sostituita dalla parola chiave var. Nel nostro esempio abbiamo un vettore di variabili x con indici in P ROD che sar´a definito in questo modo
var x{P ROD} >= 0 ;
Si noti che nella dichiarazione delle variabili sono gi´a compresi i vinco- li di non negativit´a (3) delle stesse. Nel caso una variabile sia vincolata ad assumere solo valori interi ´e sufficiente aggiungere la parola chiave integer nella sua dichiarazione, esattamente come si ´e fatto per i parametri. Si noti che questa aggiunta ´e la sola cosa che distingue un modello di AM- PL per la programmzaione lineare da uno per la programmazione lineare intera.
Vincoli Un singolo vincolo viene dichiarato nel seguente modo subject to nome vincolo : formula vincolo ;
Spesso per´o non si hanno singoli vincoli, ma collezioni di vincoli indicizzate su degli insiemi. ´E questo per esempio il caso dei vincoli (2) nel problema della dieta. Tali vincoli sono indicizzati rispetto all’insieme SOST . In generale, dato un’insieme di indici I, la collezione di vincoli indicizzata su I viene dichiarata in questo modo
subject to nome insieme vincoli{i in I} : formula vincoli ; Per i vincoli (2) si avr´a la seguente dichiarazione
subject to min sostanza{i in SOST } : sum {j in P ROD} quant unit[i,j]*x[j]
>= quant min[i] ;
Nella formula si devono notare due cose.
1. L’uso di sum {j in J} per la definizione di una sommatoria con indice J ;
2. l’uso delle parentesi quadre [] per richiamare i singoli elementi degli array.
Obiettivo L’obiettivo si dichiara, in generale, nel modo seguente maximize nome obiettivo : formula obiettivo ;
(nel caso si debba minimizzare si usa la parola chiave minimize al posto di maximize). Nel nostro esempio avremo
minimize total cost : sum{j in P ROD} cost unit[j]*x[j] ;
Abbiamo quindi definito in AMPL tutti gli elementi del nostro problema della dieta. Questi verranno trascritti in un file a cui si assegna il nome di DIE- TA.MOD che si presenter´a come segue (le scritte comprese tra ### sono com- menti).
———————————————————————————————————
DIETA.MOD
### INSIEMI ###
set P ROD ; set SOST ;
### PARAMETRI ###
param cost unit{P ROD} > 0 ;
param quant unit{SOST ,P ROD} >= 0 ; param quant min{SOST } > 0;
### VARIABILI ###
var x{P ROD} >= 0 ;
### VINCOLI ###
subject to min sostanza{i in SOST } : sum {j in P ROD} quant unit[i,j]*x[j]
>= quant min[i] ;
### OBIETTIVO ###
minimize total cost : sum{j in P ROD} cost unit[j]*x[j] ;
———————————————————————————————————
Una volta costruito il modello bisogner´a inserire in un altro file i valori di insiemi e parametri. Mentre il modello viene inserito in un file con estensione .MOD, i valori vengono inseriti in un file con estensione .DAT. Il file DIETA.DAT dovr´a contenere le definizioni degli insiemi P ROD e SOST ed i valori assegnati ai diversi parametri. Supponiamo di avere a disposizione i seguenti dati. L’insie- me P ROD contiene pasta, verdura, carne; l’insieme SOST contiene vitamine, proteine; un’unit´a di pasta, verdura o carne costa rispettivamente 3,2 e 5; le quantit´a minime di vitamine e proteine sono rispettivamente 8 e 6; le quantit´a di vitamine in un’unit´a di pasta, verdura o carne sono rispettivamente 0.3, 0.5 e 0.4; le quantit´a di proteine in un’unit´a di pasta, verdura o carne sono rispet- tivamente 0.5, 0.2 e 0.7. Bisogna ora vedere come questi dati devono essere scritti nel file DIETA.DAT. Per quanto riguarda la definizione di un insieme J contenente gli oggetti t1, t2, . . . , tn si usa la seguente sintassi
set T := t1t2 . . . tn ; Nel nostro esempio avremo
set P ROD := pasta verdura carne ; set SOST := vitamine proteine ;
Per quanto riguarda i parametri si usa la seguente sintassi param a := valore parametro ;
Per parametri vettore con insieme indice T = {t1, . . . , tn} si usa la seguente sintassi
param a :=
t1valore1
...
tn valoren ;
Per parametri che sono array bidimensionali con primo insieme di indici T = {t1, . . . , tn} e secondo insieme di indici S = {s1, . . . , sm} si usa la seguente sin- tassi
param a :
s1 · · · sm :=
t1 val(t1, s1) · · · val(t1, sm) ... ... ... ...
tn val(tn, s1) · · · val(tn, sm) ; Nel nostro esempio si avranno quindi i seguenti assegnamenti.
param cost unit :=
pasta 3 verdura 2 carne 5 ;
param quant min :=
vitamine 8 proteine 6 ;
param quant unit :
pasta verdura carne :=
vitamine 0.3 0.5 0.4
proteine 0.5 0.2 0.7 ;
Quindi il file DIETA.DAT per questo esempio si presenter´a nella seguente forma
———————————————————————————————————
DIETA.DAT
### INSIEMI ###
set P ROD := pasta verdura carne ; set SOST := vitamine proteine ;
### PARAMETRI ###
param cost unit :=
pasta 3
verdura 2 carne 5 ;
param quant min :=
vitamine 8 proteine 6 ;
param quant unit :
pasta verdura carne :=
vitamine 0.3 0.5 0.4
proteine 0.5 0.2 0.7 ;
———————————————————————————————————
Una volta inseriti i dati nel file DIETA.DAT siamo pronti per la risoluzione del problema. Prima per´o va fatta un’osservazione. Qui abbiamo inserito certi dati ma pu´o capitare che lo stesso tipo di problema debba essere risolto con altri dati (ad esempio il costo di certi prodotti pu´o cambiare o tra le sostanze se ne possono aggiungere altre come i carboidrati). AMPL ´e concepito in mo- do tale che queste modifiche possano essere fatte andando a modificare il solo file .DAT mentre nessuna modifica deve essere fatta nel file .MOD. Ora siamo pronti per la risoluzione del problema. ´E sufficiente inserire i seguenti comandi in corrispondenza del prompt ampl:
ampl: model DIETA.MOD;
ampl: data DIETA.DAT;
ampl: solve;
(Si notino i ”;” al termine di ogni comando). Appare automaticamente il valore ottimo del problema.
optimal solution; objective 45.263...
Per visualizzare la soluzione primale si deve dare il comando
ampl: display x;
Apparir´a la seguente risposta
x[*] :=
carne 0 pasta 7.36842 verdura 11.5789
;
Infine, per visualizzare la soluzione duale, ricordando che ad ogni vincolo prima- le corrisponde una variabile duale, ´e sufficiente mandare il comando ”display”
con il nome dei vincoli primali.
ampl: display min sostanza;
Apparir´a la seguente risposta
min sostanza [*] :=
proteine 4.73684 vitamine 2.10526
;
Avremo quindi che il valore dell’ottimo ´e 45.2632; che nella soluzione ottima si ha una quantit´a 0 di carne, una quantit´a 7.36842 di pasta ed una quantit´a 11.5789 di verdura; che le variabili nella soluzione ottima del duale hanno va- lore 4.73684 quella relativa al vincolo sulle proteine e 2.10526 quella relativa al vincolo sulle vitamine. Si noti che, come atteso, il valore dell’ottimo duale
4.73684∗ 6 + 2.10526 ∗ 8 = 45.2632 coincide con l’ottimo del primale.
2 Un esempio di PLI
Vogliamo ora introdurre un altro esempio di traduzione di un modello su carta in un modello in linguaggio AMPL. In questo caso si prender´a in considerazione un problema di programmazione lineare intera, il problema dello zaino. Come
gi´a fatto per il problema della dieta, si dar´a dapprima una descrizione a parole del problema, quindi lo si tradurr´a in un modello di PLI su carta ed infine si passer´a alla traduzione in linguaggio AMPL.
Descrizione a parole ´E dato un insieme OGGET T I di oggetti a ciascuno dei quali ´e associato un peso ed un valore. ´E inoltre dato uno zaino a cui ´e associata una capacit´a, ovvero un peso massimo che pu´o essere trasportato all’interno dello zaino. Si vogliono inserire degli oggetti nello zaino in mo- do tale da massimizare il valore complessivo trasportato in esso, tenendo conto che il peso totale degli oggetti inseriti non pu´o superare la capacit´a dello zaino.
Modello su carta All’oggetto i associamo una variabile binaria xi, ovvero una variabile che pu´o assumere solamente i valori 0 e 1. Se xi = 0 l’oggetto i non viene inserito nello zaino, se xi = 1 l’oggetto viene inserito nello zaino. L’unico vincolo ´e quello che gli oggetti inseriti nello zaino abbiano un peso complessivo che non superi la capacit´a dello zaino, ovvero
X
i∈OGGET T I
pesoi∗ xi≤ capacit´a.
L’obiettivo ´e quello di massimizzare il valore degli oggetti inseriti nello zaino, quindi
max X
i∈OGGET T I
valorei∗ xi.
Il modello su carta avr´a dunque la seguente forma
max P
i∈OGGET T Ivalorei∗ xi
P
i∈OGGET T Ipesoi∗ xi≤ capacit´a
xi∈ {0, 1} i∈ OGGET T I
Modello in linguaggio AMPL abbiamo un solo insieme, l’insieme OGGET T I, che verr´a dichiarato nel modo seguente
set OGGET T I ;
Come parametri abbiamo due vettori di parametri, peso e valore, con insieme indice OGGET T I ed il singolo parametro capacit´a. Tutti questi parametri sono positivi e verranno dichiarati nel modo seguente
param peso{OGGET T I} > 0 ; param valore{OGGET T I} > 0 ; param capacit´a > 0 ;
Avremo poi un vettore di variabili con insieme indice OGGET T I. Le variabili sono vincolate ad assumere i soli valori 0 e 1. Si pu´o esprimere questo accoppiando la dichiarazione delle variabili ad una dichiarazione di vincoli nel modo seguente
var x{OGGET T I} >= 0 integer ;
subject to limit var{i in OGGET T I} : x[i] <=1 ;
In questo modo le variabili sono vincolate ad essere interi compresi tra 0 e 1 e quindi possono assumere i soli valori 0 e 1. Tuttavia, visto il largo uso che si fa nella PLI di variabili binarie, AMPL prevede una dichiarazio- ne speciale per esse: invece di accoppiare la dichiarazione delle variabili ad una dichiarazione di vincoli come descritto sopra, si effettua la seguente unica dichiarazione
var x{OGGET T I} binary ;
Per quanto riguarda i vincoli, nel problema dello zaino abbiamo solo quello sulla capacit´a dello zaino che verr´a dichiarato nel modo seguente
subject to max capac : sum{i in OGGET T I} peso[i]∗x[i] <= capacit´a ; Infine l’obiettivo verr´a dichiarato nel modo seguente
maximize tot valore : sum{i in OGGET T I} valore[i] ∗ x[i] ;
Mettendo assieme quanto visto, il file contenente il modello, che chia- meremo ZAINO.MOD, si presenter´a nella seguente forma
————————————————————————————————
ZAINO.MOD
### INSIEMI ###
set OGGET T I ;
### PARAMETRI ###
param peso{OGGET T I} > 0 ; param valore{OGGET T I} > 0 ; param capacit´a > 0 ;
### VARIABILI ###
var x{OGGET T I} binary ;
### VINCOLI ###
subject to max capac : sum{i in OGGET T I} peso[i] ∗ x[i] <= capacit´a
;
### OBIETTIVO ###
maximize tot valore : sum{i in OGGET T I} valore[i] ∗ x[i] ;
————————————————————————————————
Una volta costruito il modello si tratta di considerare delle particolari istanze di problema dello zaino in cui siano date le definizioni dell’insieme OGGET T I e dei parametri. Ad esempio, consideriamo un caso in cui gli oggetti sono un libro, una radio, un telefono ed una macchina fotografica, con peso rispettivamente pari a 3, 7, 2 e 4 e valore 5, 8, 4 e 7. La capacit´a dello zaino ´e 11. Il file di dati ZAINO.DAT si presenter´a come segue
————————————————————————————————
ZAINO.DAT
### INSIEMI ###
set OGGET T I := libro radio telefono macchina fotografica ;
### PARAMETRI ###
param peso :=
libro 3 radio 7 telefono 2
macchina fotografica 4 ;
param valore :=
libro 5 radio 8 telefono 4
macchina fotografica 7 ;
param capacit´a := 11 ;
————————————————————————————————
A questo punto per risolvere il problema si procede come gi´a visto per il problema della dieta, inserendo modello e dati e chiamndo il risolutore attraverso i seguenti comandi
ampl: model ZAINO.MOD;
ampl: data ZAINO.DAT;
ampl: solve;
Il programma risolutore ´e un algoritmo Branch-and-Bound la cui esecuzio- ne resta invisibile all’utente, il quale tuttavia pu´o scegliere alcune opzioni (si veda il manuale per i dettagli). Ad esempio ´e possibile scegliere diver- se regole per la selezione della variabile su cui fare il branching o per la selezione del nodo dell’albero da suddividere. Attraverso il comando
ampl: display x;
´e possibile visualizzare la soluzione ottima. Nell’esempio specifico essa ´e
x[*] :=
libro 1
macchina fotografica 1 radio 0
telefono 1
;
con valore ottimo tot valore pari a 16. Quindi la soluzione ottima ha va- lore 16 e consiste nel mettere nello zaino il libro, la macchina fotografica ed il telefono mentre la radio viene lasciata fuori.
Nota
Va puntualizzato che questi appunti contengono solo alcune idee di base di AMPL ma il linguaggio consente di modellare problemi anche molto pi´u com- plicati rispetto al problema della dieta e dello zaino. Per tutto quello che non si trova in questi appunti si rimanda al libro AMPL: a Modeling Language for Mathematical Programming.
