Ricerca Operativa

(1)

Ricerca Operativa

Massimo Pappalardo Dipartimento di Informatica Largo B. Pontecorvo 3, Pisa [email protected]

Laurea Magistrale in Management e Controllo dei Sistemi Logistici Universit`a di Pisa

A.A. 2018/’19

(2)

Riferimenti

Massimo Pappalardo Dipartimento di Informatica Largo B. Pontecorvo 3- Pisa

Edificio C - 2^◦ piano - studio 289DE tel. 050 2212750

e-mail: [email protected] ricevimento: Gioved`ı ore 9 nel mio studio

M. Pappalardo Corso di Ricerca Operativa applicata alla logistica - Laurea Magistrale in Management e Controllo dei Sistemi LogisticiUniversit`a di Pisa 2 / 209

(3)

Materiale per il corso

Pagina web del corso

http://pages.di.unipi.it/mpappalardo/

Testi

• M.Pappalardo, M.Passacantando, Ricerca Operativa, Edizioni Plus, 2010.

• F.S.Hillier, G.J.Lieberman, Ricerca Operativa, McGraw Hill, 2010.

• G.Ghiani, R.Musmanno, Modelli e metodi per l’organizzazione dei sistemi logistici, Pitagora 2000.

Esame

Prova scritta e prova orale.

(4)

Conoscenze richieste

• Operazioni tra matrici: somma, moltiplicazione e prodotto per uno scalare.

• Matrice Inversa.

• Sistemi lineari.

(5)

Obiettivo e argomenti del corso

Obiettivo

Fornire conoscenze e metodi per la formulazione e risoluzione di problemi di ottimizzazione.

Argomenti

• Modelli matematici canonici di ottimizzazione per processi decisionali.

• Modelli matematici per la risoluzione di alcuni problemi di ottimizzazione:

produzione, assegnamento, trasporto ottimo, localizzazione, caricamento,

”bin packing”, commesso viaggiatore.

• Elementi di teoria e metodi di Programmazione Matematica: Lineare (PL) e Lineare Intera (PLI).

• MATLAB per la risoluzione di problemi di ottimizzazione.

(6)

Il processo decisionale

Problema raccolta dati Modello

variabili vincoli

funzione obiettivo

Teoria

propriet`a modello

esistenza/unicit`a soluzione

Metodi ed algoritmi esatti/euristici

(7)

Modelli matematici di problemi decisionali

• Raccolta dati.

• Variabili decisionali, funzione obiettivo, vincoli.

• Costruzione del modello matematico.

• Teoria, metodi e algoritmi per la risoluzione del modello matematico.

• Software per la soluzione.

• Controllo della soluzione.

(8)

Un esempio: il problema del contadino

Un contadino ha 12 ettari di terra per coltivare pomodori e/o patate.

Ha anche 70 kg di semi di pomodoro, 18 t di tuberi e 160 t di letame.

Il guadagno per ettaro `e 3000 euro per i pomodori e 5000 euro per le patate.

I pomodori necessitano di 7 kg di semi e 10 t di letame per ettaro, mente le patate richiedono 3 t di tuberi e 20 t di letame per ettaro.

Per massimizzare il guadagno come dividere la terra tra pomodori e patate?

(9)

Raccolta dati

Dati

• 12 ettari di terra.

• 160 t di letame, 70 Kg di semi, 18 t di tuberi.

•

profitto/ett. semi/ett. letame/ett. tuberi/ett.

pomodori 3000 7 kg 10 t

patate 5000 20 t 3 t

• Come decidere?

Quanti ettari devono essere assegnati ai pomodori e quanti alle patate.

• Quale ´e il nostroobiettivo? Massimizzare il guadagno.

• Quali sono lerichiesteper avere una soluzione ammissibile?

Limiti sulle risorse disponibili.

(10)

Modello

Cosa si deve decidere? → variabili decisionali

• xT = ettari di pomodori

• xP = ettari di patate

Massimizzare il guadagno → funzione obiettivo Guadagno = 3000xT+ 5000xP

Massimizzare il guadagno → max 3xT+ 5xP

(11)

Modello

Richieste e disponibilit´a di risorse → vincoli

• Disponibilit´a di terreno: xT + xP ≤ 12

• Semi di pomodoro disponibili: 7xT ≤ 70 → xT ≤ 10

• Tuberi di patate disponibili: 3xP ≤ 18 → x_p≤ 6

• Letame disponibile: 10xT+ 20xP ≤ 160 → xT+ 2xP ≤ 16

• Variabili non negative: xT ≥ 0, xP ≥ 0

(12)

Forma matriciale

max 3xT+ 5xP

xT+ xP ≤ 12 xT ≤ 10 xP ≤ 6 xT+ 2xP ≤ 16

−xT ≤ 0

−xP ≤ 0

max c^Tx Ax ≤ b

A =







1 1

1 0

0 1

1 2

−1 0

0 −1





 b =





 12 10 6 16

0 0





 c =

3 5

m = numero di vincoli n = numero di variabili A matrice m × n b vettore m componenti c vettore n componenti

(13)

Rappresentazione grafica della regione ammissibile

max 3xT+ 5xP

xT+ xP ≤ 12 xT ≤ 10 xP ≤ 6 xT+ 2xP ≤ 16

−xT ≤ 0

−xP ≤ 0

-1 0 1 2 3 4 5 6 7 8 9 10 11

-1 0 1 2 3 4 5 6 7 8

