Dynamic Programming

Solution Of LP By DP

Example 1

Maximize z = 5x₁ + 9x₂

subject to

-x₁ + 5x₂ £ 3
5x₁ + 3x₂ £ 27

x₁, x₂ ³ 0

Solution.

Given
-x₁ + 5x₂ £ 3   ...........(i)
5x₁ + 3x₂ £ 27   ...........(ii)

Let R₁ & R₂ 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., R₁= 3 & R₂ = 27.
From equation (i), if we are deciding only on x₂ and RHS is R1, then 5x₂ has to be less than or equal to R₁, i.e., x₂ £ R₁/5.

Similarly, from equation (ii), we have
X2 £ R₂/3.

Since we are maximizing, the maximum value of x₂ has to be equal to the minimum of R₁/5 and R₂/3.
¦₂(R₁, R₂) = Max (9x₂)
= 9 Max (x₂)
= 9 Min (R₁/5, R₂/3) -------(iii)

¦₁(3, 27) = Max [5x₁ + ¦₂(3 + x₁, 27 – 5x₁)] ------(iv)
0£ x₁ £ 27/5

From equation (iii),
¦₂(R₁,R₂) = 9 Min (R₁/5, R₂/3) ----(iv)

Therefore, ¦₂(3 + x₁, 27 – 5x₁) = 9 Min [(3 + x₁)/5, (27 – 5x₁)/ 3]

From equation (iv)
¦₁(3, 27) = Max {5x₁ + 9 Min[ (3 + x₁)/5, (27 - 5x₁)/3] } -----(v)

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

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

3(3 + x₁) = 5(27 – 5x₁)
9 + 3x₁ = 135 – 25x₁
\ x₁ = 4.5

From equation v), we have
¦₁(3,27) = Max [5x₁ + 9(3 + x₁)/5] if x₁ £ 4.5
= Max [5x₁ + 9(27 - 5x₁)/3] if x₁ > 4.5

From the above, the maximum occurs at x₁ = 4.5
x₂ = 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

x₁ = 4.5, x₂ = 1.5
z = 5 X 4.5 + 9 X 1.5 = 22.5 + 13.5 = 36

Example 2

Maximize Z = 3x₁ + 5x₂

subject to

x₁ £ 4
x₂ £ 6
3x₁ + 2x₂ £ 18

x₁, x₂ ³ 0

Solution.

x₁ £ 4   .........(i)
x₂ £ 6   .........(ii)
3x₁ + 2x₂ £ 18   .........(iii)

Let R₁, R₂ & R₃ 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., R₁= 4, R₂ = 6 & R₃ = 18.

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

Similarly, from equation (iii), we have
2x2 £ R₃
or x2 £ R₃/2

Since we are maximizing, the maximum value of x₂ has to be equal to the minimum of R₂ & R₃/2.
¦₂(R₁,R₂, R₃) = Max (5x₂)
= 5 Max (x₂)
= 5 Min (R₂, R₃/2)   ...........(iv)

¦₁(4,6,18) = Max [3x₁ + ¦2(4 - 2x₁, 6, 18 - 3x₁)]
x₂ £ 2, x₁ £ 6, x₁ ³ 0

From equation (iv) & (v)

¦1(R₁,R₂, R₃) = Max [3x₁+ 5 Min (6, (18 - 3x₁)/2] ...........(vi)

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

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

From equation (vi), we have:
¦₁(4, 6, 18) = Max [3x₁ + 5 X 6] if x £ 2
= Max [3x₁ + 5(18 - 3x₁)/2] if x₁ > 2

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

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