Università degli Studi di Padova
Progetto Lauree scientifiche
Buratto Alessandra
Dipartimento Di Matematica Pura Ed Applicata
Liceo Scientifico "L. da Vinci” Treviso
Modelli di
Ottimizzazione su rete







Cammino minimo
Minimo albero ricoprente
Flusso massimo
Flusso di costo minimo
Pianificazione di progetti
Trasporti (Ditta Zorzi – TV)
assegnamento
Programma
Introduzione alla Teoria dei Grafi
 Formulazione del problema in termini
di programmazione lineare
 Uso di Excel per la formulazione e la
risoluzione dei problemi

Cammino minimo



Minimizzazione della distanza percorsa
Minimizzazione del costo totale di una
sequenza di attività
Minimizzazione del tempo totale per
svolgere una sequenza di attività
Cammino minimo da origine a destinazione
• Cammino minimo da origine a qualunque
altro nodo
• Cammino minimo da ogni nodo a qualunque
altro nodo.
•
Cammino minimo a Seervada Park
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi
scelti
connessi
Nodi
candidati
Distanza
tot (da O)
O (A-B-C)
A
2
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
C
4
7
1
3
1
T
E
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
O (A-B-C)
A
2
A
2
OA
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
O (B-C)
C
4
A (B-D)
B
2+2=4
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
7
E
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
O (B-C)
C
4
C
4
OC
A (B-D)
B
2+2=4
B
4
AB
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
A (D)
D
2+7=9
B (D-E)
E
4+3=7
C (E)
E
4+4=8
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
A (D)
D
2+7=9
B (D-E)
E
4+3=7
C (E)
E
4+4=8
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
E
7
BE
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
A (D)
D
2+7=9
B (D)
D
4+4=8
E (D-T)
D
7+1=8
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
A (D)
D
2+7=9
B (D)
D
E (D-T)
D
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
4+4=8
D
8
BD
7+1=8
D
8
ED
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
D (T)
T
8+5=13
E (T)
T
7+7=14
T
7
E
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
Algoritmo efficiente
per Cammino minimo
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
7
E
Nodi scelti
connessi
Nodi
candidati
Distanza
tot (da O)
K-esimo
nodo
vicino
Distanza
minima
Ultimo
arco
D (T)
T
8+5=13
T
13
DT
E (T)
T
7+7=14
Cammini minimi a Seervada Park
7
A
2
2
5
4
B
O
D
5
4
C
4


1
3
1
T
O–A–B–D–T
O–A–B–E-D–T
7
E
}
Lughezza 13
Modello di programmazione
matematica

Minimizzazione distanza percorsa:
• se percorro un arco tengo conto della sua
lunghezza cij, se non lo percorro non ne tengo
conto.
Variabile
0, se non percorro l ' arco ij ,
xij  
1, se percorro l ' arco ij .
La distanza percorsa è data dalla sommatoria
n
n
 c x
i 1 j 1
ij ij
Vincoli
Dal nodo ORIGINE esco e non vi entro più.
 Nel nodo DESTINAZIONE entro e non vi
esco più.
 In ogni altro nodo se vi entro vi devo
anche uscire.
FLUSSO NETTO =
FLUSSO IN USCITA – FLUSSO IN ENTRATA

n
n
x x
j 1
ij
i 1
ij
Vincoli


ORIGINE:
FLUSSO NETTO = 1
DESTINAZIONE:
FLUSSO NETTO = -1
n
x
j 1
Ogni altro nodo:
FLUSSO NETTO = 0
Oj
n
x
j 1

n
  xiO  1
i 1
n
Dj
n
  xiD  1
i 1
n
x x
j 1
ij
i 1
ij
0
Cammino minimo (PL)
n
min
n
 c x
i 1 j 1
n
s.a.
x
Oj
j 1
n
x
j 1
ij ij
n
  xiO  1,
i 1
n
Dj
n
  xiD  1,
i 1
n
x x
j 1
ij
i 1
ij
 0,
0, se ij non viene percorso ,
xij  
1, se ij viene percorso.
Albero Ricoprente

Albero (tree): sottografo connesso
aciclico
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Valore 24
Albero Ricoprente

No Albero: sconnesso
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Albero Ricoprente

No Albero: ciclico
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
Progettazione di reti
Rete di comunicazioni
(fibre ottiche – tv via cavo)
 Rete di trasporto, min costi costruzione
(strade – ferrovie)
 Rete trasmissione elettrica alto voltaggio
 Rete collegamenti elettrici (computer)
min lunghezza collegamenti

Minimo albero Ricoprente

Albero di lunghezza minima
(si parte da un nodo qualsiasi)
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
E
7
Minimo albero Ricoprente
7
A
2
2
5
4
B
O
D
5
4
1
3
1
C
4
T
7
E
Valore 14
Flusso di costo minimo
Flusso attraverso rete con archi a
capacità limitata (= max flusso)
 Costo associato ad ogni arco

(= costo min)
Più nodi sorgente
 Più nodi destinazione

Flusso di costo minimo
Rete orientata e connessa
 Esiste almeno un nodo sorgente
 Esiste almeno un nodo destinazione
 Tutti gli altri nodi sono di trasferimento

Flusso di costo minimo




