Problemi di Ottimizzazione e Programmazione Lineare

Dispense del corso di Ottimizzazione Combinatoria (IN440)
5. Problemi di Ottimizzazione e
Programmazione Matematica
Marco Liverani
Università degli Studi Roma Tre
Dipartimento di Matematica e Fisica
Corso di Laurea in Matematica
E-mail [email protected]
Aprile 2014
2
M. Liverani – IN440
Revisione del 13 aprile 2014.
Problemi di Ottimizzazione e Programmazione Matematica
3
1 Generalità
In queste pagine ci proponiamo di descrivere una particolare classe di problemi, quelli di ottimizzazione combinatoria, studiandone una formulazione più generale che si inquadra nel contesto più ampio
di problemi di programmazione matematica. Per iniziare a circoscrivere la famiglia dei problemi di
ottimizzazione combinatoria e le caratteristiche che la distinguono da altri insiemi di problemi, dobbiamo focalizzare l’attenzione sul tipo di soluzione che viene richiesta da ciascuna classe di problema:
è proprio la tipologia della soluzione che si deve individuare per risolvere il problema che ci permette
di costruire una prima classificazione che aggrega in famiglie omogenee problemi che per ambito,
applicazioni, strumenti di risoluzione risultano altrimenti molto diversi fra loro. Nel costruire questa
classificazione procederemo in modo “incrementale”, rendendo la richiesta posta dal problema stesso,
via via sempre più “esigente”.
La formulazione più essenziale in cui può essere posto un problema è quella in cui si chiede semplicemente di rispondere «sì o no», «vero o falso», «0 o 1». Esiste uno zero della funzione f (x)
nell’intervallo (a, b)? Esiste un cammino di lunghezza inferiore a k tra i due vertici u e v del grafo
G? È possibile trovare un cammino chiuso sul grafo per raggiungere ogni vertice senza passare mai
due volte per lo stesso spigolo? È possibile vincere una determinata partita a scacchi in sole tre mosse
partendo da una certa configurazione dei pezzi sulla scacchiera? Tutti problemi la cui soluzione è
effettivamente un semplice «sì o no», «esiste o non esiste», «è possibile o non è possibile». Non si
richiede infatti di costruire ed esibire uno zero della funzione f (x), un cammino sul grafo G, o la
sequenza di mosse che mi permette di vincere la partita a scacchi, ma soltanto di dire se uno zero,
un cammino o una sequenza di mosse vincenti esiste. Questo genere di problemi sono denominati
problemi di decisione o di esistenza. È bene precisare che non solo non è richiesto di esibire una
possibile configurazione delle variabili del problema a supporto della soluzione del problema stesso,
ma spesso non è neanche necessario costruire la soluzione per poter formulare una risposta per una
particolare istanza di un problema di decisione: è sufficiente articolare la risposta in modo tale che, al
di là di ogni dubbio, questa risulti inconfutabile. Ad esempio, se la funzione f (x) è continua nell’intervallo (a, b) e risulta f (a) > 0 e f (b) < 0 allora certamente esiste un x˜ ∈ (a, b) tale che f (x)
˜ = 0. Al
contrario se il grafo G non è connesso e i due vertici u e v appartengono a due componenti connesse
distinte, allora certamente un cammino p : u v non esiste in G.
Nei cosiddetti problemi di ricerca, invece, viene richiesto proprio di costruire una soluzione del
problema, ossia si richiede di esibire esplicitamente una configurazione delle variabili del problema
che diano luogo ad una soluzione. Rifacendoci agli esempi formulati in precedenza, si richiede di
identificare un particolare valore di x ∈ (a, b) tale che f (x) = 0, oppure di costruire uno specifico
cammino p : u v sul grafo G con meno di k spigoli, o un circuito su G che non passi mai due volte
per lo stesso spigolo, o la sequenza di mosse che mi permetta di vincere la partita a scacchi a partire
da una certa disposizione dei pezzi sulla scacchiera.
È chiaro che una soluzione può essere esibita solo se esiste: in altre parole risolvere un’istanza
di un problema nella sua formulazione come problema di ricerca, comporta implicitamente anche la
soluzione dello stesso problema nella sua formulazione come problema di decisione.
Se viene richiesto di calcolare ed esibire tutte le possibili soluzioni di una determinata istanza del
problema, allora siamo di fronte ad una formulazione del problema come problema di enumerazione.
Ad esempio si richiede di identificare tutti i valori x ∈ (a, b) tali che f (x) = 0; si richiede di costruire
tutti i possibili cammini sul grafo G da u a v composti con meno di k spigoli; ecc. Anche in questo
caso dovrebbe risultare chiaro che risolvere un problema di enumerazione significa, implicitamente,
risolvere anche un problema di ricerca, in cui si chiede di esibire una sola soluzione ammissibile per il
problema, ed anche risolvere il problema di decisione associato, in cui si chiedeva soltanto di stabilire
4
M. Liverani – IN440
Classe
Problemi di decisione o di esistenza
Problemi di ricerca
Problemi di enumerazione
Problemi di ottimizzazione
Descrizione
Si richiede di verificare se esiste o meno una certa
soluzione per l’istanza del problema
Si richiede di costruire ed esibire una soluzione per
l’istanza del problema
Si richiede di costruire ed esibire tutte le soluzioni per
l’istanza del problema
Si richiede di costruire le soluzioni ottimali in base ad
un determinato criterio (funzione obiettivo o di costo)
Tabella 1: Una classificazione dei problemi in base al tipo di soluzione richiesta
se una soluzione esiste o meno per quella determinata istanza del problema. Risolvere problemi di
enumerazione sarà quindi più laborioso che risolvere problemi di ricerca; risolvere problemi di ricerca
sarà più laborioso che risolvere problemi di esistenza.
Arriviamo così alla formulazione dei problemi di ottimizzazione: in questo caso non ci si accontenterà né di stabilire soltanto se una soluzione esiste, né di identificare una soluzione qualsiasi per
l’istanza del problema e neanche di identificare tutte le soluzioni del problema stesso, indistintamente;
si richiede, invece, di identificare una o tutte le soluzioni che risultano ottimali rispetto ad un qualche
criterio di valutazione delle soluzioni ammissibili per una specifica istanza del problema. Ad esempio
tra tutti gli zeri della funzione f (x) nell’intervallo (a, b) si chiederà di individuare quelli che rendono
minima la funzione ϕ(x) nell’intervallo stesso; tra tutti i cammini che sul grafo G collegano i vertici
u e v si chiederà di trovare quelli di lunghezza minima o che minimizzano il costo dato dalla somma
dei pesi attribuiti a ciascuno spigolo del grafo, e così via.
In un problema di ottimizzazione viene quindi fornita anche una funzione con cui valutare il costo
di ciascuna soluzione del problema: questa funzione, detta funzione obiettivo, costituisce un criterio
di scelta tra le possibili soluzioni del problema, ossia uno strumento, una bussola, con cui orientarsi
nell’insieme delle soluzioni ammissibili con l’intento di selezionare solo le soluzioni migliori, quelle
che “minimizzano” il costo o massimizzano il “profitto”.
Nel seguito ci occuperemo quasi esclusivamente di problemi di ottimizzazione; in particolare, come vedremo tra breve, ci occuperemo di una particolare classe di problemi che va sotto il nome di
problemi di ottimizzazione combinatoria. In generale per questi problemi l’insieme delle soluzioni
ammissibili entro cui cercare il sottoinsieme di soluzioni ottimali è un insieme discreto, di cardinalità
finita; tuttavia il numero di elementi di cui è costituito è di un ordine di grandezza molto superiore
alla dimensione dell’istanza del problema che si intende risolvere.
2 Formulazione generale per i problemi di ottimizzazione
In termini molto generali un’istanza di un problema di ottimizzazione è definita come una coppia
(A, f ), dove A è l’insieme delle soluzioni ammissibili ed f : A → R è la funzione obiettivo che si
deve ottimizzare (massimizzare o minimizzare). Il problema di ottimizzazione viene posto chiedendo
di trovare i valori x ∈ A tali che f (x) ≤ f (y) per ogni y ∈ A (problema in forma di minimizzazione).
Tali valori x costituiscono delle soluzioni ottime globali per il problema; nel caso in cui risulti invece
f (x) ≤ f (y) soltanto per ogni y appartenente ad un intorno di x, allora la soluzione x si dice soluzione
ottima locale.
Problemi di Ottimizzazione e Programmazione Matematica
y
y
S
z
5
z
x
x
S'
Figura 1: Un insieme convesso S ed un insieme S0 non convesso (concavo): S0 è tale che, fissata una coppia di punti x, y ∈ S0 , esistono altri punti z = λx + (1 − λ)y che, per alcuni valori di λ ∈ [0, 1], non
appartengono ad S0
L’insieme A delle soluzioni ammissibili è l’insieme entro il quale devono essere cercate le soluzioni
che rendono minima o massima la funzione obiettivo: la definizione di A è una caratteristica specifica
di ciascun problema e consente di escludere punti dello spazio su cui sono definite le variabili del
problema su cui non è utile o non ha senso cercare la soluzione. Non si deve necessariamente pensare
all’insieme A come ad un sottoinsieme o un intervallo della retta reale: spesso infatti l’insieme A è
un sottoinsieme di Rn o un insieme discreto definito in modo più articolato, come ad esempio un
sottografo con determinate caratteristiche.
Ad esempio il problema della ricerca del cammino più breve tra due vertici u e v di un grafo G, può
essere formulato come problema di ottimizzazione definendo l’insieme A delle soluzioni ammissibili
come la collezione di tutti i cammini semplici in G dal vertice u al vertice v; la funzione obiettivo
f : A → R viene definita come la funzione che associa ad ogni cammino p ∈ A la sua lunghezza. I
cammini ottimi sono quelli che rendono minima la funzione obiettivo, ossia quei cammini da u a v
con la lunghezza minima.
Nella formulazione di un problema di ottimizzazione un aspetto assai critico e rilevante è costituito
dalla corretta definizione dell’insieme delle soluzioni ammissibili; è necessario circoscrivere questo
sottoinsieme dello “spazio delle soluzioni”, senza escludere punti dello spazio che possano corrispondere ad una soluzione ammissibile e dunque potenzialmente ottima e al tempo stesso cercando di
ridurre al massimo l’insieme entro cui eseguire la ricerca delle soluzioni, per rendere più efficiente e meno oneroso in termini computazionali, il procedimento di calcolo adottato per individuare le
soluzioni ottime.
In generale quindi l’insieme A delle soluzioni ammissibili viene definito attraverso un insieme
di vincoli che limitano e circoscrivono l’insieme entro cui possono assumere valori le variabili del
problema.
In particolare tra i problemi di ottimizzazione rivestono notevole importanza i problemi di programmazione matematica. In questo genere di problema i vincoli che circoscrivono l’insieme A
delle soluzioni ammissibili sono costituiti da un certo numero, anche molto ampio, ma sempre finito, di equazioni e disequazioni; da qui il nome di questa classe di problemi. In generale quindi un
problema di programmazione matematica viene definito come segue:
minimizzare f (x)
per x tale che
gi (x) ≥ 0 i = 1, 2, . . . , m
h j (x) = 0
(1)
j = 1, 2, . . . , p
Le funzioni gi e h j costituiscono i vincoli del problema.
Dati due punti dello spazio x, y ∈ Rn una combinazione convessa di x e y è un punto z dello spazio
definito come z = λx + (1 − λ)y, con λ ∈ R e 0 ≤ λ ≤ 1. Un insieme S ⊆ Rn è convesso se contiene
qualsiasi combinazione convessa di ogni coppia di elementi distinti di S; in altri termini S è convesso
6
M. Liverani – IN440
f(y)
λf(x) + (1-λ)f(y)
f(x)
f(λx + (1-λ)y)
x
y
Figura 2: La funzione convessa calcolata nei punti di una combinazione convessa è minore o uguale alla
combinazione convessa dei valori della funzione negli estremi
se per ogni x, y ∈ S, x 6= y, risulta λx + (1 − λ)y ∈ S per ogni 0 ≤ λ ≤ 1. In Figura 1 è rappresentato un
insieme S convesso ed un insieme S0 non convesso in R2 .
Proposizione 1. Se S1 , S2 , . . . , Sk sono insiemi convessi, allora anche ∩ki=1 Si è un insieme convesso.
Dimostrazione. Se x, y ∈ ∩ki=1 Si allora x, y ∈ Si , per ogni i = 1, . . . , k. Per cui, visto che per ipotesi
ogni insieme Si è convesso, ogni combinazione convessa di x e y appartiene ad Si e dunque appartiene
anche a ∩ki=1 Si .
Sia S ⊆ Rn un insieme convesso. La funzione f : S → R è convessa in S se, per ogni x, y ∈ S, risulta
f (λx + (1 − λ)y) ≤ λ f (x) + (1 − λ) f (y)
(2)
Se vale la disuguaglianza opposta, la funzione si dice concava. Evidentemente se f (x) è convessa,
allora − f (x) è concava. In Figura 2 è rappresentato il grafico di una funzione convessa f definita a
valori su R. Un esempio di funzione convessa su R2 è dato dal paraboloide f (x1 , x2 ) = x12 + x22 .
Proposizione 2. Sia f (x) una funzione convessa sull’insieme convesso S. Allora, per ogni t ∈ R,
l’insieme St = {x ∈ S : f (x) ≤ t} è convesso.
Dimostrazione. Dobbiamo mostrare che ogni combinazione convessa di elementi di St è ancora in
St , ossia che la funzione f (x), calcolata in ogni combinazione convessa di elementi di St , è minore o
uguale a t. Siano x, y ∈ St per qualche t ∈ R. Per ipotesi (S è convesso) ogni combinazione convessa
di x e y, λx + (1 − λ)y è in S. Inoltre, siccome f è una funzione convessa, risulta
f (λx + (1 − λ)y) ≤ λ f (x) + (1 − λ) f (y)
≤ λt + (1 − λ)t
= t
Quindi effettivamente f (λx + (1 − λ)y) ≤ t e dunque λx + (1 − λ)y ∈ St . In conclusione, allora, St è
un insieme convesso.
Un problema di programmazione convessa è un problema di programmazione matematica espresso nella forma (1), in cui la funzione obiettivo f (x) sia convessa, le funzioni gi (x) siano concave e
le h j (x) siano lineari. Perché è importante distinguere tra i generici problemi di programmazione
matematica quelli che sono dotati di una funzione obiettivo convessa? La risposta è semplice: se la
funzione obiettivo è convessa allora ogni soluzione ottima locale è anche una soluzione ottima globale.
Problemi di Ottimizzazione e Programmazione Matematica
7
Proposizione 3. In un problema di programmazione convessa ogni soluzione ottima locale è anche
una soluzione ottima globale.
Dimostrazione. Supponiamo che per un determinato problema di programmazione convessa (A, f )
risulti f (x) ≤ f (y) per ogni y ∈ N(x) ⊆ A (indichiamo con N(x) un intorno del punto x) e che esista un
punto z 6∈ N(x), z ∈ A, tale che f (x) 6≤ f (z). In questo caso x sarebbe una soluzione ottima locale, ma
non globale. Dunque se così fosse, allora esisterebbe sicuramente un punto y ∈ N(x) tale che possa
essere espresso come combinazione convessa di x e z: y = λx + (1 − λ)z. In questo caso si avrebbe
f (z) < f (x) ≤ f (y) contraddicendo così la convessità di f .
3 Programmazione lineare
Le funzioni lineari sono un caso molto particolare di funzioni convesse. Se la funzione obiettivo ed
i vincoli del problema di ottimizzazioni sono funzioni lineari, allora il problema di programmazione
matematica che si ottiene è un problema di programmazione lineare (LP). È facile osservare che se
la funzione obiettivo è lineare, allora i suoi punti di minimo o di massimo si trovano sicuramente sulla
frontiera dell’insieme A delle soluzioni ammissibili.
Proprio su questo principio si basa il celebre metodo per la risoluzione di problemi di programmazione lineare proposto dal matematico americano George Dantzig nel 1947 e noto come algoritmo
del simplesso. L’algoritmo proposto da Dantzig opera su un simplesso, ossia un politopo in n dimensioni con n + 1 vertici (ad esempio, in uno spazio di dimensione n = 3, un simplesso è un tetraedro,
il poliedro con il minor numero di vertici). I vincoli del problema di ottimizzazione definiscono la
regione ammissibile, cioè l’insieme dei punti che soddisfano tutti i vincoli del problema. Nel caso
della programmazione lineare la regione ammissibile è un politopo (un poligono nel piano, un poliedro nello spazio), che può essere vuoto (nel caso in cui non esistono soluzioni al problema), limitato
o illimitato. La funzione obiettivo che deve essere minimizzata o massimizzata esprime il “costo”
di ogni soluzione tenendo conto dei vincoli (ossia calcolando la soluzione all’interno del poliedro).
L’algoritmo del simplesso è in grado di determinare di che tipo di poliedro si tratta e di individuare
la soluzione ottima, che è, sotto opportune ipotesi, un vertice del poliedro, nel caso in cui il problema
abbia una soluzione ottimale finita.
Tra i problemi di programmazione lineare è opportuno distinguere i problemi di programmazione
lineare intera (PLI): in questo caso alcune delle variabili del problema sono vincolate ad assumere
soltanto valori interi. Questo vincolo ulteriore riduce drasticamente il numero di punti presenti nella
regione ammissibile.
Il problema di programmazione lineare diventa un problema di ottimizzazione combinatoria se
tutte le variabili sono vincolate ad assumere soltanto valori interi.
Quando in un problema di programmazione lineare intera si eliminano i “vincoli di integrità”, ossia
i vincoli che impongono x ∈ Zn , si ottiene un problema di programmazione lineare detto rilassamento
continuo. Se, inoltre, accade che le soluzioni ottime del problema originario sono anche soluzioni
ottime del suo rilassamento continuo, si dice che il problema gode della proprietà di integralità. In
effetti la proprietà di integralità riguarda l’insieme ammissibile del problema più che il problema in
sè. Infatti la funzione obiettivo del rilassamento continuo ha lo stesso valore di quella del problema
originario sul suo insieme ammissibile e, inoltre, poiché è un problema di programmazione lineare,
ha sempre una soluzione ottima di vertice.
Per chiarire meglio questi concetti, vediamo di seguito alcuni problemi classici di ottimizzazione
combinatoria che possono essere formulati come problemi di Programmazione Lineare e di Programmazione Lineare Intera.
8
M. Liverani – IN440
3.1 Problema della bisaccia
Il problema della bisaccia binario (knapsack problem, in inglese) può essere posto come segue: abbiamo a disposizione un sacco, una bisaccia, in grado di sopportare un carico pari a P, con cui siamo
intenzionati a trasportare un certo numero di oggetti di peso e di valore diverso, selezionandoli da una
collezione di n elementi, in modo tale da massimizzare il valore complessivo degli oggetti selezionati,
ma senza rompere la bisaccia riempiendola con un peso eccessivo, superiore a P. Naturalmente ogni
oggetto ha un peso intero ben definito e non è possibile rompere gli oggetti in modo da costituire
oggetti più piccoli di peso inferiore: ciascun oggetto può essere preso per intero oppure deve essere
lasciato al suo posto, rinunciando a trasportarlo. Qual è il modo migliore con cui è possibile operare
la scelta degli oggetti da inserire nella bisaccia? Il problema può essere formulato come un problema
di programmazione lineare intera indicando con ci e pi rispettivamente il valore e il peso dell’i-esimo
oggetto. Con la variabile binaria xi ∈ {0, 1} indicheremo se l’oggetto i-esimo è stato scelto (xi = 1)
oppure se è stato scartato (xi = 0). In questo modo la soluzione ottima del problema è una sequenza
x = (x1 , x2 , . . . , xn ) ∈ {0, 1}n con cui possiamo identificare il contenuto della bisaccia; il problema di
ottimizzazione può essere posto nei seguenti termini:
n
massimizzare f (x) = ∑ ci xi
i=1
n
∑ pi xi ≤ P
(3)
i=1
xi ∈ {0, 1} i = 1, 2, . . . , n
Le variabili del problema, x1 , . . . , xn , non soltanto sono intere, ma addirittura sono vincolate ad
assumere valori binari: xi = 0 oppure xi = 1. In questi casi si parla di problema di programmazione
lineare intera “0-1”. Il problema è chiaramente di tipo combinatorio: le soluzioni ammissibili sono in
numero finito e possono essere anche prodotte in modo esaustivo, costruendo tutte le sequenze binarie
con n caratteri; tuttavia questo approccio conduce ad un algoritmo di complessità esponenziale nella
dimensione n dell’istanza del problema, dal momento che il numero di stringhe binarie con n caratteri
(o, come abbiamo visto in precedenza, l’insieme delle parti di un insieme di cardinalità n) sono 2n .
3.2 Problema dell’assegnazione di task
Un problema classico di pianificazione riguarda l’assegnazione di task ai processori di un calcolatore
parallelo, alle macchine di una rete di calcolatori che cooperano per la soluzione di uno stesso problema o ad un gruppo di persone. Supponiamo che n processori debbano svolgere m task. Ciascuno di
essi deve essere svolto esattamente da un processore ed inoltre, ciascun processore può svolgere al al
massimo un task. Indichiamo con ci j il costo dell’utilizzo del processore i per l’esecuzione del task j.
Il problema chiede di assegnare i task alle varie risorse (processori, calcolatori o persone, a seconda
del contesto applicativo) minimizzando il costo totale per la realizzazione di tutti gli m task previsti.
Per formulare questo problema in termini di programmazione lineare intera, introduciamo le variabili
binarie xi j , per i = 1, . . . , n e j = 1, . . . , m corrispondenti all’evento “i j” (esecuzione del task j da parte
della risorsa i) definite come segue xi j = 1 se il task j viene eseguito dalla risorsa i e xi j = 0 altrimenti.
Poiché esattamente una ed una sola risorsa deve essere assegnata al task j, avremo i seguenti vincoli:
n
∑ xi j = 1, per ogni j = 1, 2, . . . , m
i=1
Problemi di Ottimizzazione e Programmazione Matematica
9
Figura 3: George Bernard Dantzig (1914–2005)
Al tempo stesso, visto che per ipotesi ogni risorsa non può svolgere più di un task, si avranno anche i
seguenti vincoli:
m
∑ xi j = 1, per ogni i = 1, 2, . . . , n
j=1
È facile verificare che un vettore x ∈ {0, 1} che soddisfa tutti i vincoli appena descritti individua
un assegnamento ammissibile di risorse ai task. La funzione obiettivo, che ovviamente deve essere
minimizzata, è la seguente:
n
m
∑ ∑ ci j xi j
i=1 j=1
4 Il metodo del simplesso
Il metodo del simplesso è un algoritmo generale per la risoluzione di problemi di programmazione
lineare proposto nel 1947 dal matematico americano George Dantzig.1 La sua rilevanza, oltre che
storica, anche dal punto di vista applicativo, è fondata proprio sulla generalità dell’approccio, piuttosto che sulla sua efficienza: l’algoritmo del simplesso permette di risolvere qualsiasi problema di
ottimizzazione formulato come problema di programmazione lineare, anche se computazionalmente
è piuttosto pesante.
Possiamo riformulare un problema di programmazione lineare partendo dall’espressione (1), formalizzandolo come segue: data una matrice A ∈ Rm×n e i vettori colonna b ∈ Rm , c ∈ Rn , si chiede di
trovare un vettore colonna x ∈ Rn tale che Ax ≤ b e ct x sia minimo (problema in forma di minimizzazione). Naturalmente il vettore c rappresenta il “costo” associato a ciascuna variabile xi della soluzione
del problema (o il “profitto”, nel caso di problemi in forma di massimizzazione) e la funzione obiettivo è espressa quindi come f (x) = ct x. La matrice A è la matrice dei coefficienti delle disequazioni
lineari con cui viene definito l’insieme delle soluzioni ammissibili del problema. L’espressione (1)
1 Per
una trattazione più completa dell’argomento, che in queste pagine viene solo tratteggiato nelle sue linee più generali,
si rimanda ai testi citati tra i riferimenti bibliografici ed in particolare [3], [5] e [6].
10
M. Liverani – IN440
può così essere riformulata come segue:
minimizzare f (x) = ct x per x tale che
Ax ≤ b
A∈R
m×n
m
(4)
n
,b ∈ R ,c ∈ R
L’insieme di disequazioni lineari Ax ≤ b definisce un poliedro P come intersezione dei semispazi
definiti da ciascuna disequazione. È all’interno di P che sono da ricercare le soluzioni ottime del
problema, tra tutte le soluzioni ammissibili.
Esistono due casi degeneri per un problema di programmazione lineare: il caso in cui il problema
/ o il caso
non ammette nessuna soluzione, quando cioè i vincoli producono un poliedro nullo, P = 0,
in cui il problema ammette infinite soluzioni, quando il poliedro P è illimitato. Quando il problema
di programmazione lineare è ben posto e dunque P non è né nullo, né illimitato, diremo che P è un
politopo. Un simplesso, il termine che dà il nome all’algoritmo di Dantzig, è un politopo di n + 1
vertici in n dimensioni: un segmento in dimensione 1, un triangolo in dimensione 2 e un tetraedro in
dimensione 3.
Cerchiamo di formalizzare meglio questi concetti. Innanzi tutto chiamiamo vertice di un poliedro
P un punto x ∈ P tale che non esistono altri due punti x0 , x00 ∈ P, con x 6= x0 , x00 e x ∈ [x0 , x00 ].
Non tutti i poliedri ottenuti come intersezioni di semispazi definiti mediante disequazioni lineari
hanno almeno un vertice. Ad esempio se consideriamo un unico semispazio di R2 , questo non ha
vertici. Dunque il poliedro P = {x ∈ Rn : Ax ≥ b} non ha vertici se la matrice A ha un numero di righe
minore di n: in tal caso non è possibile trovare n vincoli linearmente indipendenti che circoscrivano
un poliedro chiuso.
Un poliedro P non ha vertici se contiene rette: diremo che un poliedro P contiene una retta se esiste
un punto x˜ ∈ P e un vettore non nullo d ∈ Rn tale che x˜ + λd ∈ P per ogni λ ∈ R.
Possiamo infine enunciare il seguente Teorema fondamentale della Programmazione Lineare:
Teorema 1. Si consideri il problema di Programmazione Lineare
min ct x
Ax = b
Supponiamo che il poliedro P = {x ∈ Rn tale che Ax = b} non contenga rette. Allora una e una sola
delle seguenti tre affermazioni è vera:
1. il problema è inammissibile, ovvero il poliedro P è vuoto;
2. il problema è illimitato inferiormente;
3. il problema ammette soluzioni ottime e almeno una di queste è un vertice del poliedro P.
L’algoritmo del simplesso non consiste altro che in una “visita intelligente” dei vertici di P; il
teorema fondamentale della programmazione lineare garantisce infatti che la soluzione ottimale del
problema, se esiste, è situata in uno di questi vertici. Muovendosi sugli spigoli del poliedro, da un
vertice ad un altro, il metodo del simplesso cerca di individuare una soluzione ottima, che massimizzi
o minimizzi la funzione obiettivo.
Consideriamo la matrice A ∈ Rm×n ; se I è un insieme di indici di riga di A, indichiamo con AI la
sottomarine di A composta con le sole righe in I ; analogamente se b è un vettore, indichiamo con bI
il sottovettore composto dalle sole componenti di indice in I . Indichiamo con ai la riga A{i} e con
Problemi di Ottimizzazione e Programmazione Matematica
11
Algoritmo 1 S IMPLESSO(A, b, c)
Input: Una matrice di coefficienti A ∈ Rm×n , il vettore dei termini noti b ∈ Rm , il vettore dei costi
ct ∈ Rn , un vertice x ∈ P = {x ∈ Rn : Ax ≤ b}
Output: Un vertice x∗ ∈ P tale che ct x∗ = maxx∈P {ct x}, oppure un vettore w ∈ Rn con Aw ≤ 0 e
ct w > 0 (il poliedro P è illimitato)
1: Scegli un insieme di n indici di riga I tali che AI è non singolare e AI x = bI
2: Calcola c (AI )−1 e aggiungi gli zeri necessari per ottenere un vettore y tale che c = yA e tutti gli
elementi di y fuori da I siano nulli
3: se y ≥ 0 allora
4:
return x e y; stop
5: fine-condizione
6: Sia i il minimo indice per cui risulta yi < 0
7: Sia w la colonna di −(AI )−1 con indice i, tale che AI \{i} w = 0 e ai w = −1
8: se Aw ≤ 0 allora
9:
return w; stop
10: fine-condizione
n
o
b j −a j x
11: Sia λ := min j=1,...,m
a j w : a j w > 0 e sia j il più piccolo indice di riga con cui si ottiene
questo minimo
12: Sia I := (I \ {i}) ∪ { j} e x := x + λw
13: Vai al passo 2
bi = b{i} . Utilizzando queste notazioni formalizziamo il Metodo del Simplesso con lo pseudo codice
dell’Algoritmo 1.
È possibile dimostrare che l’Algoritmo del Simplesso termina al massimo dopo mn iterazioni del
ciclo 2–13. Se l’algoritmo restituisce x e y al passo 4, allora x e y sono i vettori che rappresentano le
soluzioni ottime per i seguenti problemi di programmazione lineare, con c x = y b:
max{c x : Ax ≤ b}
t
t
min{y b : y A = c , y ≥ 0}
(5)
(6)
Infine, se l’algoritmo restituisce il vettore w al passo 9, allora cw > 0 e il problema di programmazione
lineare (5) è illimitato.
Il problema di programmazione lineare espresso da (5) viene chiamato problema primale, mentre
il problema di programmazione lineare (6), associato al precedente, viene chiamato problema duale.
5 Programmazione lineare per problemi di ottimizzazione su grafi
Per concludere questa breve panoramica sui problemi di programmazione matematica e su quelli di
programmazione lineare in particolare, vediamo alcune applicazioni della programmazione lineare
alla teoria dei grafi. Una volta impostato il problema in termini di programmazione lineare è possibile
calcolarne una soluzione con l’algoritmo del simplesso, che garantisce l’identificazione di una soluzione ottima, al costo di una complessità computazionale più elevata di un algoritmo specificamente
progettato per risolvere un determinato problema (es.: il problema del cammino minimo tra due vertici di un grafo). Di seguito consideriamo alcuni problemi classici di ottimizzazione combinatoria con
l’obiettivo di offrirne una formulazione in termini di programmazione lineare intera:
12
M. Liverani – IN440
1. minimo ricoprimento di vertici per gli spigoli di un grafo G;
2. massima clique di un grafo G;
3. cammino di costo minimo dal vertice s al vertice t su un grafo G;
4. albero ricoprente di costo minimo di un grafo G.
I problemi saranno formulati come problemi di programmazione lineare intera “0 − 1”, ossia con
variabili xi che assumono valori nell’insieme {0, 1}; infatti, nel caso di problemi di ottimizzazione
combinatoria, la soluzione è data sempre da una “scelta” degli elementi che costituiscono l’istanza
del problema: una scelta di alcuni vertici di un grafo, una scelta di alcuni degli spigoli di un grafo,
in generale una scelta di alcuni elementi di un insieme discreto, per cui è comodo rappresentare
con la variabile xi il fatto di aver scelto (xi = 1) oppure di aver scartato (xi = 0) l’elemento i-esimo
dell’insieme.
5.1 Minimo insieme di copertura dei vertici
Dato un grafo G = (V, E) un ricoprimento di vertici è un sottoinsieme C ⊆ V tale che ogni spigolo di
G sia incidente almeno a un vertice di C. Il problema di ottimizzazione combinatoria che si intende
risolvere chiede di calcolare un insieme C di copertura dei vertici di G, di cardinalità minima.
Per modellizzare il problema introduciamo le seguenti variabili:
1 se vi è nel ricoprimento C
∀ vi ∈ V, xi =
0 altrimenti
Si tratta dunque di minimizzare il numero di vertici nel ricoprimento, ovvero la funzione: ∑vi ∈V xi .
La condizione che garantisce che C sia un ricoprimento è che per ogni spigolo (vi , v j ) ∈ E(G) almeno
uno tra vi e v j sia nel ricoprimento C. Formalizzando si ha dunque il seguente vincolo: ∀(vi , v j ) ∈
E(G), xi + x j ≥ 1.
Riassumendo, il problema del minimo ricoprimento può essere formalizzato nel modo seguente
come problema di programmazione lineare intera:

 min ∑vi ∈V xi
