Deterministic Dynamic Programming

CHAPTER  1 0

Deterministic Dynamic Programming

Chapter Guide. Dynamic programming (DP) determines the optimum solution of a multivariable problem by decomposing it into stages, each stage comprising a single-variable subproblem. The advantage of the decomposition is that the optimization process at each stage involves one variable only, a simpler task computationally than dealing with all the variables simultaneously. A DP model is basically a recursive equa-tion linking the different stages of the problem in a manner that guarantees that each stage's optimal feasible solution is also optimal and feasible for the entire problem. The notation and the conceptual framework of the recursive equation are unlike any you have studied so far. Experience has shown that the structure of the recursive equation may not appear "logical" to a beginner. Should you have a similar experience, the best course of action is to try to implement what may appear logical to you, and then carry out the computations accordingly. You will soon discover that the definitions in the book are the correct ones and, in the process, will learn how DP works. We have also in-cluded two partially automated Excel spreadsheets for some of the examples in which the user must provide key information to drive the DP computations. The exercise should help you understand some of the subtleties of DP.

Although the recursive equation is a common framework for formulating DP models, the solution details differ. Only through exposure to different formulations will you be able to gain experience in DP modeling and DP solution. A number of deterministic DP applications are given in this chapter. Chapter 22 on the CD presents probabilistic DP applications. Other applications in the important area of inventory modeling are presented in Chapters 11 and 14.

This chapter includes a summary of 1 real-life application, 7 solved examples, 2 Excel spreadsheet models, 32 end-of-section problems, and 1 ca·se. The case is in Ap-pendix E on the CD. The AMPL/Excel/Solver/TORA programs are in folder chl0Files.

Real-Life Application-Optimization of Crosscutting and Log Allocation at Weyerhaeuser.

Mature trees are harvested and crosscut into logs to manufacture different end prod-ucts (such as construction lumber, plywood, wafer boards, or paper). Log specifications (e.g., length and end diameters) differ depending on the mill where the logs are used. With harvested trees measuring up to 100 feet in length, the number of crosscut combi-nations meeting mill requirements can be large, and the manner in which a tree is dis-assembled into logs can affect revenues. The objective is to determine the crosscut combinations that maximize the total revenue. The study uses dynamic programming to optimize the process. The proposed system was first implemented in 1978 with an annual increase in profit of at least $7 million. Case 8 in Chapter 24 on the CD pro-vides the details of the study.