Solve the following Linear Programming Problem (LPP) graphically :

Maximize $z = 3x + 5y$

subject to the constraints :

$x + 2y \le 2000$

$x + y \le 1500$

$y \le 600$

$x \ge 0, y \ge 0$

Linear Programming

Graphical Solution of an LPP

Official Answer

The maximum is found at a corner point of the feasible region.

Corner points of the feasible region:

$(0, 0)$
$(1500, 0)$ - from $x + y = 1500$ on the x-axis.
$(1000, 500)$ - intersection of $x + 2y = 2000$ and $x + y = 1500$ .
$(800, 600)$ - intersection of $x + 2y = 2000$ and $y = 600$ .
$(0, 600)$ - from $y = 600$ on the y-axis.

Value of $z = 3x + 5y$ at each corner:

$(0, 0)$ : $z = 0$
$(1500, 0)$ : $z = 4500$
$(1000, 500)$ : $z = 5500$
$(800, 600)$ : $z = 5400$
$(0, 600)$ : $z = 3000$

Final answer:

Maximum z = 5500 at $x = 1000, y = 500$ .

linear programminggraphical methodfeasible regioncorner point theoremobjective functionmaximize zoptimal solutionz = 5500

Marking Scheme

11 mark: correctly drawing/identifying the feasible region and its corner points.
21 mark: evaluating z at all corners $(0,0)$ , $(1500,0)$ , $(1000,500)$ , $(800,600)$ , $(0,600)$ .
31 mark: correct maximum $z = 5500$ at $(1000, 500)$ .

Hint

Graph all constraints, find the corner points of the feasible region, then evaluate $z = 3x + 5y$ at each and choose the maximum.

Quick Oral Answer

I graph the constraints, list the feasible region's corners, and evaluate $z = 3x + 5y$ at each; the largest value 5500 occurs at $(1000, 500)$ , so that is the optimal solution.

Analysis & Explanation

By the corner point (fundamental) theorem of linear programming, the optimum of a linear objective over a bounded feasible region always occurs at a vertex, so we only test the corners.

Concept:

Each inequality is graphed as a half-plane; their intersection (with $x, y \ge 0$ ) is the feasible region. The optimal solution lies at one of its corner points, so we evaluate z at every vertex and pick the largest.

Finding the vertices:

The non-trivial corners come from solving pairs of boundary lines simultaneously, e.g., $x + 2y = 2000$ with $x + y = 1500$ gives $(1000, 500)$ . Each candidate must be checked against all constraints before it is accepted.

Exam trap:

Including an infeasible intersection such as $(900, 600)$ (where $x + 2y = 2100 > 2000$ ) as a corner, or forgetting to test all vertices.

Real-world link:

This is a classic product-mix problem: x and y could be units of two products, the constraints being material, labour and demand limits, and z the total profit to be maximised.

Common Mistakes

1Including an infeasible intersection point (e.g. $(900, 600)$ ) as a corner without checking all constraints.
2Evaluating z at only some corners and missing the true maximum vertex.
3Reading the objective coefficients wrongly, e.g. computing $5x + 3y$ instead of $3x + 5y$ .

Interesting Facts

The corner point theorem guarantees the optimum sits at a vertex, which is why the graphical method needs to check only finitely many points, not the whole region.

Linear programming was developed during the 1940s by George Dantzig, whose simplex method (an algebraic cousin of this graphical approach) is still used to schedule airlines and optimise supply chains today.

Spotted a mistake or something unclear?

Tell us — we fix reported answers fast.

Frequently Asked Questions

Why do we only check corner points in an LPP?

By the corner point theorem, a linear objective function attains its optimum value (maximum or minimum) over a bounded feasible region at one of the vertices of that region. So evaluating z at every corner and choosing the best is guaranteed to find the optimum.

How do I find the corner (1000, 500)?

Solve the two boundary lines that meet there simultaneously: $x + 2y = 2000$ and $x + y = 1500$ . Subtracting gives y = 500 and then $x = 1000$ . Always verify the point satisfies the remaining constraints (here $y = 500 \le 600$ holds).