0
11kviews
Use dynamic programming to solve the LPP.

Maximize $Z = 2X_1 + 5X_2$

Subject to $2X_1 + X_2 ≤ 43 \\ 2X_2 ≤ 46 \\ X_1, X_2 ≥ 0$

Mumbai University > MECH > Sem 7 > Operations Research

Marks: 10 M

Year: May 2014

1 Answer
1
558views
  • Stage I:

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

    From the constraints:

    The constraint $“2X_2 ≤ 46”$ shows that X1 can go till infinity.

    So we only look at the other constraint.

    $2X_1 + X_2 ≤ 43 → X_1 ≤ \dfrac{43 - X_2}{2} \\ \text{Therefore,} F_1 = 2 \max. \bigg[\dfrac{43 - X_2}{2}\bigg]$

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

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

  • Stage II:

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

    $2X_1 + X_2 ≤ 43 → X_2 ≤ 43 - 2X_1 \\ 2X_2 ≤ 46 →X_2 ≤ 23$

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

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

    $Max. X_2 = \min. [43 - 0, 23] = \min. [43, 23] = 23$

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

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

    Since max. $X_2 = 23, \text{putting this value in} \ X_1 ≤ \dfrac{43 - X_2}{2} \ \ give: \ \ X_1= 10$

    Therefore, $F_2 = 2×\dfrac{(43-23)}{2} + 5×23 = 135$

    Therefore, $Z_{\max} = 135, X_1 = 10, X_2 = 23$

Please log in to add an answer.