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: Compare how efficiently $x_1$ and $x_2$ use the tightest resource.
Look at the constraint that ties both variables together: $5x_1 + x_2 \le 150$. Think of $150$ as a budget, where increasing $x_1$ by $1$ unit uses up $5$ units of that budget, while increasing $x_2$ by $1$ unit uses up only $1$ unit.
Increasing $x_1$ by $1$ unit costs $5$ units of budget and adds $10$ to $z$, a return of $10/5 = 2$ per unit of budget used.
Increasing $x_2$ by $1$ unit costs $1$ unit of budget and adds $20$ to $z$, a return of $20/1 = 20$ per unit of budget used.

Step 2: Decide which variable to push as far as possible.
Since $x_2$ gives a much better return per unit of the shared budget ($20$ against $2$), the maximum of $z$ is reached by keeping $x_1$ as small as the constraints allow, that is $x_1=0$, and making $x_2$ as large as the budget constraint permits.

Step 3: Set $x_1=0$ and find the largest allowed $x_2$.
With $x_1=0$, the constraint $5x_1+x_2 \le 150$ becomes $x_2 \le 150$, so the largest possible value is $x_2=150$.

Step 4: Check this point against every other constraint.
At $(x_1,x_2)=(0,150)$: $x_1=0\le 36$ holds, $x_2=150\ge 42$ holds, $x_1+x_2=150\ge 48$ holds, and $x_1,x_2\ge 0$ holds. Every constraint is satisfied, so $(0,150)$ is feasible, and by the return-per-budget argument in Step 2, no other feasible point can give a larger $z$.

Step 5: Compute the maximum value of $z$.
\[ z = 10(0) + 20(150) = 3000. \] \[ \boxed{z_{max} = 3000} \]