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).
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.
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 a sequence of Bellman's function, Bk(r). This function reflects the optimal value of the goal function for a system of k redundant groups and a specified restriction r. As usual, we start at the beginning:
It is clear that in such a way we determine the number of units that are necessary for the redundant group to have a reliability index equal to r(1) that is within the interval [0, R0]. (See Fig. 5.1.)
Now we compose the next function (see Fig. 5.2):
In a sense, we have a “convolution” of the first and second redundant groups, and for each level of current redundancy, the best variant of such convolution is kept for the next stage of the procedure. In an analogous way, the recurrent procedure continues until the last Bellman's equation is compiled:
Actually, Equation (5.3) gives us only a solution for xn: other xis are “hidden” in previous stages of compiling Bellman's equation. Indeed, Equation (5.3) contains Bn−1(r(n−1)), which allows us to determine xn−1, and so on. The last found will be x1. In a sense, the process of finding optimal xis is going backward relating to the process of Bellman's function compiling.
Solution of the inverse problem of optimal redundancy is similar. The only difference is that the system reliability becomes an objective function and the total system cost becomes the constraint. The procedure does not need additional explanations.
At the first stage of the recurrent procedure, one compiles the Bellman's equation of the form:
(5.4)
Then consequently other equations:
(5.5)
(5.6)
The optimal solution is found by the same return to the beginning of the recurrent procedure.
For illustration of the calculated procedure of dynamic programming, let us consider a simple illustrative example.
DPM is a well-organized enumeration using convolutions of a set of possible solutions. It has some “psychological” deficiency: a researcher gets the final results without “submerging” into the solving process. If a researcher is not satisfied by a particular solution for some specified restrictions and decides to change them, it may lead to a complete resolving of the problem.
For most practical engineering problems, using Kettelle's Algorithm (Kettelle, 1962; see Box) is actually a modification of the DPM. It differs from DPM by a simple and intuitively clear organization of calculating process. This algorithm is very effective for the exact solution of engineering problems due to its clarity and flexibility of calculations.
Of course, Kettelle's Algorithm, as well as DPM, requires more computer time and memory than SDM, but it gives strict solutions. At the same time, this algorithm allows one to construct an entire dominating sequence (as SDM) that allows one to switch from solving the direct optimal redundancy problem to the inverse one using the previously calculated sequence.
We shall describe Kettelle's Algorithm step by step.
The size of the table (i.e., values m and n) is not fixed a priori. It could be increased if a sequence of dominating pairs {R12(x1, x2), C12(x1, x2)} does not include a desired solution.
As the result, now we have a system with n − 1 redundant groups: groups from 3 to N and one new group formed by the described composing of groups 1 and 2.
The procedure continues until one obtains a single composed group that is used in both cases: for solving direct as well as inverse problems of optimal redundancy.
For demonstration of the Kettelle's Algorithm, let us consider a simple numerical example with a system of three redundant groups of active units (see Fig. 5.3).
Let and Cj(xj) = cjxj where 1 ≤ j ≤ 3. Assume that q1 = 0.3, q2 = 0.5, q3 = 0.5, and c1 = 1, c2 = 3, c3 = 1.
For the sake of calculating convenience, let us prepare in advance dominated sequences for each redundant group, presented in Table 5.5. (Notice that for a single group, sequence of a pair's “reliability-cost” is always dominating, since each added unit increases simultaneously both the cost and reliability index.)
Looking at Figure 5.4, it is easy to see that each function R(C) is concave.
The next step is construction of a table (Table 5.6) with various combinations of possible configurations of groups 1 and 2 by the rules and C(x1, x2) = c1x1 + c2x2. (Numbers in bold italic denote the members of dominating pairs by ascending ordering by weights.)
From Figure 5.5, one can see that the dominating sequence is not strictly concave, though there is some kind of concave envelope that, by the way, very often coincides with solutions obtained by the SDM.
On the basis of Table 5.6, one can construct Table 5.7, containing only dominating reliability-cost pairs.
Let us enumerate corresponding pairs of this dominating sequence with the number x(1). Now we have a system consisting of two redundant groups: group 3 (data are on the lower lines of Table 5.5) and the newly composed group (data are in Table 5.7). On the basis of these data let us combine the final group for the considering system (Table 5.8 and Table 5.9).
Using Table 5.7, it is easy to get solutions for both direct and inverse problems of optimal redundancy (see Fig. 5.6). For instance, if one needs to find the best redundant unit allocation to satisfy the requirement R ≥ 0.8, then from Table 5.7 we find that the solution for corresponding value (R = 0.825) is in cell (x(1) = 9, x3 = 4). The cost of redundant units in this case is 12. In turn, for x(1) = 9 one finds that this corresponds to x2 = 1 and x2 = 2.
Thus, the solution of the inverse problem is (x1 = 2, x2 = 2, x3 = 3).
If there is a limitation on the redundant units total cost equal to 10, then from Table 5.7 one finds that corresponding maximum value of probability of failure-free operation (PFFO) is 0.746. This solution corresponds to a cell (x(1) = 8, x3 = 3). In turn, for x(1) = 8 one finds that this corresponds to x1 = 1 and x2 = 2.
Thus, the solution of the inverse problem is (x1 = 1, x2 = 2, x3 = 3).
There are two ways of choosing redundant groups for composing a dominating sequence (see Fig. 5.7).
For computer solution, both types are equivalent. However if one needs to make calculations by hand, then the dichotomous way gives a substantial decrease in calculations.
Chronological Bibliography
Bellman, R. 1957. Dynamic Programming. Princeton University Press.
Bellman, R., and Dreyfus, S. E. 1962. Applied Dynamic Programming. Princeton University Press.
Kettelle, J. D., Jr.Jr. 1962. “Least-coast allocation of reliability investment.” Operations Research, no. 2.
Li, J. 1966. “A bound dynamic programming for solving reliability redundancy optimization.” Microelectronics Reliability, no. 10.
Ushakov, I. A. 1969. Method of Solving Optimal Redundancy Problems under Constraints (in Russian). Sovetskoe Radio.
Misra, K. B. 1971. “Dynamic programming formulation of the redundancy allocation problem.” International Journal of Mathematical Education in Science and Technology, no. 3.
Yalaoui, A., Chatelet, E., and Chu, C. 2005. “A new dynamic programming method for reliability and redundancy allocation in a parallel-series system.” IEEE Transactions on Reliability, no. 2.