0
1.1kviews
Solve the following LP problem by dynamic programming approach.

Maximize $Z = 8X_1 + 7X_2$

Subject to $2X_1 + X_2 ≤ 2 \\ 5X_1 + 2X_2 ≤ 15 \\ X_1, X_2 ≥ 0$

0
24views
• Stage I:

$F_1$ $= \text{Maximize} \ 8X_1 \\ = 8 \max. (X_1)$

From the constraints:

$2X_1 + X_2 ≤ 2 → X_1 ≤ \dfrac{2 - X_2}{2} \\ 5X_1 + 2X_2 ≤ 15 → X_1 ≤ \dfrac{15 - 2X_2}{5} \\ So \ X_1 ≤ \min. \bigg[\dfrac{2 - X_2}{2} ,\dfrac{15 - 2X_2}{5}\bigg] \\ \text{Therefore}, F_1 = 8 \min. \bigg[\dfrac{2 - X_2}{2} ,\dfrac{15 - 2X_2}{5}\bigg]$

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

So $F_1 = 8 × \min. \bigg[\dfrac{2 - 0}{2} ,\dfrac{15 - 0}{5}\bigg] = 8 × \min. [1, 3] = 8 × 1 = 8$

• Stage II:

$F_2$ $= Max. \bigg[F_1 + 7X_2\bigg] \\ = Max. [8 \min. \bigg\{\dfrac{2 - X_2}{2} ,\dfrac{15 - 2X_2}{5} \bigg\} + 7X_2]$

$2X_1 + X_2 ≤ 2 → X_2 ≤ 2 - 2X_1 \\ 5X_1 + 2X_2 ≤ 15 → X_2 ≤ \dfrac{15 - 5X_1}{2}$

The max. value of $X_2$ has to be min. $\bigg[2 - 2X_1, \dfrac{15 - 5X_1}{2} \bigg]$

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

Max. $X_2 = \min. \bigg[2 - 0,\dfrac{15 - 0}{2}\bigg] = \min. [2, 7.5] = 2$

Therefore $F_2$ $= Max.\bigg[8 \bigg\{\dfrac{2 - X_2}{2} \bigg\} + 7X_2\bigg] if \dfrac{2 - X_2}{2} ≤ \dfrac{15 - 2X_2}{5} \\ = Max. \bigg[8 \bigg\{\dfrac{15 - 2X_2}{5} \bigg\} + 7X_2\bigg] if \dfrac{15 - 2X_2}{5} ≤ \dfrac{2 - X_2}{2}$

$\text{Both values become equal if} \dfrac{2 - X_2}{2} =\dfrac{15 - 2X_2}{5}$

So $X_2 = -20$

However, this does not satisfy the constraint $X_1, X_2 ≥ 0$

In other words, $0 ≤ X_2 ≤ 2$

So we have to choose between $\dfrac{2 - X_2}{2} \ \& \ \dfrac{15 - 2X_2}{5}$ whichever is smaller.

When $X_2 = 0: \dfrac{2 - X_2}{2} = 1, \dfrac{15 - 2X_2}{5} = 3$

When $X_2 = 2: \dfrac{2 - X_2}{2} = 0, \dfrac{15 - 2X_2}{5} = 2.2$

As evident, $\dfrac{2 - X_2}{2}$ will always be smaller than $\dfrac{15 - 2X_2}{5}$ , since $0 ≤ X_2 ≤ 2$.

Therefore $F_2= Max. \bigg[8 \bigg\{\dfrac{2 - X_2}{2} \bigg\} + 7X_2\bigg]$

When $X_2 = 0: F_2 = \bigg[8 \bigg\{\dfrac{2 - 0}{2} \bigg\} + 7×0\bigg] = 8 i.e. F_1 (i.e. X_1 = 1, X_2 = 0)$

When $X_2 = 2: F_2 = \bigg[8 \bigg\{\dfrac{2 - 2}{2}\bigg\} + 7×2\bigg] = 14 (i.e. X_2 = 2, X_1 = \dfrac{2 - X_2}{2} = 0)$

So $F_2 = 14$

Therefore $Z_{\max} = 14; X_1 = 0; X_2 = 2$