Dynamic programming is a quantitative analysis technique that has been applied to large, complex problems that have sequences of decisions to be made. Dynamic programming divides problems into a number of decision stages; the outcome of a decision at one stage affects the decision at each of the next stages. The technique is useful in a large number of multiperiod business problems, such as smoothing production employment, allocating capital funds, allocating salespeople to marketing areas, and evaluating investment opportunities.

Dynamic programming differs from linear programming in two ways. First, there is no algorithm (as in the simplex method) that can be programmed to solve all problems. Dynamic programming is, instead, a technique that allows us to break up difficult problems into a sequence of easier subproblems, which are then evaluated by stages. Second, linear programming is a method that gives single-stage (one-time-period) solutions. Dynamic programming has the power to determine the optimal solution over a 1-year time horizon by breaking the problem into 12 smaller 1-month horizon problems and to solve each of these optimally. Hence, it uses a multistage approach.

Solving problems with dynamic programming involves four steps.

In this module, we show how to solve two types of dynamic programming problems: network and nonnetwork. The shortest-route problem is a network problem that can be solved by dynamic programming. The knapsack problem is an example of a nonnetwork problem that can be solved using dynamic programming.