x_T x_P

xT+ xP= 12 xT= 10 xP= 6

xT+ 2xP= 16

-1 0 1 2 3 4 5 6 7 8 9 10 11

-1 0 1 2 3 4 5 6 7

xT+ 2xP= 16

(14)

Soluzione grafica della PL per n=2

Le linee di isocosto o isoguadagno sono

L(v ) = {x ∈Rⁿ: c^Tx = v } dove v ∈R ´e un numero reale.

max 3xT+ 5xP

xT+ xP ≤ 12 xT ≤ 10 xP ≤ 6 xT+ 2xP ≤ 16

−x_T ≤ 0

−x_P ≤ 0

-1 0 1 2 3 4 5 6 7 8 9 10 11

-1 0 1 2 3 4 5 6 7 8

x_T x_P

-1 0 1 2 3 4 5 6 7 8 9 10 11

-1 0 1 2 3 4 5 6 7

3xT+ 5xP= 0 3xT+ 5xP= 30

3xT+ 5xP= 42

c

3xT+ 5xP= 44

Soluzione ottima xT = 8, xP = 4

(15)

PL e la sua forma standard

Definizione

Un problema di Programmazione Lineare (PL) consiste nel trovare il massimo o il minimo di una funzione lineare soggetta ad un insieme finito di vincoli lineari di disuguaglianza o di uguaglianza:











max(min) c^Tx A1x ≤ b1

A2x ≥ b2

A3x = b3

Definizione

Un problema nella forma

max c^Tx Ax ≤ b

`e detto problema di PL in formato primale standard.

(16)

PL e formato primale standard

Osservazione

Ogni problema di PL pu`o essere equivalentemente scritto in formato primale standard.

Dimostrazione. min c^Tx = − max (−c^Tx) a^Tx ≥ b `e equivalente a −a^Tx ≤ −b a^Tx = b `e equivalente a

a^Tx ≤ b

−a^Tx ≤ −b . Definizione

Un poliedro P `e l’intersezione di un numero finito di semispazi chiusi o, equivalentemente, l’insieme {x ∈Rⁿ: Ax ≤ b} .

(17)

Vertici dei poliedri

Definizione

Un punto x di un poliedro P `e unverticese non esistono due punti di P differenti da x tali che x appartenga al segmento generato da essi.

Esempi.

Vertici di P1= {x ∈R²: 1 ≤ x1≤ 4, 1 ≤ x2≤ 3} sono (1, 1), (1, 3), (4, 1) e (4, 3).

Vertici di P2= {x ∈R²: x1≥ 1, x2≥ 1, x1+ x2≥ 3} sono (1, 2) e (2, 1).

P3= {x ∈R²: 0 ≤ x2≤ 1} non ha vertici.

(18)

Teorema fondamentale della PL

Consideriamo un problema di PL in forma primale standard:

max c^Tx

x ∈ P = {x ∈Rⁿ: A x ≤ b} (P)

Teorema fondamentale della PL

Se P `e limitato e non vuoto, allora un vertice di P `e ottimo.

Esempio. Consideriamo il problema











max −2x1− 3x2

x1≥ 1 x2≥ 1 x1+ x2≥ 3 La soluzione ottima `e (2, 1).

(19)

Scarti complementari

Come riconoscere una soluzione ottima?

Teorema

Una soluzione ¯x `e ottima se e solo se esiste ¯y ∈R^m+ tale che

¯y^TA = c^T

¯

y^T(b − A¯x) = 0 (scarti complementari)

Esempio. Consideriamo il problema di PL











max 3x1+ 4x2

2x1+ x2≤ 3 x1+ 2x2≤ 3

−x1≤ 0

−x2≤ 0

¯

x= (1, 1) `e ottima perch`e ¯y = (2/3, 5/3, 0, 0) risolve il sistema.

¯

x= (0, 0) non `e ottima perch`e il sistema non ha soluzione.

(20)

Caratterizzazione algebrica dei vertici

Sappiamo che se P 6= ∅ e limitato, allora un vertice di P `e ottimo.

Cometrovare un vertice ottimo? Sevono propriet`aalgebrichedei vertici Consideriamo un problema

max c^Tx Ax ≤ b

Definizione

Unabase`e un insieme B di n indici di riga tali che det(AB) 6= 0.

A = A_B AN

b = b_B bN

Data una base B, il vettore ¯x = A⁻¹_B bB `e dettosoluzione di base primale.

¯

x `eammissibilese AN¯x ≤ bN.

(21)

Esempio. Consideriamo











max 2x1+ x2

x1≤ 2 x1+ x2≤ 3

−x1≤ 0

−x2≤ 0

A =







1 0

1 1

−1 0

0 −1





 b =





 2 3 0 0







B = {1, 2} `e una base perch`e AB =1 0 1 1

`e invertibile.

La soluzione corrispondente `e ¯x = A⁻¹_B bB = 1 0

−1 1

2 3

=2 1

.

¯

x `e ammissibile perch`e AN¯x =−1 0

0 −1

2 1

=−2

−1

≤0 0

= bN.

(22)

B = {1, 3} non `e una base perch`e AB = 1 0

−1 0

non `e invertibile.

B = {2, 4} `e una base e la corrispondente soluzione di base `e inammissibile:

AB =1 1 0 −1

, ¯x =3 0

, AN¯x = 3

−3

2 0

= bN.

(23)

Soluzioni ottime

