Decision Distance

To State  2 3 4

From State

1 10+42=52 12+36=48 16+40=56 3 48

Hence optimum (shortest) route is 137810 and the optimum (minimum) distance is 48 units.

8.6 Dynamic Programming using Calculus Method

Here we shall discuss the problems which can be solved using dynamic programming techniques through
calculus method. We illustrate the following cases:

Case-1. When both the objective function and the constraint are in additive form.

Let us consider the problem

n
Max (or Min) Z =f1(x1)+f2(x2)+……….+fn(xn) =  f i xi
i 1

s.t. a1 x1 +a2 x2 +a3 x3+……….+ an xn ≥ or = or  b

n
or  ai xi  or  or  b
i 1

and (a1, a2, a3,…., an)  0, (x1, x2, x3,…., xn)  0 and b0

or ai 0, xi 0 and b0.

To solving this type of problem, first we define the state variables si’s as

sn= a1 x1 +a2 x2 +a3 x3+……….+ an xn ≥ or = or  b

sn-1= a1 x1 +a2 x2 +a3 x3+……….+ an-1 xn-1 = sn- an xn=Tn-1(sn, xn)

sn-2= a1 x1 +a2 x2 +a3 x3+……….+ an-2 xn-2 = sn-1- an-1 xn-1=Tn-2(sn-1, xn-1)

… … … … … … …

… … … … … … …
 si= a1 x1 +a2 x2 +a3 x3+……….+ ai xi = si+1- ai+1 xi+1=Ti(si+1, xi+1)

… … … … … … …

… … … … … … …

s2= a1 x1 +a2 x2 = s3- a3 x3=T2(s3, x3)

s1= a1 x1 =s2- a2 x2=T1(s2, x2)

Where si =Ti(si+1, xi+1), i=1, 2, 3,…., n-1 are called state transformation functions connecting different
states. The recursive relations are

Fi(si) =Max (or Min) [fi (xi)+ Fi-1(si-1)]; i=1, 2, 3,….,n.

and F1(s1)=f1(x1).

Now we can start with F1(s1) and recursively optimize to get F2(s2), F3(s3), …………, Fn(sn).

This is forward dynamic programming. Also we can solve this type of problem by using backward
dynamic programming technique.

Case-2. When the objective function is in additive form and the constraint is in multiplicative form.

Case-3. When the objective function is in multiplicative form and the constraint is in additive form.

Examples
Example.3. Solve the following problem using dynamic programming:

Min Z= x12+x22+x32

s.t. x1 +x2 +x3 ≥15

and x1, x2, x3  0.

Solution. We can solve it either using forward dynamic programming or backward dynamic
programming. We solve it by using backward dynamic programming.

Backward Dynamic Programming

As there are three variables in the problem, we will have three stages to solve the problem using dynamic
programming.

Now we define the state variables as:

s1= x1 +x2 +x3 ≥15

s2= x2 +x3= s1- x1

 s3= x3= s2- x2

The recursive relations are

F3(s3) = x32= (s2- x2)2

F2(s2) = min [x22+ F3(s3)]

= min (x22+x32)

= min [x22+(s2- x2)2] with respect to x2

F1(s1) = min [x12+ F2(s2)] with respect to x1

For minimum of F2, we have

dF2
0
dx2

gives 2x2-2(s2- x2) = 0

s2
 x2= .
2

d 2 F2
Also  2+4=4 which is positive.
dx22

s2
Therefore F2 in minimum at x2 = .
2

 s 2  2  s2   s22
2
F2(s2) =     s2     .
2
 
 2   2  2


 2 s22   2 s1  x1 2 
Now F1(s1)= min  x1    min  x1  
 2  2 
For minimum of F1, we have

dF1
0
dx1

gives 2x1- (s1- x1) = 0

 s1
 x1= .
3

d 2 F1
Also  2+1=3 which is positive.
dx12

s1
Therefore F1 in minimum at x1= .
3

s12
Thus F1(s1)= , s1 15.
3
Now Min Z= min [x12+x22+x32]

= min F1(s1)
2
= (15)  75 for s1  15.
3
Here x1 = (s1/3) = 5.

s2
Min Z=75, for x1=5, s2= s1- x1=10, x2=  5, s3= s2- x2=5, x3=s3=5.
2
Hence Min Z=75, for x1=5, x2= 5, x3=5.

