0
805views
Solve the following LP problem by dynamic programming approach.

Maximize $Z = 3X_1 + 5X_2$

Subject to $X_1 ≤ 4 \\ X_2 ≤ 6 \\ 3X_1 + 2X_2 ≤ 18 \\ X_1, X_2 ≥ 0$

0
2views
• Stage I:

$F_1$ $= Maximize 3X_1 \\ = 3 \max. (X_1)$

From the constraints:

$X_1 ≤ 4 \\ 3X_1 + 2X_2 ≤ 18→X_1 ≤ \dfrac{18 - 2X_2}{3}$

So $X_1 ≤ \min. \bigg[4,\dfrac{18 - 2X_2}{3}\bigg]$

Therefore, $F_1 = 3 \min. \bigg[4, \dfrac{18 - 2X_2}{3} \bigg]$

The maximum value that $X_1$ can assume, is when $X_2$ is zero:

So $F_1 = 3 × \min. \bigg[4,\dfrac{18 - 0}{3} \bigg] = 3 × \min. [4, 6] = 3 × 2 = 4$

Therefore, range of $X_1 \ is \ 0 ≤ X_1 ≤ 4$

• Stage II:

$F_2$ $= Max. [F_1 + 5X_2] \\ = Max. [3 \min. \bigg\{4, \dfrac{18 - 2X_2}{3} \bigg\}+ 5X_2]$

$X_2 ≤ 6 \\ 3X_1 + 2X_2 ≤ 18→ X_2 ≤ \dfrac{18 - 3X_1}{2}$

The max. value of $X_2$ has to be min. $[6,\dfrac{18 - 3X_1}{2} ]$

The maximum value that $X_2$ can assume, is when $X_1$ is zero:

$Max. X_2 = \min. \bigg[6, \dfrac{18 - 0}{2} \bigg] = \min. [6, 9] = 6$

Therefore, range of $X_2 is 0 ≤ X_2 ≤ 6$

Therefore $F_2$ $= Max. [3 \{4\} + 5X_2] \hspace{1.5cm} if \hspace{1.5cm} 4 ≤ \dfrac{18 - 2X_2}{3} \\ = Max. \bigg[3 \bigg\{\dfrac{18 - 2X_2}{3} \bigg\} + 5X_2 \bigg] \hspace{1.5cm} if \hspace{1.5cm} \dfrac{18 - 2X_2}{3} ≤ 4$

Both values become equal if $\dfrac{18 - 2X_2}{3} = 4$

So $X_2 = 3$

Therefore, $4 ≤ \dfrac{18 - 2X_2}{3} \text{when} 0 ≤ X_2 ≤ 3 \\ \& \dfrac{18 - 2X_2}{3} ≤ 4 \text{when} 3 \lt X_2 ≤ 6$

When $X_2 = 3: F_2 = [3 \{4\} + 5X_2] = [3 \{4\} + 5 \{3\}] = 27$

When $X_2 = 6: F_2 = [3 \bigg\{\dfrac{18 - 2X_2}{3} \bigg\} + 5X_2] = [3 \{2\} + 5 \{6\}] = 36$

Therefore, $Z\max = 36, X_2 = 6, \& \ X_1 = \min. \bigg[4,\dfrac{18 - 2X_2}{3} \bigg] = \min. [4, 2] = 2$