Università degli Studi di CagliariFACOLTA’ DI INGEGNERIA

Ricerca Operativa- RO -

Dott.ssa Michela Laimlai@unica.it

http://sorsa.unica.it/

Esercitazione 6

2

Esercizio:

Dato il problema primale:P min 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5

s.t.x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4

2 x1 – 2 x2 + 3 x3 + x4 + x5 ≥ 3

x1, x2, x3, x4, x5 ≥ 0

Risolvere il suo duale su carta e poi implementare P e D su Lindo.

Dualità

3

Dualità – Relazioni P&D

Min P Max D

Variabili

≥ 0 ↔ ≤ 0 Vincoli

≤ 0 ↔ ≥ 0

Libera ↔ =

Vincoli

≥ 0 ↔ ≥ 0 Variabili

≤ 0 ↔ ≤ 0

= ↔ Libera

4

Esercizio:

Seguendo le relazioni P&D otteniamo:D max 4 w1 + 3 w2

s.t.w1 + 2 w2 ≤ 2

w1 – 2 w2 ≤ 3

2 w1 + 3 w2 ≤ 5

w1 + w2 ≤ 2

3 w1 + w2 ≤ 3

w1, w2 ≥ 0

Dualità

5

Lindo P:min 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5s.t.x1 + x2 + 2 x3 + x4 + 3 x5 = 42 x1 - 2 x2 + 3 x3 + x4 + x5 = 3end

Lindo D:max 4 w1 + 3 w2s.t.w1 + 2 w2 = 2w1 - 2 w2 = 32 w1 + 3 w2 = 5w1 + w2 = 23 w1 + w2 = 3end

SoluzioniSoluzione P: OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 1.000000 0.000000 X2 0.000000 3.400000 X3 0.000000 1.600000 X4 0.000000 0.600000 X5 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.800000 3) 0.000000 -0.600000

Soluzione D: OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST W1 0.800000 0.000000 W2 0.600000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.000000 3) 3.400000 0.000000 4) 1.600000 0.000000 5) 0.600000 0.000000 6) 0.000000 1.000000

6

Analisi di sensitività

7

Introduzione

I problemi di flusso su rete presentano una speciale struttura che consente di adottare algoritmi particolarmente efficienti per la loro risoluzione

Tra i vari problemi di flusso, ci occuperemo del Problema del Flusso di Minimo Costo (MCF). In questa esercitazione:

faremo brevi richiami della teoria dei grafi e del MCFvedremo possibili applicazioni del MCFutilizzeremo un solver specializzato per problemi di MCF

8

Richiami di teoria dei grafiUn grafo G(N, A) è definito da una coppia di insiemi N e A

N, detto insieme dei nodi, è l’insieme dei primi n numeri naturali A, detto insieme degli archi, è un sottoinsieme del prodotto

cartesiano N x N

Dato un nodo i Є N P(i) = {j: (j, i) Є A}, è l’insieme dei predecessori di i S(i) = {k: (i, k) Є A}, è l’insieme dei successori di i

Dato un arco (i, j) Є A Il nodo i rappresenta la coda dell’arco Il nodo j rappresenta la testa dell’arco Si ha un grafo orientato quando (i, j)≠(j,i)

9

G(N, A) orientato N = {1, 2, 3, 4, 5} A = {(1, 2), (1, 4), (2, 3), (2, 5), (3, 1), (3, 5),

(4, 5), (5, 4)}

Si dice cammino un insieme di archi in cui ogni coppia contiene un nodo della coppia precedente.

Esempio: {(1, 2), (2, 5), (4, 5)}Si dice cammino orientato un insieme di

archi in cui la testa di ogni arco coincide con la coda dell’arco seguente.

Esempio: {(1, 2), (2, 5), (5, 4)}

Richiami di teoria dei grafi

10

Grafo connesso esiste sempre un cammino tra qualsiasi coppia di nodi

Grafo fortemente connesso esiste un cammino orientato tra ogni coppia di nodi

Ciclo cammino chiuso, inizia e termina nello stesso nodo. Se il cammino è orientato, anche il ciclo è orientato.

Ciclo Hamiltoniano ciclo che passa per ogni nodo del grafo una sola volta

Richiami di teoria dei grafi

11

Foglia nodo testa/coda di un solo arcoAlbero grafo connesso privo di cicli

ha almeno due foglie Estraendo un qualsiasi arco l’albero viene suddiviso in due

sottoalberi distinti un albero con n nodi presenta n-1 archi

