Modelli e Algoritmi della Logistica
Lezione - 18
Programmazione della Produzione
ANTONIO SASSANO
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Roma, 25-11-01
Programmazione della Produzione - Ipotesi
• Modello Deterministico
• Controllo Discreto [ 1,2,3,...,T ]
• Singolo bene
• Domanda Variabile nel tempo
d2 d3
d5
d1
dT
d4
[d1,d2,d3,...,dT]
di>0
1 2 3 4 5
T
• Funzioni Costo (Produzione e Stoccaggio) Variabili nel tempo
(es: Produrre nel periodo k costa meno che nel periodo h)
• “Lead time” nullo (il bene prodotto è immediatamente disponibile)
Programmazione della Produzione - Obiettivo
Determinare:
1. Quantità x1,x2,... da produrre in ciascun periodo
2. Quantità s1,s2,... da immagazzinare in ciascun periodo
con l’obiettivo di soddisfare la domanda e minimizzare i costi di
produzione e stoccaggio
x1
s0
1
s1
d1
x2
2
s2
d2
x3
3
s3
d3
xk
...
sk-1
k
xT
sk
dk
...
sT-1
T
sT
dT
• s0 Giacenza di magazzino all’inizio dell’orizzonte temporale
• sT Giacenza di magazzino alla fine dell’orizzonte temporale
Programmazione della Produzione - Costi
Costo di Produzione nel periodo t
ct ( x t )
Ct( xt )=Ath( xt )+ ct( xt )
At
xt
Costo di Stoccaggio nel periodo t
Ht( st )= pth( st )+bth( -st )+ ht( st )
ht( st )
ht( st )
bt pt
st
Programmazione della Produzione - Modello
x1
s0
1
s1
d1
x2
2
x3
s2
d2
3
s3
xk
...
d3
sk-1
k
xT
sk
...
dk
T
min f ( x, s ) =  (Ct ( xt )  H t ( st ))
t =1
xk + sk-1 - sk = dk
k = 1,...,T
x k , sk > 0
k = 1,...,T
sk > 0 = “no backlogging”
sT-1
T
sT
dT
Programmazione della Produzione - Modello
T
min f ( x, s ) =  (Ct ( xt )  H t ( st ))
t =1
xk + sk-1 - sk = dk
x k , sk > 0
k = 1,...,T
k = 1,...,T
Problema di Programmazione Concava con Vincoli Lineari
min f ( x, s )
 x
A  = b
s
 x
   02T -1
s
Funzione concava
p
p
k =1
k =1
f (  uk vk )   uk f (vk )
Forma standard
Programmazione della Produzione - Soluzioni
xk + sk-1 - sk = dk
30
0
1
30
2
30
0
30
40
70
3
4
30
20
30
0
10
30
2
20
4
10
20
1
40
3
10
20
k = 1,...,T
40
0
30
Programmazione della Produzione - Soluzioni
min f ( x, s )
 x
  = y
s
 x
A  = b
s
 x
   02T -1
s
min f ( y )
Ay = b
y  02T -1
Teorema: L’insieme delle soluzioni ammissibili del problema di
Programmazione della Produzione:
P = y  
2T -1
: Ay = b, y  02T -1
è un poliedro limitato (politopo).

Programmazione della Produzione - Soluzioni
P = y  
2T -1
: Ay = b, y  02T -1

Politopo
y
y è un vertice di P se e solo se è una
soluzione di base ammissibile (SBA)
• SBA definita da una sottomatrice quadrata nonsingolare B di A
By B  NyN = b, yB  0T , yN  0T -1
 yB = B -1b  0T

 y N = 0T -1
SBA definita da B
• Una SBA ha al più T componenti diverse da zero
Programmazione della Produzione - Soluzioni
Perchè i vertici (SBA) sono importanti?
Teorema: Un problema con funzione obiettivo concava f(y) e regione
ammissibile costituita da un politopo (non vuoto) ha sempre una
soluzione ottima su un vertice.
Dimostrazione:
y* soluzione ottima ( f(y*)< f(y) per ogni yP)
Ext(P)=v1,v2,...,vp vertici di P (v*: f(v*)< f(v) per ogni v Ext(P))
p
y* =  uk vk ; uk  0;
k =1
p
u
k
=1
k =1
p
p
p
k =1
k =1
k =1
f ( y*) = f (  uk vk )   uk f ( vk )   uk f ( v*) = f ( v*)
concavità
v* soluzione ottima
CVD.
Programmazione della Produzione - Soluzioni
Possiamo limitare la ricerca della soluzione ottima alle SBA !
Come caratterizzare (e riconoscere) una SBA ?
30
0
1
30
2
0
4
10
30
20
1
20
3
10
20
40
30
40
30
2
70
3
4
30
20
30
0
10
Soluzione
ammissibile
non di base
40
0
30
Soluzione
ammissibile
di base (SBA)
Programmazione della Produzione - Soluzioni
 yB = B -1b  0T

 y N = 0T -1
SBA definita da B
• Una SBA ha al più T componenti diverse da zero
xk
...
sk-1
k
sk
...
dk
In ogni periodo k deve essere:
xk+sk-1>0
Una soluzione ha almeno T componenti diverse da zero
• Una SBA ha esattamente T componenti diverse da zero
Programmazione della Produzione - Soluzioni
• Una SBA ha esattamente T componenti diverse da zero
xk
...
sk-1
k
sk
dk
In ogni periodo k deve essere:
...
xk+sk-1>0
In ognuno dei T periodi esattamente una delle variabili xk ,sk-1
è diversa da zero (xk  sk-1=0)
Se (x,s) è una SBA, in ogni periodo k abbiamo uno dei due casi:
1. Produzione positiva (xk > 0) e Scorte nulle (sk-1=0)
2. Produzione nulla (xk =0) e Scorte positive (sk-1>0)
Programmazione della Produzione - Soluzioni
Se (x,s) è una SBA, in ogni periodo k abbiamo uno dei due casi:
1. Produzione positiva (xk > 0) e Scorte nulle (sk-1=0)
2. Produzione nulla (xk =0) e Scorte positive (sk-1>0)
• k[1,...,T ] è un periodo produttivo se xk > 0
• La domanda di un periodo non produttivo h è soddisfatta dalla
produzione nell’ultimo periodo produttivo k<h.
50
0
1
70
2
30
3
4
30
0
30
40
30
20
• L’insieme di periodi (non produttivi) la cui domanda è soddisfatta da
uno specifico periodo produttivo viene detto intervallo di produzione
• All’inizio e alla fine di un intervallo di produzione la giacenza è nulla