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.
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.