Il flusso in ogni arco è ammesso solo in
una direzione (rete orientata) e nel
rispetto dei vincoli di capacità (quantità
max di flusso) di tale arco.
La rete ha abbastanza archi con capacità
sufficiente perché il flusso generato dalla
sorgenti arrivi alle destinazioni
Il costo del flusso lungo un arco è
proporzionale alla qtà del flusso stesso
Costi per unità do flusso noti
Flusso di costo minimo

Obiettivo:
• Minimizzare il costo totale per spedire il
flusso attrverso la rete così da
soddisfare la domanda richiesta
• Miassimizzare il profitto totale nimizzare
il costo totale per spedire il flusso
attrverso la rete così da soddisfare la
domanda richiesta
Flusso di costo minimo - Applicazioni
Tipo di
applicazione
Nodi
sorgente
Nodi di
trasporto
Nodi
destinazione
Rete di
distribuzione
Produttori di
beni
Servizi/magazzini
intermedi
Clienti
Smaltimento
rifiuti solidi
Produttori
rifiuti
Impianti di
produzione
discariche
Rete di servizi
fornitori
magazzini
intermedi
Impianti di
produzione
Mix di
produzione
fabbriche
produzione
mercato
Gestione flusso
di cassa
Sorgenti di
contante
Opzioni di
investimento
Bisogni di
contante
Flusso di costo minimo Applicazioni

Rete di distribuzione aziendale:
trasporti delle merci dalle fabbriche
ai magazzini intermedi fino ai clienti
Formulazione del modello
Variabili decisional i :
xij flusso lungo l' arco ij ,
Dati (informazi oni) :
cij costo per unità di flusso lungo l' arco ij ,
uij
capacità dell' arco ij ,
bi
flusso esterno per il nodo i
bi
 0 per ogni nodo i sorgente,

 0 per ogni nodo i destinazio ne,
 0 per ogni nodo i di trasferim ento,

Flusso di costo minimo (PL)
n
min
n
 c x
i 1 j 1
n
s.a.
ij ij
n
x x
 bi , per ogni nodo i,
0  xij  uij
per ogni arco ij ,
j 1
ij
i 1
ij
0, se ij non viene percorso ,
xij  
1, se ij viene percorso.
Condizioni necessarie

Condizione necessaria perché un problema
di flusso minimo abbia almeno una
soluzione ammissibile è che
n
b
i 1
i
0
il flusso totale generato dai nodi sorgente
deve essere uguale al flusso totale
richiesto dai nodi destinazione.
Condizioni necessarie violate

Se non è soddisfatta
necessaria, allora:
la
condizione
• o si aggiunge un nodo destinazione fittizio per
assorbire le disponibilità in eccesso (con cij = 0
per gli archi aggiunti da ogni nodo sorgente
verso questo nodo)
• oppure si aggiunge un nodo sorgente fittizio
che generi il flusso necessio a soddisfare la
richiesta in eccesso (cij = 0 per gli archi
aggiunti da questo nodo sorgente verso ogni
altro nodo destinazione)
Interezza della soluzione ottima
Per un problema di flusso a costo
minimo in cui bi e uij hanno valori
interi, tutte le variabili di base di ogni
soluzione di base ammissibile (inclusa
quella ottima) hanno valori interi
Non serve mettere i vincoli di interezza
al problema e neppure quelli di
binarietà  risoluzione efficiente con
metodo del simplesso su rete.
Flusso di costo minimo (PL)
n
min
n
 c x
i 1 j 1
n
s.a.
ij ij
n
x x
 bi , per ogni nodo i,
0  xij  uij
per ogni arco ij .
j 1
ij
i 1
ij
Esempio flusso di costo minimo
produzione
b
A
=[50]
[-30]
CAD=9
A
D
4
2
C
(uAB=10)
2
3
1
3
B
[40]
(uCE=80)
E
[-60]
Flusso di costo minimo (PL)
min
Z  x AB  4 x AC  9 x AD  3xBC  xCE  3xDE  2 xED
s.a.
x AB  x AC  x AD
 x AB
 x AC
 50
 xBC
 40
 xBC  xCE
 0
 x AD
 xDE  xED  30
 xCE  xDE  xED  60
x AB  10, xCE  80, xij  0.
Coefficienti flusso di costo minimo
X11
X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34
1
1
1
…
1
1
1
1
1
A
1
-1
-1
-1
1
…
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1
Trasporti





La P&T COMPANY produce piselli in scatola
in 3 fabbriche (F1 – F2 – F3)
Una volta confezionati li spedisce via
camion a 4 magazzini di distribuzione (M1
– M2 – M3 – M4)
Il trasporto da ogni fabbrica ad ogni
magazzino ha dei costi (da minimizzare)
Ogni fabbrica ha una propria capacità
produttiva
Ogni magazzino richiede una data quantità
di fornitura
Trasporti
Costo Sped
($) per
container
magazzino
M1
M2
Capacità
Produtt.
M3
M4
F1
464
513
654
867
75
F2
352
416
690
791
125
F3
995
682
388
685
100
65
72
85
Alloca 80
zione
Trasporti – P&T COMPANY
464
[75]
[125]
[100]
F1
M1
[-80]
M2
[-65]
F2
F3
685
M3
[-70]
M4
[-85]
Trasporti (PL)
n
min
n
 c x
i 1 j 1
n
s.a.
x
j 1
ij
n
x
i 1
ij
ij ij
 si
per i  1,2, ,3
(m  3)
 d j , per i  1,2, ,4 (n  4)
0  xij  uij  
Trasporti (PL)
X11
X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34
1
1
1
1
1
1
1
1
A
1
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1