Dynamic Programming

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:

mi i = 1 i =2 i = 3
  r1m1 c1m1 r2m2 c2m2 r3m3 c3m3
1 .5 2 .7 3 .6 1
2 .7 4 .8 5 .8 2
3 .9 5 .9 6 .9 3

Here mi is the number of parallel units placed with ith component, rimi is the reliability of the ith component and cimi is the cost for the ith component. Determine mi 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 xi be defined as the capital allocated stages 1, 2, ..., i. The reliability rimi is a function of cimi, i.e., rimi (cimi).
In general the recursive equation is ¦i(xi) = Max. {rimi (cimi) ¦i -1(xi – cimi)}
where mi = 1, 2, 3.
0 £ cimi £ xi, 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

State Evaluations of feasible alternatives
¦1(x1) = r1m1 (c1m1) 		Maximum reliability
  m1 = 1 m1 = 2 m1 = 3
x1 r1m1 = .5 c1m1 = 2 r1m1 = .7 c1m1 = 4 r1m1 = .9 c1m1 = 5 ¦1(x1) m1*
0 - - - - -
1 - - - - -
2 .5 - - .5 1
3 .5 - - .5 1
4 .5 .7 - .7 2
5 .5 .7 .9 .9 3
6 .5 .7 .9 .9 3
7 .5 .7 .9 .9 3
8 .5 .7 .9 .9 3
9 .5 .7 .9 .9 3
10 .5 .7 .9 .9 3

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

Stage 2

State ¦2(x2) = r2m2 (c2m2). ¦1(x2 – c2m2) Maximum reliability
  m2 = 1 m2 = 2 m2 = 3
x2 r2m2 = .7 c2m2 = 3 r2m2 = .8 c2m2 = 5 r2m2 = .9 c2m2 = 6 ¦2(x2) m2*
0 - - - - -
1 - - - - -
2 - - - - -
3 .7 X ( - ) = - - - - -
4 .7 X ( - ) = - - - - -
5 .7 X .5 = .35 .8 X ( - ) = ( - ) - .35 1
6 .7 X .5 = .35 .8 X ( - ) = ( - ) .9 X ( - ) = ( - ) .35 1
7 .7 X .7 = .49 .8 X .5 = .40 .9 X ( - ) = ( - ) .49 1
8 .7 X .9 = .63 .8 X .5 = .40 .9 X .5 = .45 .63 1
9 .7 X .9 = .63 .8 X .7 = .56 .9 X .5 = .45 .63 1
10 .7 X .9 = .63 .8 X .9 = .72 .9 X .7 = .63 .72 2

Note that in case m2 = 1, ¦1(x2 - c2m2) has no value until x2 – c2m2 £ 1 or x2 £ 1+ c2m2 = 1 + 3 = 4. Similar is the case with other columns in this table.

Stage 3

State ¦3(x3) = r3m3 (c3m3). ¦2(x3 - c3m3) Maximum reliability
  m3 = 1 m3 = 2 m3 = 3
x3 r3m3 = .6 c3m3 = 1 r3m3 = .8 c3m3 = 2 r3m3 = .9 c3m3 = 3 ¦3(x3) m3*
0 - - - - -
1 .6 X ( - ) = ( - ) - - - -
2 .6 X ( - ) = ( - ) .8 X ( - ) = ( - ) - - -
3 .6 X ( - ) = ( - ) .8 X ( - ) = ( - ) .9 X ( - ) = ( - ) - -
4 .6 X ( - ) = ( - ) .8 X ( - ) = ( - ) .9 X ( - ) = ( - ) - -
5 .6 X ( - ) = ( - ) .8 X ( - ) = ( - ) .9 X ( - ) = ( - ) - -
6 .6 X .35 = .210 .8 X ( - ) = ( - ) .9 X ( - ) = ( - ) .210 1
7 .6 X .35 = .210 .8 X .35 = .280 .9 X ( - ) = ( - ) .280 2
8 .6 X .49 = .294 .8 X .35 = .280 .9 X .35 = .315 .315 3
9 .6 X .63 = .378 .8 X .49 = .392 .9 X .35 = .315 .392 2
10 .6 X .63 = .378 .8 X .63 = .504 .9 X .49 = .441 .504 2

The maximum reliability is .504. for the m3* = 2. Also for this, the optimal ¦2(x3 – c3m2) = ¦2(8) = .63. Hence the corresponding m2* = 2. Similarly, the corresponding m1* = 3.

The dynamic programming technique is useful for making a sequence of interrelated decisions where the objective is to optimize the overall outcome of the entire sequence of decisions over a period of time. This technique decomposes the original problem into a sequence of stages, which can then be handled more efficiently from the computational point of view. In contrast, most linear and nonlinear programming approaches attempt to solve such problems by considering all the constraints simultaneously. The dynamic programming technique is used in various fields such as inventory control, replacement, bidding problems, allocation, etc.


Operations Research Contents
  
Copyright © www.universalteacher.com