25.2.2 Un algoritmo di PD per l'ULS: Passo 1 e Passo 2¶

Parte 3 · Programmazione dinamica · Capitolo 25 · Capitolo 25: Lot sizing senza capacità (ULS) · Dispensa, volume 3 (PDF) · Slide · Esercizi: Lot sizing senza capacità (ULS) · App: Wagner-Whitin per il lot sizing senza capacità

Passo 1: calcolo del valore ottimo

Per ogni $t \in \{1,2,\dots,m\}$, sia $v(t)$ il valore ottimo della sottoistanza dell'ULS data da:

un insieme $\{1,2,\dots,t\}$ di $t$ periodi di tempo,
per ogni periodo $j \in \{1,2,\dots,t\}$, una domanda $d_j$,
per ogni periodo $j \in \{1,2,\dots,t\}$, un costo di setup $sc_j$, un costo variabile di produzione $vc_j$ e un costo di mantenimento a scorta $hc_j$.

La formula ricorsiva per calcolare $v(t)$ è la seguente:

\[\begin{equation*} \label{eq:ww} v(t)= \left\{ \begin{array}{ll} \displaystyle \min \bigg\{ v(j-1) + c_{j,t} : j \in \{1,2,\dots,t\}\bigg\} & \textrm{se $1\le t \le m$,}\\[2ex] 0 & \textrm{se $t=0$.} \end{array} \right. \tag{25.3} \end{equation*}\]

La sottoistanza con i periodi $\{1,\dots,t\}$ è un'istanza dell'ULS dello stesso tipo: la sua scorta deve essere vuota alla fine del periodo $t$. Qui $v(0)=0$, perché un insieme vuoto di periodi non ha domanda né costo.
Il processo di decomposizione ricorsiva della formula $\eqref{eq:ww}$ genera $t$ sottoproblemi indipendenti, ciascuno corrispondente a una possibile scelta del periodo $j$ dell'ultimo lotto di produzione, che produce le domande dei periodi $j,\dots,t$.
Per la proprietà zero-inventory ordering applicata alla sottoistanza, la scorta è vuota alla fine del periodo $j-1$, e il sottoproblema residuo è la sottoistanza dell'ULS con i periodi $\{1,\dots,j-1\}$.
Il valore ottimo $v(t)$ si ottiene provando tutti i possibili periodi dell'ultimo lotto di produzione e scegliendo quello che minimizza la somma $v(j-1)+c_{j,t}$ del valore ottimo del sottoproblema residuo e del costo dell'ultimo lotto.
Quindi una soluzione ottima per i periodi $\{1,\dots,t\}$ si costruisce combinando l'ultimo lotto di produzione scelto nel periodo $j$ con una soluzione ottima del sottoproblema residuo con i periodi $\{1,\dots,j-1\}$.

$\rightsquigarrow$ Sottostruttura ottima verificata!
Scelte diverse dell'ultimo lotto di produzione, fatte eventualmente per valori diversi di $t$, possono portare allo stesso insieme residuo di periodi, e quindi lo stesso valore $v(t)$ può dover essere calcolato più volte durante la valutazione ricorsiva della formula $\eqref{eq:ww}$.

$\rightsquigarrow$ Sottoproblemi sovrapposti verificati!
Un primo metodo per calcolare il valore ottimo $v(m)$ dell'istanza dell'ULS è l'approccio top-down. Il metodo parte dalla chiamata con $t=m$ e valuta ricorsivamente la formula $\eqref{eq:ww}$: ogni chiamata per i periodi $\{1,\dots,t\}$ genera altre chiamate per i periodi $\{1,\dots,j-1\}$, per ogni $j \in \{1,2,\dots,t\}$, finché non si raggiunge il caso base $v(0)$.
L'albero di ricorsione della funzione $v$ ha un nodo per ogni chiamata ricorsiva, etichettato con la chiamata che rappresenta. La radice rappresenta la chiamata iniziale. I figli di un nodo rappresentano le chiamate ricorsive effettuate da quella chiamata. Le foglie rappresentano i casi base.

Esempio 25.5: Albero di ricorsione

Consideriamo i primi quattro periodi dell'istanza dell'ULS dell'Esempio 25.1 (con cinque periodi l'albero ha $32$ nodi). Questo è l'albero di ricorsione dell'approccio top-down per calcolare $v(4)$:

