Dynamic Programming Example

An Electronic Device Problem

Example

An electronic device consists of three main components. The failure of one of the components results in the failure of the whole device because the three components are arranged in series. Therefore, it is decided that the reliability (prob. of not failure) of the device can be increased by installing parallel units on each component. Each component may be installed at most 3 parallel units. The total capital (in thousands) available for the device is 10. Consider the following data:

On small screens, use horizontal scrollbar to view full calculation

Here m_i is the number of parallel units placed with i^th component, r_im_i is the reliability of the i^th component and c_im_i is the cost for the i^th component. Determine m_i which will maximize the total reliability of the system without exceeding the given capital.

Solution.

In this example, we consider each component as one stage. Let the state x_i be defined as the capital allocated stages 1, 2, ..., i. The reliability r_im_i is a function of c_im_i, i.e., r_im_i (c_im_i).
In general the recursive equation is ƒ_i(x_i) = Max. {r_im_i (c_im_i) ƒ_{i -1}(x_i – c_im_i)}
where m_i = 1, 2, 3.
0 ≤ c_im_i ≤ x_i, i = 1, 2, 3.
There is one table for each possible stage n, namely, n = 1, 2, and 3. We summarize this information in the format below:

Stage 1

The analysis for n = 2 appears in the following table.

Stage 2

Use horizontal scrollbar to view full calculation

Note that in case m₂ = 1, _ƒ1(x₂ - c₂m₂) has no value until x₂ – c₂m₂ ≤ 1 or x₂ ≤ 1+ c₂m₂ = 1 + 3 = 4. Similar is the case with other columns in this table.

Stage 3

The maximum reliability is .504. for the m₃* = 2. Also for this, the optimal _ƒ2(x₃ – c₃m₂) = _ƒ2(8) = .63. Hence the corresponding m₂* = 2. Similarly, the corresponding m₁* = 3.