Esercizi · PD per il problema del lot sizing senza capacità¶
Esercizi · Capitolo 25 · ogni soluzione si apre con un clic · Capitolo 25: Lot sizing senza capacità (ULS) · Eserciziario, volume 3 (PDF)
Esercizio 25.1: Esercizio 1: problema di lot sizing senza capacità
Consideriamo la seguente istanza dell'ULS con \(m=4\) periodi, in cui le domande, i costi di setup, i costi variabili di produzione e i costi di mantenimento a scorta sono:
Domande
-
Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori della matrice \({c}\), del vettore \({v}\) e del vettore \({r}\).
-
Usando il vettore \({r}\), ricostruire una soluzione ottima \((x_1,x_2,\dots,x_m)\) e riportare il valore ottimo.
Soluzione
-
Esecuzione passo per passo dell'algoritmo di PD bottom-up
Per prima cosa si calcola la matrice \({c}\). Per ogni passo, la tabella riporta i valori di \(j\) e \(t\), il valore corrente di \(\mathit{u}\), la cella \({c}[j][t]\) e l'operazione eseguita; la cella \({c}[j][t]\) è evidenziata in blu quando viene assegnata.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Azione \(1\) \(1\) \(2\) \(110\) \(\mathit{u}\leftarrow vc[1]=2\), \(\mathit{g}\leftarrow sc[1]{+}vc[1]\cdot d[1]=50{+}2\cdot 30=110\), \({c}[1][1]\leftarrow 110\) \(1\) \(2\) \(3\) \(140\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[1]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[2]=110{+}3\cdot 10=140\), \({c}[1][2]\leftarrow 140\) \(1\) \(3\) \(5\) \(340\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=3{+}2=5\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=140{+}5\cdot 40=340\), \({c}[1][3]\leftarrow 340\) \(1\) \(4\) \(7\) \(410\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=5{+}2=7\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=340{+}7\cdot 10=410\), \({c}[1][4]\leftarrow 410\) \(2\) \(2\) \(3\) \(110\) \(\mathit{u}\leftarrow vc[2]=3\), \(\mathit{g}\leftarrow sc[2]{+}vc[2]\cdot d[2]=80{+}3\cdot 10=110\), \({c}[2][2]\leftarrow 110\) \(2\) \(3\) \(5\) \(310\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=3{+}2=5\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=110{+}5\cdot 40=310\), \({c}[2][3]\leftarrow 310\) \(2\) \(4\) \(7\) \(380\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=5{+}2=7\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=310{+}7\cdot 10=380\), \({c}[2][4]\leftarrow 380\) \(3\) \(3\) \(1\) \(110\) \(\mathit{u}\leftarrow vc[3]=1\), \(\mathit{g}\leftarrow sc[3]{+}vc[3]\cdot d[3]=70{+}1\cdot 40=110\), \({c}[3][3]\leftarrow 110\) \(3\) \(4\) \(3\) \(140\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=1{+}2=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=110{+}3\cdot 10=140\), \({c}[3][4]\leftarrow 140\) \(4\) \(4\) \(2\) \(80\) \(\mathit{u}\leftarrow vc[4]=2\), \(\mathit{g}\leftarrow sc[4]{+}vc[4]\cdot d[4]=60{+}2\cdot 10=80\), \({c}[4][4]\leftarrow 80\) Questa è la matrice \({c}\):
\[ \begin{array}{l|rrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {j=1} & {110} & {140} & {340} & {410} \\ {j=2} & {-} & {110} & {310} & {380} \\ {j=3} & {-} & {-} & {110} & {140} \\ {j=4} & {-} & {-} & {-} & {80} \\ \hline \end{array} \]Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(t\) e \(j\), le celle \({v}[t]\) e \({r}[t]\), il valore corrente di \(\mathit{b}\) e il valore corrente di \(\mathit{a}\). La cella di \(\mathit{b}\) è evidenziata in rosso quando viene aggiornata; la cella di \(\mathit{a}\) è evidenziata in blu quando viene aggiornata; le celle di \({v}[t]\) e \({r}[t]\) sono evidenziate in blu quando vengono assegnate.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Azione \(-\) \(-\) 0 \(-\) \(-\) \(-\) \({v}[0]\leftarrow 0\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 1 1 \(-\) \(-\) 110 1 \({v}[0]{+}{c}[1][1]=0{+}110=110<+\infty\): \(\mathit{b}\leftarrow 110\), \(\mathit{a}\leftarrow 1\) \(-\) 110 1 110 1 \({v}[1]\leftarrow \mathit{b}=110\), \({r}[1]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 2 1 \(-\) \(-\) 140 1 \({v}[0]{+}{c}[1][2]=0{+}140=140<+\infty\): \(\mathit{b}\leftarrow 140\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 140 1 \({v}[1]{+}{c}[2][2]=110{+}110=220>140\): nessun aggiornamento \(-\) 140 1 140 1 \({v}[2]\leftarrow \mathit{b}=140\), \({r}[2]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 3 1 \(-\) \(-\) 340 1 \({v}[0]{+}{c}[1][3]=0{+}340=340<+\infty\): \(\mathit{b}\leftarrow 340\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 340 1 \({v}[1]{+}{c}[2][3]=110{+}310=420>340\): nessun aggiornamento 3 \(-\) \(-\) 250 3 \({v}[2]{+}{c}[3][3]=140{+}110=250<340\): \(\mathit{b}\leftarrow 250\), \(\mathit{a}\leftarrow 3\) \(-\) 250 3 250 3 \({v}[3]\leftarrow \mathit{b}=250\), \({r}[3]\leftarrow \mathit{a}=3\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 4 1 \(-\) \(-\) 410 1 \({v}[0]{+}{c}[1][4]=0{+}410=410<+\infty\): \(\mathit{b}\leftarrow 410\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 410 1 \({v}[1]{+}{c}[2][4]=110{+}380=490>410\): nessun aggiornamento 3 \(-\) \(-\) 280 3 \({v}[2]{+}{c}[3][4]=140{+}140=280<410\): \(\mathit{b}\leftarrow 280\), \(\mathit{a}\leftarrow 3\) 4 \(-\) \(-\) 280 3 \({v}[3]{+}{c}[4][4]=250{+}80=330>280\): nessun aggiornamento \(-\) 280 3 280 3 \({v}[4]\leftarrow \mathit{b}=280\), \({r}[4]\leftarrow \mathit{a}=3\) Questo è il vettore \({v}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|ccccc} \hline & {t=0} & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{v}[t]} & 0 & 110 & 140 & 250 & 280 \\ \hline \end{array} \]Questo è il vettore \({r}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 \\ \hline \end{array} \] -
Abbiamo il seguente vettore \({r}\):
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 \\ \hline \end{array} \]Possiamo ricostruire una soluzione ottima come segue:
Iterazione \(t\) \({r}[t]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(t\leftarrow {r}[t]-1\) \(-\) \(-\) \(-\) 0 0 0 0 \(t=4\) \(1\) \(4\) \(3\) 0 0 50 0 \(t=3-1=2\) \(2\) \(2\) \(1\) 40 0 50 0 \(t=1-1=0\) -
\(t=4\), \({r}[4]=3\): l'ultimo lotto di produzione dei periodi \(1,\dots,4\) è nel periodo \(3\) e copre le domande dei periodi \(3,\dots,4\), quindi \(x[3]\leftarrow d_{3}+d_{4}=40+10=50\)
-
\(t=2\), \({r}[2]=1\): l'ultimo lotto di produzione dei periodi \(1,\dots,2\) è nel periodo \(1\) e copre le domande dei periodi \(1,\dots,2\), quindi \(x[1]\leftarrow d_{1}+d_{2}=30+10=40\)
Quindi il vettore
\[ (40,\allowbreak 0,\allowbreak 50,\allowbreak 0) \]è una soluzione ottima. I setup sono nei periodi \(1\), \(3\), le scorte sono \((s_1,\dots,s_{4})=(10,\allowbreak 0,\allowbreak 10,\allowbreak 0)\), e il costo totale è
\[\begin{align*} &\underbrace{50+70}_{\text{setup}}+\underbrace{2\cdot 40+3\cdot 0+1\cdot 50+2\cdot 0}_{\text{produzione}}\\ &\quad+\underbrace{1\cdot 10+2\cdot 0+2\cdot 10+1\cdot 0}_{\text{mantenimento}}=120+130+30=280. \end{align*}\]Il valore ottimo è
\[ {v}[4]=280. \] -
Esercizio 25.2: Esercizio 2: problema di lot sizing senza capacità
Consideriamo la seguente istanza dell'ULS con \(m=4\) periodi, in cui le domande, i costi di setup, i costi variabili di produzione e i costi di mantenimento a scorta sono:
Domande
-
Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori della matrice \({c}\), del vettore \({v}\) e del vettore \({r}\).
-
Usando il vettore \({r}\), ricostruire una soluzione ottima \((x_1,x_2,\dots,x_m)\) e riportare il valore ottimo.
Soluzione
-
Esecuzione passo per passo dell'algoritmo di PD bottom-up
Per prima cosa si calcola la matrice \({c}\). Per ogni passo, la tabella riporta i valori di \(j\) e \(t\), il valore corrente di \(\mathit{u}\), la cella \({c}[j][t]\) e l'operazione eseguita; la cella \({c}[j][t]\) è evidenziata in blu quando viene assegnata.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Azione \(1\) \(1\) \(1\) \(80\) \(\mathit{u}\leftarrow vc[1]=1\), \(\mathit{g}\leftarrow sc[1]{+}vc[1]\cdot d[1]=50{+}1\cdot 30=80\), \({c}[1][1]\leftarrow 80\) \(1\) \(2\) \(2\) \(160\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[1]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[2]=80{+}2\cdot 40=160\), \({c}[1][2]\leftarrow 160\) \(1\) \(3\) \(3\) \(190\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=160{+}3\cdot 10=190\), \({c}[1][3]\leftarrow 190\) \(1\) \(4\) \(4\) \(270\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=3{+}1=4\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=190{+}4\cdot 20=270\), \({c}[1][4]\leftarrow 270\) \(2\) \(2\) \(3\) \(200\) \(\mathit{u}\leftarrow vc[2]=3\), \(\mathit{g}\leftarrow sc[2]{+}vc[2]\cdot d[2]=80{+}3\cdot 40=200\), \({c}[2][2]\leftarrow 200\) \(2\) \(3\) \(4\) \(240\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=3{+}1=4\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=200{+}4\cdot 10=240\), \({c}[2][3]\leftarrow 240\) \(2\) \(4\) \(5\) \(340\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=4{+}1=5\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=240{+}5\cdot 20=340\), \({c}[2][4]\leftarrow 340\) \(3\) \(3\) \(2\) \(100\) \(\mathit{u}\leftarrow vc[3]=2\), \(\mathit{g}\leftarrow sc[3]{+}vc[3]\cdot d[3]=80{+}2\cdot 10=100\), \({c}[3][3]\leftarrow 100\) \(3\) \(4\) \(3\) \(160\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=100{+}3\cdot 20=160\), \({c}[3][4]\leftarrow 160\) \(4\) \(4\) \(1\) \(70\) \(\mathit{u}\leftarrow vc[4]=1\), \(\mathit{g}\leftarrow sc[4]{+}vc[4]\cdot d[4]=50{+}1\cdot 20=70\), \({c}[4][4]\leftarrow 70\) Questa è la matrice \({c}\):
\[ \begin{array}{l|rrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {j=1} & {80} & {160} & {190} & {270} \\ {j=2} & {-} & {200} & {240} & {340} \\ {j=3} & {-} & {-} & {100} & {160} \\ {j=4} & {-} & {-} & {-} & {70} \\ \hline \end{array} \]Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(t\) e \(j\), le celle \({v}[t]\) e \({r}[t]\), il valore corrente di \(\mathit{b}\) e il valore corrente di \(\mathit{a}\). La cella di \(\mathit{b}\) è evidenziata in rosso quando viene aggiornata; la cella di \(\mathit{a}\) è evidenziata in blu quando viene aggiornata; le celle di \({v}[t]\) e \({r}[t]\) sono evidenziate in blu quando vengono assegnate.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Azione \(-\) \(-\) 0 \(-\) \(-\) \(-\) \({v}[0]\leftarrow 0\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 1 1 \(-\) \(-\) 80 1 \({v}[0]{+}{c}[1][1]=0{+}80=80<+\infty\): \(\mathit{b}\leftarrow 80\), \(\mathit{a}\leftarrow 1\) \(-\) 80 1 80 1 \({v}[1]\leftarrow \mathit{b}=80\), \({r}[1]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 2 1 \(-\) \(-\) 160 1 \({v}[0]{+}{c}[1][2]=0{+}160=160<+\infty\): \(\mathit{b}\leftarrow 160\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 160 1 \({v}[1]{+}{c}[2][2]=80{+}200=280>160\): nessun aggiornamento \(-\) 160 1 160 1 \({v}[2]\leftarrow \mathit{b}=160\), \({r}[2]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 3 1 \(-\) \(-\) 190 1 \({v}[0]{+}{c}[1][3]=0{+}190=190<+\infty\): \(\mathit{b}\leftarrow 190\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 190 1 \({v}[1]{+}{c}[2][3]=80{+}240=320>190\): nessun aggiornamento 3 \(-\) \(-\) 190 1 \({v}[2]{+}{c}[3][3]=160{+}100=260>190\): nessun aggiornamento \(-\) 190 1 190 1 \({v}[3]\leftarrow \mathit{b}=190\), \({r}[3]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 4 1 \(-\) \(-\) 270 1 \({v}[0]{+}{c}[1][4]=0{+}270=270<+\infty\): \(\mathit{b}\leftarrow 270\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 270 1 \({v}[1]{+}{c}[2][4]=80{+}340=420>270\): nessun aggiornamento 3 \(-\) \(-\) 270 1 \({v}[2]{+}{c}[3][4]=160{+}160=320>270\): nessun aggiornamento 4 \(-\) \(-\) 260 4 \({v}[3]{+}{c}[4][4]=190{+}70=260<270\): \(\mathit{b}\leftarrow 260\), \(\mathit{a}\leftarrow 4\) \(-\) 260 4 260 4 \({v}[4]\leftarrow \mathit{b}=260\), \({r}[4]\leftarrow \mathit{a}=4\) Questo è il vettore \({v}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|ccccc} \hline & {t=0} & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{v}[t]} & 0 & 80 & 160 & 190 & 260 \\ \hline \end{array} \]Questo è il vettore \({r}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 1 & 4 \\ \hline \end{array} \] -
Abbiamo il seguente vettore \({r}\):
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 1 & 4 \\ \hline \end{array} \]Possiamo ricostruire una soluzione ottima come segue:
Iterazione \(t\) \({r}[t]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(t\leftarrow {r}[t]-1\) \(-\) \(-\) \(-\) 0 0 0 0 \(t=4\) \(1\) \(4\) \(4\) 0 0 0 20 \(t=4-1=3\) \(2\) \(3\) \(1\) 80 0 0 20 \(t=1-1=0\) -
\(t=4\), \({r}[4]=4\): il periodo \(4\) produce solo la propria domanda, quindi \(x[4]\leftarrow d_{4}=20\)
-
\(t=3\), \({r}[3]=1\): l'ultimo lotto di produzione dei periodi \(1,\dots,3\) è nel periodo \(1\) e copre le domande dei periodi \(1,\dots,3\), quindi \(x[1]\leftarrow d_{1}+d_{2}+d_{3}=30+40+10=80\)
Quindi il vettore
\[ (80,\allowbreak 0,\allowbreak 0,\allowbreak 20) \]è una soluzione ottima. I setup sono nei periodi \(1\), \(4\), le scorte sono \((s_1,\dots,s_{4})=(50,\allowbreak 10,\allowbreak 0,\allowbreak 0)\), e il costo totale è
\[\begin{align*} &\underbrace{50+50}_{\text{setup}}+\underbrace{1\cdot 80+3\cdot 0+2\cdot 0+1\cdot 20}_{\text{produzione}}\\ &\quad+\underbrace{1\cdot 50+1\cdot 10+1\cdot 0+2\cdot 0}_{\text{mantenimento}}=100+100+60=260. \end{align*}\]Il valore ottimo è
\[ {v}[4]=260. \] -
Esercizio 25.3: Esercizio 3: problema di lot sizing senza capacità
Consideriamo la seguente istanza dell'ULS con \(m=5\) periodi, in cui le domande, i costi di setup, i costi variabili di produzione e i costi di mantenimento a scorta sono:
Domande
-
Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori della matrice \({c}\), del vettore \({v}\) e del vettore \({r}\).
-
Usando il vettore \({r}\), ricostruire una soluzione ottima \((x_1,x_2,\dots,x_m)\) e riportare il valore ottimo.
Soluzione
-
Esecuzione passo per passo dell'algoritmo di PD bottom-up
Per prima cosa si calcola la matrice \({c}\). Per ogni passo, la tabella riporta i valori di \(j\) e \(t\), il valore corrente di \(\mathit{u}\), la cella \({c}[j][t]\) e l'operazione eseguita; la cella \({c}[j][t]\) è evidenziata in blu quando viene assegnata.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Azione \(1\) \(1\) \(1\) \(80\) \(\mathit{u}\leftarrow vc[1]=1\), \(\mathit{g}\leftarrow sc[1]{+}vc[1]\cdot d[1]=70{+}1\cdot 10=80\), \({c}[1][1]\leftarrow 80\) \(1\) \(2\) \(2\) \(140\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[1]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[2]=80{+}2\cdot 30=140\), \({c}[1][2]\leftarrow 140\) \(1\) \(3\) \(3\) \(260\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=140{+}3\cdot 40=260\), \({c}[1][3]\leftarrow 260\) \(1\) \(4\) \(5\) \(410\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=3{+}2=5\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=260{+}5\cdot 30=410\), \({c}[1][4]\leftarrow 410\) \(1\) \(5\) \(6\) \(650\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=5{+}1=6\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=410{+}6\cdot 40=650\), \({c}[1][5]\leftarrow 650\) \(2\) \(2\) \(1\) \(110\) \(\mathit{u}\leftarrow vc[2]=1\), \(\mathit{g}\leftarrow sc[2]{+}vc[2]\cdot d[2]=80{+}1\cdot 30=110\), \({c}[2][2]\leftarrow 110\) \(2\) \(3\) \(2\) \(190\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=110{+}2\cdot 40=190\), \({c}[2][3]\leftarrow 190\) \(2\) \(4\) \(4\) \(310\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=2{+}2=4\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=190{+}4\cdot 30=310\), \({c}[2][4]\leftarrow 310\) \(2\) \(5\) \(5\) \(510\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=4{+}1=5\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=310{+}5\cdot 40=510\), \({c}[2][5]\leftarrow 510\) \(3\) \(3\) \(1\) \(90\) \(\mathit{u}\leftarrow vc[3]=1\), \(\mathit{g}\leftarrow sc[3]{+}vc[3]\cdot d[3]=50{+}1\cdot 40=90\), \({c}[3][3]\leftarrow 90\) \(3\) \(4\) \(3\) \(180\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=1{+}2=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=90{+}3\cdot 30=180\), \({c}[3][4]\leftarrow 180\) \(3\) \(5\) \(4\) \(340\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=3{+}1=4\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=180{+}4\cdot 40=340\), \({c}[3][5]\leftarrow 340\) \(4\) \(4\) \(1\) \(110\) \(\mathit{u}\leftarrow vc[4]=1\), \(\mathit{g}\leftarrow sc[4]{+}vc[4]\cdot d[4]=80{+}1\cdot 30=110\), \({c}[4][4]\leftarrow 110\) \(4\) \(5\) \(2\) \(190\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=110{+}2\cdot 40=190\), \({c}[4][5]\leftarrow 190\) \(5\) \(5\) \(2\) \(130\) \(\mathit{u}\leftarrow vc[5]=2\), \(\mathit{g}\leftarrow sc[5]{+}vc[5]\cdot d[5]=50{+}2\cdot 40=130\), \({c}[5][5]\leftarrow 130\) Questa è la matrice \({c}\):
\[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {80} & {140} & {260} & {410} & {650} \\ {j=2} & {-} & {110} & {190} & {310} & {510} \\ {j=3} & {-} & {-} & {90} & {180} & {340} \\ {j=4} & {-} & {-} & {-} & {110} & {190} \\ {j=5} & {-} & {-} & {-} & {-} & {130} \\ \hline \end{array} \]Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(t\) e \(j\), le celle \({v}[t]\) e \({r}[t]\), il valore corrente di \(\mathit{b}\) e il valore corrente di \(\mathit{a}\). La cella di \(\mathit{b}\) è evidenziata in rosso quando viene aggiornata; la cella di \(\mathit{a}\) è evidenziata in blu quando viene aggiornata; le celle di \({v}[t]\) e \({r}[t]\) sono evidenziate in blu quando vengono assegnate.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Azione \(-\) \(-\) 0 \(-\) \(-\) \(-\) \({v}[0]\leftarrow 0\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 1 1 \(-\) \(-\) 80 1 \({v}[0]{+}{c}[1][1]=0{+}80=80<+\infty\): \(\mathit{b}\leftarrow 80\), \(\mathit{a}\leftarrow 1\) \(-\) 80 1 80 1 \({v}[1]\leftarrow \mathit{b}=80\), \({r}[1]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 2 1 \(-\) \(-\) 140 1 \({v}[0]{+}{c}[1][2]=0{+}140=140<+\infty\): \(\mathit{b}\leftarrow 140\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 140 1 \({v}[1]{+}{c}[2][2]=80{+}110=190>140\): nessun aggiornamento \(-\) 140 1 140 1 \({v}[2]\leftarrow \mathit{b}=140\), \({r}[2]\leftarrow \mathit{a}=1\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 3 1 \(-\) \(-\) 260 1 \({v}[0]{+}{c}[1][3]=0{+}260=260<+\infty\): \(\mathit{b}\leftarrow 260\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 260 1 \({v}[1]{+}{c}[2][3]=80{+}190=270>260\): nessun aggiornamento 3 \(-\) \(-\) 230 3 \({v}[2]{+}{c}[3][3]=140{+}90=230<260\): \(\mathit{b}\leftarrow 230\), \(\mathit{a}\leftarrow 3\) \(-\) 230 3 230 3 \({v}[3]\leftarrow \mathit{b}=230\), \({r}[3]\leftarrow \mathit{a}=3\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 4 1 \(-\) \(-\) 410 1 \({v}[0]{+}{c}[1][4]=0{+}410=410<+\infty\): \(\mathit{b}\leftarrow 410\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 390 2 \({v}[1]{+}{c}[2][4]=80{+}310=390<410\): \(\mathit{b}\leftarrow 390\), \(\mathit{a}\leftarrow 2\) 3 \(-\) \(-\) 320 3 \({v}[2]{+}{c}[3][4]=140{+}180=320<390\): \(\mathit{b}\leftarrow 320\), \(\mathit{a}\leftarrow 3\) 4 \(-\) \(-\) 320 3 \({v}[3]{+}{c}[4][4]=230{+}110=340>320\): nessun aggiornamento \(-\) 320 3 320 3 \({v}[4]\leftarrow \mathit{b}=320\), \({r}[4]\leftarrow \mathit{a}=3\) \(-\) \(-\) \(-\) \(+\infty\) 0 \(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\) 5 1 \(-\) \(-\) 650 1 \({v}[0]{+}{c}[1][5]=0{+}650=650<+\infty\): \(\mathit{b}\leftarrow 650\), \(\mathit{a}\leftarrow 1\) 2 \(-\) \(-\) 590 2 \({v}[1]{+}{c}[2][5]=80{+}510=590<650\): \(\mathit{b}\leftarrow 590\), \(\mathit{a}\leftarrow 2\) 3 \(-\) \(-\) 480 3 \({v}[2]{+}{c}[3][5]=140{+}340=480<590\): \(\mathit{b}\leftarrow 480\), \(\mathit{a}\leftarrow 3\) 4 \(-\) \(-\) 420 4 \({v}[3]{+}{c}[4][5]=230{+}190=420<480\): \(\mathit{b}\leftarrow 420\), \(\mathit{a}\leftarrow 4\) 5 \(-\) \(-\) 420 4 \({v}[4]{+}{c}[5][5]=320{+}130=450>420\): nessun aggiornamento \(-\) 420 4 420 4 \({v}[5]\leftarrow \mathit{b}=420\), \({r}[5]\leftarrow \mathit{a}=4\) Questo è il vettore \({v}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|cccccc} \hline & {t=0} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{v}[t]} & 0 & 80 & 140 & 230 & 320 & 420 \\ \hline \end{array} \]Questo è il vettore \({r}\) dopo l'esecuzione dell'algoritmo di PD:
\[ \begin{array}{c|ccccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 & 4 \\ \hline \end{array} \] -
Abbiamo il seguente vettore \({r}\):
\[ \begin{array}{c|ccccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 & 4 \\ \hline \end{array} \]Possiamo ricostruire una soluzione ottima come segue:
Iterazione \(t\) \({r}[t]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(t\leftarrow {r}[t]-1\) \(-\) \(-\) \(-\) 0 0 0 0 0 \(t=5\) \(1\) \(5\) \(4\) 0 0 0 70 0 \(t=4-1=3\) \(2\) \(3\) \(3\) 0 0 40 70 0 \(t=3-1=2\) \(3\) \(2\) \(1\) 40 0 40 70 0 \(t=1-1=0\) -
\(t=5\), \({r}[5]=4\): l'ultimo lotto di produzione dei periodi \(1,\dots,5\) è nel periodo \(4\) e copre le domande dei periodi \(4,\dots,5\), quindi \(x[4]\leftarrow d_{4}+d_{5}=30+40=70\)
-
\(t=3\), \({r}[3]=3\): il periodo \(3\) produce solo la propria domanda, quindi \(x[3]\leftarrow d_{3}=40\)
-
\(t=2\), \({r}[2]=1\): l'ultimo lotto di produzione dei periodi \(1,\dots,2\) è nel periodo \(1\) e copre le domande dei periodi \(1,\dots,2\), quindi \(x[1]\leftarrow d_{1}+d_{2}=10+30=40\)
Quindi il vettore
\[ (40,\allowbreak 0,\allowbreak 40,\allowbreak 70,\allowbreak 0) \]è una soluzione ottima. I setup sono nei periodi \(1\), \(3\), \(4\), le scorte sono \((s_1,\dots,s_{5})=(30,\allowbreak 0,\allowbreak 0,\allowbreak 40,\allowbreak 0)\), e il costo totale è
\[\begin{align*} &\underbrace{70+50+80}_{\text{setup}}+\underbrace{1\cdot 40+1\cdot 0+1\cdot 40+1\cdot 70+2\cdot 0}_{\text{produzione}}\\ &\quad+\underbrace{1\cdot 30+1\cdot 0+2\cdot 0+1\cdot 40+2\cdot 0}_{\text{mantenimento}}=200+150+70=420. \end{align*}\]Il valore ottimo è
\[ {v}[5]=420. \] -