I figli di un nodo $v(t)$ sono ordinati secondo $j\in\{1,\dots,t\}$: il figlio $v(j-1)$ corrisponde a un ultimo lotto di produzione nel periodo $j$. La funzione $v$ viene chiamata $16$ volte, e gli stessi sottoproblemi vengono risolti più volte: $v(2)$ viene chiamata $2$ volte, $v(1)$ viene chiamata $4$ volte e $v(0)$ viene chiamata $8$ volte. Tutte le altre chiamate vengono effettuate una sola volta.
Il valore $v(t)$, per un periodo generico $t$, si può calcolare una volta noti i valori $v(j)$ per tutti i periodi minori $j<t$.
Esempio 25.6: Calcolo dei valori della funzione $v$

Consideriamo l'istanza dell'ULS dell'Esempio 25.1, con la matrice ${c}$ dei costi dei lotti di produzione:

\[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

Il valore della funzione $v$ si può calcolare partendo dal caso base $v(0)=0$ e calcolando poi i valori di $v(1)$, $v(2)$, $v(3)$, $v(4)$ e $v(5)$ nell'ordine, come segue:
- Poiché conosciamo il valore di $v(0)$, possiamo calcolare $v(1)$ come segue:
  
  \[ v(1)=v(0)+c_{1,1}=0+50=50 \]
- Calcolati $v(1)$ e $v(0)$, possiamo calcolare $v(2)$ come segue:
  
  \[\begin{align*} v(2)&=\min\{v(0)+c_{1,2},v(1)+c_{2,2}\}\\ &=\min\{0+60,50+50\}=60 \end{align*}\]
- Calcolati $v(2)$, $v(1)$ e $v(0)$, possiamo calcolare $v(3)$ come segue:
  
  \[\begin{align*} v(3)&=\min\{v(0)+c_{1,3},v(1)+c_{2,3},v(2)+c_{3,3}\}\\ &=\min\{0+120,50+80,60+50\}=110 \end{align*}\]
- Calcolati $v(3)$, $v(2)$, $v(1)$ e $v(0)$, possiamo calcolare $v(4)$ come segue:
  
  \[\begin{align*} v(4)&=\min\{v(0)+c_{1,4},v(1)+c_{2,4},v(2)+c_{3,4},v(3)+c_{4,4}\}\\ &=\min\{0+240,50+160,60+90,110+50\}=150 \end{align*}\]
- Calcolati $v(4)$, $v(3)$, $v(2)$, $v(1)$ e $v(0)$, possiamo calcolare $v(5)$ come segue:
  
  \[\begin{align*} v(5)&=\min\{v(0)+c_{1,5},v(1)+c_{2,5},v(2)+c_{3,5},v(3)+c_{4,5},v(4)+c_{5,5}\}\\ &=\min\{0+280,50+190,60+110,110+60,150+50\}=170 \end{align*}\]
Possiamo evitare di risolvere ripetutamente gli stessi sottoproblemi memorizzando il valore di ciascun sottoproblema appena viene calcolato. I valori sono memorizzati in una tabella di lookup, il vettore ${v}[0..m]$, la cui cella ${v}[t]$ contiene $v(t)$.
Poiché la soluzione di un sottoproblema con valore $v(t)$ dipende solo dai sottoproblemi con valori $v(j-1)$, con $j-1<t$, possiamo risolvere i sottoproblemi per valori crescenti di $t$, partendo dal caso base $v(0)=0$ fino ad arrivare a $v(m)$: questa osservazione porta in modo naturale a un metodo molto più efficiente per calcolare il valore ottimo $v(m)$ dell'istanza dell'ULS.

Un secondo metodo per calcolare il valore ottimo $v(m)$ dell'istanza dell'ULS è l'approccio bottom-up. Il metodo parte dal caso base $v(0)=0$ e valuta la formula $\eqref{eq:ww}$ per periodi crescenti $t \in \{1,2,\dots,m\}$: ogni valore $v(t)$ si calcola usando i valori già calcolati $v(0), v(1), \dots, v(t-1)$, fino a ottenere il valore $v(m)$ dell'istanza dell'ULS.

Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up:

Algoritmo: DP_WW

Input: Un'istanza dell'ULS data dal numero $m$ di periodi e dai vettori $d[1..m]$, $sc[1..m]$, $vc[1..m]$, $hc[1..m]$

Output: Il valore ottimo

1Function DP_WW($m,d,sc,vc,hc$)

2${c} := \textnormal{CostMatrix}(m,d,sc,vc,hc)$

3${v} := \textnormal{new array}[0..m]$

4${v}[0] \leftarrow 0$

5for $t := 1$ to $m$ do

6$\mathit{b} := +\infty$

7for $j := 1$ to $t$ do

8if ${v}[j-1] + {c}[j][t] < \mathit{b}$ then

9$\mathit{b} \leftarrow {v}[j-1] + {c}[j][t]$

10end

11end

12${v}[t] \leftarrow \mathit{b}$

13end

14return ${v}[m]$

La matrice ${c}$ contiene i costi dei lotti di produzione, calcolati dall'algoritmo CostMatrix.
Il vettore ${v}[0..m]$ è la tabella di lookup: memorizza i valori ottimi di tutti i sottoproblemi, con il caso base ${v}[0]=0$.
Il ciclo esterno, su $t \in \{1,2,\dots,m\}$, calcola ${v}[t]$ in ordine crescente dell'ultimo periodo.
Il ciclo interno, su $j \in \{1,2,\dots,t\}$, valuta tutti i possibili periodi dell'ultimo lotto di produzione e conserva in $\mathit{b}$ il valore minimo ${v}[j-1]+{c}[j][t]$; la variabile $\mathit{b}$ parte da $+\infty$, quindi il primo confronto la aggiorna sempre.
Al termine del ciclo interno, ${v}[t] \leftarrow \mathit{b}$ memorizza il valore ottimo ${v}[t]$.
Infine, viene restituito il valore ottimo ${v}[m]$ dell'istanza dell'ULS.

Esempio 25.7: Esecuzione dell'algoritmo di PD

Consideriamo l'istanza dell'ULS dell'Esempio 25.1, con la matrice ${c}$ dei costi dei lotti di produzione:

\[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di $t$ e $j$, il valore corrente di $\mathit{b}$ e la cella ${v}[t]$. La cella di $\mathit{b}$ è evidenziata in rosso quando viene aggiornata; la cella di ${v}[t]$ è evidenziata in blu quando viene assegnata.

$t$	$j$	${v}[t]$	$\mathit{b}$	Azione
$-$	$-$	0	$-$	${v}[0]\leftarrow 0$
	$-$	$-$	$+\infty$	$\mathit{b}\leftarrow +\infty$
1	1	$-$	50	${v}[0]{+}{c}[1][1]=0{+}50=50<+\infty$: $\mathit{b}\leftarrow 50$
	$-$	50	50	${v}[1]\leftarrow \mathit{b}=50$
	$-$	$-$	$+\infty$	$\mathit{b}\leftarrow +\infty$
2	1	$-$	60	${v}[0]{+}{c}[1][2]=0{+}60=60<+\infty$: $\mathit{b}\leftarrow 60$
	2	$-$	60	${v}[1]{+}{c}[2][2]=50{+}50=100>60$: nessun aggiornamento
	$-$	60	60	${v}[2]\leftarrow \mathit{b}=60$
	$-$	$-$	$+\infty$	$\mathit{b}\leftarrow +\infty$
3	1	$-$	120	${v}[0]{+}{c}[1][3]=0{+}120=120<+\infty$: $\mathit{b}\leftarrow 120$
	2	$-$	120	${v}[1]{+}{c}[2][3]=50{+}80=130>120$: nessun aggiornamento
	3	$-$	110	${v}[2]{+}{c}[3][3]=60{+}50=110<120$: $\mathit{b}\leftarrow 110$
	$-$	110	110	${v}[3]\leftarrow \mathit{b}=110$
	$-$	$-$	$+\infty$	$\mathit{b}\leftarrow +\infty$
4	1	$-$	240	${v}[0]{+}{c}[1][4]=0{+}240=240<+\infty$: $\mathit{b}\leftarrow 240$
	2	$-$	210	${v}[1]{+}{c}[2][4]=50{+}160=210<240$: $\mathit{b}\leftarrow 210$
	3	$-$	150	${v}[2]{+}{c}[3][4]=60{+}90=150<210$: $\mathit{b}\leftarrow 150$
	4	$-$	150	${v}[3]{+}{c}[4][4]=110{+}50=160>150$: nessun aggiornamento
	$-$	150	150	${v}[4]\leftarrow \mathit{b}=150$
	$-$	$-$	$+\infty$	$\mathit{b}\leftarrow +\infty$
5	1	$-$	280	${v}[0]{+}{c}[1][5]=0{+}280=280<+\infty$: $\mathit{b}\leftarrow 280$
	2	$-$	240	${v}[1]{+}{c}[2][5]=50{+}190=240<280$: $\mathit{b}\leftarrow 240$
	3	$-$	170	${v}[2]{+}{c}[3][5]=60{+}110=170<240$: $\mathit{b}\leftarrow 170$
	4	$-$	170	${v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}$: nessun aggiornamento
	5	$-$	170	${v}[4]{+}{c}[5][5]=150{+}50=200>170$: nessun aggiornamento
	$-$	170	170	${v}[5]\leftarrow \mathit{b}=170$

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 & 50 & 60 & 110 & 150 & 170 \\ \hline \end{array} \]

Dopo l'esecuzione dell'algoritmo di PD, il vettore ${v}$ contiene il valore ottimo ${v}[t]$ per ogni insieme di periodi $\{1,\dots,t\}$.
Osservazione (cammino minimo). La formula $\eqref{eq:ww}$ calcola un cammino minimo in una rete con nodi $0,1,\dots,m$ e un arco dal nodo $j-1$ al nodo $t$, di costo $c_{j,t}$, per ogni $j\le t$. Il valore $v(t)$ è la lunghezza di un cammino minimo dal nodo $0$ al nodo $t$. È la formulazione a cammino minimo del Capitolo 15 «Formulazioni dei problemi di lot sizing», senza le capacità: un arco è un lotto di produzione.

Passo 2: calcolo di una soluzione ottima

Per calcolare una soluzione ottima è necessario memorizzare alcune informazioni aggiuntive.
Per ogni periodo $t$, oltre al valore ottimo ${v}[t]$, memorizziamo ${r}[t]$, il periodo dell'ultimo lotto di produzione in una soluzione ottima per i periodi $\{1,\dots,t\}$.

Partendo da $t=m$, il valore ${r}[t]$ dà il periodo dell'ultimo lotto di produzione, che produce $D_{{r}[t],t}$ unità; i periodi rimanenti sono $\{1,\dots,{r}[t]-1\}$, e la stessa regola si può applicare di nuovo, e così via, finché non resta alcun periodo.

Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, con la memorizzazione delle informazioni necessarie a calcolare una soluzione ottima:

Algoritmo: DP_WW_InfoSol

Input: Un'istanza dell'ULS data dal numero $m$ di periodi e dai vettori $d[1..m]$, $sc[1..m]$, $vc[1..m]$, $hc[1..m]$

Output: Il valore ottimo e il vettore delle informazioni ${r}[1..m]$

1Function DP_WW_InfoSol($m,d,sc,vc,hc$)

2${c} := \textnormal{CostMatrix}(m,d,sc,vc,hc)$

3${v} := \textnormal{new array}[0..m]$

4${r} := \textnormal{new array}[1..m]$

5${v}[0] \leftarrow 0$

6for $t := 1$ to $m$ do

7$\mathit{b} := +\infty$

8$\mathit{a} := 0$

9for $j := 1$ to $t$ do

10if ${v}[j-1] + {c}[j][t] < \mathit{b}$ then

11$\mathit{b} \leftarrow {v}[j-1] + {c}[j][t]$

12$\mathit{a} \leftarrow j$

13end

14end

15${v}[t] \leftarrow \mathit{b}$

16${r}[t] \leftarrow \mathit{a}$

17end

18return ${v}[m], {r}$

L'algoritmo di PD usa la variabile temporanea aggiuntiva $\mathit{a}$ per tenere traccia della decisione presa quando $\mathit{b}$ viene aggiornato. Se viene scelto l'ultimo lotto di produzione nel periodo $j$, $\mathit{a}\leftarrow j$ memorizza questa decisione. Al termine del ciclo interno, ${r}[t]\leftarrow \mathit{a}$ memorizza il periodo dell'ultimo lotto di produzione scelto, insieme al valore ottimo ${v}[t]\leftarrow \mathit{b}$.
A causa del confronto stretto, in caso di pareggio si memorizza il periodo $j$ minimo.

Esempio 25.8: Calcolo delle informazioni aggiuntive

Consideriamo l'istanza dell'ULS dell'Esempio 25.1, con la matrice ${c}$ dei costi dei lotti di produzione:

\[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di $t$ e $j$, la cella ${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}$ e la cella di ${r}[t]$ sono evidenziate in blu quando vengono aggiornate.

$t$	$j$	${r}[t]$	$\mathit{b}$	$\mathit{a}$	Azione
$-$	$-$	$-$	$-$	$-$	Stato iniziale
	$-$	$-$	$+\infty$	0	$\mathit{b}\leftarrow +\infty$, $\mathit{a}\leftarrow 0$
1	1	$-$	50	1	${v}[0]{+}{c}[1][1]=0{+}50=50<+\infty$: $\mathit{b}\leftarrow 50$, $\mathit{a}\leftarrow 1$
	$-$	1	50	1	${v}[1]\leftarrow \mathit{b}=50$, ${r}[1]\leftarrow \mathit{a}=1$
	$-$	$-$	$+\infty$	0	$\mathit{b}\leftarrow +\infty$, $\mathit{a}\leftarrow 0$
2	1	$-$	60	1	${v}[0]{+}{c}[1][2]=0{+}60=60<+\infty$: $\mathit{b}\leftarrow 60$, $\mathit{a}\leftarrow 1$
	2	$-$	60	1	${v}[1]{+}{c}[2][2]=50{+}50=100>60$: nessun aggiornamento
	$-$	1	60	1	${v}[2]\leftarrow \mathit{b}=60$, ${r}[2]\leftarrow \mathit{a}=1$
	$-$	$-$	$+\infty$	0	$\mathit{b}\leftarrow +\infty$, $\mathit{a}\leftarrow 0$
3	1	$-$	120	1	${v}[0]{+}{c}[1][3]=0{+}120=120<+\infty$: $\mathit{b}\leftarrow 120$, $\mathit{a}\leftarrow 1$
	2	$-$	120	1	${v}[1]{+}{c}[2][3]=50{+}80=130>120$: nessun aggiornamento
	3	$-$	110	3	${v}[2]{+}{c}[3][3]=60{+}50=110<120$: $\mathit{b}\leftarrow 110$, $\mathit{a}\leftarrow 3$
	$-$	3	110	3	${v}[3]\leftarrow \mathit{b}=110$, ${r}[3]\leftarrow \mathit{a}=3$
	$-$	$-$	$+\infty$	0	$\mathit{b}\leftarrow +\infty$, $\mathit{a}\leftarrow 0$
4	1	$-$	240	1	${v}[0]{+}{c}[1][4]=0{+}240=240<+\infty$: $\mathit{b}\leftarrow 240$, $\mathit{a}\leftarrow 1$
	2	$-$	210	2	${v}[1]{+}{c}[2][4]=50{+}160=210<240$: $\mathit{b}\leftarrow 210$, $\mathit{a}\leftarrow 2$
	3	$-$	150	3	${v}[2]{+}{c}[3][4]=60{+}90=150<210$: $\mathit{b}\leftarrow 150$, $\mathit{a}\leftarrow 3$
	4	$-$	150	3	${v}[3]{+}{c}[4][4]=110{+}50=160>150$: nessun aggiornamento
	$-$	3	150	3	${v}[4]\leftarrow \mathit{b}=150$, ${r}[4]\leftarrow \mathit{a}=3$
	$-$	$-$	$+\infty$	0	$\mathit{b}\leftarrow +\infty$, $\mathit{a}\leftarrow 0$
5	1	$-$	280	1	${v}[0]{+}{c}[1][5]=0{+}280=280<+\infty$: $\mathit{b}\leftarrow 280$, $\mathit{a}\leftarrow 1$
	2	$-$	240	2	${v}[1]{+}{c}[2][5]=50{+}190=240<280$: $\mathit{b}\leftarrow 240$, $\mathit{a}\leftarrow 2$
	3	$-$	170	3	${v}[2]{+}{c}[3][5]=60{+}110=170<240$: $\mathit{b}\leftarrow 170$, $\mathit{a}\leftarrow 3$
	4	$-$	170	3	${v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}$: nessun aggiornamento
	5	$-$	170	3	${v}[4]{+}{c}[5][5]=150{+}50=200>170$: nessun aggiornamento
	$-$	3	170	3	${v}[5]\leftarrow \mathit{b}=170$, ${r}[5]\leftarrow \mathit{a}=3$

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 & 3 \\ \hline \end{array} \]

Calcolato il vettore ${r}$, si può calcolare una soluzione ottima dell'istanza dell'ULS applicando ripetutamente la regola seguente, partendo da $t=m$ e da $x_j=0$ per ogni $j \in \{1,2,\dots,m\}$:

\[ x_{{r}[t]} \leftarrow D_{{r}[t],t}, \qquad t \leftarrow {r}[t]-1, \]

finché $t=0$. Si ottiene così il vettore $(x_1,x_2,\dots,x_m)$, in cui ogni componente $x_j$ è il numero di unità prodotte nel periodo $j$ in una soluzione ottima.

Lo pseudocodice seguente implementa il calcolo di una soluzione ottima, dato il vettore ${r}$.

Algoritmo: DP_WW_SolComputation

Input: Il numero $m$ di periodi e le domande $d[1..m]$ dell'istanza dell'ULS, e il vettore ${r}[1..m]$

Output: Una soluzione ottima dell'istanza dell'ULS

1Function DP_WW_SolComputation($m,d,{r}$)

2$x := \textnormal{new array}[1..m]$

3for $j := 1$ to $m$ do

4$x[j] \leftarrow 0$

5end

6$t := m$

7while $t > 0$ do

8$x[{r}[t]] \leftarrow \sum_{k={r}[t]}^{t} d[k]$

9$t \leftarrow {r}[t] - 1$

10end

11return $x$

Esempio 25.9: Calcolo di una soluzione ottima

Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 25.1, 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 & 3 \\ \hline \end{array} \]