Perch`e le soluzioni di base sono importanti?

Teorema

¯

x `e un vertice di P se e solo se ¯x `e una soluzione di base ammissibile.

Esempio. Consideriamo il precedente problema











max 2x1+ x2

x1≤ 2 x1+ x2≤ 3

−x1≤ 0

−x2≤ 0

A =







1 0

1 1

−1 0

0 −1





 b =





 2 3 0 0







c =2 1

¯

x = (2, 1) `e una soluzione di base ammissibile corrispondente alla base B = {1, 2}.

(24)

Dualit`a

Al problema primale in forma standard

max c^Tx

x ∈ P = {x ∈Rⁿ: A x ≤ b} (P)

associamo il seguente problema di PL:

min y^Tb

y ∈ D = {y ∈R^m: y^TA = c^T, y ≥ 0} (D)

che sar`a chiamato problema duale in forma standard.

Il valore ottimo del problema (D) verr`a indicato con v (D).

Poich´e ogni problema di PL si pu`o trasformare in un problema primale standard di tipo (P), allora ogni problema di PL ha un suo problema duale.

(25)

Duale standard

Osservazione

Ogni problema di PL si pu`o trasformare in un duale standard.

Dimostrazione. Una disuguaglianza

A^T_ix ≤ bi

si pu`o trasformare nell’uguaglianza

A^T_i x + si= bi,

aggiungendo i vincoli si≥ 0, dove le si sono dette variabili di scarto.

(26)

Duale standard

Ogni numero reale è la differenza di due numeri non negativi quindi si può sempre introdurre il vincolo di positività sulle variabili spezzando ogni variabile non vincolata in segno nella differenza di due variabili vincolate in segno e porre

x = x⁺− x⁻ con x⁺≥ 0, e x⁻≥ 0.

Teorema