∀ (vi , v j ) ∈ E, xi + x j ≥ 1

∀ vi ∈ V xi ∈ {0, 1}
5.2 Clique massima
Dato un grafo G = (V, E) una clique di G è un sottoinsieme C ⊆ V tale che ogni coppia di vertici in C
sia collegata da uno spigolo in G (C induce un sottografo completo su G). Dato un grafo G si vuole
quindi individuare una clique di dimensione massima su G.
Per modellizzare il problema in termini di programmazione lineare introduciamo le seguenti variabili:
1 se vi è nella clique
∀ vi ∈ V, xi =
0 altrimenti
Si tratta dunque di massimizzare il numero di vertici nella clique, ovvero la funzione: ∑vi ∈V xi . La
condizione che garantisce che C sia una clique è che per ogni coppia (vi , v j ) che non sia uno spigolo di
G almeno uno tra vi e v j non sia in C. In termini formali si ha dunque il seguente vincolo: ∀ (vi , v j ) ∈
/
E(G), xi + x j ≤ 1.
13
Problemi di Ottimizzazione e Programmazione Matematica
Riassumendo, il problema della massima clique può essere formulato come problema di programmazione lineare intera nel modo seguente:

 max ∑vi ∈V xi
∀ (vi , v j ) ∈
/ E, xi + x j ≤ 1

