Exercises · DP for the uncapacitated lot sizing problem¶
Exercises · Chapter 25 · each solution opens with a click · Chapter 25: Uncapacitated lot sizing (ULS) · Exercises, volume 3 (PDF)
Exercise 25.1: Exercise 1: Uncapacitated Lot-Sizing Problem
Consider the following ULS instance with \(m=4\) periods, where the demands, the setup costs, the variable production costs, and the holding costs are:
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrix \({c}\), of the vector \({v}\), and of the vector \({r}\).
-
Using the vector \({r}\), reconstruct an optimal solution \((x_1,x_2,\dots,x_m)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
First, the matrix \({c}\) is computed. For each step, the table shows the values of \(j\) and \(t\), the current value of \(\mathit{u}\), the cell \({c}[j][t]\), and the operation performed; the cell \({c}[j][t]\) is highlighted in blue when assigned.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Action \(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\) This is the matrix \({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} \]For each step of the DP algorithm, the table shows the values of \(t\) and \(j\), the cells \({v}[t]\) and \({r}[t]\), the current value of \(\mathit{b}\), and the current value of \(\mathit{a}\). The cell of \(\mathit{b}\) is highlighted in red when updated; the cell of \(\mathit{a}\) is highlighted in blue when updated; the cells of \({v}[t]\) and \({r}[t]\) are highlighted in blue when assigned.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Action \(-\) \(-\) 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\): no update \(-\) 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\): no update 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\): no update 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\): no update \(-\) 280 3 280 3 \({v}[4]\leftarrow \mathit{b}=280\), \({r}[4]\leftarrow \mathit{a}=3\) This is the vector \({v}\) after the execution of the DP algorithm:
\[ \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} \]This is the vector \({r}\) after the execution of the DP algorithm:
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 \\ \hline \end{array} \] -
We have the following vector \({r}\):
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 \\ \hline \end{array} \]We can reconstruct an optimal solution as follows:
Iteration \(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\): the last production run of periods \(1,\dots,4\) is in period \(3\) and covers the demands of periods \(3,\dots,4\), so \(x[3]\leftarrow d_{3}+d_{4}=40+10=50\)
-
\(t=2\), \({r}[2]=1\): the last production run of periods \(1,\dots,2\) is in period \(1\) and covers the demands of periods \(1,\dots,2\), so \(x[1]\leftarrow d_{1}+d_{2}=30+10=40\)
Thus, the vector
\[ (40,\allowbreak 0,\allowbreak 50,\allowbreak 0) \]is an optimal solution. The setups are in periods \(1\), \(3\), the inventories are \((s_1,\dots,s_{4})=(10,\allowbreak 0,\allowbreak 10,\allowbreak 0)\), and the total cost is
\[\begin{align*} &\underbrace{50+70}_{\text{setup}}+\underbrace{2\cdot 40+3\cdot 0+1\cdot 50+2\cdot 0}_{\text{production}}\\ &\quad+\underbrace{1\cdot 10+2\cdot 0+2\cdot 10+1\cdot 0}_{\text{holding}}=120+130+30=280. \end{align*}\]The optimal value is
\[ {v}[4]=280. \] -
Exercise 25.2: Exercise 2: Uncapacitated Lot-Sizing Problem
Consider the following ULS instance with \(m=4\) periods, where the demands, the setup costs, the variable production costs, and the holding costs are:
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrix \({c}\), of the vector \({v}\), and of the vector \({r}\).
-
Using the vector \({r}\), reconstruct an optimal solution \((x_1,x_2,\dots,x_m)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
First, the matrix \({c}\) is computed. For each step, the table shows the values of \(j\) and \(t\), the current value of \(\mathit{u}\), the cell \({c}[j][t]\), and the operation performed; the cell \({c}[j][t]\) is highlighted in blue when assigned.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Action \(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\) This is the matrix \({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} \]For each step of the DP algorithm, the table shows the values of \(t\) and \(j\), the cells \({v}[t]\) and \({r}[t]\), the current value of \(\mathit{b}\), and the current value of \(\mathit{a}\). The cell of \(\mathit{b}\) is highlighted in red when updated; the cell of \(\mathit{a}\) is highlighted in blue when updated; the cells of \({v}[t]\) and \({r}[t]\) are highlighted in blue when assigned.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Action \(-\) \(-\) 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\): no update \(-\) 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\): no update 3 \(-\) \(-\) 190 1 \({v}[2]{+}{c}[3][3]=160{+}100=260>190\): no update \(-\) 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\): no update 3 \(-\) \(-\) 270 1 \({v}[2]{+}{c}[3][4]=160{+}160=320>270\): no update 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\) This is the vector \({v}\) after the execution of the DP algorithm:
\[ \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} \]This is the vector \({r}\) after the execution of the DP algorithm:
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 1 & 4 \\ \hline \end{array} \] -
We have the following vector \({r}\):
\[ \begin{array}{c|cccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} \\ \hline {{r}[t]} & 1 & 1 & 1 & 4 \\ \hline \end{array} \]We can reconstruct an optimal solution as follows:
Iteration \(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\): period \(4\) produces only its own demand, so \(x[4]\leftarrow d_{4}=20\)
-
\(t=3\), \({r}[3]=1\): the last production run of periods \(1,\dots,3\) is in period \(1\) and covers the demands of periods \(1,\dots,3\), so \(x[1]\leftarrow d_{1}+d_{2}+d_{3}=30+40+10=80\)
Thus, the vector
\[ (80,\allowbreak 0,\allowbreak 0,\allowbreak 20) \]is an optimal solution. The setups are in periods \(1\), \(4\), the inventories are \((s_1,\dots,s_{4})=(50,\allowbreak 10,\allowbreak 0,\allowbreak 0)\), and the total cost is
\[\begin{align*} &\underbrace{50+50}_{\text{setup}}+\underbrace{1\cdot 80+3\cdot 0+2\cdot 0+1\cdot 20}_{\text{production}}\\ &\quad+\underbrace{1\cdot 50+1\cdot 10+1\cdot 0+2\cdot 0}_{\text{holding}}=100+100+60=260. \end{align*}\]The optimal value is
\[ {v}[4]=260. \] -
Exercise 25.3: Exercise 3: Uncapacitated Lot-Sizing Problem
Consider the following ULS instance with \(m=5\) periods, where the demands, the setup costs, the variable production costs, and the holding costs are:
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrix \({c}\), of the vector \({v}\), and of the vector \({r}\).
-
Using the vector \({r}\), reconstruct an optimal solution \((x_1,x_2,\dots,x_m)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
First, the matrix \({c}\) is computed. For each step, the table shows the values of \(j\) and \(t\), the current value of \(\mathit{u}\), the cell \({c}[j][t]\), and the operation performed; the cell \({c}[j][t]\) is highlighted in blue when assigned.
\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Action \(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\) This is the matrix \({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} \]For each step of the DP algorithm, the table shows the values of \(t\) and \(j\), the cells \({v}[t]\) and \({r}[t]\), the current value of \(\mathit{b}\), and the current value of \(\mathit{a}\). The cell of \(\mathit{b}\) is highlighted in red when updated; the cell of \(\mathit{a}\) is highlighted in blue when updated; the cells of \({v}[t]\) and \({r}[t]\) are highlighted in blue when assigned.
\(t\) \(j\) \({v}[t]\) \({r}[t]\) \(\mathit{b}\) \(\mathit{a}\) Action \(-\) \(-\) 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\): no update \(-\) 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\): no update 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\): no update \(-\) 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\): no update \(-\) 420 4 420 4 \({v}[5]\leftarrow \mathit{b}=420\), \({r}[5]\leftarrow \mathit{a}=4\) This is the vector \({v}\) after the execution of the DP algorithm:
\[ \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} \]This is the vector \({r}\) after the execution of the DP algorithm:
\[ \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} \] -
We have the following vector \({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} \]We can reconstruct an optimal solution as follows:
Iteration \(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\): the last production run of periods \(1,\dots,5\) is in period \(4\) and covers the demands of periods \(4,\dots,5\), so \(x[4]\leftarrow d_{4}+d_{5}=30+40=70\)
-
\(t=3\), \({r}[3]=3\): period \(3\) produces only its own demand, so \(x[3]\leftarrow d_{3}=40\)
-
\(t=2\), \({r}[2]=1\): the last production run of periods \(1,\dots,2\) is in period \(1\) and covers the demands of periods \(1,\dots,2\), so \(x[1]\leftarrow d_{1}+d_{2}=10+30=40\)
Thus, the vector
\[ (40,\allowbreak 0,\allowbreak 40,\allowbreak 70,\allowbreak 0) \]is an optimal solution. The setups are in periods \(1\), \(3\), \(4\), the inventories are \((s_1,\dots,s_{5})=(30,\allowbreak 0,\allowbreak 0,\allowbreak 40,\allowbreak 0)\), and the total cost is
\[\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{production}}\\ &\quad+\underbrace{1\cdot 30+1\cdot 0+2\cdot 0+1\cdot 40+2\cdot 0}_{\text{holding}}=200+150+70=420. \end{align*}\]The optimal value is
\[ {v}[5]=420. \] -