0
630views
Use dynamic programming to solve the LPP.

Maximize $Z = 2X_1 + 5X_2$

Subject to $2X_1 + X_2 ≤ 430 \\ 2X_2 ≤ 460 \\ X_1, X_2 ≥ 0$

0
1views
• $F_1$ $= Maximize 2X_1 \\ = 2 \ \max. (X_1)$

From the constraints:

The constraint $“2X_2 ≤ 460”$ shows that $X_1$ can go till infinity.

So we only look at the other constraint.

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

Therefore, $F_1 = 2 \max. \bigg[\dfrac{430 - X_2}{2} \bigg]$

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

So $F_1 = 2 × \dfrac{430}{2} = 430$

• Stage II:

$F_2$ $= Max. [F_1 + 5X_2] \\ = Max. \bigg[2 \max. \bigg[\dfrac{430 - X_2}{2}\bigg] + 5X_2\bigg]$

$2X_1 + X_2 ≤ 430 → X_2 ≤ 430 - 2X_1 \\ 2X_2 ≤ 460 → X_2 ≤ 230$

The max. value of $X_2$ has to be min. $[430 - 2X_1, 230]$

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

$Max. X_2 = \min. [430 - 0, 230] = \min. [430, 230] = 230$

Therefore, $0 ≤ X_2 ≤ 230$ (‘0’ from stage 1, 23 from above)

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

Since max. $X_2 = 230, \text{putting this value in} X_1 ≤ \dfrac{430 - X_2}{2}$ give: $X_1 = 100$

Therefore, $F_2 = 2×\dfrac{(430-230)}{2} + 5×230 = 1350$

Therefore, $Z \max = 1350, X_1 = 100, X_2 = 230$