Possiamo calcolare una soluzione ottima per $m=5$ periodi come segue:

Iterazione	$t$	${r}[t]$	$x[1]$	$x[3]$	$t\leftarrow {r}[t]-1$
$-$	$-$	$-$	0	0	$t=5$
$1$	$5$	$3$	0	80	$t=3-1=2$
$2$	$2$	$1$	30	80	$t=1-1=0$

$t=5$, ${r}[5]=3$: l'ultimo lotto di produzione dei periodi $1,\dots,5$ è nel periodo $3$ e copre le domande dei periodi $3,\dots,5$, quindi $x[3]\leftarrow d_{3}+d_{4}+d_{5}=30+40+10=80$
$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}=20+10=30$

Una soluzione ottima è il vettore:

\[ (30,\allowbreak 0,\allowbreak 80,\allowbreak 0,\allowbreak 0) \]

Il valore ottimo corrispondente è ${v}[5]=170$, lo stesso valore ottenuto dall'enumerazione dell'Esempio 25.3 e da Gurobi sul modello $\mathrm{ILP}_{\mathrm{ULS}}$.

Osservazione (pareggi). Nel calcolo di ${v}[5]$, il lotto nel periodo $4$ dà lo stesso valore del lotto nel periodo $3$, ma il confronto stretto conserva $j=3$. Scegliendo invece $j=4$ si ottiene l'altra soluzione ottima $(30,\allowbreak 0,\allowbreak 30,\allowbreak 50,\allowbreak 0)$ dell'Esempio 25.3. L'algoritmo di PD restituisce una soluzione ottima, non tutte.

