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$

1 Answer
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$

Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.

Search