Dato un grafo G=(N, A) Grafo parziale G‘=(N, A‘) grafo in cui

Albero ricoprente di un grafo albero che costituisce un grafo parziale che tocca tutti i nodi del grafo

Richiami di teoria dei grafi

AA '

12

Matrice di incidenza nodi-archi uno dei possibili modi in cui rappresentare un grafo

Ha un numero di righe pari al numero dei nodi Ha un numero di colonne pari al numero degli archi In ogni colonna solo due elementi sono non-nulli:

1 in corrispondenza della coda di quell’arco -1 in corrispondenza della testa di quell’arco

La matrice di incidenza è una struttura adatta a ricavare algoritmi, ma non consente una buona implementazione.

Richiami di teoria dei grafi

13

EsercizioRicavare la matrice di incidenza nodi-archi del grafo

Richiami di teoria dei grafi

Una matrice di incidenza con n nodi ha rango n-1.

Esiste una corrispondenza biunivoca tra gli alberi ricoprenti del grafo e le basi della matrice di incidenza (purché rendiamo la

matrice di incidenza a rango pieno).

14

Dimostrazione rango n-1:Il suo rango non è n, infatti, comunque si estragga un minore di ordine n la somma delle sue colonne risulta sempre nullaConsiderato un albero ricoprente del grafo, il minore ad esso corrispondente ha n righe e n-1 colonne.Questo albero presenta almeno 2 foglie e la sua matrice di incidenza presenta almeno 2 righe con un coefficiente non nulloCon delle permutazioni si porta il coefficiente non nullo di una foglia in prima riga sulla diagonale principaleSi cancella quella foglia e quel ramo, si ottiene un nuovo albero con almeno 2 foglie che possono essere portate in seconda riga sulla diagonale principaleIterando questo procedimento, si portano n-1 coefficienti non nulli sulla diagonale principale

Richiami di teoria dei grafi

15

Il problema del flusso di minimo costoDato un grafo G(N,A), ad ogni nodo i viene associata una quantità di risorsa bi

Se bi > 0 il nodo i è un nodo offerta Se bi < 0 il nodo i è un nodo domanda Se bi = 0 il nodo i è un nodo di transito

Si assume che l’offerta totale di risorsa sia uguale alla domanda, in questo caso la rete si dice bilanciata

Notazione: xij : flusso di risorsa che transita sull’arco (i,j) cij : costo di transito sull’arco (i,j), il costo è unitario

16

Formalizzazione del MCF

Aji

