Optimal Resource Allocation: With Practical Statistical Applications and Theory

CHAPTER 5

Dynamic Programming

As mentioned earlier, the problem has an essentially discrete nature, so the SDM cannot guarantee the accuracy of the solution. Thus, if an exact solution of the optimal redundancy problem is needed, one generally needs to use the Dynamic Programming Method (DPM).

5.1 Bellman's Algorithm

The main ideas of the DPM were formulated by an American mathematician Richard Bellman (Bellman, 1957; see Box), who has formulated the so-called optimality principle.

Richard Ernest Bellman (1920–1984)

American applied mathematician, who is famous for his invention of dynamic programming in 1953. He also made many important contributions in other fields of mathematics. Over the course of his career Bellman published 619 papers and 39 books. During the last 11 years of his life he published over 100 papers, despite suffering from the crippling complications of brain surgery. Bellman's fundamental contributions to science and engineering won him many honors, including the First Norbert Wiener Prize in Applied Mathematics (1970).

The DPM provides an exact solution of discrete optimization problems. In fact, it is a well-organized method of direct enumeration. For the accuracy of the solutions, one has to pay with a high calculation time and a huge computer memory if the problem is highly dimensional.

To solve the direct optimal redundancy problem, let us construct ...