25.2.3 Numero di passi¶

Indichiamo con $S_c(m)$ il numero di passi eseguiti da CostMatrix nel caso peggiore, dove $m$ è il numero di periodi. Il numero di esecuzioni delle sue righe è:
- La riga 2 viene eseguita $1$ volta.
- Le righe 3, 4, 5 e 6 vengono eseguite $m$ volte ciascuna.
- Le righe 7, 8, 9 e 10 vengono eseguite $\displaystyle\sum_{j=1}^{m}(m-j)=\frac{m(m-1)}{2}$ volte ciascuna.
- La riga 13 viene eseguita $1$ volta.
Quindi

\[ S_c(m)=2+4m+4\cdot\frac{m(m-1)}{2}=2m^2+2m+2. \]
Indichiamo con $S(m)$ il numero di passi eseguiti da DP_WW nel caso peggiore. La riga 2 esegue CostMatrix, cioè $S_c(m)$ passi. Nel caso peggiore, la condizione alla riga 8 è vera a ogni iterazione del ciclo interno, e quindi la riga 9 viene eseguita tante volte quanto la riga 8. Il numero di esecuzioni delle altre righe è:
- La riga 3 viene eseguita $1$ volta.
- La riga 4 viene eseguita $1$ volta.
- La riga 5 viene eseguita $m$ volte.
- La riga 6 viene eseguita $m$ volte.
- La riga 7 viene eseguita $\displaystyle\sum_{t=1}^{m}t$ volte.
- La riga 8 viene eseguita $\displaystyle\sum_{t=1}^{m}t$ volte.
- La riga 9 viene eseguita $\displaystyle\sum_{t=1}^{m}t$ volte.
- La riga 12 viene eseguita $m$ volte.
- La riga 14 viene eseguita $1$ volta.
Quindi il numero totale di passi nel caso peggiore è

