Linear programming problems

A furniture workshop has 60 hours of carpentry and 40 hours of finishing time each week. Tables need more carpentry, chairs need less — and each earns a different profit. How many of each should the workshop make to earn the most money? This is a linear programming problem (LPP): find the best value of a linear quantity (the objective function) when the choices are limited by linear restrictions (the constraints). ISC Class 12 restricts the technique to two decision variables and up to three non-trivial constraints, solved entirely by graphing — no calculus, no simplex method. The payoff is a genuinely useful piece of mathematics: the same reasoning that fixes a furniture-maker's weekly plan drives real production, diet, and resource-allocation decisions. This article builds the vocabulary, proves why the optimum always sits at a corner of the feasible region, and works two full examples end to end.

The core insight

When a linear quantity $Z=ax+by$ is optimized subject to linear inequality constraints, the maximum or minimum value (if one exists) always occurs at a corner point of the feasible region, so you only ever need to evaluate $Z$ at the vertices.

The core idea

Every LPP has three ingredients. The decision variables ( $x,y$ , almost always $\ge 0$ since they count physical quantities) are the unknowns you are solving for. The objective function is the linear expression to be maximized or minimized,

Z = ax + by,

where: $a,b$ are given constants (rates such as profit per unit or cost per unit) and $Z$ is the quantity being optimized. The constraints are linear inequalities in $x,y$ arising from limited resources — time, material, budget — and, together with the non-negativity restrictions $x\ge0,\ y\ge0$ , they carve out the region of permissible plans. The feasible region is the set of points $(x,y)$ satisfying every constraint at once — geometrically, the intersection of the half-planes defined by each inequality. Any point inside it is a feasible solution; a point violating even one constraint is infeasible. The region can be bounded (fenced in on all sides) or unbounded (open to infinity in some direction), and this distinction decides whether a maximum, a minimum, both, or neither actually exists.

Figure

A shaded triangular feasible region with vertices at the origin, on the x axis and on the y axis, bounded by two constraint lines, illustrating that the region is the overlap of two half planes

Graphical method, step by step. Turn each inequality into an equation and plot the line. Test a convenient point, usually the origin, in the original inequality to decide which side to shade; shade the satisfying half-plane. Mark the region common to all the shaded half-planes, including $x\ge0,\ y\ge0$ — that intersection is the feasible region. Find every corner point of that region by solving the boundary equations pairwise. Evaluate $Z$ at each corner and compare: the largest value is the maximum, the smallest is the minimum. On an unbounded region an optimum can fail to exist. To check for a maximum on an unbounded region, test whether the open half-plane $ax+by>M$ , for a candidate value $M$ , shares any point with the feasible region; if it does, no finite maximum exists (the minimum, on the other side, is usually still safe).

Why the optimum sits at a corner

An LPP asks you to slide the line $Z=ax+by$ across the feasible region, for increasing (or decreasing) values of $Z$ , and find the last point it still touches — proving that this last point must be a vertex is the one piece of theory the syllabus asks you to understand, even without a formal proof.

Derivation AThe corner point theorem for a linear objective

The goal is to see why sliding a family of parallel lines $ax+by=k$ across a bounded polygon, in the direction of increasing $k$ , must leave the polygon last through one of its corners rather than through some interior point or a mid-edge point — so that checking every vertex of the feasible region is always enough to find the optimum, with no calculus and no search over interior points required.

Step 1. Picture the objective as a family of parallel lines. For each value of $k$ , the equation $ax+by=k$ is a straight line with fixed slope $-a/b$ ; different values of $k$ give parallel lines, and $Z$ increases as $k$ increases (assuming $b>0$ , moving the line away from the origin). Optimizing $Z$ over the feasible region is exactly the same as finding the largest (or smallest) $k$ for which the line $ax+by=k$ still touches the region.

Step 2. Slide the line across the bounded feasible region. Start with $k$ very negative, so the line lies entirely outside the region on one side; increase $k$ steadily. The line sweeps across the polygon and, because the polygon is bounded and convex (an intersection of half-planes is always convex), there is a largest $k$ for which the line still meets the region at all — beyond that $k$ the line misses the polygon entirely.

Step 3. Argue that this last touching point cannot be a plain interior point. If the last line touched the polygon only at an interior point, you could nudge the line slightly further in the increasing- $k$ direction and it would still intersect a small neighbourhood of that interior point — contradicting that this $k$ was the largest possible. So the last touching point must lie on the boundary.

Step 4. Argue it cannot be a non-corner boundary point either. If the last line coincides with an entire edge of the polygon (happens exactly when the objective line is parallel to that edge), then every point of that edge — including its two endpoints, which are corners — gives the same optimal $Z$ . If instead the last line touches the boundary at a single point that is not a vertex, that point sits strictly between two corners on one edge, and one of those two corners lies at least as far in the increasing- $k$ direction, so it gives a $Z$ -value at least as large. Either way, some corner attains the optimal value.

