Linear programming problems and the corner point method

What is a linear programming problem?

In plain words: choose the values of the variables that make a linear objective as large or as small as possible, while obeying linear inequalities. NCERT starts with a furniture dealer who has Rs 50 000 and room for 60 pieces. A table costs Rs 2500 and earns Rs 250; a chair costs Rs 500 and earns Rs 75. How many of each should he buy for the most profit (NCERT Section 12.1, page 394; Section 12.2 takes the problem up on page 395)?

Formulating the problem

Let x be the number of tables and y the number of chairs (NCERT Section 12.2.1, pages 395–396):

NCERT’s terms (page 396):

• Objective function: the linear function Z = ax + by to be maximised or minimised. Its variables x and y are the decision variables.
• Constraints: the linear inequalities (or equations) on the variables; x ≥ 0, y ≥ 0 are the non-negative restrictions.
• Optimisation problem: a problem that maximises or minimises an objective subject to constraints. In general the functions need not be linear; linear programming is the special linear case considered here.

The graphical method

Graph each constraint as a half plane (NCERT Section 12.2.2, page 397). For ax + by ≤ c, draw the line ax + by = c (solid, since ≤ includes it). Test a point off the line, such as (0, 0), and shade the side where the test holds. The common shaded region is the feasible region.

NCERT slip (pages 394 and 397): the text says Class 11 taught linear inequalities in two variables and their graphical solution. The 2026–27 Class 11 book (NCERT Chapter 5, Sections 5.1–5.3) solves linear inequalities in one variable only, so the method is given here. In an exam, shade each half plane by testing a point.

The words NCERT uses (pages 397–398):

• The feasible region is the common region of all the constraints, including x, y ≥ 0; outside it is the infeasible region.
• Each point of the feasible region, inside or on its boundary, is a feasible solution; for the dealer, (10, 50), (0, 60) and (20, 0) are feasible and (25, 40) is not.
• An optimal solution is a feasible point that gives the optimal value of Z (page 398).

The corner point method

A nonempty feasible region usually has infinitely many points (it can also reduce to a segment or a single point), but two theorems narrow the search to its corners (page 398; NCERT does not prove them):

• Theorem 1: if Z has an optimal value on the feasible region, it occurs at a corner point (vertex), where two boundary lines meet.
• Theorem 2: if the nonempty feasible region is bounded (it can be enclosed in a circle), Z has both a maximum and a minimum, each at a corner point.

If R is unbounded, then a maximum or a minimum value of the objective function may not exist.

NCERT Mathematics Part II (Class 12), Section 12.2.2, page 398

Special cases from NCERT’s examples (pages 399–403):

• If two corners give the same optimal value, every point of the segment joining them does too: multiple optimal solutions (NCERT Example 3, with maximum 180 at (15, 15) and (0, 20)).
• On an unbounded region, the smallest corner value need not be a minimum (NCERT Example 4: Z = −50x + 20y has no minimum, though −300 is its smallest corner value).
• If the constraints have no common point, there is no feasible region and no solution (NCERT Example 5).

Solved examples

Common mistakes to avoid

Quick revision summary

• A linear programming problem optimises a linear objective function Z = ax + by of non-negative decision variables subject to linear constraints.
• The feasible region is the common region of the constraints; its points are the feasible solutions.
• The optimal value, if it exists, is at a corner point; on a nonempty bounded feasible region both the maximum and the minimum exist.
• On an unbounded region, test ax + by > M or < m before accepting a corner value. Two optimal corners give a whole optimal segment.

Questions students ask

Is linear programming in the JEE Main syllabus?

Linear programming is not in the JEE Main syllabus: none of the 14 mathematics units of the JEE Main 2027 syllabus for Paper 1 (B.E./B.Tech.) names it, and the mathematics parts of Paper 2A (B.Arch.) and Paper 2B (B.Planning) leave it out as well. It is a Class 12 board chapter instead: Chapter 12 of NCERT Mathematics Part II, and Unit V of CBSE’s Class XII Mathematics syllabus for 2026–27, which limits it to two-variable problems solved graphically, with no more than three constraints besides x ≥ 0 and y ≥ 0.

What is linear programming used for in real life?

Linear programming is used to share out limited resources such as money, machine time, storage or raw material for the most profit or the least cost; “programming” here means making a plan, not writing computer code (NCERT page 396). NCERT names industry, commerce and management science as fields that use it (page 394), and its Historical Note (pages 404–405) traces it to Second World War planning, the transportation problem studied by Leonid Kantorovich and, separately, Frank Hitchcock, and George Stigler’s 1945 cheapest-diet problem. NCERT links the 1975 economics prize awarded to Kantorovich and Tjalling Koopmans to linear programming. The Nobel citation describes their contributions to the theory of optimum allocation of resources.

Why is the feasible region of a linear programming problem always convex?

