10 Dynamic Programming ——$<$— Se rm Introduction In the ficld of mana aa “olving multistage decisi agement there occur optimization problems jqvolving mu! ee ecision processes. Such problems involving n dicision rariables x, -.. x, in their optimization models can be broken in a sequence of optimization problems each involving a single decision variable. Fundamentals of Dynamic Programming Technique mization problem involving n variables is Thus a multi stage opti such problems each involving a single txpressible as a sequence of n variable. Each one of them is called a stage. d with its state variables $j) 55j2 9 is associate 1)" stage acts as Each stage { represented simply by 5). The state variable 5; of (i= input for the ith stage and is of the ith stage by a ret esented symbolically as connected with the decision variable x; and State variable s; cursive type relation called the Sj transition function, rept 5, =t Gn Sn) jn which the problem is defined. @j-1> Si-v» optimization — (a) ‘ans is derived from the Way 27 The (i—1)th stage objective functionfi-s . timal value denoted Wat, the decision variable P ; gives the © Pf G_). ; é Under the principal of optimality as given by i Bellman (19: turn f(x, 5) is dependent 00 the previous optimal return | TGs 8 é ¢ 1)" stage by relatio® fies0.2 where o represents the relationship between the in the objective function of the main problem. 3 After expressing s;_, in (2) in terms Of Xe» Sy with: transition relation (1), the i‘* stage return function f; become of x; and s;, which on optimizing w.r.t. x; , gives x=; (5) Stage return is then a function of 5; only, given as fj (s). this way upto the last stage i=n, we get f* (s,,), which is value of the objective function of the problem. 10.2 Principle of Optimality z The principle of optimality as given by R. Bellman fy optimal policy has the Property that whatever the initial initial decisions are, the remaining decisions must o Policy with regard to the state resulting from the first Dynamic Programming Dynamic Programmin, Optimization Problem iny, breaking it in a sequence one decision. As solving the Case, we finally have get the Solution of the main Problem ul Definitions gZ is the technique of olving n (-J)th stage state variable s,_ variable x; and state Variables 5; through the to > taGeunyx oy amic Programming . : 103 The relation is used in changing sj. int (s, 1 (Sj policy : In a multi stage decision Process, jecsion al each stage. The sequence of all the 1) inx; and s;. there is a rule for making decisions form a policy. Optimal policy : Optimal policy is the sequence of values ofdicisi sariable under which the preassigned objective function is Bilis z cach stage- There is no single set procedure in dynamic programming which may te applicable in the solution of all types of problems. However the general geps, to be taken in most of the cases may be as follows : General Algorithm Step 1. As in any optimization problem, identify the decision variables and define the objective function which is to be optimized. Step 2. Decompose the problem in a sequence of stages each involving a single variable decision together with all its states. The states involved ala particular stage are also defined. Define the transformation function 5; = (@; , Sj) Conmecting s;_, with x; and 5; . Step 3. Define the relation ii @ 9) =f (ie i- -) connecting the i" stage return with the optimum return of the previous stage and the variable x; , representing the decision variable of the present (i) stage. Step 4. In the discrete type problem construct tables showing ‘clationship between stages of the present and the optimal states of the revious stage and mentioning the states of the present stage to be chosen ‘he optimality considerations (decisions). 3 Step 5. Determine the sequence of optimal decisions represe: ‘imal policy, There may be more such policies which give the same : ‘he objective function ultimately at the last final stage. “ward and Backward Recursion ,,_ Computation in a problem may be done either by fe ae we start from the initial stage to the final stage nn, *i0n by moving from the last to the first stage. "© efficient computationally and is therefore ©_ In forward recursion the transition Ce will ie sj) where as in back recursion it will be s; fe) Spay = EMG Se V i lesman Problem Model 1. Travelling Sa a Ex. 1. We illustrate both forward and backwa: ecu by solving the shortest route problem represented graphical 13 1 1 3 Fig. 1 (i) Solution by Forward Pass method Stage 1. Paths from 12, Liss distance is same. So shortest distance from 1+ 2, shortest distance from 1+3 = | shortest distance from 1 4 = Stage 2. Going from 1 to 5 There are three alternates, going from 1 | . shortest distance 1 to 5, via2 = 1 from 1 to 5 via 3 viad = least F 12 for path 1-+4-»5,(Note : No path exi stage 3. Going fr For path via 6, shortest =6+17=23 min {21, 23} So the shortest path is 1 (ii) By Backward Pass M Note : The formula is for forwar direction. If stage number! g fe nth stage (on ‘¢ above formula wi12+9 =@i) No. route 2 = Minimum | to 6 exists =a 719-69 [assis a6 Shortest Route 1+4+5-7Programming ‘SS ic eo 10.7 -, 2. Find the minimum Ex path for the foll m represented graphically, lowing travelli: ' y oO 17 74, , salesman pple’ fr Fig. 2 stage i=4 i=3 i=2 i=1 stage i=0 states y= {1} 53= {2,3} 52= {4, 5, 6} 5, = {7, 8} 59 ={9}- Sol. We follow the backward pass method and mark the stages from as 0, 1, 2, 3, 4 as indicated in the figure. Stage 0 No stage so beyond States so10.8 Stage 2 d(s1,s2) + fi () ae ee pt | 747 = 14 | +5 a7) | ob a Bisse spiv+17 = 3615.90 = 35 « i : Shortest route : Total distance = 47 mil 1+3, 34S Renae 1+3 +4. 49 YA Example 3. A salesman has the cost of the trowel Rs. and available below. Determine the minimum ‘d (5,52) +f} (1) |» |) a 7+9=16 6+12=18 9+8=17 | 6 | 6eom1s | 7412-10 8+9=17 94+12=21 8+9=17 10+12=22 8+8=I66 | 1-3 +7 11 »12 Model 2 Sing 16Py = fy =X2 Sy P2 = 2(S2 For P; to be maximum stage 2& (64-3) Using (2) pet For P, to be ee od {iey-2” =x, 2 (63 -x)} or} (83-3) (3 — 43 — 23) = i a As 53-340 80 43 = 353 =3 4, a_2a s 3 =%- 5a Zam 2 2a a using (4) %=Z=> 3 - (3) 22. 16 a le 5. Stage the peinciple of optimality it the solve the following problem. I Minimize zexntgtoeed subject to 4%) %2 %y%4 = 16, yy Sol, (Principle of optimality is 1 Define state variables ‘y»Sqital 5" %, Bene MMe 54 =aFor min of z9For mixima of 23,5 so X3 = x az, Furthers, —> = ae; for optimal policy if this stage 1 +3 = (53)3 j Xy = V5y minimum 53 =O or asia a 3 X3 = (s3)3 2523 (5) =x —=0 dry a (3)3 +ive, so Z3 is min by (9)BY 2 z A , using (2) I 3 = (23), using (14) “s =x, =2 we 6 cs “lS ee So XY =X) = = Xy = 2 Ex. 6. A company has decided to introduce a prod Phase 1. |Heavil reduced rate for a small period n pine Ane plus special offering A budget of Rs. 5 croses has been set for me and loses incurred in these phases. Ifm is the market share captured in phase il m could remain in phase 2, and fraction fz of m retained is phase 3. How should the, money be ; so that the final share be maximum, using the fo