15.2 Modelli PLI per il problema di lot sizing capacitato¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 15 · Capitolo 15: Problemi di lot sizing · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di lot sizing
Il problema di lot sizing capacitato e la sua istanza di riferimento (Esempio 8.1) sono definiti nel Capitolo 8 «Problemi di lot sizing», Sezione 8.2.
-
Il CLS ha due formulazioni: la formulazione big-\(M\) \(\mathrm{ILP}_{\mathrm{CLSP}}\) della Sezione 15.3 e la formulazione a cammino minimo \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\) della Sezione 15.5.
-
La Sezione 15.6 confronta i bound dei loro rilassamenti lineari sull'istanza di riferimento.
15.3 Una formulazione con un legame big-M¶
-
Dato un insieme \(T=\{1,2,\dots,m\}\) di periodi con domande \(d_t\), per \(j \le t\) scriviamo \(D_{j,t}=\sum_{k=j}^{t} d_k\) per la domanda totale dei periodi \(j,j+1,\dots,t\).
-
Introduciamo le seguenti variabili intere e variabili binarie, per ogni periodo \(t \in T\):
\[ x_t \in \Z_{\ge 0}~\text{(produzione)},\qquad s_t \in \Z_{\ge 0}~\text{(scorta alla fine del periodo)}, \]\[ y_t=\begin{cases} 1 & \text{se c'è un setup nel periodo $t$}\\[1.5ex] 0 & \text{altrimenti} \end{cases} \]La scorta all'inizio dell'orizzonte è la costante \(s_0\).
-
Le variabili di setup sono collegate alle quantità dall'implicazione logica
\[ x_t>0 ~~~\Longrightarrow~~~ y_t=1, \]modellata dal vincolo big-M \(x_t \le M_t\, y_t\), dove \(M_t\) è un upper bound sulla produzione del periodo \(t\).
-
Se si ignorano i setup, il piano migliore produce in ogni periodo esattamente la sua domanda: non ha scorte e, nell'istanza di riferimento, ha costo \(0\). È un lower bound molto debole: i costi di setup vanno modellati.
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing capacitato (CLS) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{CLSP}}\), o formulazione big-M.
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{CLSP}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLS-1}\) minimizza il costo dei setup, della produzione e del mantenimento a scorta;
-
i vincoli \(\eqref{CL1:bal}\) sono i vincoli di bilanciamento del flusso: la domanda del periodo \(t\) è soddisfatta dalla produzione del periodo e dalla scorta del periodo precedente, e l'eccedenza diventa la scorta alla fine del periodo \(t\) (\(m\) vincoli lineari);
-
i vincoli \(\eqref{CL1:M}\) collegano le quantità con i setup, e i vincoli \(\eqref{CL1:cap}\) sono i vincoli di capacità (\(m\) vincoli lineari ciascuno);
-
il vincolo \(\eqref{CL1:end}\) impone una scorta vuota all'inizio e alla fine dell'orizzonte;
-
infine, i vincoli \(\eqref{CL1:int}\), \(\eqref{CL1:ints}\) e \(\eqref{CL1:bin}\) definiscono le variabili del modello PLI.
-
15.3.1 Valori deboli e forti di big-M¶
-
Un valore debole. Poiché \(s_m=0\) e le scorte sono non negative, la produzione del periodo \(t\) non può superare la domanda dei periodi \(t,\dots,m\): \(M^{\mathrm{dem}}_{t}=D_{t,m}\) è un valore valido.
-
Un secondo valore. Per i vincoli di capacità \(\eqref{CL1:cap}\), anche \(M^{\mathrm{cap}}_{t}=cap_t\) è valido.
-
Un valore forte. Il valore migliore è il più piccolo dei due:
\[ M_t=\min\left\{cap_t,~D_{t,m}\right\}. \]
Più piccolo è il valore di big-M, più forte è il rilassamento lineare: il vincolo \(x_t \le M_t y_t\) taglia i valori frazionari di \(y_t\) inferiori a \(x_t/M_t\). Un valore troppo piccolo, però, taglia piani ammissibili.
Esempio 15.1: L'istanza di riferimento
Consideriamo \(m=5\) periodi, con i seguenti dati:
| periodo \(t\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| domanda \(d_t\) | \(2\) | \(1\) | \(3\) | \(4\) | \(1\) |
| capacità \(cap_t\) | \(4\) | \(4\) | \(4\) | \(4\) | \(4\) |
| costo di setup \(sc_t\) | \(50\) | \(50\) | \(50\) | \(50\) | \(50\) |
| costo di produzione \(vc_t\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| costo di mantenimento \(hc_t\) | \(10\) | \(10\) | \(10\) | \(10\) | \(10\) |
È l'istanza dell'Esempio 8.1 del Capitolo 8 «Problemi di lot sizing». I valori di big-M sono:
| periodo \(t\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(M^{\mathrm{dem}}_t = D_{t,5}\) | \(11\) | \(9\) | \(8\) | \(5\) | \(1\) |
| \(M^{\mathrm{cap}}_t = cap_t\) | \(4\) | \(4\) | \(4\) | \(4\) | \(4\) |
| \(M_t\) | \(4\) | \(4\) | \(4\) | \(4\) | \(1\) |
Chiamiamo questa istanza del CLS Esempio 15.1.
Esempio 15.2: Modello \(\mathrm{ILP}_{\mathrm{CLSP}}\)
Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}\) con i valori forti di big-M per l'istanza del CLS dell'Esempio 15.1 è (\(s_0=0\) è una costante e non compare):
Una soluzione ottima \((\tilde{\vet y},\tilde{\vet x},\tilde{\vet s})(\mathrm{ILP}_{\mathrm{CLSP}})\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}})\) è \(3\cdot 50+3\cdot 10=180\), il costo del piano ottimo trovato per enumerazione nel Capitolo 8 «Problemi di lot sizing». I valori deboli di big-M danno la stessa soluzione ottima.
15.4 Il rilassamento lineare della formulazione big-M¶
Per ottenere un rilassamento lineare (LP) del modello \(\mathrm{ILP}_{\mathrm{CLSP}}\), rilassiamo i vincoli \(\eqref{CL1:int}\)–\(\eqref{CL1:bin}\) in vincoli di non negatività e nei bound \(y_t\le 1\). Il modello LP ottenuto è il seguente:
Questo modello LP si chiama modello \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{dem}}\), \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{cap}}\) o \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{strong}}\), quando i valori di big-M sono \(M^{\mathrm{dem}}_t\), \(M^{\mathrm{cap}}_t\) o i valori forti \(M_t\).
Esempio 15.3: Valori di big-M e bound LP
Il modello LP (15.2) per l'istanza del CLS dell'Esempio 15.1 è:
con i valori \(M_1,\dots,M_5\) della tabella dell'Esempio 15.1. Le tre scelte danno le seguenti soluzioni ottime \((\tilde{\vet y},\tilde{\vet x},\tilde{\vet s})\), con \(\tilde s_5=0\):
| Modello | \(\tilde{\vet y}\) | \(\tilde{\vet x}\) | \((\tilde s_1,\dots,\tilde s_4)\) | valore ottimo |
|---|---|---|---|---|
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{dem}}\) | \((\frac{2}{11},\frac{1}{9},\frac{1}{2},\frac{4}{5},0)\) | \((2,1,4,4,0)\) | \((0,0,1,1)\) | \(\frac{9865}{99}\approx 99.65\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{cap}}\) | \((\frac{1}{2},\frac{1}{4},\frac{3}{4},1,\frac{1}{4})\) | \((2,1,3,4,1)\) | \((0,0,0,0)\) | \(\frac{275}{2}=137.5\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{strong}}\) | \((\frac{1}{2},\frac{1}{4},1,1,0)\) | \((2,1,4,4,0)\) | \((0,0,1,1)\) | \(\frac{315}{2}=157.5\) |
In ogni soluzione \(\tilde y_t=\tilde x_t/M_t\): più piccolo è \(M_t\), maggiore è il costo dei setup pagato dal rilassamento. La soluzione ottima intera dell'Esempio 15.2 ha valore \(z(\mathrm{ILP}_{\mathrm{CLSP}})=180\).
15.5 Una formulazione a cammino minimo¶
-
La seconda formulazione non decide direttamente le quantità. Per ogni \(t,k \in T\), con \(k \ge t\), introduciamo la seguente variabile continua: \(zv_{tk} \ge 0\), la frazione della domanda \(D_{t,k}\) dei periodi \(t,\dots,k\) prodotta nel periodo \(t\).
-
Produrre nel periodo \(t\) la domanda dei periodi \(t,\dots,k\) costa la produzione di \(D_{t,k}\) unità e il mantenimento a scorta delle unità che attendono il loro periodo:
\[ cv_{tk}=vc_{t}\;D_{t,k}+\sum_{s=t+1}^{k}\sum_{u=t}^{s-1}hc_{u}\,d_{s}. \]
Usando queste variabili e le variabili binarie \(y_t\), un modello di programmazione lineare intera mista (MIP) per il CLS è il seguente:
Questo modello MIP si chiama modello \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\), o formulazione a cammino minimo.
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLS-2}\) minimizza il costo dei setup e degli archi del piano;
-
i vincoli \(\eqref{SP1}\) e \(\eqref{SP2}\) sono i vincoli di flusso di una rete (\(m\) vincoli lineari);
-
i vincoli \(\eqref{SP3}\) impongono il setup se il prodotto è prodotto nel periodo \(t\), e i vincoli \(\eqref{SP4}\) impongono le capacità (\(m\) vincoli lineari ciascuno);
-
infine, i vincoli \(\eqref{SP5}\) e \(\eqref{SP6}\) definiscono le variabili del modello MIP.
-
-
La rete è disegnata nella Figura \(\ref{fig:CLS-SP}\): i nodi sono \(0,1,\dots,m\), e la variabile \(zv_{tk}\) è l'arco dal nodo \(t-1\) al nodo \(k\), con costo \(cv_{tk}\). Un'unità di flusso esce dal nodo \(0\) (vincolo \(\eqref{SP1}\)), e il flusso si conserva negli altri nodi (vincoli \(\eqref{SP2}\)).
-
Un cammino dal nodo \(0\) al nodo \(m\) è un piano che produce solo quando la scorta è vuota: ogni arco \((t-1,k)\) è una produzione nel periodo \(t\) per i periodi \(t,\dots,k\). Per questo la formulazione si chiama formulazione a cammino minimo: rilassate le capacità, il piano ottimo è un cammino minimo.
-
I vincoli \(\eqref{SP3}\) collegano gli archi con i setup con il coefficiente \(1\) invece di un valore di big-M. Nei vincoli \(\eqref{SP4}\) la quantità prodotta nel periodo \(t\) è \(x_t=\sum_{k} D_{t,k}\,zv_{tk}\).
-
I cammini sono i mattoni elementari, e un piano che non è un cammino è una combinazione di cammini: le quantità sono intere, ma le variabili \(zv_{tk}\) possono essere frazionarie.
Rete delle variabili \(zv_{tk}\) per \(m=3\): la variabile \(zv_{tk}\) è l'arco dal nodo \(t-1\) al nodo \(k\).
Esempio 15.4: Modello \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\) e combinazioni di cammini
Per l'istanza del CLS dell'Esempio 15.1 le domande \(D_{t,k}\) e i costi \(cv_{tk}\) sono (il costo di produzione è nullo, quindi \(cv_{tk}\) è solo costo di mantenimento a scorta):
Il modello \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\) per questa istanza è:
Una soluzione ottima \((\tilde{\vet{zv}},\tilde{\vet y})(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}})\) è:
e tutte le altre variabili \(zv_{tk}\) sono nulle. È il piano ottimo \(\tilde{\vet x}=(3,0,4,4,0)\), che non è un cammino: nel periodo \(3\) produce \(4\) unità, più della domanda \(3\) del periodo \(3\) e meno della domanda \(7\) dei periodi \(3\) e \(4\). È la combinazione, con pesi \(\tfrac{4}{5}\) e \(\tfrac{1}{5}\), dei cammini \(0\to2\to3\to5\) (piano \((3,0,3,5,0)\)) e \(0\to2\to5\) (piano \((3,0,8,0,0)\)). Le quantità sono \(x_1=D_{1,2}\,zv_{12}=3\), \(x_3=3\cdot\tfrac{4}{5}+8\cdot\tfrac{1}{5}=4\) e \(x_4=5\cdot\tfrac{4}{5}=4\). Il valore ottimo \(z(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}})\) è
Per ottenere un rilassamento lineare del modello \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\), rilassiamo i vincoli \(\eqref{SP6}\) nei bound \(0\le y_t\le 1\). Il modello LP ottenuto è il seguente:
Questo modello LP si chiama modello \(\mathrm{LP}^{\mathrm{SP}}_{\mathrm{CLSP}}\).
Esempio 15.5: Modello \(\mathrm{LP}^{\mathrm{SP}}_{\mathrm{CLSP}}\)
Il modello \(\mathrm{LP}^{\mathrm{SP}}_{\mathrm{CLSP}}\) per l'istanza del CLS dell'Esempio 15.1 è:
Una soluzione ottima \((\tilde{\vet{zv}},\tilde{\vet y})(\mathrm{LP}^{\mathrm{SP}}_{\mathrm{CLSP}})\) è:
e tutte le altre variabili \(zv_{tk}\) sono nulle: sono gli archi del piano ottimo, con il setup del periodo \(4\) pagato solo per la frazione \(\tfrac{4}{5}\). Il valore ottimo \(z(\mathrm{LP}^{\mathrm{SP}}_{\mathrm{CLSP}})\) è \(180-\tfrac{1}{5}\cdot 50=170\).
15.6 Confronto fra le formulazioni¶
-
Le formulazioni hanno lo stesso valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}})=z(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}})=180\), ma i loro rilassamenti lineari hanno valori ottimi diversi. Sull'istanza di riferimento i lower bound, calcolati con l'algoritmo del simplesso in aritmetica esatta e verificati con Gurobi, sono i seguenti.
-
L'ultima colonna è il gap del Capitolo 1 «Problemi di ottimizzazione combinatoria» fra il bound e il valore ottimo; non è definito per il bound \(0\).
| Modello | Lower bound | Gap \(\frac{180-\LB}{\LB}\) |
|---|---|---|
| Senza setup | \(0\) | non definito |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{dem}}\) (\(M_t=D_{t,m}\)) | \(99.65\) | \(80.6\%\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{cap}}\) (\(M_t=cap_t\)) | \(137.50\) | \(30.9\%\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{strong}}\) (\(M_t=\min\{cap_t,D_{t,m}\}\)) | \(157.50\) | \(14.3\%\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{SP}}\) (cammino minimo) | \(170\) | \(5.9\%\) |
-
Il bound \(170\) della formulazione a cammino minimo è il valore ottimo del problema senza capacità (piano \((3,0,8,0,0)\), di costo \(170\)): i vincoli di capacità \(\eqref{LPSP4}\) agiscono solo sulle quantità, e una combinazione di cammini può soddisfarli.
-
Il prezzo della formulazione a cammino minimo è la sua dimensione: ci sono \(O(m^2)\) variabili \(zv_{tk}\), contro le \(O(m)\) variabili della formulazione big-M.
Avanti: 15.7 Modelli PLI per le varianti