Step 5. Conclude. The optimal value of $Z$ over a bounded feasible region is always attained at a corner point (possibly along with an entire edge, if two adjacent corners tie). This justifies the whole graphical method: list the vertices, evaluate $Z$ at each, and the best value among them is the true optimum — no other point in the region can beat every vertex.

Worked example

A furniture dealer makes tables and chairs. Each table needs 4 hours of carpentry and 2 hours of finishing; each chair needs 2 hours of carpentry and 1 hour of finishing. Each week 60 hours of carpentry and 40 hours of finishing are available. Profit is ₹300 per table and ₹150 per chair. How many of each should be made to maximize profit?

Step 1. Formulate. Let $x$ = number of tables, $y$ = number of chairs. Maximize $Z = 300x + 150y$ subject to $4x+2y\le60$ (carpentry), $2x+y\le40$ (finishing), $x\ge0,\ y\ge0$ . Dividing the carpentry constraint by 2 gives $2x+y\le30$ , which is stronger everywhere than $2x+y\le40$ , so the finishing hours are never the binding limit.

Step 2. Graph and shade. The line $2x+y=30$ passes through $(15,0)$ and $(0,30)$ ; testing the origin in $2x+y\le30$ gives $0\le30$ , true, so shade towards the origin. The feasible region is the triangle with corners $(0,0)$ , $(15,0)$ , $(0,30)$ .

Step 3. Evaluate $Z=300x+150y$ at each corner. At $(0,0)$ , $Z=0$ . At $(15,0)$ , $Z=4500$ . At $(0,30)$ , $Z=4500$ .

Step 4. Read off the optimum. Both $(15,0)$ and $(0,30)$ tie at $Z=4500$ , so the whole edge $2x+y=30$ between them is equally optimal — for instance, 10 tables and 10 chairs also give $Z=3000+1500=4500$ . Maximum weekly profit is ₹4500, achieved by any mix of tables and chairs on that boundary edge (including the pure choices of 15 tables or 30 chairs alone).

Competitive stretch

For minimization on an unbounded region, take $Z=20x+10y$ subject to $x+2y\le40$ , $3x+y\ge30$ , $4x+3y\ge60$ , $x,y\ge0$ . Solving the boundary equations pairwise gives corners $(15,0)$ , $(6,12)$ , $(4,18)$ , with $Z=300,\ 240,\ 260$ respectively. The region is unbounded, so only a minimum is guaranteed; checking that $20x+10y<240$ shares no point with the feasible region confirms the minimum is $Z=240$ at $x=6,\ y=12$ .

Common traps

Shading the wrong side of a boundary line. Always test a convenient point (the origin, if it's not on the line) in the original inequality — never guess from the picture.
Forgetting non-negativity. Even when not stated explicitly, $x\ge0,\ y\ge0$ almost always apply, restricting the feasible region to the first quadrant.
Assuming an optimum always exists. On an unbounded region a maximum can fail to exist even though a minimum does (or vice versa) — always test the relevant half-plane before declaring an answer.
Treating any line intersection as a vertex. Two boundary lines can cross at a point that lies outside a third constraint; that intersection is not a corner of the feasible region unless it satisfies every inequality.

Ask the tutor: if you would like another word problem turned into constraints and graphed step by step, or want your shading and corner-point work checked, ask the AI tutor to walk through it with you.

Why do we only check corner points and not every point in the feasible region?

Because the objective function is linear, its value changes steadily as you move across the region, and sliding the family of parallel lines $ax+by=k$ shows the largest or smallest $k$ that still touches a bounded, convex region must occur where the line last meets the boundary — always at a vertex, or along a whole edge if two vertices tie. This is exactly the corner point theorem worked out above, and it is why the graphical method never needs to search the interior.

What if two corner points give the same optimal value of Z?

Then every point on the edge joining those two corners also gives that same optimal value — the objective line is exactly parallel to that edge. In the furniture example, $(15,0)$ and $(0,30)$ both give $Z=4500$ , so any combination of tables and chairs along that boundary segment, including 10 tables and 10 chairs, earns the same maximum profit. The problem has infinitely many optimal solutions, not a unique one.

How do I know whether a region is bounded or unbounded just from the constraints?

Sketch it: if the shaded feasible region is enclosed on every side by the constraint lines, it is bounded, like the triangle in the furniture example. If it extends without limit in some direction, as when constraints are all "greater than or equal to" type with no upper cap, it is unbounded. On an unbounded region always check the appropriate half-plane test before claiming a maximum exists, since a minimum can be well-defined while a maximum is not, or the reverse.