JMU
Dynamic Programming
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Review
A "Special" Example with Two Decision Variables
Motivation
An Example of a Problem with Stages

\( \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} \)

An Example of a Problem with Stages (cont.)

A Visualization

images/dynamic-programming_stages_small.gif
An Example of a Problem with Stages (cont.)

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} \)

An Larger Example with Stages

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} \)

A Myopic/Greedy Heuristic
Complete Enumeration
Dynamic Programming Algorithm
Applying the Algorithm to the Example
Applying the Algorithm to the Example (cont.)
Applying the Algorithm to the Example (cont.)
Applying the Algorithm to the Example (cont.)
Characteristics of Dynamic Programming Problems