Dynamic Programming
An Introduction |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
\( \begin{array}{r r r r r r r r r r r} \text{max} &c_{12}x_{12}&+c_{13}x_{13}&+c_{24}x_{24}&+c_{25}x_{25}& +c_{34}x_{34}&+c_{35}x_{35}&+c_{46}x_{46}&+c_{56}x_{56} \\ \text{s.t.} &+x_{12}&+x_{13}& & & & & & & = &1\\ &-x_{12}& &+x_{24}&+x_{25}& & & & & = & 0 \\ & &-x_{13}& & & +x_{34}&+x_{35}& & & = & 0 \\ & & &-x_{24}& & -x_{34}& &+x_{46}& & = & 0 \\ & & & &-x_{25}& &-x_{35}& &+x_{56}& = & 0 \\ & & & & & & &-x_{46}&-x_{56}& = & -1 \\ \end{array} \)
A Visualization
The Costs
\( \begin{array}{| c | c c c c c c |} \hline & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & &c_{12}&c_{13}& & & \\ 2 & & & &c_{24}&c_{25}& \\ 3 & & & &c_{34}&c_{35}& \\ 4 & & & & & &c_{46} \\ 5 & & & & & &c_{56} \\ 6 & & & & & & \\ \hline \end{array} \)
The Costs (by Stage)
\( \begin{array}{| c | c c c |} \hline & 2 & 3 & 4 \\ \hline 1 & 2 & 4 & 3 \\ \hline \end{array} \) \( \begin{array}{| c | c c c |} \hline & 5 & 6 & 7 \\ \hline 2 & 7 & 4 & 6 \\ 3 & 3 & 2 & 4 \\ 4 & 4 & 1 & 5 \\ \hline \end{array} \) \( \begin{array}{| c | c c |} \hline & 8 & 9 \\ \hline 5 & 1 & 4 \\ 6 & 6 & 3 \\ 7 & 3 & 3 \\ \hline \end{array} \) \( \begin{array}{| c | c |} \hline & 10 \\ \hline 8 & 3 \\ 9 & 4 \\ \hline \end{array} \)