Linear Programming

Written and reviewed by Devendra Dubey, Mathematics faculty at UniDrill (M.Sc. Mathematics, Osmania University · 10 years teaching Mathematics). Based on NCERT Mathematics Class XII, Chapter 12.

Why can't a shopkeeper make unlimited profit?

A furniture dealer earns ₹250 on every table and ₹75 on every chair. So why not make a million tables? Because money, space and time run out. The dealer has only ₹50,000 to invest and room for only 60 pieces. Within those limits, which mix of tables and chairs earns the most?

That question, "the best outcome subject to limits", is called optimisation. When both the quantity you want to maximise (profit) and every limit are straight line relationships, it is a linear programming problem (LPP). "Linear" means straight lines and "programming" means planning. The wonderful fact of this chapter is that you never have to try thousands of mixes. The best plan always sits at a corner of a region you can draw, so you test a handful of points and you are done.

Only two decision variables appear here, so the graphical method is enough. (Other methods exist for larger problems, as the history box below explains.)

Turning words into mathematics

Take the dealer's story with $x$ tables and $y$ chairs. A table costs ₹2500 and a chair ₹500, so the investment limit is $2500x + 500y \le 50000$, which simplifies to $5x + y \le 100$ after dividing by 500. Storage gives $x + y \le 60$. You cannot make a negative number of pieces, so $x \ge 0$ and $y \ge 0$. The profit to maximise is $Z = 250x + 75y$. The complete problem is:

$$\text{Maximise } Z = 250x + 75y \quad \text{subject to } 5x + y \le 100,\ \ x + y \le 60,\ \ x \ge 0,\ y \ge 0$$

Phrases map to inequality signs in a fixed way:

The vocabulary, in one table

Each word has a precise meaning and NTA tests them one by one.

Drawing the feasible region

To shade one inequality, draw its boundary line as if it were an equation, then test a point not on the line. The origin is the usual choice. If $(0, 0)$ satisfies the inequality, shade the origin's side; otherwise shade the other side. The feasible region is where all the shaded parts overlap. Because each inequality is a half-plane, the overlap is always a convex region: draw a segment between any two points of it and the whole segment stays inside. A convex region has no dents.

Corner points are found by solving the boundary equations in pairs, and then keeping only those solutions that satisfy every other constraint. For the dealer, the line $5x + y = 100$ meets the axes at $(20, 0)$ and $(0, 100)$, and $x + y = 60$ meets them at $(60, 0)$ and $(0, 60)$. The two lines meet where $5x + y = 100$ and $x + y = 60$ agree. Subtracting gives $4x = 40$, so $x = 10$ and $y = 50$. The feasible region is the quadrilateral with corners $O(0, 0)$, $A(20, 0)$, $B(10, 50)$ and $C(0, 60)$. The points $(60, 0)$ and $(0, 100)$ are outside because they break the other limit.

Why the answer is always at a corner

Suppose you want the largest $Z = ax + by$. Each value $Z = c$ is a straight line, and different $c$ give parallel lines. Slide that line across the region in the direction of increasing $Z$. The last point it touches before it leaves is the maximum, and a straight line leaving a region with straight edges always leaves at a corner (or along a whole edge).

Here is the algebra behind the picture. Pick any point $P$ on a segment between two feasible points $A$ and $B$. Then $P = (1 - t)A + tB$ for some $t$ between 0 and 1, and because $Z$ is linear, $Z(P) = (1 - t)Z(A) + tZ(B)$. This is a weighted average, so it can never beat the better of $Z(A)$ and $Z(B)$. Push this argument along the edges of the region and you reach the corners. That gives the two theorems that run the chapter.

The corner point method

Worked example: the furniture dealer. Maximise $Z = 250x + 75y$ subject to $5x + y \le 100$, $x + y \le 60$, $x, y \ge 0$.

Common wrong step. Listing only the axis intercepts and forgetting the intersection of the two limit lines. Then $(20, 0)$ looks best at $5000$, and the true optimum at $B$ is never tested. The best plan is 10 tables and 50 chairs, not "as many tables as possible".

Worked example: a corner that isn't the intersection. Maximise $Z = 4x + y$ subject to $x + y \le 50$, $3x + y \le 90$, $x, y \ge 0$.

Common wrong step. Assuming the intersection point $(20, 30)$ must be best because it is the "interesting" corner. It gives only $110$. Which corner wins depends on the coefficients in $Z$, not on how complicated the corner looks.