∀ vi ∈ V, xi ∈ {0, 1}
5.3 Cammino di costo minimo
Sia G = (V, E) un grafo con dei pesi non negativi assegnati agli spigoli: per ogni (vi , v j ) ∈ E(G)
di j ≥ 0 sia il peso corrispondente. Dati due vertici s,t ∈ V , si vuole trovare un cammino p da s a t per
cui la somma dei pesi assegnati agli spigoli sia minima.
Per formulare il problema in termini di programmazione lineare, si introducono le seguenti variabili,
questa volta una per ogni spigolo:
∀ (vi , v j ) ∈ E(G) xi j =
1 se (vi , v j ) è nel cammino p : s
0 altrimenti
t
Per trovare una soluzione del problema dobbiamo quindi minimizzare la seguente funzione obiettivo: ∑(vi ,v j )∈E di j xi j .
Affinché un insieme di spigoli del grafo G costituisca un cammino da s a t bisogna assicurarsi
che esattamente uno spigolo del cammino esca da s e nessuno entri in esso, esattamente uno spigolo
del cammino entri in t e nessuno esca da esso e che per tutti gli altri vertici il numero di spigoli del
cammino uscenti sia pari a quello di spigoli entranti. Formalizzando si ottengono i seguenti vincoli:

 −1, vh = s