The feasible region of a linear programming problem is always convex (the segment joining any two of its points stays inside it) because each constraint keeps a convex half plane (or a line, if it is an equation), and the common part of convex regions is convex (NCERT states this without proof, pages 398 and 403). For one constraint the numbers show why: from P(2, 7) to Q(6, 0), 5x + 2y rises steadily from 24 to 30, so every point between, such as the midpoint (4, 3.5) with 27, satisfies 5x + 2y ≤ 30. Joining constraints by “or” would break this: with x, y ≥ 0, “x ≤ 1 or y ≤ 1” is an L-shaped region holding (5, 0.5) and (0.5, 5) but not their midpoint (2.75, 2.75).

What is the difference between a bounded and an unbounded feasible region?

A bounded feasible region can be enclosed in a circle, while an unbounded one stretches without end in at least one direction (NCERT page 398). On a nonempty bounded feasible region Z = ax + by has both a maximum and a minimum, each at a corner (NCERT’s Theorem 2); on an unbounded region either can fail to exist, so the largest and smallest corner values must pass the open half plane test, though both can still exist. For example, the strip x − y ≤ 1, y − x ≤ 2, x, y ≥ 0 is unbounded along the line y = x, yet Z = x − y, which is 0, 1 and −2 at the corners (0, 0), (1, 0) and (0, 2), has maximum 1 and minimum −2, because the constraints themselves keep x − y between −2 and 1.

What is the difference between linear and non-linear programming?

In linear programming the objective function and every constraint contain only first-degree terms such as 3x or 5y; non-linear programming, which is beyond NCERT, allows terms such as x^², xy or 1/x, and then the optimal value need not occur at a corner, so the corner point method can give a wrong answer. To minimise Z = (x − 3)^² + (y − 1)^² subject to x ≤ 4, y ≤ 3, x, y ≥ 0, the corners (0, 0), (4, 0), (4, 3) and (0, 3) give Z = 10, 2, 5 and 13, so the corner point method would report 2, but the true minimum is 0, at the point (3, 1) inside the rectangle.

What is the difference between linear programming and integer programming?

Integer linear programming, beyond NCERT, adds to linear programming the extra rule that the decision variables be whole numbers, as when they count tables or workers; the corner point method ignores that rule, so its optimal corner can have fractions. Rounding that corner is not a safe fix: to maximise Z = 5x + 4y subject to 3x + y ≤ 6, x + y ≤ 3, x, y ≥ 0, the best corner is (1.5, 1.5), with Z = 13.5, but rounding up to (2, 2) breaks both constraints and rounding down to (1, 1) gives only 9, while checking the few whole-number points of the region shows the best to be (1, 2), with Z = 13. Larger problems need other methods, such as branch and bound, taught in operations research.

What is the simplex method, and is it in the Class 12 NCERT book?

The simplex method is not a separate topic from linear programming but an algorithm for solving any linear programming problem, put forward by George Dantzig in 1947; the Class 12 NCERT book names it only in its Historical Note (page 405), and the chapter itself uses the graphical method alone (pages 394 and 397). Beyond NCERT, the method starts at one corner of the feasible region and moves along edges from corner to neighbouring corner, never making Z worse, until no neighbouring corner does better. It rests on the same fact as the corner point method, that an optimal value, if there is one, occurs at a corner, but it works with many variables, where no graph can be drawn.

Practice questions

Try each question first, then open the answer to check your working.

1. Q1. Minimise Z = −3x + 4y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x, y ≥ 0 (NCERT Exercise 12.1, Q2, page 404).

   Show answerHide answer

   The corners are (0, 0), (4, 0), (2, 3) and (0, 4), with Z = 0, −12, 6 and 16. Minimum Z = −12 at (4, 0).

2. Q2. Maximise Z = 3x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x, y ≥ 0 (NCERT Exercise 12.1, Q5, page 404).

   Show answerHide answer

   The corners are (0, 0), (5, 0), (4, 3) and (0, 5), with Z = 0, 15, 18 and 10. Maximum Z = 18 at (4, 3).

3. Q3. Minimise and maximise Z = 5x + 10y subject to x + 2y ≤ 120, x + y ≥ 60, x − 2y ≥ 0, x, y ≥ 0 (NCERT Exercise 12.1, Q7, page 404).

   Show answerHide answer

   The corners are (60, 0), (120, 0), (60, 30) and (40, 20), with Z = 300, 600, 600 and 400. Minimum Z = 300 at (60, 0); maximum Z = 600 at every point of the segment joining (120, 0) and (60, 30).

4. Q4. Minimise and maximise Z = x + 2y subject to x + 2y ≥ 100, 2x − y ≤ 0, 2x + y ≤ 200, x, y ≥ 0 (NCERT Exercise 12.1, Q8, page 404).

   Show answerHide answer

   The corners are (0, 50), (20, 40), (50, 100) and (0, 200), with Z = 100, 100, 250 and 400. Minimum Z = 100 at every point of the segment joining (0, 50) and (20, 40); maximum Z = 400 at (0, 200).