Dynamic Programming : Solving Linear Programming Problem using Dynamic Programming Approach

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 + x1) ----------- 5

=

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

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: Solving Linear Programming using Dynamic Programming

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