Consider the following linear programming (LP): \(\begin{array}{ll}…
2020
Consider the following linear programming (LP):
\(\begin{array}{ll} \text{Max.} & z=2x_1+3x_2 \\ \text{Such that} & 2x_1+x_2 \leq 4 \\ & x_1 + 2x_2 \leq 5 \\ & x_1, x_2 \geq 0 \end{array}\)
The optimum value of the LP is
- A.
23
- B.
9.5
- C.
13
- D.
8
Attempted by 7 students.
Show answer & explanation
Correct answer: D
We maximize z = 2x1 + 3x2 subject to 2x1 + x2 ≤ 4, x1 + 2x2 ≤ 5, and x1, x2 ≥ 0.
Key idea: For a linear program with a bounded feasible region, the maximum occurs at a corner (vertex) of the feasible region. Compute the objective at each corner.
Corner at (0,0): z = 2·0 + 3·0 = 0
Intersection of 2x1 + x2 = 4 with x2 = 0 gives x1 = 2, point (2,0): z = 2·2 + 3·0 = 4
Intersection of x1 + 2x2 = 5 with x1 = 0 gives x2 = 2.5, point (0,2.5): z = 2·0 + 3·2.5 = 7.5
Intersection of the two constraints: solve 2x1 + x2 = 4 and x1 + 2x2 = 5. From the first x2 = 4 - 2x1, substitute into the second: x1 + 2(4 - 2x1) = 5 ⇒ x1 + 8 - 4x1 = 5 ⇒ -3x1 = -3 ⇒ x1 = 1, then x2 = 2. Point (1,2): z = 2·1 + 3·2 = 8
Compare the objective values at all corners: 0, 4, 7.5, and 8. The maximum value is 8, attained at the point (1, 2).