Tipi di problemi di programmazione lineare

Formulazione di Problemi Decisionali
come Problemi di Programmazione
Lineare
Consideriamo i seguenti problemi decisionali ed
esaminiamo come possono essere formulati come
problemi di PL:
z Il problema del trasporto
z
Il problema del carico macchina
z
I problemi di ottimizzazione su rete
z
Il problema dell’assegnamento
z
Il problema del commesso viaggiatore
1
Il Problema dei Trasporti
z
m punti origine O1, O2, Om hanno la disponibilità di
p1,p2,…,pm quantità di un certo prodotto
z
n punti destinazione D1, D2, Dn richiedono q1,q2,
...,qn quantità di prodotto
z
il prodotto può essere trasportato da ogni fornitore
ad ogni destinatario
z
per ogni unità di prodotto trasportata dal fornitore i
al cliente j viene pagato un costo cij
2
Il problema: determinare quali quantità di prodotto
trasportare tra ogni coppia (i,j) di fornitoridestinatari in modo da minimizzare il costo
complessivo del trasporto.
q1
p1
M
M
p
c ij
i
M
p
m
M
q
j
q
n
3
Formulazione del problema.
Le variabili:
la quantità di prodotto trasportata su ciascun arco
xij ∈ R
i = 1,...,m; j = 1,..., n
sono variabili continue
La funzione obiettivo:
il costo del trasporto complessivo
m
n
∑ ∑ cij xij
i = 1 j =1
4
I vincoli:
z
la quantità totale di prodotto fornita da ciascun
fornitore non può superare la disponibilità del
fornitore stesso
n
∑x
ij
j =1
z
≤ pi
i = 1,..., m
la quantità totale di prodotto ricevuta da ciascun
destinatario deve essere uguale a quella richiesta
m
∑x
i =1
ij
≥ qj
j = 1,..., n
5
z
le quantità di prodotto trasportate sugli archi sono
sempre non negative
xij ≥ 0 i = 1,..,m; j = 1,..., n
z
(3)
Particolarità del problema:i coefficienti numerici
delle variabili sono tutti unitari
6
Il problema del
m n
min∑ ∑cijxij
trasporto
i=1
j=1
n
∑x ≤ p
i =1,...,m
(1)
∑x ≥q
j =1,...,n
(2)
xij ≥0
i =1,...,m; j =1,...,n (3)
j=1
ij
i
m
i=1
ij
j
z
E’ un problema di PL con variabili continue.
z
Può essere risolto con l’algoritmo del simplesso.
7
Forma bilanciata di un problema dei
trasporti
La forma bilanciata si ha quando la somma
delle richieste dei punti destinazione uguaglia
la somma delle disponibilità dei punti origine
D1
O1
O2
O3
D2
80
215
x12
x11
100
x21
108
x22
102
x31
2300
68
x32
1400
1000
1500
1200
8
Forma bilanciata di un problema dei
trasporti
La richiesta supera la disponibilità
D1
O1
O2
O3
Of
D2
80
215
x12
x11
100
x21
108
x22
102
x31
68
x32
cf1
xf1
2300
cf2
xf2
1400
900
1100
1200
500
Si introduce una origine fittizia con disponibilità
pari alla differenza tra richiesta e disponibilità
reali
9
Forma bilanciata di un problema dei
trasporti
Costo nullo
Costo del trasporto
tra origine fittizia e
destinazione reale
Costo di mancanza
dell’unità di prodotto
presso la
destinazione
Quantità spedita da origine fittizia ad ogni
destinazione: mancanza di prodotto presso la
destinazione
10
Forma bilanciata di un problema dei
trasporti
La disponibilità supera la richiesta
D2
D1
O1
O2
O3
80
215
x12
x11
100
x21
c1f
x1f
108
x22
102
x31
2000
Df
c2f
x2f
68
x32
1400
c3f
x3f
300
1000
1500
1200
Si introduce una destinazione fittizia con
richiesta pari alla differenza tra disponibilità e
richiesta reali
11
Forma bilanciata di un problema dei
trasporti
Costo nullo
Costo del trasporto
tra origine reale e
destinazione fittizia
Costo di stoccaggio
dell’unità di prodotto
presso l’origine
Quantità spedita da origine ad ogni
destinazione fittizia : eccesso di prodotto
presso l’origine
12
Possibili variazioni:
z
introduzione della massima capacità per gli archi;
z
non tutti i fornitori sono connessi a tutti i
destinatari;
z
il trasporto non avviene direttamente tra fornitore
e destinatario ma attraverso dei centri di raccolta
e distribuzione intermedi
13
Il Problema dei Trasbordi
•Problema dei trasporti: transito diretto dai punti
origine ai punti destinazione
•Problema dei trasbordi: ogni punto è in grado di
spedire e/o ricevere prodotto
B+1000
O1
O1
B+1500
O2
O2
B
B+1200
O3
O3
B
B
D1
D1
B+2300
B
D2
D2
B
B+1400
14
Il Problema dei Trasbordi
•Il passare dal problema dei trasporti al problema
dei trasbordi richiede l’incremento delle
disponibilità e delle richieste dei punti origine e
destinazione
B ≥ ∑i =1 pi = ∑ j =1 qi
m
n
15
Il Problema dei Trasbordi
O1
O1
O2
0
O3
130
D1
90
3700
0
3700
95
O3
80
215
100
108
102
68
1000
135
O2
D2
101
200
105
1300
0
3500
79
D1
99
1400
110
0
205
205
0
3700
200
D2
3700
107
3700
72
3700
6000
3700
5100
4700
2500
4900
3700
3700
per formulare il problema dei trasbordi occorre
definire i costi della movimentazione dai punti
destinazione ai punti origine del problema
originale
16
Il Problema dei Trasbordi
1000
1000
O1
D1
2300
1300
1500
O2
200
1200
O3
D2
1400
1400
17
Il Problema del carico macchina
lotti
macchine
1
2
m
1 q11
2 q21
q12
q22
q1m
q2 m
P1
P2
n qn1
qn 2
qnm
Pn
H1
H2
Hm
18
Il Problema del carico macchina
• È nota la produttività oraria del lotto i sulla
macchina j, pari a qij,
• Ogni lotto va prodotto in quantità nota pari a Pi
• Ogni macchina ha a disposizione un tempo per
effettuare le lavorazioni pari ad Hj
• Va determinato il piano di produzione per
realizzare le quantità stabilite dei lotti di
produzione sulle macchine disponibili
19
Il Problema del carico macchina
• Variabile del problema: tij tempo cha la
macchina j dedica alla lavorazione del lotto i
min ∑i =1
n
m
∑q
j =1
∑t
i =1
⋅ tij ≥ Pi
ij
n
ij
∑
≤ Hj
tij ≥ 0
m
t
j =1 ij
i = 1,2, K , n
j = 1,2, K , m
∀i, j
20
Il Problema del carico macchina
lotti
macchine
1
2
m
1 h11
2 h21
h12
h22
h1m
h2 m
n hn1
hn 2
hnm
H1
H2
Hm
21
Il Problema del carico macchina
• È nota il tempo complessivo hij per la
realizzazione del loto i sulla macchina j,
• Ogni lotto va prodotto interamente du una sola
macchina
• Ogni macchina ha a disposizione un tempo per
effettuare le lavorazioni pari ad Hj
• Va determinato il piano di produzione per
realizzare tutti i lotti di produzione sulle macchine
disponibili
22
Il Problema del carico macchina
• Variabile del problema: xij variabile binaria
(0;1) che indica se il lotto i viene o meno
prodotto sulla macchina j
min ∑i =1
n
m
∑x
j =1
ij
n
∑x
i =1
ij
∑
=1
m
i = 1,2, K , n
⋅ hij ≤ H j
xij binaria
x ⋅ hij
j =1 ij
j = 1,2, K , m
∀i, j
23
Il Problema dell’assegnamento
Un numero n di attività vanno svolte utilizzando n
risorse per la loro esecuzione
z
È noto il costo di esecuzione dell’attività i da parte
della risorsa j
z
z
Tutte le attività vanno svolte
Ogni risorsa è utilizzabile per l’esecuzione di una
sola attività
z
24
Il Problema dell’assegnamento
attività
risorse
1
2
n
1 c11
c12
c1m
1
2 c21
c22
c2 m
1
n cn1 cn 2
cnn
1
1
1
1
25
Il Problema dell’assegnamento
• Variabile del problema: xij variabile binaria
(0;1) che indica se l’attività i viene o meno
svolta dalla risorsa j
min ∑i =1
n
n
∑x
j =1
ij
n
∑x
i =1
ij
∑
=1
=1
xij binaria
n
x ⋅ cij
j =1 ij
i = 1,2,K , n
j = 1,2, K, n
∀i, j
26
I Problemi di ottimizzazione su rete
z
Il problema del percorso minimo
Va ricercato il percorso minimo per collegare un
punto origine ed un punto destinazione all’interno di
una rete
Presso il nodo iniziale vi è una disponibilità unitaria
I costi sono rappresentati dalla lunghezza degli archi
che collegano i diversi nodi
27
I Problemi di ottimizzazione su rete
z
Il problema del percorso minimo
La variabile xij del problema è di tipo binario ed
indica se l’arco di lunghezza dij che collega il nodo j
al nodo j verrà percorso
Ogni variabile corrisponde ad un arco
Ogni vincolo corrisponde ad un nodo
28
I Problemi di ottimizzazione su rete
z
Il problema del percorso minimo
min ∑
i, j
∑x
i≠ j
ij
∑x
=1
∑x
= ∑ xkj
1j
⋅ d ij
nodo origine
j
ik
i
∑x
nodi intermedi
j
jN
=1
nodo finale
j
xij binaria
∀i, j
29
I Problemi di ottimizzazione su rete
z
Il problema del percorso minimo
2
1
5
4
3
7
6
Nodo 1
x12 + x13 + x14 = 1
Nodo 4
x14 + x24 + x34 = x45 + x46
Nodo 7
x57 + x67 = 1
30
I Problemi di ottimizzazione su rete
2
Nodi destinazione
5
5
8
11
9
0
3
2
1
6
7
1
1
2
Nodi origine
3
5
1
0+B
1
4
3
0
2
0+B
1
9
4
0
2
23
7
9
1
0
5
1
8
6
0+B
3
0+B
5
0+B
1
1
0+B
0
0+B
10
0+B
0+B
0+B
1
B=1
31
I Problemi di ottimizzazione su rete
32
I Problemi di ottimizzazione su rete
z
Il problema del massimo flusso
Un nodo origine ed un nodo destinazione sono
collegati da una rete di archi unidirezionali,
caratterizzati da una capacità di flusso massima
L’obiettivo del problema consiste nella ricerca del
valore massimo del flusso dal nodo origine verso i
nodi destinazione
33
I Problemi di ottimizzazione su rete
z
Il problema del massimo flusso
1
7
4
0
2
9
6
5
8
3
Sorgente
Raffinerie
Stazioni di pompaggio
Terminali
Deposito
34
I Problemi di ottimizzazione su rete
z
Il problema del percorso minimo
La variabile Y del problema è il flusso che percorre la
rete dal nodo iniziale al nodo terminale della stessa
maz Z = Y
∑x
=Y
∑x
= ∑ xkj
1j
nodo origine
j
ik
i
∑x
nodi intermedi
j
jN
=Y
nodo finale
j
0 ≤ xij ≤ uij
∀i, j
35
Il Problema del commesso viaggiatore
• Sia dato un grafo formato da n vertici e da m
archi
• Il problema del commesso viaggiatore
consiste nel trovare il circuito a costo minimo
all’interno del grafo che a partire da un nodo
iniziale passi per tutti i nodi una sola volta
ritornando al nodo iniziale
• Sono noti i costi di percorrenza degli archi
• La variabile del problema di tipo binario
indica se un arco vada o meno percorso
36
Il Problema del commesso viaggiatore
• Variabile del problema: xij variabile binaria
(0;1) che indica se viene percorso l’arco che
collega il nodo i al nodo j
min ∑i =1
n
n
∑x
j =1
ij
n
∑x
i =1
ij
∑
=1
=1
xij binaria
n
j =1, j ≠ i
xij ⋅ cij
1
i = 1,2, K , n
j = 1,2, K , m
2
5
4
3
∀i, j
37
Il Problema del commesso viaggiatore
• Vincoli relativi alla condizione che a/da ogni
nodo si arrivi/si parta da/verso un solo nodo
• Vincoli relativi alla
presenza di sotto cicli
1
1
2
5
2
5
4
3
4
3
38
Un algoritmo risolutivo per il
problema del commesso viaggiatore
•La complessità del problema aumenta
all’aumentare delle dimensioni del grafo
(numero dei nodi)
•Esistono algoritmi risolutivi che forniscono
soluzioni “buone” (ma non ottime) con
ridotta complessità computazionale
•Algoritmo “closest insertion candidate”
39
Un algoritmo risolutivo per il
problema del commesso viaggiatore
•Se la matrice dei costi è simmetrica
(cik=cki) e se è soddisfatta la condizione di
triangolarità (cik ≤cil +clk) l’algoritmo
produce un valore della soluzione obiettivo
non superiore a due volte il valore ottimo
•Qualora le condizioni non fossero
rispettate si può applicare l’algoritmo più
volte a partire da nodi iniziali differenti
40
Un algoritmo risolutivo per il
problema del commesso viaggiatore
1
1M
2 10
3
3
4
4
5 20
6 12
2
3
4
5
6
10
3
4 20 12
M
8 15
4
7
8M
25 15
9
15 25 M
17
6
4 15 17 M
9
7
9
6
9M
Passo 2:inserimento de nodo J*, aggiornamento di c(J)
e dell'insieme Sa
si ricerchi il nodo i* Sp tale che, indicando con [i] il nodo
nella posizione i-esima nella sequenza parziale, si abbia
{C
Descrizione dell'algoritmo "closest insertion"
i∗ = min
Passo 0: inizializzazione
k =1
Sp = {1} Sa = {2,3,...,n}
[ i ]∈S p
i, J∗
+ C J∗ ,[i +1] − C [ i ],[i +1]
}
Per J=2,3,…,n si ponga c(J)=1
si aggiorni la sequenza
Passo 1:scelta del nuovo nodo
∀ J ∈ S a se min C J , J∗ , C J∗ , J < C J, c ( J )
J
∗
{C
= m in
J∈ S
e si p o n ga
J ,c ( J )
a
k = k + 1
S p = {S1 ,..., i∗ , J ∗ , i∗ + 1,...}
;C
c ( J ), j
}
{
}
si ponga c(J) = J∗
se k < N si ritorni al passo 2
41