Pause and predict: for the region above, with corners $(0, 0)$, $(30, 0)$, $(20, 30)$ and $(0, 50)$, which objective function makes the corner $(20, 30)$ the winner: $Z = 4x + y$, $Z = 2x + y$ or $Z = x + 3y$?

Check your answer: $Z = 2x + y$. It gives $0, 60, 70, 50$ at the four corners, so $70$ at $(20, 30)$ wins. The coefficient ratio $2 : 1$ in $Z$ lies between the coefficient ratios of the two constraint lines ($1 : 1$ and $3 : 1$). A ratio above $3$ favours $(30, 0)$, as in $4x + y$. A ratio below $1$ favours $(0, 50)$, as in $x + 3y$ with a maximum of $150$.

Worked example: a minimum with a "greater than" constraint. Minimise $Z = 200x + 500y$ subject to $x + 2y \ge 10$, $3x + 4y \le 24$, $x, y \ge 0$.

Common wrong step. Including the origin as a corner. It would give $Z = 0$, but $(0, 0)$ fails $x + 2y \ge 10$, so it is not feasible. Always check a candidate against every constraint before using it.

Four ways an LPP can end

Not every LPP has one neat answer. Three special cases need a sentence of explanation, and each has a classic example.

Worked example: many best answers. Maximise $Z = 3x + 9y$ subject to $x + 3y \le 60$, $x + y \ge 10$, $x \le y$, $x, y \ge 0$.

Why does this happen? Because $Z = 3x + 9y = 3(x + 3y)$. The edge from $(0, 20)$ to $(15, 15)$ lies on the line $x + 3y = 60$, so $Z = 180$ along the whole edge. The sliding line $Z = c$ is parallel to that edge, so it leaves the region along the entire edge at once.

Common wrong step. Reporting only one of the tied corners, or the midpoint alone. The correct statement is "maximum value $180$, attained at every point of the segment joining $(0, 20)$ and $(15, 15)$".

Pause and predict: the feasible region is the whole first quadrant, which is unbounded, and $Z = x + y$. The only corner is $(0, 0)$ with $Z = 0$. Is $0$ the minimum? Is there a maximum?

Check your answer: $0$ is the minimum, because $x + y < 0$ has no point in the first quadrant. There is no maximum, because $x + y > 0$ (any number you like) has points in the region and $Z$ grows without end. The tests for $M$ and $m$ are separate, and one can pass while the other fails.

Worked example: an unbounded region. Minimise $Z = -50x + 20y$ subject to $2x - y \ge -5$, $3x + y \ge 3$, $2x - 3y \le 12$, $x, y \ge 0$.

Common wrong step. Reading the smallest tabulated value, $-300$, as the minimum. On a bounded region that is exactly right. On an unbounded one the region can run off in a direction that keeps lowering $Z$, so the half-plane test is not optional.

Worked example: an infeasible problem. Minimise $Z = 3x + 2y$ subject to $x + y \ge 8$, $3x + 5y \le 15$, $x, y \ge 0$.

Common wrong step. Calling an empty region "unbounded". Unbounded regions have points, and may still have an optimum. An empty region has no points at all.

Beyond the textbook. For the exam: a feasible region with fractional corners, such as the corner $\left(\dfrac{20}{19}, \dfrac{45}{19}\right)$, is accepted as the answer. In reality: a factory cannot make $\dfrac{20}{19}$ of a table. When whole numbers are required, rounding the corner can break a constraint or miss the best whole number plan, and the problem becomes an integer programming problem, which is harder. CUET stays with the corner point answer unless a question explicitly asks otherwise.

Beyond the textbook. For the exam: only the graphical method with two variables is needed. In reality: the first LPPs were formulated in the 1940s. L. Kantorovich and F. L. Hitchcock formulated the transportation problem in 1941, G. Stigler stated the diet problem in 1945, and G. B. Dantzig gave the simplex method in 1947. Kantorovich and Koopmans shared the 1975 Nobel Prize in Economics for work on the allocation of resources. Real problems, such as scheduling airline crews or blending refinery products, have thousands of variables. The region then lives in thousands of dimensions, yet the optimum still sits at a corner, and the simplex method works by walking from corner to corner, the same idea you use here.

Exam traps

Formula sheet

60-second revision

Where this chapter connects

• Before: Linear Inequalities teaches the half-plane graphs and systems of inequalities that form the feasible region.
• Lines: Straight Lines gives the intercepts and intersection of the boundary lines you solve for corners.
• Another kind of optimisation: Application of Derivatives finds maxima and minima of curved functions with calculus. Linear programming finds them for straight line functions with corners.