# Dynamic Programming : Solving Linear Programming Problem using Dynamic Programming Approach

## Example 1

Maximize z = 5x1 + 9x2

subject to

-x1 + 5x2 ≤ 3
5x1 + 3x2 ≤ 27

x1, x2 ≥ 0

Solution.

Given
-x1 + 5x2 ≤ 3   ...........(i)
5x1 + 3x2 ≤ 27   ...........(ii)

Let R1 & R2 be the resources associated with first and second constraint respectively.
The maximum value of the resources are specified in the RHS of the two constraints, i.e., R1= 3 & R2 = 27.
From equation (i), if we are deciding only on x2 and RHS is R1, then 5x2 has to be less than or equal to R1, i.e., x2 ≤ R1/5.

Similarly, from equation (ii), we have
X2 ≤ R2/3.

Since we are maximizing, the maximum value of x2 has to be equal to the minimum of R1/5 and R2/3.
ƒ2(R1, R2) = Max (9x2)
= 9 Max (x2)
= 9 Min (R1/5, R2/3) -------(iii)

ƒ1(3, 27) = Max [5x1 + ƒ2(3 + x1, 27 – 5x1)] ------(iv)
0 ≤ x1 ≤ 27/5

From equation (iii),
ƒ2(R1,R2) = 9 Min (R1/5, R2/3) ----(iv)

Therefore, ƒ2(3 + x1, 27 – 5x1) = 9 Min [(3 + x1)/5, (27 – 5x1)/ 3]

From equation (iv)
ƒ1(3, 27) = Max {5x1 + 9 Min[ (3 + x1)/5, (27 - 5x1)/3] } -----(v)

We now find the range of x1 for which (3 + x1)/5 < (27 – 5x1)/3.

Comparing (3 + x1)/5 & (27 – 5x1)/3, we get

 (3 + x1) ----------- 5 = (27 – 5x1) ------------- 3

3(3 + x1) = 5(27 – 5x1)
9 + 3x1 = 135 – 25x1
x1 = 4.5

From equation v), we have
ƒ1(3,27) = Max [5x1 + 9(3 + x1)/5] if x1 ≤ 4.5
= Max [5x1 + 9(27 - 5x1)/3] if x1 > 4.5

From the above, the maximum occurs at x1 = 4.5
x2 = Min [3 + 4.5)/5 ,(27 – 5 X 4.5)/3]
= Min (7.5/5, 4.5/3) = 1.5

Hence, the optimal solution is

x1 = 4.5, x2 = 1.5
z = 5 X 4.5 + 9 X 1.5 = 22.5 + 13.5 = 36

## Example 2: Solving Linear Programming using Dynamic Programming

Maximize Z = 3x1 + 5x2

subject to

x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18

x1, x2 ≥ 0

Solution.

x1 ≤ 4   .........(i)
x2 ≤ 6   .........(ii)
3x1 + 2x2 ≤ 18   .........(iii)

Let R1, R2 & R3 be the resources associated with first, second and third constraint respectively.
The maximum value of the resources are specified in the RHS of the two constraints, i.e., R1= 4, R2 = 6 & R3 = 18.

From equation (ii), if we are deciding only on x2 and RHS is R2 then x2 has to be less than equal to R2, i.e., x2 ≤ R2.

Similarly, from equation (iii), we have
2x2 ≤ R3
or x2 ≤ R3/2

Since we are maximizing, the maximum value of x2 has to be equal to the minimum of R2 & R3/2.
ƒ2(R1,R2, R3) = Max (5x2)
= 5 Max (x2)
= 5 Min (R2, R3/2)   ...........(iv)

ƒ1(4,6,18) = Max [3x1 + ƒ2(4 - 2x1, 6, 18 - 3x1)]
x2 ≤ 2, x1 ≤ 6, x1 ≥ 0

From equation (iv) & (v)

ƒ1(R1,R2, R3) = Max [3x1+ 5 Min (6, (18 - 3x1)/2] ...........(vi)

We now find the range of x1 for which
6 < (18 - 3x1)/2

Comparing 6 & (18 - 3x1)/2, we get
12 = 18 - 3x1
or 3x1 = 6
or x1 = 2

From equation (vi), we have:
ƒ1(4, 6, 18) = Max [3x1 + 5 X 6] if x ≤ 2
= Max [3x1 + 5(18 - 3x1)/2] if x1 > 2

From the above, the maximum occurs at x1 = 2.
x2 = Min [6, (18 - 3 X 2)/2] = 6

The values for x1 and x2 are 2 and 6. The corresponding value of the objective function is
Z = 3 X 2 + 5 X 6 = 36