\[ S(m)=S_c(m)+3+3m+3\sum_{t=1}^{m}t =2m^2+2m+2+3+3m+3\cdot\frac{m(m+1)}{2} =\frac{7m^2+13m+10}{2}. \]

Di conseguenza,

\[ S(m)=\Theta(m^2). \]

Infatti,

\[ \lim_{m\to\infty} \frac{\frac{7m^2+13m+10}{2}}{m^2} = \lim_{m\to\infty} \frac{1}{2}\left(7+\frac{13}{m}+\frac{10}{m^2}\right) = \frac{7}{2}\in\mathbb{R}_{>0}. \]

L'algoritmo di PD esegue

\[ S(m)=\Theta(m^2) \]

passi nel caso peggiore.
DP_WW_InfoSol aggiunge solo un numero costante di operazioni negli stessi cicli, e quindi il suo numero di passi ha lo stesso ordine di crescita.

Avanti: Errori tipici · In sintesi

\(t\)	\(j\)	\({v}[t]\)	\(\mathit{b}\)	Azione
\(-\)	\(-\)	0	\(-\)	\({v}[0]\leftarrow 0\)
	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
1	1	\(-\)	50	\({v}[0]{+}{c}[1][1]=0{+}50=50<+\infty\): \(\mathit{b}\leftarrow 50\)
	\(-\)	50	50	\({v}[1]\leftarrow \mathit{b}=50\)
	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