Example.4. Solve the following problem using dynamic programming:

Min Z= x12+x22+x32+x42

s. t. x1 x2 x3 x4 =16

and x1, x2, x3, x4  0.

Solution. We define the state variables as:

s1= x1

s2= x1 x2

s3= x1 x2x3

s4= x1 x2x3 x4

s s s
This gives s1=x1= 2 , s2 = 3 , s3 = 4 .
x2 x3 x4
As there are four decision variables in the problem, we shall have four stages in the form of following four
recursive relations:

F1(s1)= x12= s12

F2(s2) = min [x22+ F1(s1)] = min  x 2  s2  with respect to x2

2
2
 x22 

F3(s3)= min [x32+ F2(s2)] with respect to x3

F4(s4)= min [x42+ F3(s3)] with respect to x4

For minimum of F2, we have

dF2
0
dx2

s 22
gives 2x2-2 =0
x23

 x2= s2 .

d 2 F2 s 22
Also  2+6 4 which is positive.
dx22 x2

Therefore F2 in minimum at x2= s2 .

 
F2(s2) =  s   2

s22
  2s2 .


2
 
s2 
2

Now F3(s3)= min [x32+ F2(s2)]

F3(s3)= min x 2
3  2s2 
For minimum of F3, we have

dF3
0
dx3

gives 2x3- 2 s3 = 0
x32
  s 
 x3= s3
1/ 3
.  s2  3 
 x3 

d 2 F3 s3
Also  2+4 which is positive.
dx32 x33
1/ 3
Therefore F3 in minimum at x3= s3 .
2/3
Thus F3(s3)= 3 s3 .
Now F4(s4) = min [x42+ F3(s3)]

 
= min x 2  3s 2 / 3  min  x 2  3 s4 
2/3

4 3  4 2/3 
 x4 

For minimum of F4, we have

dF4
0
dx4

s42 / 3
gives 2x4- 2 5 / 3 =0
x4
1/ 4
 x4= s4 .

d 2 F4 10 s42 / 3
Also  2+ which is positive.
dx42 3 x48 / 3
1/ 4
Therefore F4 in minimum at x4= s4 .
1/ 2
Thus F4(s4)= 4 s4 .

x4  s4  16  2.
1/ 4 1/ 4

Now we have

s4 16
s3 =   8,
x4 2
  (8)1/ 3  2,
1/ 3
x3= s3

s3 8
s2 =   4,
x3 2

x2= s2  4  2,

s2 4
s1 =   2  x1.
x2 2
Hence Min Z=16, for x1= x2= x3=x4= 2.

Example.5. Solve the following problem using dynamic programming:

Max Z=x1x2x3

s.t. x1 +x2 +x3=5

x1, x2, x3  0.

Solution. We first define the state variables as:

s1= x1

s2= x1+ x2

s3= x1 +x2 +x3=5

This gives

s1= x1= s2- x2

s2= x1+ x2= s3-x3

s3= x1 +x2 +x3=5

Recursive relations are

F1(s1) = x1= s1

F2(s2) = max [x2 F1(s1)] = max (x2.s1) = max [x2. (s2- x2)] with respect to x2

F3(s3) = max [x3.F2(s2)] with respect to x3

dF2
For maximum of F2, 0
dx2
 gives s2-2x2= 0

s2
 x2= .
2
d 2 F2
Also  -2x2 which is negative.
dx22

s2
Therefore F2 in maximum at x2= .
2
s 22
Thus F2(s2) = .
4

 s22   s3  x3 2 
Now F3(s3)= max  x3 .  max  x3 . 
 4   4 

dF3
For minimum of F3, we have 0
dx3

gives (s3-x3)2-2x3(s3-x3) = 0

 (s3-x3) (s3-3x3) = 0

or (s3-3x3) = 0 [s3-x3≠0 because x2= s3-x30, x2≠0 because if x2=0, then max Z=0.]

s3
i.e., x3= .
3

d 2 F3
Also  6x3-4s3 = -2s3  0 which is negative.
dx32

s3
Therefore F3 in maximum at x3= .
3

s33 5 125

3
Thus F3(s3)=   for s3  5.
27 27 27
s3 5 5
Now we have x3=  , s2= s3- x3= 5  5  10 , x2= s2  10 . 1  5 , s1= s2- x2= 10  5  5 , x1=s1= .
3 3 3 3 2 3 2 3 3 3 3 3