(Dualit`a forte) Se i poliedri P e D sono non vuoti, allora

−∞ < v (P) = v (D) < +∞

(27)

Soluzioni di base duali

Data una base B, definiamo:

Soluzione di base duale: y =¯ ¯yB

¯ yN

dove ¯y_B^T= c^TA⁻¹_B , y¯N = 0.

Una soluzione di base duale pu`o essere:

¯ y

ammissibile per ogni i ∈ B si ha ¯yi≥ 0 non ammissibile esiste i ∈ B tale che ¯yi < 0 degenere esiste i ∈ B tale che ¯yi = 0 non degenere per ogni i ∈ B si ha ¯yi6= 0

(28)

Ottimalit´a

Teorema

Due soluzioni di base complementari ¯x e ¯y sono in scarti complementari.

Dimostrazione:

¯

y^T(b − A ¯x) = (¯y_B^T, ¯y_N^T)b_B− ABx¯ bN− AN¯x

= (c^TA⁻¹_B , 0)bB− ABA⁻¹_B bB

bN− ANA⁻¹_B bB

= (c^TA⁻¹_B , 0)

0

bN− A_NA⁻¹_B bB

= 0

(29)

Dualit`a

Dal teorema precedente e dal teorema degli scarti complementari possiamo dedurre le seguenti condizioni sufficienti di ottimalit`a.

Teorema(Condizioni sufficienti di ottimalit`a per soluzioni di base) Date due soluzioni di base complementari ¯x e ¯y , si ha:





¯

x `e ammissibile per (P) e

¯

y `e ammissibile (D)



 =⇒





¯

x `e ottima per (P) e

¯

y `e ottima (D)





(30)

Algoritmo del simplesso

1 Trova una base B tale che la corrispondente soluzione di base ¯x := A⁻¹_B bB

sia ammissibile.

2 Calcola

¯ y := ¯yB

¯ yN

, with y¯_B^T = c^TA⁻¹_B , y¯N = 0.

3 se ¯yB ≥ 0 allora STOP (¯x `e ottima) altrimenti troval’indice uscente h := min{i ∈ B : ¯yi < 0}

poniamo W := −A⁻¹_B , denotiamo W^hla h–ma colonna di W .

4 se AiW^h≤ 0 per tutti gli indici i ∈ N allora STOP (ottimo di (P) `e +∞) altrimenti calcola ϑ := min bi− Ai¯x

AiW^h : i ∈ N, AiW^h> 0

, troval’indice entrante

k := min

i ∈ N : AiW^h> 0, bi− Ai¯x AiW^h = ϑ

, aggiorna la base B := B \ {h} ∪ {k}, vai al passo 2.

(31)

Teorema

L’algoritmo del simplesso si ferma dopo un numero finito di iterazioni.

(32)

Esempio. Partendo dalla base B = {3, 4}, risolviamo il problema:











max 2x1+ x2

x1≤ 2 x1+ x2≤ 3

−x1≤ 0

−x2≤ 0

A=







1 0

1 1

−1 0

0 −1





 b=





 2 3 0 0







c=2 1

Iterazione 1. AB =−1 0

0 −1

= A⁻¹_B , ¯x =0 0

`e ammissibile.

¯

y_B^T= (2, 1)−1 0

0 −1

= (−2, −1), h = 3, W³=1 0

. A1W³= 1, A2W³= 1, ϑ = min{2/1, 3/1} = 2, k = 1.

Iterazione 2. B = {1, 4}, AB =1 0 0 −1

= A⁻_B¹, ¯x=2 0

,

¯

y_B^T= (2, 1)1 0 0 −1

= (2, −1), h = 4, W⁴=0 1

. A2W⁴= 1, A3W⁴= 0, k = 2.

Iterazione 3. B = {1, 2}, AB =1 0 1 1

, ¯x =2 1

, ¯yB^T= (1, 1) ≥ 0 stop ¯x `e ottima.

(33)

Simplesso duale

Descriviamo l’algoritmo del simplesso duale per risolvere un problema in forma

duale standard: 





min y^Tb y^TA = c^T y ≥ 0

(D)

L’algoritmo `e analogo al simplesso primale con la differenza che ad ogni passo si mantiene ammissibile la soluzione di base duale e si controlla l’ammissibilit`a di quella primale.

Se la soluzione di base primale `e ammissibile, allora abbiamo trovato una coppia primale/duale di soluzioni ottime.

Il cambio di base `e definito in modo che, se la nuova soluzione di base duale `e diversa da quella vecchia, il valore della funzione obiettivo diminuisce.

(34)

ALGORITMO DEL SIMPLESSO DUALE

1 Trova una base B che genera una soluzione di base duale ammissibile.

2 Calcola la soluzione di base primale ¯x = A⁻¹_B bB e la soluzione di base duale

¯

y = (¯yB, ¯yN), con y¯_B^T= c^TA⁻¹_B , y¯N = 0.

3 Se bN− A_N¯x ≥ 0 allora STOP (¯y `e ottima per (D) e ¯x `e ottima per (P)).

altrimenti calcola l’indice entrante

k = min{i ∈ N : bi− Aix < 0}¯ (regola anticiclo di Bland) poni W = −A⁻¹_B ed indica con Wⁱ la i–esima colonna di W .

4 Se AkWⁱ ≥ 0 per ogni i ∈ B allora STOP ((D) ha valore −∞).

altrimenti calcola ϑ = min

¯yi

−AkWⁱ : i ∈ B, AkWⁱ < 0

, calcola l’indice uscente

h = min

i ∈ B : AkWⁱ < 0, y¯i

−AkWⁱ = ϑ

(regola anticiclo di Bland), aggiorna la base B := B \ {h} ∪ {k} e torna al passo 2.

(35)

Algoritmo del simplesso duale

Teorema

Il simplesso duale risolve (D) in un numero finito di iterazioni.

Illustriamo ora una risoluzione di un problema di PL applicando il simplesso duale.

Esempio. Risolviamo il seguente problema











min 13 y3+ 9 y4+ 7y5

−y1+ y3+ y4+ y5= 3

−y2+ 2 y3+ y4= −4 y ≥ 0

(1)

con il simplesso duale partendo dalla base B = {2, 3}.

(36)

Iterazione 1.

La matrice di base e la sua inversa sono AB =0 −1

1 2

A⁻¹_B = 2 1

−1 0

,

la soluzione di base duale `e

¯

y_B^T= (3, −4)A⁻¹_B = (10, 3), y = (0, 10, 3, 0, 0)¯ ^T, e quella primale è ¯x = (13, 0)^Tche non è ammissibile perché

b1− A1¯x = 13, b4− A4¯x = −4, b5− A5¯x = −6, quindi l’indice che entra in base `e 4. Calcoliamo i prodotti

A4W²= −1, A4W³= −1, e i rapporti:

¯ y2

−A4W² = 10, ¯y3

−A4W³ = 3, quindi l’indice uscente dalla base `e 3.

(37)

Iterazione 2.

La nuova base `e B = {2, 4}, la matrice di base e la sua inversa sono AB =0 −1

1 1

A⁻¹_B = 1 1

−1 0

¯

y = (0, 7, 0, 3, 0)^T,

e quella primale è ¯x = (9, 0)^Tche non è ammissibile perché

b1− A1¯x = 9, b3− A3¯x = 4, b5− A5x = −2,¯ quindi l’indice che entra in base `e 5. Calcoliamo i prodotti

A5W²= −1, A5W⁴= −1, e i rapporti:

¯ y2

−A5W² = 7, y¯4

−A5W⁴ = 3, quindi l’indice uscente dalla base `e 4.

(38)

Iterazione 3.

La nuova base `e B = {2, 5}, la matrice di base e la sua inversa sono AB =0 −1

1 0

A⁻¹_B = 0 1

−1 0

¯

y = (0, 4, 0, 0, 3)^T, e quella primale è ¯x = (7, 0)^Tche è ammissibile perché

b1− A1x = 7,¯ b3− A3¯x = 6, b4− A4¯x = 2, quindi (0, 4, 0, 0, 3) `e la soluzione ottima del problema.

(39)

Problema ausiliario duale

Consideriamo il problema in forma duale standard:







min y^Tb y^TA = c^T y ≥ 0

(D)

Senza ledere la generalit`a della trattazione possiamo supporre che c ≥ 0, cambiando eventualmente segno alle equazioni.

Per trovare una base ammissibile di (D) che sia la base di partenza del simplesso duale si costruisce il problema ausiliario duale:









 min

n

P

i=1

ǫi

y^TA + ǫ^T= c^T y ≥ 0

ǫ ≥ 0

(Daux)

(40)

La base formata dagli indici relativi alle variabili ausiliarie ǫ1, . . . , ǫn, con la matrice identità come matrice di base, è una base ammissibile per il problema ausiliario, infatti la corrispondente soluzione di base è ¯y = 0, ¯ǫ = c ≥ 0.

A partire da tale base ammissibile, possiamo applicare il simplesso duale per risolvere il problema ausiliario.

Il valore ottimo del problema ausiliario stabilisce se esiste una base ammissibile per il problema (D).

Teorema

1 Se il valore ottimo di (Daux) `e > 0 allora (D) non ha soluzioni ammissibili.

2 Se il valore ottimo di (Daux) `e = 0 allora c’`e una base ammissibile per (D) che si costruisce a partire da una base ottima per (Daux).

(41)

1. Problema di produzione

DATI: Un’azienda deve produrre due tipi di tessuto.

Per produrre un quintale del primo tessuto servono 28 kg di lana e 7 kg di cotone.

Per il secondo tipo servono 7 kg di lana e 14 kg di cotone.

Per produrre i tessuti servono 3 ore di lavoro di un operaio specializzato per ogni quintale da produrre.

Ogni settimana sono disponibili 168 kg di lana, 84 kg di cotone e 42 ore di lavoro.

Siano 20 e 10 euro i guadagni (per quintale) per il tessuto 1 e per il tessuto 2.

VARIABILI: Indichiamo con x1 e x2i quintali prodotti del primo e del secondo tessuto.

(42)

Problema di produzione











max 20 x1+ 10 x2

28 x1+ 7 x2≤ 168 7 x1+ 14 x2≤ 84 3 x1+ 3 x2≤ 42 x1, x2≥ 0

La soluzione ottima ´e: (36/7, 24/7) per un guadagno di 137,14 euro.

Qualora il bene da produrre fosse stato un vestito anzich´e un chilogrammo di tessuto, la soluzione trovata non era ammissibile e si sarebbe dovuto aggiungere il vincolo di interezza.

In tal caso la soluzione ottima sarebbe stata (5,3) con un guadagno di 130 euro.

(43)

Problema di produzione

Supponiamo che si debbano produrre n oggetti, ognuno composto da m diverse materie prime.

Sia data una matrice di composizione A. In tale matrice l’elemento aij rappresenta la quantit`a di materia prima i che serve per produrre l’oggetto j.

Sia dato il guadagno cj ottenuto vendendo l’oggetto j e la disponibilit`a bi della materia prima i.

Introducendo le variabili xj, che rappresentano le quantit`a prodotta dell’oggetto j, il problema viene formulato nel modo seguente:











max Pⁿ

j=1

cjxj n

P

j=1

aijxj ≤ bi per ogni i = 1, . . . , m xj ≥ 0 per ogni j = 1, . . . , n

(44)

2. Problema di assegnamento

• Date n persone e n lavori.

• Ogni lavoro deve essere fatto da esattamente una persona.

• Ogni persona pu´o fare al pi´u un lavoro.

• Il costo della persona j = 1, . . . , n che fa il lavoro i = 1, . . . , n ´e cij.

• Vogliamo trovare un assegnamento di costo minimo.

• Possiamo associare una variabile 0-1 xij ad ogni possibile assegnamento(vale 1 se lavoro i assegnato alla persona j, 0 altrimenti).

(45)

Problema di assegnamento Assegnamento non cooperativo:

min

n

P

i=1 n

P

j=1

cijxij

s.t.

n

P

j=1

xij = 1 (i = 1, . . . , n)

n

P

i=1

xij = 1 (j = 1, . . . , n) xij∈ {0, 1}.

Assegnamento cooperativo:

min

n

P

i=1 n

P

j=1

cijxij

s.t.

n

P

j=1

xij = 1 (i = 1, . . . , n)

n

P

i=1

xij = 1 (j = 1, . . . , n) xij∈ [0, 1].

(46)

Problema di assegnamento

Un assegnamento non cooperativo ´e una permutazione.

Un problema di assegnamento non cooperativo ´e un problema di PLI.

Un problema di assegnamento cooperativo ´e un problema di PL.

Teorema

I vertici del poliedro dell’assegnamento cooperativo hanno componenti intere.

Quindi anche il problema dell’assegnamento non cooperativo ´e un problema di PL.

(47)

Problema di assegnamento generalizzato

Ogni persona j = 1, . . . , n ha una capacit´a bj (per esempio ore di lavoro).

Ogni lavoro i = 1, . . . , m assegnato alla persona j usa wij della capacitá bj. Ogni lavoro deve essere assegnato ad una persona e ogni persona non puó superare la propria capacitá.

min

m

P

i=1 n

P

j=1

cijxij

s.t. Pⁿ

j=1

xij = 1 (i = 1, . . . , m) Pm

i=1

wijxij≤ bj (j = 1, . . . , n) xij ∈ {0, 1}.

(48)

PLI: il problema di posizionare ambulanze

• Ambulanze possono essere posizionate in prefissati luoghi.

• Malati importanti devono essere raggiunti in al pi´u 8 minuti.

Problema

Come posizionare il minimo numero di ambulanze per arrivare in ogni posto in al pi´u 8 minuti?

• Dati:

I = insieme di possibili posizioni delle ambulanze.

J = insieme delle richieste.

aij =

1 se ´e possibile andare da i a j in al pi´u 8 minuti 0 altrimenti

(49)

Struttura del modello matematico

• Decisioni (dove porre le ambulanze) −→variabili xi=

1 se un’ambulanza ´e posizionata al posto i 0 altrimenti

• Il pi´u piccolo numero di ambulanze −→funzione obiettivo

• Richieste: tutte gli utenti raggiunti in al pi´u 8 minuti −→vincoli

(50)

Modello matematico

Funzione obiettivo

Minimizzare il numero di ambulanze minX

i∈I

xi

Vincoli

Per ogni posizione j almeno un’ambulanza deve arrivare in al pi´u 8 minuti X

i∈I

aijxi ≥ 1, ∀ j ∈ J

Dominio delle variabili

xi ∈ {0, 1}, ∀ i ∈ I

(51)

Relazioni tra PLI e PL

Consideriamo un problema di programmazione lineare intera (PLI) in formato

standard: 





max c^Tx A x ≤ b x ∈Zⁿ

(P)

Definizione Il problema di PL

max c^Tx

A x ≤ b (RC)

´e dettorilassamento continuodel problema (P).

(52)

Quale ´e la relazione tra (P) e (RC)?

Teorema

• Il valore ottimo di (RC) ´e unavalutazione superioreper il valore ottimo di (P).

• Se una soluzione ottima di (RC) ´eammissibileper (P), allora ´e ottima anche per (P).

Usualmente la soluzione ottima di (RC) ´e inammissibile per (P).

(53)

Per risolvere (P), ´e sufficiente risolvere (RC) ed arrotondare la soluzione? NO Esempio











max x1+ 3 x2

x1+ 5 x2≤ 21 8 x1+ 2 x2≤ 35 x ≥ 0

x ∈Z²

7 2,7

2

ottima per (RC) arrotondamento → (3, 3) (3, 3) non ´e ottima per (P) (1, 4) ´e ottima per (P)

optimum

c

12 13

0 1 2 3 4 5

1 2 3 4

x₁ x₂

(54)

E’ sufficiente risolvere (RC) e trovare la soluzione intera ammissibile pi´u vicina?

NO Esempio











max x1+ 3 x2

x1+ 5 x2≤ 21 8 x1+ 2 x2≤ 35 x ≥ 0

x ∈Z²

7 2,7

2

ottima per (RC).

la soluzione intera ammissibile pi´u vicina ´e (3, 3).

(3, 3) non ´e ottima per (P).

(1, 4) ´e ottima per (P)

optimum

0 1 2 3 4 5

1 2 3 4

x1

x₂

(55)

Metodi: enumerazione esplicita Consideriamo il problema di PLI:











max 5 x1+ 6 x2

3 x1+ 4 x2≤ 7 x1≥ 0, x2≥ 0 x ∈Z²

(P)

I vincoli implicano x1= 0 o 1 o 2.

Scriviamo unapartizionedella regione ammissibile Ω in tre sottoinsiemi:

Ω = (Ω ∩ {x1= 0}) ∪ (Ω ∩ {x1= 1}) ∪ (Ω ∩ {x1= 2}) corrispondente al primo livello dell’albero decisionale:

P

P1,1 P1,2 P1,3

x₁= 0

x1= 1

x₁= 2

(56)

Enumerazione esplicita

Similarmente, x2= 0 or 1. Quindi, l’albero delle decisioni completo ´e:

P

P1,1 P1,2 P1,3

P2,1 P2,2 P2,3 P2,4 P2,5 P2,6

x1= 0

x₁= 1

x1= 2

x2= 0 x2= 1 x2= 0 x2= 1 x2= 0 x2= 1

I nodi P2,1, . . . , P2,5corrispondono a soluzioni ammissibili di (P), mentre il nodo P2,6 corrisponde a x = (2, 1) che ´e inammissibile. I valori della funzione obiettivo per i nodi P2,1, . . . , P2,5sono 0, 6, 5, 11, 10. Allora, la soluzione ottima ´e data da P2,4, i.e., x^∗= (1, 1).

(57)

Enumerazione implicita











max x1+ 3 x2

x1+ 5 x2≤ 21 8 x1+ 2 x2≤ 35 x≥ 0, x ∈Z²

0 1 2 3 4 5

1 2 3 4

x1

x2 • Sappiamo che (3, 3) ´e

ammissibile con valore 12.

• Consideriamo il vincolo aggiuntivo x1≥ 4: l’ottimo del rilassamento continuo del sottoproblema ´e (4, 3/2) con valore 8.5 quindi le soluzioni ammissibili del

sottoproblema sono peggiori di (3, 3)

→enumerazione implicita.

(58)

”Branch and Bound”

L’idea di base del Branch and Bound ´e:

• La regione ammissibile ´e partizionata, generando un albero di ricerca.

• Per ogni sottoregione (corrispondente ad un sottoproblema) il valore ottimo ´e approssimato tramite valutazioni.

• Le regioni che non possono contenere l’ottimo sono scartate.

(59)

Principali componenti

• Branching : come partizionare la regione ammissibile per generare sottoproblemi.

• Bounding : come stimare il valore dell’ottimo in ogni sottoregione.

• Fathoming : come depennare le sottoregioni che non contengono l’ottimo (come chiudere i nodi dell’albero di ricerca).

Come partizionare la regione ammissibile

• Le sottoregioni sono generate aggiungendo vincoli.

• Le sottoregioni devono essere una partizione della regione ammissibile, in modo tale da garantire che nessuna soluzione intera sia scartata.

(60)

Regole di ”Branching”

”Branching” bipartito

Ogni regione ´e partizionata in due sottoregioni, aggiungendo i vincoli x1≤ 3 e x1≥ 4

0 1 2 3 4 5

1 2 3 4

x1 x2

(61)

Albero di ”branching” corrispondente

P

P1 P2

x1≤ 3 x1≥ 4

(62)

Regole di ”Branching”

k-partito ”branching”

Ogni regione ´e divisa in k sottoregioni, aggiungendo k vincoli E.g. x1= 0, x1= 1, x1= 2, x1= 3, e x1= 4

0 1 2 3 4 5

1 2 3 4

x1 x2

(63)

Albero di ”branching” corrispondente

P

P1 P2 P3 P4 P5

x1= 0 x1= 1 x1= 2 x1= 3 x1= 4

(64)

Valutazioni per problemi di massimo

Valutazioni inferiori LB date da soluzioni ammissibili.

Valutazioni superiori UB date da un rilassamento:

• Rilassamento continuo (eliminazione del vincolo di interezza) x ∈ {0, 1} ⇒ 0 ≤ x ≤ 1

x ∈Z+⇒ x ≥ 0

• Eliminazione di uno o pi´u vincoli.

(65)

Criteri di ”fathoming” o ”pruning”

Un nodo dell’albero di decisione pu´o esserechiusose una delle seguenti condizioni sussite:

• il sottoproblema ´e inammissibile.

• UB del sottoproblema ´e ≤ LB di (P).

• UB del sottoproblema ´e > LB e la soluzione ottima del sottoproblema ´e ammissibile per (P). In tal caso noi aggiorniamo LB = UB.

(66)

Schema del metodo

1. Calcola una valutazione inferiore LB del valore ottimo di (P) 2. Se tutti i nodi sono stati esplorati allora STOP

3. Seleziona il nodo (sottoproblema) da esplorare

4. Calcola una valutazione superiore UB del valore ottimo del sottoproblema 5. Controlla i criteri:

se il sottoproblema ´e inammissibile allora chiudi il nodo se UB ≤ LB, allora chiudi il nodo

se UB > LB e la soluzione ottima del sottoproblema ´e ammissibile per (P), allora chiudi il nodo ed aggiorna LB = UB

6. se il nodo non ´e chiuso allora scendi 7. vai al passo 2

(67)

Esempio

Applica il ”Branch and Bound” per risolvere il problema











max x1+ 3 x2

x1+ 5 x2≤ 21 8 x1+ 2 x2≤ 35 x ≥ 0, x ∈Z².

(P)

Usiamo un albero bipartito.

Sappiamo che la soluzione ottima del rilassamento continuo ´e (7/2, 7/2) quindi UB(P) = 14.

Conosciamo la soluzione ammissibile (3, 3) quindi LB = 12.

P 12,14

x₁≤ 3 x₁≥ 4

(68)

Esempio

La soluzione ottima del rilassamento continuo di P1´e (3, 18/5).

E’ inammissibile con valore 13.8, quindi UB(P1) = 13 > 12 = LB.

Il nodo P1rimane aperto.

Partizione: x2≤ 3 e x2≥ 4.

P 12,14

P1

12,13

x₁≤ 3 x₁≥ 4

x₂≤ 3 x₂≥ 4

(69)

Esempio

La soluzione ottima del rilassamento continuo di P2´e (3, 3), quindi UB(P2) = 12 = LB, chiudiamo il nodo P2.

La soluzione ottima del rilassamento continuo di P3´e (1, 4) e

UB(P3) = 13 > 12 = LB.Poich´e (1, 4) ´e ammissibile per P, aggiorniamo LB = 13 e chiudiamo il nodo P3.

La soluzione ottima del rilassamento continuo di P4´e (4, 3/2) con valore 8.5, quindi UB(P4) = 8 < 13 = LB. Chiudiamo il nodo P4.

P 12,14

P1

12,13

P4

13,8

P2

12,12

P3

13,13

x1≤ 3 x1≥ 4

x2≤ 3 x2≥ 4

Tutti i nodi sono chiusi, la soluzione ottima di P ´e (1, 4) e il valore ´e 13.

(70)

3. Problema dello zaino (knapsack problem)

Problema

Dati: un contenitore di capacit`a C , n oggetti di valore v1, . . . , vne peso p1, . . . , pn. Quali oggetti inserisco nel contenitore, rispettando la sua capacit`a, in modo da massimizzare il valore totale?

Esempio

Budget 100. Scegliere tra 9 investimenti possibili:

Investimento 1 2 3 4 5 6 7 8 9

Ricavo atteso 50 65 35 16 18 45 45 40 25

Costo 40 50 25 10 10 40 35 30 20

(71)

Modello dello zaino binario

Variabili: xj =

(1 se oggetto j viene inserito, 0 altrimenti.

max

n

X

j=1

vjxj n

X

j=1

pjxj ≤ C

xj∈ {0, 1} ∀ j = 1, . . . , n

(72)

Metodi euristici ”greedy”

Metodi greedy per trovare una soluzione ammissibile.

Metodo 1

Esamino gli oggetti in ordine divalore decrescente.

Ogni oggetto viene inserito purch´e sia rispettato il vincolo di capacit`a.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x2= 1, x6= 1, x1= 1, x7= 0, x8= 0, x3= 0, x9= 0, x5= 0, x4= 0.

Quindi vI(P) = 170.

(73)

Metodo 2

Esamino gli oggetti in ordine dipeso crescente.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x4= 1, x9= 1, x5= 1, x3= 1, x8= 0, x6= 0, x7= 0, x1= 0, x2= 0.

Quindi vI(P) = 94.

(74)

Metodo 3

Esamino gli oggetti in ordine direndimento (valore/peso) decrescente.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x6= 1, x2= 1, x1= 1, x7= 0, x8= 0, x3= 0, x9= 0, x4= 0, x5= 0.

Quindi vI(P) = 170.

(75)

Rilassamenti

Teorema

Supponiamo che le variabili siano in ordine di rendimento decrescente.

Sia h l’indice tale che P^h

j=1

pj≤ C e

h+1

P

j=1

pj> C .

Ilrilassamento continuo











max Pⁿ

j=1

vjxj n

P

j=1

pjxj≤ C 0 ≤ xj≤ 1

ha come soluzione ottima

¯

x1= 1, . . . , ¯xh= 1, ¯xh+1= C −

h

P

j=1

pj

ph+1

, ¯xh+2= 0, . . . , ¯xn= 0

(76)

Esempio

Sia dato il seguente problema:







max 10 x1+ 13 x2+ 18 x3+ 24 x4

2 x1+ 3 x2+ 4 x3+ 6 x4≤ 7 xj ∈ {0, 1}

Disponiamo le variabili in ordine di rendimento decrescente:

variabili 1 3 2 4

rendimenti 5 4.5 4.33 4

Applicando il terzo algoritmo greedy otteniamo la soluzione ammissibile (1, 0, 1, 0) e quindi vI(P) = 28.

L’ottimo del rilassamento continuo `e 1,¹₃, 1, 0, quindi vS(P) = 32.

(77)

Problema dello zaino a variabili intere

Problema

Dati: n oggetti, ognuno di valore vj peso pj, un contenitore di capacit`a C . Quanti oggetti di ogni tipo inserisco nel contenitore per massimizzare il valore totale?

Modello

xj = numero (intero) di oggetti di tipo j inseriti nel contenitore max

n

X

j=1

vjxj n

X

j=1

pjxj ≤ C

xj ∈N ∀ j = 1, . . . , n

(78)

Metodi greedy per trovare una soluzione ammissibile.

Metodo 1

Esamino gli oggetti in ordine divalore decrescente.

Inserisco ogni oggetto nella massima quantità possibile, purché sia rispettato il vincolo di capacità.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x2= 2, x6= 0, x1= 0, x7= 0, x8= 0, x3= 0, x9= 0, x5= 0, x4= 1.

Quindi vI(P) = 146.

(79)

Metodo 2

Esamino gli oggetti in ordine dipeso crescente.

Inserisco ogni oggetto nella massima quantità possibile, purché sia rispettato il vincolo di capacità.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x4= 4, x9= 0, x5= 0, x3= 0, x8= 0, x6= 0, x7= 0, x1= 0, x2= 0.

Quindi vI(P) = 64.

(80)

Metodo 3

Esamino gli oggetti in ordine direndimento decrescente.

Inserisco ogni oggetto nella massima quantit`a, rispettando il vincolo di capacit`a.

Esempio

Oggetto 1 2 3 4 5 6 7 8 9

Valore 50 65 35 16 18 55 45 40 25

Peso 31 39 26 21 25 28 29 27 23 C = 100

x6= 3, x2= 0, x1= 0, x7= 0, x8= 0, x3= 0, x9= 0, x4= 0, x5= 0.

Quindi vI(P) = 165.

(81)

Rilassamenti

Calcoliamo una vS(P) risolvendo il rilassamento continuo.

Teorema Se max

j {_p^v^j

j} = _p^v^r

r, allora il rilassamento continuo











max Pⁿ

j=1

vjxj n

P

j=1

pjxj ≤ C x ≥ 0 ha come soluzione ottima

¯

x1= 0, . . . , ¯xr−1= 0, ¯xr = C pr

, ¯xr+1 = 0, . . . , ¯xn= 0 e valore ottimo C vr/pr.

(82)

Esempio

Consideriamo il problema:







max 4 x1+ 20 x2+ 27 x3+ 26 x4

4 x1+ 19 x2+ 16 x3+ 14 x4≤ 32 xj ∈N

(P)

Disponiamo le variabili in ordine di rendimento decrescente:

variabili 4 3 2 1

rendimenti 1.85 1.68 1.05 1

Il terzo algoritmo greedy trova la soluzione (1, 0, 0, 2) con vI(P) = 56.

La soluzione ottima del rilassamento continuo `e (0, 0, 0,³²₁₄), quindi vS(P) = 59.

(83)

4. Problema di trasporto ottimo

Supponiamo di avere m luoghi di produzione collegati con n luoghi di raccolta.

Per fissare le idee si pu`o pensare alla distribuzione giornaliera su un territorio di un prodotto come ad esempio un carburante.

Supponiamo che siano note le capacit`a produttive oi, per i = 1, . . . , m, le

domande dj, per j = 1, . . . , n, ed il costo di trasporto da ogni luogo di produzione ad ogni luogo di destinazione.

Si voglia determinare un piano di trasporto compatibile con la produzione e con la richiesta e che minimizzi il costo totale.

(84)

Problema di trasporto ottimo

Supponiamo che il costo di spedizione sia proporzionale (lineare) e quindi esista il costo unitario cij del trasporto da i a j.

Indichiamo con xij la quantit`a di merce da trasportare da i a j.

Fissato j, sommando su i le xij si ottiene la quantit`a di merce che arriva al luogo di raccolta j e viceversa, fissato i, sommando su j le xij si ottiene la quantit`a di merce spedita dal luogo di produzione i.