2	1	\(-\)	60	\({v}[0]{+}{c}[1][2]=0{+}60=60<+\infty\): \(\mathit{b}\leftarrow 60\)
	2	\(-\)	60	\({v}[1]{+}{c}[2][2]=50{+}50=100>60\): nessun aggiornamento
	\(-\)	60	60	\({v}[2]\leftarrow \mathit{b}=60\)
	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
3	1	\(-\)	120	\({v}[0]{+}{c}[1][3]=0{+}120=120<+\infty\): \(\mathit{b}\leftarrow 120\)
	2	\(-\)	120	\({v}[1]{+}{c}[2][3]=50{+}80=130>120\): nessun aggiornamento
	3	\(-\)	110	\({v}[2]{+}{c}[3][3]=60{+}50=110<120\): \(\mathit{b}\leftarrow 110\)
	\(-\)	110	110	\({v}[3]\leftarrow \mathit{b}=110\)
	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
4	1	\(-\)	240	\({v}[0]{+}{c}[1][4]=0{+}240=240<+\infty\): \(\mathit{b}\leftarrow 240\)
	2	\(-\)	210	\({v}[1]{+}{c}[2][4]=50{+}160=210<240\): \(\mathit{b}\leftarrow 210\)
	3	\(-\)	150	\({v}[2]{+}{c}[3][4]=60{+}90=150<210\): \(\mathit{b}\leftarrow 150\)
	4	\(-\)	150	\({v}[3]{+}{c}[4][4]=110{+}50=160>150\): nessun aggiornamento
	\(-\)	150	150	\({v}[4]\leftarrow \mathit{b}=150\)
	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
