Dynamic Programming11Dynamic programming is an optimization approach that transforms a complex problem into a sequence ofsimpler problems; its essential characteristic is the multistage nature of the optimization procedure. More sothan the optimization techniques described previously, dynamic programming provides a general frameworkfor analyzing many problem types. Within this framework a variety of optimization techniques can beemployed to solve particular aspects of a more general formulation. Usually creativity is required beforewe can recognize that a particular problem can be cast effectively as a dynamic program; and often subtleinsights are necessary to restructure the formulation so that it can be solved effectively.We begin by providing a general insight into the dynamic programming approach by treating a simpleexample in some detail. We then give a formal characterization of dynamic programming under certainty,followed by an in-depth example dealing with optimal capacity expansion. Other topics covered in thechapter include the discounting of future returns, the relationship between dynamic-programming problemsand shortest paths in networks, an example of a continuous-state-space problem, and an introduction todynamic programming under uncertainty.11.1 AN ELEMENTARY EXAMPLEIn order to introduce the dynamic-programming approach to solving multistage problems, in this section weanalyze a simple example. Figure 11.1 represents a street map connecting homes and downtown parkinglots for a group of commuters in a model city. The arcs correspond to streets and the nodes correspond tointersections. The network has been designed in a diamond pattern so that every commuter must traverse fivestreets in driving from home to downtown. The design characteristics and traffic pattern are such that the totaltime spent by any commuter between intersections is independent of the route taken. However, substantialdelays, are experienced by the commuters in the intersections. The lengths of these delays in minutes, areindicated by the numbers within the nodes. We would like to minimize the total delay any commuter canincur in the intersections while driving from his home to downtown. Figure 11.2 provides a compact tabularrepresentation for the problem that is convenient for discussing its solution by dynamic programming. In thisfigure, boxes correspond to intersections in the network. In going from home to downtown, any commutermust move from left to right through this diagram, moving at each stage only to an adjacent box in the nextcolumn to the right. We will refer to the ‘‘stages to go," meaning the number of intersections left to traverse,not counting the intersection that the commuter is currently in.The mostnaive approach to solving the problem would be to enumerate all 150 paths through the diagram,selecting the path that gives the smallest delay. Dynamic programming reduces the number of computationsby moving systematically from one side to the other, building the best solution as it goes.Suppose that we move backward through the diagram from right to left. If we are in any intersection (box)with no further intersections to go, we have no decision to make and simply incur the delay corresponding tothat intersection. The last column in Fig. 11.2 summarizes the delays with no (zero) intersections to go.32011.1 An Elementary Example 321Figure 11.1 Street map with intersection delays.Figure 11.2 Compact representation of the network.322 Dynamic Programming 11.1Our first decision (from right to left) occurs with one stage, or intersection, left to go. If for example, weare in the intersection corresponding to the highlighted box in Fig. 11.2, we incur a delay of three minutes inthis intersection and a delay of either eight or two minutes in the last intersection, depending upon whetherwe move up or down. Therefore, the smallest possible delay, or optimal solution, in this intersection is3+ 2 = 5 minutes. Similarly, we can consider each intersection (box) in this column in turn and compute thesmallest total delay as a result of being in each intersection. The solution is given by the bold-faced numbersin Fig. 11.3. The arrows indicate the optimal decision, up or down, in any intersection with one stage, or oneintersection, to go.Note that the numbers in bold-faced type in Fig. 11.3 completely summarize, for decision-making pur-poses, the total delays over the last two columns. Although the original numbers in the last two columnshave been used to determine the bold-faced numbers, whenever we are making decisions to the left of thesecolumns we need only know the bold-faced numbers. In an intersection, say the topmost with one stage togo, we know that our (optimal) remaining delay, including the delay in this intersection, is five minutes. Thebold-faced numbers summarize all delays from this point on. For decision-making to the left of the bold-facednumbers, the last column can be ignored.With this in mind, let us back up one more column, or stage, and compute the optimal solution in eachintersection with two intersections to go. For example, in the bottom-most intersection, which is highlightedin Fig. 11.3, we incur a delay of two minutes in the intersection, plus four or six additional minutes, dependingupon whether we move up or down. To minimize delay, we move up and incur a total delay in this intersectionand all remaining intersections of 2 + 4 = 6 minutes. The remaining computations in this column aresummarized in Fig. 11.4, where the bold-faced numbers reflect the optimal total delays in each intersectionwith two stages, or two intersections, to go.Once we have computed the optimal delays in each intersection with two stages to go, we can again moveback one column and determine the optimal delays and the optimal decisions with three intersections to go.In the same way, we can continue to move back one stage at a time, and compute the optimal delays anddecisions with four and five intersections to go, respectively. Figure 11.5 summarizes these calculations.Figure 11.5(c) shows the optimal solution to the problem. The least possible delay through the networkis 18 minutes. To follow the least-cost route, a commuter has to start at the second intersection from thebottom. According to the optimal decisions, or arrows, in the diagram, we see that he should next move downto the bottom-most intersection in column 4. His following decisions should be up, down, up, down, arrivingfinally