15.7 Modelli PLI per le varianti¶
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
I problemi di questa sezione sono le varianti del problema di lot sizing capacitato definite nel Capitolo 8 «Problemi di lot sizing», Sezione 8.6. Ogni sottosezione scrive il modello PLI di una variante, nell'ordine di quel capitolo.
15.7.1 Il problema di lot sizing senza capacità¶
-
Dato un insieme \(T=\{1,2,\dots,m\}\) di periodi con domande \(d_t\) e senza capacità vincolante, introduciamo, per ogni periodo \(t \in T\), le seguenti variabili intere e variabili binarie:
\[ 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} \] -
Poiché \(s_m=0\), la produzione del periodo \(t\) vale al più la domanda \(D_{t,m}\) dei periodi \(t,\dots,m\): questo è il valore di big-M del legame fra \(x_t\) e \(y_t\).
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing senza capacità (ULS) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{ULS}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{ULS}}\):
-
la funzione obiettivo lineare \(\eqref{ULS:obj}\) minimizza il costo dei setup, della produzione e del mantenimento a scorta;
-
i vincoli \(\eqref{ULS:bal}\) sono i vincoli di bilanciamento del flusso (\(m\) vincoli lineari);
-
i vincoli \(\eqref{ULS:big}\) impongono un setup in ogni periodo con produzione positiva (\(m\) vincoli lineari);
-
il vincolo \(\eqref{ULS:end}\) impone una scorta vuota all'inizio e alla fine dell'orizzonte;
-
infine, i vincoli \(\eqref{ULS:domx}\)–\(\eqref{ULS:domy}\) definiscono le variabili del modello PLI.
-
-
Il modello \(\mathrm{ILP}_{\mathrm{ULS}}\) è il modello \(\mathrm{ILP}_{\mathrm{CLSP}}\) senza i vincoli di capacità (15.1d) e con i valori di big-M \(M_t=D_{t,m}\). L'algoritmo di PD di Wagner e Whitin del Capitolo 25 «PD per il problema di lot sizing senza capacità» risolve l'ULS in tempo polinomiale.
Esempio 15.6: Modello \(\mathrm{ILP}_{\mathrm{ULS}}\)
Consideriamo l'istanza del CLS dell'Esempio 15.1 senza le capacità: le domande sono \(\vet d=(2,1,3,4,1)\), i costi di setup \(sc_t=50\), i costi di mantenimento \(hc_t=10\), e \(vc_t=0\). I valori di big-M sono \(D_{t,5}=(11,9,8,5,1)\), e il modello \(\mathrm{ILP}_{\mathrm{ULS}}\) per questa istanza dell'ULS è:
Una soluzione ottima \((\tilde{\vet y},\tilde{\vet x},\tilde{\vet s})(\mathrm{ILP}_{\mathrm{ULS}})\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{ULS}})\) è \(2\cdot 50+(1+5+1)\cdot 10=170\), il bound della formulazione a cammino minimo del CLS. La soluzione ottima non è unica: anche il piano \((3,0,3,5,0)\), con tre setup e le scorte \((1,0,0,1,0)\), costa \(3\cdot 50+2\cdot 10=170\).
15.7.2 Più prodotti e tempi di setup¶
-
Un insieme \(P\) di prodotti condivide la risorsa di ogni periodo. Scriviamo \(d_{pt}\), \(sc_{pt}\), \(vc_{pt}\) e \(hc_{pt}\) per i dati del prodotto \(p \in P\) nel periodo \(t \in T\). Produrre un'unità di \(p\) richiede il tempo \(vt_{pt} \in \Z_{\ge 1}\), un setup richiede il tempo \(st_{pt} \in \Z_{\ge 0}\), e la capacità \(cap_t\) è un tempo. Per \(j\le k\) scriviamo \(sd_{pjk}=\sum_{u=j}^{k} d_{pu}\) per la domanda del prodotto \(p\) nei periodi \(j,\dots,k\).
-
Introduciamo, per ogni prodotto \(p \in P\) e ogni periodo \(t \in T\), le seguenti variabili intere e variabili binarie:
\[ x_{pt} \in \Z_{\ge 0}~\text{(produzione)},\qquad s_{pt} \in \Z_{\ge 0}~\text{(scorta alla fine del periodo)}, \]\[ y_{pt}=\begin{cases} 1 & \text{se c'è un setup del prodotto $p$ nel periodo $t$}\\[1.5ex] 0 & \text{altrimenti} \end{cases} \]Le scorte all'inizio dell'orizzonte sono le costanti \(s_{p0}=0\).
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing con più prodotti e tempi di setup (MLS) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLSPm}\) minimizza il costo dei setup, della produzione e del mantenimento a scorta di tutti i prodotti;
-
i vincoli \(\eqref{CLSPm:bal}\) sono i vincoli di bilanciamento del flusso di ogni prodotto (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPm:cap}\) impongono che i tempi di setup e i tempi di produzione di ogni periodo non superino la sua capacità (\(m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPm:M}\) collegano le quantità con i setup (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPm:end}\) impongono una scorta vuota all'inizio e alla fine dell'orizzonte;
-
infine, i vincoli \(\eqref{CLSPm:x}\)–\(\eqref{CLSPm:y}\) definiscono le variabili del modello PLI.
-
-
Un setup di \(p\) nel periodo \(t\) lascia il tempo \(cap_t-st_{pt}\) per la produzione, e \(s_{pm}=0\) limita la produzione alla domanda residua. Il valore forte di big-M è
\[ M_{pt}=\min\left\{\left\lfloor\frac{cap_t-st_{pt}}{vt_{pt}}\right\rfloor,~sd_{ptm}\right\}. \] -
I prodotti interagiscono solo attraverso i vincoli di capacità \(\eqref{CLSPm:cap}\): senza di essi, il modello si scompone in \(|P|\) modelli indipendenti a un solo prodotto.
Esempio 15.7: Modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\)
Consideriamo \(|P|=2\) prodotti e \(m=3\) periodi, con capacità \(cap_t=9\), tempi di produzione \(vt_{pt}=1\), tempi di setup \(st_{pt}=1\), costi di mantenimento \(hc_{pt}=5\) e costi di produzione \(vc_{pt}=0\). I costi di setup sono \(sc_{1t}=30\) e \(sc_{2t}=40\), e le domande sono:
| prodotto \(1\) | prodotto \(2\) | |||||
|---|---|---|---|---|---|---|
| periodo \(t\) | \(1\) | \(2\) | \(3\) | \(1\) | \(2\) | \(3\) |
| \(d_{pt}\) | \(3\) | \(2\) | \(4\) | \(2\) | \(4\) | \(1\) |
| \(sd_{ptm}\) | \(9\) | \(6\) | \(4\) | \(7\) | \(5\) | \(1\) |
| \(M_{pt}\) | \(8\) | \(6\) | \(4\) | \(7\) | \(5\) | \(1\) |
Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) con i valori forti di big-M per questa istanza è:
Una soluzione ottima \((\tilde{\vet y},\tilde{\vet x},\tilde{\vet s})(\mathrm{ILP}_{\mathrm{CLSP}}^{P})\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}}^{P})\) è \(2\cdot 30+2\cdot 40+(2+1)\cdot 5=155\), e la soluzione ottima è unica (Gurobi). Il periodo \(1\) usa tutta la sua capacità, \(5+2+1+1=9\). Senza i vincoli di capacità il prodotto \(2\) sarebbe prodotto solo nel periodo \(1\), con valore \(140\): questo piano richiede il tempo \(5+7+1+1=14>9\).
15.7.3 Scorta iniziale¶
-
I dati sono quelli del problema di lot sizing con più prodotti e tempi di setup. In più, la scorta iniziale del prodotto \(p\) è una decisione, acquistata al costo \(fc_p\) per unità.
-
Introduciamo le variabili intere \(x_{pt}\), \(s_{pt}\) e le variabili binarie \(y_{pt}\) del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) e, per ogni prodotto \(p\in P\), la seguente variabile intera:
\[ si_p \in \Z_{\ge 0}~\text{(scorta del prodotto $p$ all'inizio dell'orizzonte)}. \]
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing con scorta iniziale (LS-SI) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLSP}\) minimizza il costo della scorta iniziale, dei setup, della produzione e del mantenimento a scorta;
-
i vincoli \(\eqref{CLSP:bal1}\) e \(\eqref{CLSP:bal}\) sono i vincoli di bilanciamento del flusso di ogni prodotto, con la scorta iniziale \(si_p\) nel primo periodo (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSP:cap}\) impongono che i tempi di setup e i tempi di produzione di ogni periodo non superino la sua capacità (\(m\) vincoli lineari); i vincoli \(\eqref{CLSP:M}\) collegano le quantità con i setup (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSP:end}\) impongono una scorta vuota alla fine dell'orizzonte (\(|P|\) vincoli lineari);
-
infine, i vincoli \(\eqref{CLSP:x}\)–\(\eqref{CLSP:y}\) definiscono le variabili del modello PLI.
-
-
Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) è il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) con le variabili \(si_p\) al posto delle costanti \(s_{p0}=0\), e con il loro costo nella funzione obiettivo; i valori forti di big-M \(M_{pt}\) sono gli stessi.
Esempio 15.8: Modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\)
Consideriamo \(|P|=2\) prodotti e \(m=3\) periodi, con capacità \(cap_1=2500\), \(cap_2=2100\), \(cap_3=2500\), i costi della scorta iniziale \(fc_1=fc_2=3000\) e i costi di setup \(sc_{pt}=10000\). Gli altri dati sono:
| prodotto \(1\) | prodotto \(2\) | |||||
|---|---|---|---|---|---|---|
| periodo \(t\) | \(1\) | \(2\) | \(3\) | \(1\) | \(2\) | \(3\) |
| \(d_{pt}\) | \(100\) | \(200\) | \(10\) | \(10\) | \(100\) | \(150\) |
| \(vt_{pt}\) | \(20\) | \(10\) | \(10\) | \(10\) | \(5\) | \(5\) |
| \(st_{pt}\) | \(100\) | \(100\) | \(100\) | \(110\) | \(110\) | \(110\) |
| \(hc_{pt}\) | \(110\) | \(100\) | \(100\) | \(105\) | \(105\) | \(105\) |
| \(vc_{pt}\) | \(1100\) | \(1000\) | \(1000\) | \(900\) | \(800\) | \(800\) |
I valori di big-M sono:
| periodo \(t\) | \(1\) | \(2\) | \(3\) | \(1\) | \(2\) | \(3\) |
|---|---|---|---|---|---|---|
| \(sd_{ptm}\) | \(310\) | \(210\) | \(10\) | \(260\) | \(250\) | \(150\) |
| \(\lfloor (cap_t-st_{pt})/vt_{pt} \rfloor\) | \(120\) | \(200\) | \(240\) | \(239\) | \(398\) | \(478\) |
| \(M_{pt}\) | \(120\) | \(200\) | \(10\) | \(239\) | \(250\) | \(150\) |
Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) con i valori forti di big-M per questa istanza è:
Una soluzione ottima del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) è:
con un setup in ogni periodo tranne che per il prodotto \(2\) nel periodo \(2\). Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}})\) è \(677\,400\), e la soluzione ottima è unica (Gurobi). Il prodotto \(1\) parte con \(41\) unità acquistate all'inizio dell'orizzonte, perché il periodo \(1\) non ha il tempo di produrre tutta la sua domanda.
Per ottenere un rilassamento lineare del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\), rilassiamo i vincoli \(\eqref{CLSP:x}\)–\(\eqref{CLSP:y}\) in vincoli di non negatività e nei bound \(y_{pt}\le 1\). Il modello LP ottenuto è il seguente:
Questo modello LP si chiama modello \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{SI}}\).
-
Nella formulazione a cammino minimo ogni prodotto ha la sua rete, con una variabile continua aggiuntiva \(w_{pt}\ge 0\), l'arco dal nodo \(0\) al nodo \(t\), per la frazione della scorta iniziale che copre le domande dei primi \(t\) periodi. I costi degli archi sono
\[ cv_{ptk}=vc_{pt}\,sd_{ptk}+\sum_{s=t+1}^{k}\sum_{u=t}^{s-1}hc_{pu}\,d_{ps}, \qquad ci_{pt}=fc_p\,sd_{p1t}+\sum_{s=2}^{t}\sum_{u=1}^{s-1}hc_{pu}\,d_{ps}. \]
Usando queste variabili, un modello di programmazione lineare intera mista (MIP) per il problema di lot sizing con scorta iniziale (LS-SI) è il seguente:
Questo modello MIP si chiama modello \(\mathrm{MIP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\). Rilassando i vincoli \(\eqref{CLSPSP7}\) in \(0\le y_{pt}\le 1\) ed eliminando i vincoli \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) otteniamo il modello LP chiamato modello \(\mathrm{LP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{MIP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLSP-SP}\) minimizza il costo dei setup, della scorta iniziale e degli archi dei piani di tutti i prodotti;
-
i vincoli \(\eqref{CLSPSP1}\) e \(\eqref{CLSPSP2}\) sono i vincoli di flusso della rete di ogni prodotto, con gli archi \(w_{pt}\) della scorta iniziale uscenti dal nodo \(0\) (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPSP3}\) impongono il setup del prodotto \(p\) nel periodo \(t\) se questo è prodotto (\(|P|\,m\) vincoli lineari), e i vincoli \(\eqref{CLSPSP4}\) impongono le capacità, tempi di setup compresi (\(m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) mantengono intere le quantità e le scorte iniziali;
-
infine, i vincoli \(\eqref{CLSPSP5}\)–\(\eqref{CLSPSP7}\) definiscono le variabili del modello MIP.
-
-
La quantità prodotta è \(x_{pt}=\sum_{k=t}^{m} sd_{ptk}\,zv_{ptk}\), e la scorta iniziale è \(si_p=\sum_{t\in T} sd_{p1t}\,w_{pt}\): i vincoli \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) le mantengono intere, come nel modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\).
-
Con un solo prodotto e \(vt_t=1\) questi vincoli non servono: fissati i setup, resta un problema di flusso di costo minimo, che ha una soluzione ottima intera.
-
Con più prodotti e tempi di produzione \(vt_{pt}>1\), una quantità frazionaria può usare meglio la capacità. Senza i vincoli \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) il modello è solo un rilassamento del problema, e il suo valore ottimo può essere minore di \(z(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}})\) (Esempio 15.9).
Esempio 15.9: Lower bound con due prodotti
Per l'istanza dell'Esempio 15.8, ignorando i setup (nei costi e nelle capacità), il valore ottimo è \(575400\), raggiunto dalla soluzione intera \(x_{11}=120\), \(x_{12}=160\), \(x_{13}=10\), \(x_{21}=10\), \(x_{22}=100\), \(x_{23}=150\), \(s_{11}=40\), \(si_1=20\). I lower bound e il valore ottimo delle formulazioni sono:
| Modello | Valore |
|---|---|
| Senza setup | \(575\,400.00\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) con \(M_{pt}=sd_{ptm}\) | \(638\,882.20\) |
| \(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) con gli \(M_{pt}\) forti | \(651\,267.37\) |
| \(\mathrm{LP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\) | \(668\,928.57\) |
| \(\mathrm{MIP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\) senza \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) | \(676\,450.00\) |
| \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) e \(\mathrm{MIP}^{\mathrm{SP},\mathrm{SI}}_{\mathrm{CLSP}}\) (ottimo intero) | \(677\,400\) |
Senza i vincoli \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\) il modello a cammino minimo raggiunge \(676\,450\) con gli stessi setup e le quantità frazionarie \(x_{11}=59.5\) e \(si_1=40.5\): il periodo \(1\) usa allora tutta la sua capacità, \(100+20\cdot 59.5+110+10\cdot 110=2500\).
15.7.4 Straordinari¶
-
I dati sono quelli del problema di lot sizing con più prodotti e tempi di setup, ma il tempo di ogni periodo non è una capacità fissa: nel periodo \(t\) il tempo di lavoro in orario normale costa \(cw_t\) per unità, fino a \(cap^{N}_t\), e lo straordinario costa \(co_t\) per unità, fino a \(cap^{O}_t\).
-
Introduciamo le variabili intere \(x_{pt}\), \(s_{pt}\) e le variabili binarie \(y_{pt}\) del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) e, per ogni periodo \(t\in T\), le seguenti variabili intere:
\[ \mu_t \in \Z_{\ge 0}~\text{(tempo di lavoro in orario normale)},\qquad \nu_t \in \Z_{\ge 0}~\text{(straordinario)}. \]Poiché i tempi \(vt_{pt}\) e \(st_{pt}\) sono interi, i tempi di lavoro si possono prendere interi.
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing con straordinari (LS-OT) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLSPo}\) aggiunge ai costi del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) il costo del tempo di lavoro in orario normale e in straordinario;
-
i vincoli \(\eqref{CLSPo:bal}\) sono i vincoli di bilanciamento del flusso di ogni prodotto (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPo:time}\) impongono che i tempi di setup e i tempi di produzione di ogni periodo siano coperti dal tempo di lavoro, in orario normale e in straordinario (\(m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPo:N}\) e \(\eqref{CLSPo:O}\) limitano i due tempi di lavoro (\(m\) vincoli lineari ciascuno);
-
i vincoli \(\eqref{CLSPo:M}\) collegano le quantità con i setup (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPo:end}\) impongono una scorta vuota all'inizio e alla fine dell'orizzonte;
-
infine, i vincoli \(\eqref{CLSPo:x}\)–\(\eqref{CLSPo:y}\) definiscono le variabili del modello PLI.
-
-
Il tempo disponibile nel periodo \(t\) è al più \(cap^{N}_t+cap^{O}_t\), quindi il valore forte di big-M è
\[ M_{pt}=\min\left\{\left\lfloor\frac{cap^{N}_t+cap^{O}_t-st_{pt}}{vt_{pt}}\right\rfloor,~sd_{ptm}\right\}. \] -
Con \(co_t>cw_t\) una soluzione ottima usa lo straordinario solo quando le ore normali del periodo sono esaurite.
Esempio 15.10: Modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\)
Consideriamo l'istanza del CLS dell'Esempio 15.1, con un solo prodotto (\(|P|=1\), e omettiamo l'indice \(p\)), tempi di produzione \(vt_t=1\) e tempi di setup \(st_t=0\). La capacità \(cap_t=4\) diventa l'orario normale \(cap^{N}_t=4\), al costo \(cw_t=1\), e in ogni periodo è disponibile un'unità di straordinario: \(cap^{O}_t=1\), al costo \(co_t=6\). I valori di big-M sono \(M_t=\min\{5,D_{t,5}\}\), ossia \((5,5,5,5,1)\). Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\) per questa istanza è:
Una soluzione ottima del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}})\) è \(3\cdot 50+2\cdot 10+10\cdot 1+1\cdot 6=186\), e la soluzione ottima è unica (Gurobi). Un'unità di straordinario nel periodo \(4\), al costo \(6\), sostituisce un'unità tenuta a scorta dal periodo \(3\) al periodo \(4\), al costo \(10\): il piano ottimo \((3,0,4,4,0)\) del CLS qui costa \(191\).
15.7.5 Domanda non soddisfatta¶
-
I dati sono quelli del problema di lot sizing con più prodotti e tempi di setup. In più, una parte della domanda \(d_{pt}\) può restare non soddisfatta, con la penalità \(cu_{pt}\) per unità.
-
Introduciamo le variabili intere \(x_{pt}\), \(s_{pt}\) e le variabili binarie \(y_{pt}\) del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) e, per ogni prodotto \(p\in P\) e ogni periodo \(t\in T\), la seguente variabile intera:
\[ \varepsilon_{pt} \in \Z_{\ge 0}~\text{(domanda del prodotto $p$ nel periodo $t$ non soddisfatta)}. \]
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di lot sizing con domanda non soddisfatta (LS-UD) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\):
-
la funzione obiettivo lineare \(\eqref{obj:CLSPu}\) aggiunge ai costi del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) la penalità della domanda non soddisfatta;
-
i vincoli \(\eqref{CLSPu:bal}\) sono i vincoli di bilanciamento del flusso, con la domanda ridotta della sua parte non soddisfatta (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPu:cap}\) sono i vincoli di capacità e i vincoli \(\eqref{CLSPu:M}\) collegano le quantità con i setup (\(m\) e \(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPu:eps}\) garantiscono che la domanda non soddisfatta non superi la domanda (\(|P|\,m\) vincoli lineari);
-
i vincoli \(\eqref{CLSPu:end}\) impongono una scorta vuota all'inizio e alla fine dell'orizzonte;
-
infine, i vincoli \(\eqref{CLSPu:x}\)–\(\eqref{CLSPu:y}\) definiscono le variabili del modello PLI.
-
-
I valori di big-M del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) restano validi, poiché la produzione può solo diminuire. Con \(\varepsilon_{pt}=0\) per ogni prodotto e periodo il modello è il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\).
Esempio 15.11: Modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\)
Consideriamo l'istanza del CLS dell'Esempio 15.1, con un solo prodotto (\(|P|=1\), e omettiamo l'indice \(p\)), tempi di produzione \(vt_t=1\), tempi di setup \(st_t=0\) e i valori forti di big-M \(M_t=(4,4,4,4,1)\). Ogni unità di domanda non soddisfatta costa \(cu_t=18\). Il modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\) per questa istanza è:
Una soluzione ottima del modello \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}})\) è \(2\cdot 50+4\cdot 18=172\), e la soluzione ottima è unica (Gurobi). Le domande dei periodi \(1\), \(2\) e \(5\) non sono soddisfatte: le loro \(4\) unità costano \(72\), e il piano risparmia un setup e tutti i costi di mantenimento a scorta del piano ottimo \((3,0,4,4,0)\) del CLS, di costo \(180\).
15.8 Errori tipici¶
Attenzione
-
Prendere un valore di big-M troppo piccolo. Un valore minore della produzione di un piano ammissibile taglia quel piano: i valori \(D_{t,m}\) e \(cap_t\) sono entrambi validi.
-
Prendere un valore di big-M troppo grande. Ogni valore valido dà un modello corretto, ma un valore grande dà un rilassamento debole: le variabili di setup diventano quasi nulle nelle soluzioni LP, come nel bound \(99.65\) dell'istanza di riferimento.
-
Dimenticare i tempi di setup nei vincoli di capacità. Con più prodotti i vincoli contengono \(st_{pt}\,y_{pt}\) oltre a \(vt_{pt}\,x_{pt}\).
-
Contare il costo di mantenimento della domanda del periodo di produzione. In \(cv_{tk}\) le unità per il periodo \(t\) non vanno a scorta: la somma dei costi di mantenimento parte dalla domanda del periodo \(t+1\).
-
Credere che la formulazione a cammino minimo richieda cammini binari. Le variabili \(zv_{tk}\) sono continue: un piano ammissibile che non è un cammino è una combinazione di cammini.
-
Dimenticare l'interezza delle quantità con più prodotti. Con tempi di produzione \(vt_{pt}>1\) le variabili continue \(zv_{ptk}\) possono dare quantità frazionarie: il modello a cammino minimo richiede i vincoli di interezza \(\eqref{CLSPSP-intx}\) e \(\eqref{CLSPSP-intsi}\), altrimenti è solo un rilassamento (\(676\,450<677\,400\)).
-
Mantenere la capacità fissa nel modello con straordinari. Il tempo del periodo \(t\) è limitato dal tempo di lavoro \(\mu_t+\nu_t\), e i valori di big-M usano \(cap^{N}_t+cap^{O}_t\).
-
Lasciare illimitata la domanda non soddisfatta. Senza \(\varepsilon_{pt}\le d_{pt}\) i vincoli di bilanciamento ammetterebbero una domanda netta negativa, ossia scorta creata dal nulla al prezzo della penalità.
15.9 In sintesi¶
In sintesi
-
Senza i setup il CLS è un semplice problema di flusso; i setup richiedono le variabili binarie \(y_t\) e un legame con le quantità.
-
Nella formulazione big-M il legame \(x_t \le M_t\, y_t\) è corretto per ogni \(M_t\) valido, ma il bound LP migliora quando \(M_t\) diminuisce: il valore forte è \(\min\{cap_t, D_{t,m}\}\).
-
La formulazione a cammino minimo scrive i piani come cammini in una rete, con il legame \(\sum_k zv_{tk} \le y_t\) e senza valore di big-M: il suo rilassamento è il più forte.
-
Le due formulazioni hanno lo stesso valore ottimo; differiscono nel lower bound e nella dimensione del modello.
-
Il modello ULS è il modello big-M senza capacità e con \(M_t=D_{t,m}\): sull'istanza di riferimento il suo valore ottimo è \(170\).
-
Le varianti mantengono la struttura del modello big-M: più prodotti condividono la capacità con i loro tempi di setup, la scorta iniziale aggiunge le variabili \(si_p\), gli straordinari aggiungono i tempi di lavoro \(\mu_t,\nu_t\), e la domanda non soddisfatta aggiunge le variabili \(\varepsilon_{pt}\). Sull'istanza di riferimento, gli straordinari danno \(186\) e la domanda non soddisfatta \(172\).
Quadro riassuntivo dell'istanza di riferimento. Lower bound sul valore ottimo calcolati in questo capitolo:
| Bound | Valore | Da |
|---|---|---|
| Senza setup | \(0\) | piano lot-for-lot |
| Big-M, \(M_t=D_{t,m}\) | \(99.65\) | \(z(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{dem}})=\tfrac{9865}{99}\) |
| Big-M, \(M_t=cap_t\) | \(137.5\) | \(z(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{cap}})\) |
| Big-M forte | \(157.5\) | \(z(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{strong}})\) |
| Cammino minimo | \(170\) | \(z(\mathrm{LP}_{\mathrm{CLSP}}^{\mathrm{SP}})\) |
| Valore ottimo | \(180\) | piano \((3,0,4,4,0)\) |
Esercizi su questo capitolo: Problemi di lot sizing