5	1	\(-\)	280	\({v}[0]{+}{c}[1][5]=0{+}280=280<+\infty\): \(\mathit{b}\leftarrow 280\)
	2	\(-\)	240	\({v}[1]{+}{c}[2][5]=50{+}190=240<280\): \(\mathit{b}\leftarrow 240\)
	3	\(-\)	170	\({v}[2]{+}{c}[3][5]=60{+}110=170<240\): \(\mathit{b}\leftarrow 170\)
	4	\(-\)	170	\({v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}\): nessun aggiornamento
	5	\(-\)	170	\({v}[4]{+}{c}[5][5]=150{+}50=200>170\): nessun aggiornamento
	\(-\)	170	170	\({v}[5]\leftarrow \mathit{b}=170\)

\(t\)	\(j\)	\({r}[t]\)	\(\mathit{b}\)	\(\mathit{a}\)	Azione
\(-\)	\(-\)	\(-\)	\(-\)	\(-\)	Stato iniziale
	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
1	1	\(-\)	50	1	\({v}[0]{+}{c}[1][1]=0{+}50=50<+\infty\): \(\mathit{b}\leftarrow 50\), \(\mathit{a}\leftarrow 1\)
	\(-\)	1	50	1	\({v}[1]\leftarrow \mathit{b}=50\), \({r}[1]\leftarrow \mathit{a}=1\)
	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