ijijxc),(

min

)( )(iSj iPj

ijiij bxx Ni

0ijx Aji ),(

cxmin

bEx

0x

dove E è la matrice di incidenza nodi archi

Se una rete non è bilanciata, occorre bilanciarla con opportuni valori di domande/offerte in nodi artificiali connessi da archi di costo molto elevato

Il problema del flusso di minimo costo

17

Esercizio

La rete è bilanciata?SI

A cosa corrisponde un costo negativo?BENEFICIO

18

Passo ITrovare una base ammissibile e calcolare

il flusso delle variabili di base.

Partiamo dalla base segnata in verde:

Scrivere la matrice di incidenzaCalcolare il flusso sugli archi a partire dalle

foglie (1 solo elemento sulla riga ≠ 0)

Foglia 1 w1 = 2Foglia 2 w2 = 5

Eliminiamo le foglie, le utilizziamo per correggere i bi dei nodi su cui incidono e iteriamo il calcolo dei w…

19

Passo ITerminati i calcoli dei flussi otteniamo:

Foglia 1 w1 = 2Foglia 2 w2 = 5Foglia 3 w3 = 6Foglia 4 w4 = 2

L’equazione ∑jЄS(i) xij – ∑kЄP(i) xki = bi

è rispettata!La nostra base è ammissibile!

20

Passo II

Effettuare il criterio di entrata

Per effettuare il criterio di entrata in generale bisogna risolvere il sistema wB = cB

(w1, w2, w3, w4, w5) (matrice di incidenza) = (2, -4, 0, 3, 0-costo r-)

L’equazione che usiamo per risolvere il sistema è wi-wj=cij per le variabili in base!

Il costo della radice è 0 innesco da cui partire

Andiamo avanti ricorsivamente esaminando un solo w alla volta!

21

Passo II

w1 – w5 = 2 – 0 = 2 w1 = 2w4 – w5 = 3 – 0 = 3 w4 = 3w3 – w4 = w3 – 3 = 0 w3 = 3w2 – w3 = w2 – 3= -4 w2 = -1

Ora abbiamo tutto ciò che ci serve per calcolare le zij – cij = wi – wj – cij

per gli archi fuori base!

arco(1,2): w1 – w2 – 5 -2arco(1,3): w1 – w3 – (-2) 1arco(4,2): w4 – w2 – 6 -2arco(5,3): w5 – w3 – 4 -7

22

Passo II

arco(1,2) -2arco(1,3) 1arco(4,2) -2arco(5,3) -7

Chi entra? Il maggiore tra i positivi!

23

Passo III

Chi esce? L’arco discorde al ciclo con flusso

minore!

Questo è il nuovo albero!Non ripetiamo la fase di ammissibilità

perché i nuovi flussi sono stati calcolati con il criterio di uscita.

Ripartiamo dal calcolo dei w perché ci aspettiamo una nuova configurazione!

24

Passo IIIQuando ci si ferma?

1. Tutti i valori per le variabili fuori base sono ≤ 0!

2. Troviamo un ciclo che non migliora!

Completare l’esercizio e trovare la soluzione ottima!

Trovata la soluzione ottima risolvere l’istanza sul Lindo e confrontarla!

25

Esercizio

Risolvere l’istanza con Lindo

Aji

ijijxc),(

min

)( )(iSj iPj

ijiij bxx

0ijx Aji ),(

Ni

26

Esercizio

Su Lindo:

min 5 x12 - 2 x13 + 2 x15 - 4 x23 + 0 x34 + 6 x42 + 3 x45 + 4 x53s.t.x12 + x13 + x15 = 2x23 - x12 - x42 = 5x34 - x13 - x23 - x53 = 1x42 + x45 - x34 = -4x53 - x15 - x45 = -4end

27

Soluzione con Lindo:

OBJECTIVE FUNCTION VALUE 1) -12.00000 VARIABLE VALUE REDUCED COST X12 0.000000 3.000000 X13 2.000000 0.000000 X15 0.000000 1.000000 X23 5.000000 0.000000 X34 8.000000 0.000000 X42 0.000000 2.000000 X45 4.000000 0.000000 X53 0.000000 7.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 -2.000000 5) 0.000000 -2.000000 6) 0.000000 1.000000

Esercizio

28

Utilizzo del solver specializzato MCFc Problem line (il carattere c introduce righe utilizzate per commenti)p min 5 8 (il carattere p introduce la riga della f.o. questo problema ha 5 nodi e 8 archi)cc Node descriptor lines (per convenzione l’offerta è positiva e la domanda è negativa)n 1 2 (il carattere n introduce la riga relativa a un nodo; ad esempio il nodo 1 offre 2 unità di risorsa)n 2 5n 3 1n 4 -4n 5 -4 (il nodo 5 domanda 4 unità di risorsa)cc Arc descriptor linesa 1 2 0 10 5 (il carattere a introduce la riga relativa a un arco, riportando nell’ordine coda, a 1 3 0 10 -2 testa, limite inferiore del flusso, limite superiore del flusso e costo)a 1 5 0 10 2a 2 3 0 10 -4a 3 4 0 10 0a 4 2 0 10 6a 4 5 0 10 3a 5 3 0 10 4cc End of file

read nome_file.dimacs optimize display write sol_nome_file.txt

Comandi essenziali per MCF:

29

c Output to minimum-cost flow problem sample3.dimacsc The problem was solved with a network simplex codecc need 4 iteration(s) in 0 second(s).s -12 (questo è il valore ottimo della f.o.)f 1 3 2 (il flusso da 1 a 3 vale 2 all’ottimo)f 2 3 5f 3 4 8f 4 5 4cc All other variables are zero

Utilizzo del solver specializzato MCFSoluzione con MCF:

30

Con OPL

31

{int} Nodi = { 1, 2, 3, 4, 5};int dom[Nodi]= [2, 5, 1, -4, -4];tuple arco{

int i;int j;

}{arco} archi = {<1,2>, <1,3>, <1,5>, <2,3>, <3,4>, <4,2>, <4,5>, <5,4>};int costi[archi] = [5, -2, 2, -4, 0, 6, 3, 4];dvar int+ x[archi];minimize sum(a in archi)costi[a] * x[a];subject to{

forall(i in Nodi) sum (<i, s> in archi) x[<i, s>] - sum(<p, i> in archi) x[<p, i>] == dom[i];

}

Con OPL