∑ xh j − ∑ xi j =  1, vh = t
(vi ,vh )∈E
(v j ,vi )∈E
0,
∀ vh ∈ V \ {s,t}
Riassumendo, il problema del cammino minimo può essere formalizzato nel modo seguente come
un problema di programmazione lineare intera:


∑(vi ,v j )∈E di j xi j




 ∑(vi ,vh )∈E xh j − ∑(v j ,vi )∈E xi j = −1, se vh = s
∑(vi ,vh )∈E xh j − ∑(v j ,vi )∈E xi j = 1, se vh = t



 ∑(vi ,vh )∈E xh j − ∑(v j ,vi )∈E xi j = 0, se vh ∈ V \ {s,t}

 ∀ (v , v ) ∈ E, x ∈ {0, 1}
i j
ij
5.4 Albero ricoprente di costo minimo
Un albero ricoprente (spanning tree) di un grafo G = (V, E) è un albero T = (V, E 0 ), con E 0 ⊆ E, ossia
un albero con gli stessi vertici di G e n − 1 spigoli di G, affinché T sia un grafo connesso e aciclico
(un albero). Se associamo un peso non negativo w(u, v) ad ogni spigolo (u, v) ∈ E(G), è possibile
definire il problema di ottimizzazione combinatoria che chiede di costruire l’albero ricoprente di G di
peso minimo, ossia l’albero T ∗ tale che
∑
(u,v)∈E(T ∗ )
w(u, v) =
min
T che ricopre G
∑
(u,v)∈E(T )
w(u, v)
14
M. Liverani – IN440
x3
1
x’ = (1, 0, 1)
v1
3)=
e
w(
e
3 =
(v
10
1,v
3)
)
,v2
v1
=(
20
e2
)=
e
w( 2
x’’’ = (0, 1, 1)
1
x1
1
e2 = (v2, v3)
v3
w(e2) = 30
x2
v2
(a)
x’’ = (1, 1, 0)
(b)
Figura 4: Un grafo pesato G = (V, E) e il politopo con la regione delle soluzioni ammissibili per il problema
MST.
Anche in questo caso, per formulare il problema in termini di programmazione lineare, si introducono le seguenti variabili associate agli spigoli del grafo:
∀ ei ∈ E(G) xi =
1 se ei ∈ E(T )
0 altrimenti
In questo modo possiamo formulare il problema del minimo albero ricoprente (MST – minimum
spanning tree) come segue:
min
per x tale che
f (x) = ∑m
i=1 w(ei )xi
x1 + x2 + · · · + xm = n − 1
xi ≥ 0 per i = 1, 2, . . . , m
xi ≤ 1 per i = 1, 2, . . . , m
Per aiutare a visualizzare il significato geometrico di questa formulazione, consideriamo il grafo G = (V, E) definito ponendo V = {v1 , v2 , v3 }, E = {e1 = (v1 , v2 ), e2 = (v2 , v3 ), e3 = (v1 , v3 )};
supponiamo anche che w(e1 ) = 20, w(e2 ) = 30 e w(e3 ) = 10. Il grafo è rappresentato in Figura
4(a).
Effettuando un rilassamento continuo del problema, possiamo rappresentare l’insieme delle soluzioni ammissibili con il poliedro (triangolo) evidenziato in Figura 4(b), ossia il poliedro a 2 dimensioni collocato nello spazio a 3 dimensioni, con vertici nei punti x0 = (1, 0, 1), x00 = (1, 1, 0) e
x000 = (0, 1, 1). Per il vincolo di integrità delle variabili del problema (dobbiamo scegliere uno spigolo o non sceglierlo per nulla, non possiamo prenderne solo un pezzo!), le soluzioni del problema si
trovano proprio nei vertici del politopo costituito dal triangolo. In particolare, come si può osservare
facilmente senza la necessità di applicare l’Algoritmo del Simplesso, la soluzione ottima è costituita
dal punto x00 = (1, 0, 1): questo punto rappresenta l’albero ricoprente costruito scegliendo gli spigoli
e1 ed e3 , con peso complessivo f (x00 ) = w(e1 ) + w(e3 ) = 20 + 10 = 30.
Problemi di Ottimizzazione e Programmazione Matematica
15
Riferimenti bibliografici
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli
algoritmi e strutture dati, seconda edizione, McGraw-Hill, 2005.
[2] Ottavio D’Antona, Introduzione alla Matematica Discreta, Apogeo, 1999.
[3] Bernhard Korte, Jens Vygen, Ottimizzazione Combinatoria, Springer, 2011.
[4] Marco Liverani, Qual è il problema? Metodi, strategie risolutive, algoritmi, Mimesis, 2005.
[5] Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization – Algorithms and
Complexity, Dover Publications Inc., 1998.
[6] Antonio Sassano, Modelli e algoritmi della Ricerca Operativa, Franco Angeli, 1999.
[7] Paolo Serafini, Ottimizzazione, Zanichelli, 2000.

Download Report