Question

Consider the following Linear Programming Problem (LPP): \[ \text{maximize } z = 10x_1 + 20x_2 \] subject to \[ x_1 \leq 36, \quad x_2 \geq 42, \quad x_1 + x_2 \geq 48, \quad 5x_1 + x_2 \leq 150, \quad x_1, x_2 \geq 0. \] The maximum value of \(z\) in the above LPP is equal to ______. (Answer in integer)

Hint:

Find the corner points of the feasible region formed by the given constraints and evaluate \(z\) at each corner; the largest value is the answer.

Answer 1

Correct Answer: 3000

Step 1: Identify the constraints and understand the region.
We must maximize \(z = 10x_1 + 20x_2\) subject to \(x_1 \leq 36\), \(x_2 \geq 42\), \(x_1 + x_2 \geq 48\), \(5x_1 + x_2 \leq 150\), and \(x_1, x_2 \geq 0\). Since \(x_2 \geq 42\) already, the constraint \(x_1+x_2\geq 48\) only bites when \(x_2\) is close to \(42\); for example at \(x_2=42\) we need \(x_1\geq 6\), but once \(x_2\geq 48\) it holds for any \(x_1\geq 0\).

Step 2: Find the corner points of the feasible region.
The maximum of a linear objective over a region bounded by straight lines always occurs at a corner point, so we find where the boundary lines cross.
Line \(x_2=42\) meets line \(x_1+x_2=48\) at \(x_1=48-42=6\), giving \((6,42)\).
Line \(x_2=42\) meets line \(5x_1+x_2=150\) at \(5x_1=150-42=108\), so \(x_1=21.6\), giving \((21.6,42)\).
Line \(5x_1+x_2=150\) meets the line \(x_1=0\) at \(x_2=150\), giving \((0,150)\).
Line \(x_1+x_2=48\) meets the line \(x_1=0\) at \(x_2=48\), giving \((0,48)\).
Checking each point against all five constraints confirms these four points are the corners of the feasible region, and \(x_1\leq 36\) never actually cuts this region since \(x_1\) never exceeds \(21.6\) inside it.

Step 3: Evaluate \(z\) at every corner.
\[ z(6,42) = 10(6)+20(42) = 60+840 = 900. \] \[ z(21.6,42) = 10(21.6)+20(42) = 216+840 = 1056. \] \[ z(0,150) = 10(0)+20(150) = 0+3000 = 3000. \] \[ z(0,48) = 10(0)+20(48) = 0+960 = 960. \]
Step 4: Pick the largest value.
Comparing \(900\), \(1056\), \(3000\) and \(960\), the largest is \(3000\), reached at \((x_1,x_2)=(0,150)\), and this point satisfies every constraint.

Final Answer:
The maximum value of \(z\) is 3000. \[ \boxed{z_{max} = 3000} \]