Use Dynamic programming to solve the following problems :- maximize z=8x1 + 7x2 subject to constraints 2x1 + x2 <8, 5 x1 + 2x2 < 15, and x1, x2 > 0.

• 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$