2	1	\(-\)	60	1	\({v}[0]{+}{c}[1][2]=0{+}60=60<+\infty\): \(\mathit{b}\leftarrow 60\), \(\mathit{a}\leftarrow 1\)
	2	\(-\)	60	1	\({v}[1]{+}{c}[2][2]=50{+}50=100>60\): nessun aggiornamento
	\(-\)	1	60	1	\({v}[2]\leftarrow \mathit{b}=60\), \({r}[2]\leftarrow \mathit{a}=1\)
	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
3	1	\(-\)	120	1	\({v}[0]{+}{c}[1][3]=0{+}120=120<+\infty\): \(\mathit{b}\leftarrow 120\), \(\mathit{a}\leftarrow 1\)
	2	\(-\)	120	1	\({v}[1]{+}{c}[2][3]=50{+}80=130>120\): nessun aggiornamento
	3	\(-\)	110	3	\({v}[2]{+}{c}[3][3]=60{+}50=110<120\): \(\mathit{b}\leftarrow 110\), \(\mathit{a}\leftarrow 3\)
	\(-\)	3	110	3	\({v}[3]\leftarrow \mathit{b}=110\), \({r}[3]\leftarrow \mathit{a}=3\)
	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
4	1	\(-\)	240	1	\({v}[0]{+}{c}[1][4]=0{+}240=240<+\infty\): \(\mathit{b}\leftarrow 240\), \(\mathit{a}\leftarrow 1\)
	2	\(-\)	210	2	\({v}[1]{+}{c}[2][4]=50{+}160=210<240\): \(\mathit{b}\leftarrow 210\), \(\mathit{a}\leftarrow 2\)
	3	\(-\)	150	3	\({v}[2]{+}{c}[3][4]=60{+}90=150<210\): \(\mathit{b}\leftarrow 150\), \(\mathit{a}\leftarrow 3\)
	4	\(-\)	150	3	\({v}[3]{+}{c}[4][4]=110{+}50=160>150\): nessun aggiornamento
	\(-\)	3	150	3	\({v}[4]\leftarrow \mathit{b}=150\), \({r}[4]\leftarrow \mathit{a}=3\)
	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
5	1	\(-\)	280	1	\({v}[0]{+}{c}[1][5]=0{+}280=280<+\infty\): \(\mathit{b}\leftarrow 280\), \(\mathit{a}\leftarrow 1\)
	2	\(-\)	240	2	\({v}[1]{+}{c}[2][5]=50{+}190=240<280\): \(\mathit{b}\leftarrow 240\), \(\mathit{a}\leftarrow 2\)
	3	\(-\)	170	3	\({v}[2]{+}{c}[3][5]=60{+}110=170<240\): \(\mathit{b}\leftarrow 170\), \(\mathit{a}\leftarrow 3\)
	4	\(-\)	170	3	\({v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}\): nessun aggiornamento
	5	\(-\)	170	3	\({v}[4]{+}{c}[5][5]=150{+}50=200>170\): nessun aggiornamento
	\(-\)	3	170	3	\({v}[5]\leftarrow \mathit{b}=170\), \({r}[5]\leftarrow \mathit{a}=3\)

Iterazione	\(t\)	\({r}[t]\)	\(x[1]\)	\(x[3]\)	\(t\leftarrow {r}[t]-1\)
\(-\)	\(-\)	\(-\)	0	0	\(t=5\)
\(1\)	\(5\)	\(3\)	0	80	\(t=3-1=2\)
\(2\)	\(2\)	\(1\)	30	80	\(t=1-1=0\)