Linear Programming: Class 12 Maths · Chapter 12

The best plan inside straight-line limits

Mathematics Part 2 · Companion notes, simulations and practice · Official NCERT chapter PDF ↗

Published 12 Oct 2026 · Updated 12 Oct 2026

60 min
1 simulation
14 practice questions
15 MCQs

What you will learn in Linear Programming

Recognise an optimisation problem and the features that make it a linear programming problem
Turn a word problem into decision variables, a linear objective function and linear constraints, non-negativity included
Graph a system of linear constraints in two variables, shade its feasible region and find its corner points
Use the corner point method to find the maximum or minimum of a linear objective on a bounded feasible region
Decide with the open half-plane test whether an optimum exists when the feasible region is unbounded
Recognise problems with infinitely many optimal solutions and problems with no feasible solution

Original companion text aligned to NCERT Mathematics Class 12, Chapter 12, pp. 394–405. Not affiliated with or endorsed by NCERT.

12.1 Introduction

Every real plan meets limits. A shop has only so much money, a kitchen only so many hours, a tempo only so much room. Inside those limits we still want the best plan: the largest profit, the smallest bill, the shortest delivery time. This chapter gives a tidy method for an important family of such questions.

Here is the problem we will carry through the chapter. Before Diwali, Anjali makes two products at home in Jaipur: boxes of painted diyas and jar candles. A box of diyas needs ½ kg of wax and 2 hours of work; a jar candle needs 1 kg of wax and 1 hour. She has 20 kg of wax and 50 working hours left before the festival. She earns ₹30 on each box and ₹40 on each jar, and she can sell everything she makes. How many of each should she make?

A sensible first move is to try a few plans and compare them, as Fig. 12.1 does. Boxes alone: the 50 hours run out after 25 boxes, though wax for 40 boxes is on the shelf, so she earns ₹750. Jars alone: the wax is gone after 20 jars and she earns ₹800. A mix of 10 boxes and 15 jars uses all the wax but only 35 hours, and earns ₹900, more than either pure plan. On paper, 24 boxes and 6 jars would earn ₹960, but that plan needs 54 hours, which she does not have.

3/410 boxes and 15 jars: ₹900, better than both.

Fig. 12.1Four plans checked against the two limits. Mixing helps, but one plan breaks the time limit.

Two horizontal bars, one for wax and one for time, each measured against a dashed limit line, with the plan and its profit written above and below. Step 1, 25 boxes and no jars: wax 12.5 of 20 kg, time 50 of 50 hours, profit 750 rupees, time runs out. Step 2, no boxes and 20 jars: wax 20 of 20 kg, time 20 of 50 hours, profit 800 rupees, wax runs out. Step 3, 10 boxes and 15 jars: wax 20 of 20 kg, time 35 of 50 hours, profit 900 rupees, so a mix earns more. Step 4, 24 boxes and 6 jars: wax 18 of 20 kg, but time 54 of 50 hours, so the time bar runs past the limit into a hatched zone and the plan is not possible.

Three lessons come out of this. The profit depends on the plan; some plans break a limit and are simply not available; and mixing the two products can beat making only one. Still, guessing is a poor strategy. Even counting only whole numbers, Anjali has 356 possible plans, and a lucky guess would come with no proof that nothing better exists.

Questions that ask for the largest or the smallest value of some quantity, subject to limits, are called optimisation problems. When the quantity and all the limits are linear in the unknowns, as in Anjali's case, the question is a linear programming problem (रैखिक प्रोग्रामन), or LPP for short. Such problems turn up wherever something is scarce: blending ingredients at the lowest cost, scheduling machines, routing delivery vans, staffing hospital shifts.

Real problems may have thousands of unknowns and are solved by computer. In this chapter we keep to two unknowns, where a graph shows everything at once, and we solve every problem by the graphical method.

Quick check

1 of 3

Making 24 boxes of diyas and 6 jar candles is one of Anjali's possible plans.

TrueFalse

Show answer

Answer False

The wax is fine (12 kg + 6 kg = 18 kg), but the time is

48 + 6 = 54

hours, more than the 50 she has. A plan must respect every limit, so this one is out even though its profit looks attractive.

12.2 Linear Programming Problem and its Mathematical Formulation

Look back at the plans we tried. Two features stand out. Anjali has a choice: every pair of numbers (boxes, jars) is a plan, and different plans earn different amounts. And the choice is fenced in by the wax and the hours, which no plan may overrun. A linear programming problem has exactly this shape: one quantity to push as high (or as low) as it will go, and a list of straight-line fences on the choices.

12.2.1 Mathematical formulation of the problem

Let $x$ be the number of boxes of diyas and $y$ the number of jar candles. These are the quantities Anjali gets to choose, so they are called the decision variables. Neither can be negative:

non-negativity

x \geq 0, y \geq 0

(12.1)

Wax. A plan uses $\frac{1}{2} x + y$ kg of wax, and that may not exceed 20 kg. Doubling both sides clears the fraction:

wax

x + 2 y \leq 40

(12.2)

Time. The plan takes $2 x + y$ hours, and only 50 are available:

time

2 x + y \leq 50

(12.3)

Goal. At ₹30 a box and ₹40 a jar, the profit in rupees is

profit

Z = 30 x + 40 y

(12.4)

Collecting the pieces, the whole story fits in four lines. Maximise $Z = 30 x + 40 y$ subject to

\begin{aligned} x + 2 y & \leq 40 \\ 2 x + y & \leq 50 \\ x, y & \geq 0 \end{aligned}

Definition

Linear programming problem (LPP)

A problem that asks for the largest or the smallest value of a linear expression $Z = a x + b y$ over all choices of $x \geq 0$ , $y \geq 0$ that satisfy a given list of linear inequalities (or equations).

ExampleAnjali's problem: maximise $Z = 30 x + 40 y$ subject to (12.1)–(12.3).

Each part of that description has a name. The expression to be made as large or as small as possible is the objective function (उद्देश्य फलन). The inequalities that fence in the choices are the constraints (व्यवरोध); the particular constraints $x \geq 0$ , $y \geq 0$ are the non-negativity restrictions.

Definition

Objective function

The quantity to be optimised, written as a linear expression $Z = a x + b y$ in the decision variables, with $a$ and $b$ fixed numbers.

ExampleAnjali's profit $Z = 30 x + 40 y$ , in rupees.

Definition

Constraints

Conditions on the decision variables, each a linear inequality or equation, that every acceptable plan must meet.

ExampleWax $x + 2 y \leq 40$ , time $2 x + y \leq 50$ , and $x \geq 0$ , $y \geq 0$ .

Every LPP is an optimisation problem, but not the other way round. Choosing the sides of a rectangular pen to enclose the largest area $x y$ with a fixed length of fencing is an optimisation problem, yet its objective is not linear, so the methods of this chapter do not apply to it.

Step by step

Formulating an LPP in four moves

Step 1 of 4

Name the unknowns

Decide what you control and give each quantity a letter with its unit: " $x$ = number of boxes made".

1 / 4

Example

A canteen budget, in symbols

The canteen of a school in Chennai serves a mid-morning snack made from trays of sundal and trays of upma. A tray of sundal supplies 2 units of protein and costs ₹200; a tray of upma supplies 1 unit and costs ₹50. The snack must supply at least 12 units of protein, and the stove can cook at most 10 trays in the morning. Write this as an LPP whose aim is the lowest cost.

Try it yourself first. Then reveal the solution one step at a time.

Quick check

1 of 3

A tailor in Surat has at most 30 m of cloth. A kurta takes 2 m and a dupatta 1 m. With

x

kurtas and

y

dupattas, the cloth constraint is

x + 2 y \leq 30

2 x + y \geq 30

2 x + y \leq 30

2 x + y = 30

Show answer

Answer (C) $2 x + y \leq 30$

Cloth used is

2 x + y

metres and "at most 30" means

\leq 30

. Writing

x + 2 y

swaps the two garments,

\geq

would demand at least 30 m, and

=

would force every metre to be used.

12.2.2 Graphical method of solving linear programming problems

With two decision variables, every plan is a point $(x, y)$ of the plane. In Class XI you saw that a linear inequality keeps one side of a straight line, a half-plane. To graph $x + 2 y \leq 40$ , draw the line $x + 2 y = 40$ through its intercepts (40, 0) and (0, 20). Then test any point off the line, usually the origin: $0 \leq 40$ is true, so the origin's side is kept.

Doing this for every constraint and overlapping the results gives Fig. 12.2. The plans that survive all the tests make up the feasible region (सुसंगत क्षेत्र). For Anjali it is the quadrilateral $O P Q R$ . Three corners sit on the axes; the fourth, $Q$ , is where the two lines cross. Solving $x + 2 y = 40$ and $2 x + y = 50$ together gives $x = 20$ , $y = 10$ .

4/4The overlap $O P Q R$ is the feasible region.

Fig. 12.2Each constraint keeps a half-plane; the feasible region is what all of them share.NCERT Fig 12.1 · p. 397

Axes from 0 to 50 for x and y. Step 1 shades the whole first quadrant, where x and y are at least 0. Step 2 draws the solid wax line x + 2y = 40 from (40, 0) to (0, 20) and hatches the side containing the origin. Step 3 adds the dashed time line 2x + y = 50 from (25, 0) to (0, 50) and hatches its origin side in the other direction. Step 4 keeps only the overlap, the quadrilateral OPQR with corners O(0, 0), P(25, 0), Q(20, 10) and R(0, 20), shaded as the feasible region; Q is where the two lines meet.

Definition

Feasible region

All the points that pass every constraint test of an LPP, including $x \geq 0$ and $y \geq 0$ . The rest of the plane is the infeasible region.

ExampleAnjali's quadrilateral $O P Q R$ .

Definition

Feasible solution

A plan that meets every constraint, that is, a point of the feasible region; boundary points count. A plan that breaks even one constraint is an infeasible solution.

Example(10, 15) lies on the edge $Q R$ and is feasible; (24, 6) breaks the time limit and is infeasible.

Among the feasible solutions we want one that gives the objective its best value: an optimal solution. Before hunting for it, practise telling feasible plans from infeasible ones.

Try this

Possible or not?

You’ll need

pencil and paper

Predict first

Before you calculate: which plan do you expect to break a limit?

22 boxes and 5 jars12 boxes and 15 jars8 boxes and 16 jars

For each plan, work out $x + 2 y$ and compare it with 40.
Work out $2 x + y$ and compare it with 50.
If both tests pass, the plan is possible: work out its profit $30 x + 40 y$ .

Table 12.1

Plan $(x, y)$	Possible?
(22, 5)
(12, 15)
(8, 16)
(21, 9)

Your entries are saved automatically.

Can’t do it now? Try the simulation · Fig. 12.3

SimulationTest a plan against Anjali's corners

A coordinate plane from minus 5 to 30 on both axes with four fixed points O(0, 0), P(25, 0), Q(20, 10) and R(0, 20), the corners of Anjali's feasible region, and one draggable point X that starts at (10, 15) and snaps to whole numbers. The coordinates of X are shown as it moves, so the learner can check the wax and time constraints and see whether X lies inside the quadrilateral OPQR.

Fig. 12.3O, P, Q and R are the fixed corners of the feasible region. Drag the plan X and read its coordinates; it is feasible when it lies inside

O P Q R

or on its edges.

Try this

Drag X to (21, 9). It looks close to the edge $P Q$ : does $2 x + y \leq 50$ hold?
Find three whole-number points on the edge $Q R$ , where $x + 2 y = 40$ .
Put X at (15, 15). Which constraint fails, and by how much?

Where the best plan lives

The feasible region holds infinitely many points, so we cannot test them one by one. A picture shows where to look. Fix a profit, say ₹800. The plans earning exactly that much satisfy $30 x + 40 y = 800$ , which is a straight line. Change the target and the line moves parallel to itself, because its slope, $- \frac{3}{4}$ , does not depend on the target. Lines of equal profit are called iso-profit lines (iso-cost lines when $Z$ is a cost).

3/4 $Z = 1000$ : the line touches the region only at $Q (20, 10)$ .

Fig. 12.4Raising the profit slides the line outward; the last point of contact is the corner

Q

Anjali's feasible region OPQR with corners O(0, 0), P(25, 0), Q(20, 10) and R(0, 20), and an arrow pointing up and to the right, the direction in which profit rises. A dashed profit line slides parallel to itself, leaving faint copies behind. Step 1: the 400 rupee line crosses the region. Step 2: the 800 rupee line still crosses it and passes through R. Step 3: the 1000 rupee line touches the region only at the corner Q(20, 10), which is highlighted as the maximum. Step 4: the 1200 rupee line misses the region completely, so no plan earns that much.

Pushing the line outward raises the profit. It keeps cutting through the region until $Z = 1000$ , where it touches the region at the single point $Q (20, 10)$ ; any higher line misses the region altogether. So Anjali's best plan is 20 boxes and 10 jars, earning ₹1000. The last point a sliding line touches is always a corner, or, if the line lies along an edge, that whole edge with its two corners. This picture is the idea behind the two theorems below, which we use without proof.

InteractiveFeasible-region explorer

An interactive graph of six problems from this chapter: Anjali's candles, the canteen, the tie example, the unbounded example, the recharge vouchers and the tiffin service. The feasible region is shaded, its corner points are marked with their coordinates, and each constraint line is drawn. A dashed objective line ax + by = Z can be dragged by a round handle or moved with a slider; a status panel says whether the line crosses the region, touches it only at a corner or along an edge (an optimum), or misses it. Two more sliders change a and b, so the line tilts and the best corner moves. A button lists the value of Z at every corner. For unbounded regions the panel explains when Z can grow or shrink without limit, and for the tiffin problem it reports that there is no feasible region. Nothing moves until the learner acts.

Fig. 12.5Pick a problem from this chapter, then drag the objective line (or use the slider) and watch where it last touches the region. Tilt the objective with the

a

and

b

sliders to see the best corner change.

Definition

Corner point

A vertex of the feasible region: a point of the region at which two of its boundary lines cross.

Example $O$ , $P$ , $Q$ and $R$ for Anjali's region.

Theorem 1The optimum sits at a corner

Suppose an LPP with objective $Z = a x + b y$ has a feasible region $R$ that is a convex polygon. Whenever $Z$ reaches a largest or a smallest value on $R$ , it reaches that value at one of the corner points of $R$ (perhaps at other points as well).

Idea of the proof. Suppose the best value were reached only at a point inside $R$ . A small step from that point, in the direction that raises $Z$ , stays inside $R$ and gives a larger value, which is impossible. So the best value is reached on the boundary.

Along any edge, $Z$ changes at a constant rate, because the edge is a straight segment and $Z$ is linear. So along an edge $Z$ is largest at one end, smallest at the other, or constant. Either way some corner does at least as well as any point of the edge.

Definition

Bounded region

A feasible region that fits inside some circle. A region that stretches without end in some direction is unbounded.

ExampleAnjali's region is bounded; the region $x + y \geq 3$ , $x, y \geq 0$ is unbounded.

3/3A bigger circle does not help: the region is unbounded.

Fig. 12.6Bounded means "fits inside some circle"; an unbounded region escapes every circle.

Two panels. Left: Anjali's quadrilateral feasible region with a dashed circle drawn around it, labelled bounded, fits inside a circle. In step 1 only this panel is complete. In step 2 the right panel shows an unbounded wedge-shaped region between two lines that open out towards the upper right, with an arrow showing that it goes on, and a dashed circle that covers only part of it, labelled unbounded, no circle holds it. In step 3 the circle grows larger but the region still sticks out beyond it.

Theorem 2Bounded regions always have both

When the feasible region $R$ is bounded, the objective $Z = a x + b y$ is sure to reach a largest and a smallest value on $R$ , and it reaches each of them at a corner point of $R$ .

Idea of the proof. Every point of a bounded convex polygon is a weighted average of its corners, with non-negative weights adding up to 1. Because $Z$ is linear, its value at the point is the same weighted average of its values at the corners.

An average can never exceed the largest of the numbers averaged, nor fall below the smallest. So the largest corner value is the maximum on $R$ , and the smallest corner value is the minimum.

The corner point method

The theorems turn an endless search into a short table: list the corners, work out $Z$ at each, and read off the answer. For Anjali:

Table 12.2Anjali's profit at each cornerNCERT table of corner values · p. 398

Corner	$Z = 30 x + 40 y$ (₹)
$O (0, 0)$	0
$P (25, 0)$	750
$Q (20, 10)$	1000 (maximum)
$R (0, 20)$	800

The region is bounded, so by Theorem 2 the largest entry is the maximum. Anjali should make 20 boxes of diyas and 10 jar candles, for a profit of ₹1000. Notice that this plan uses all the wax ( $20 + 2 \times 10 = 40$ ) and all the hours ( $2 \times 20 + 10 = 50$ ). The smallest entry, ₹0 at $O$ , is the minimum, a true answer to a question nobody asked: make nothing, earn nothing.

Why does step 4 work? The open half-plane $a x + b y > M$ is exactly where $Z$ beats $M$ . If no feasible point lies in it, nothing beats the corner value $M$ , so $M$ is the maximum. If some feasible point does lie in it, no maximum can exist: by Theorem 1 a maximum would sit at a corner and so be at most $M$ , yet that point already does better. The test for $m$ works the same way.

Example 1NCERT Example 1 · p. 399

A print shop in Sivakasi

A small press prints batches of greeting cards and batches of wall calendars. Each batch of either uses one roll of paper, and 8 rolls are in stock. A card batch needs 3 hours on the press and a calendar batch 1 hour; the press is free for 18 hours. A card batch earns ₹2500 and a calendar batch ₹600. With $x$ card batches and $y$ calendar batches, find the plan that earns the most.

Try it yourself first. Then reveal the solution one step at a time.

3/3The profit line $Z = 15 000$ touches the region only at $L (6, 0)$ .

Fig. 12.7The best corner can lie on an axis: here the shop prints no calendars at all.NCERT Fig 12.2 · p. 400

Axes from 0 to 10. The solid paper line x + y = 8 and the dashed press line 3x + y = 18 bound the shaded region OLMN with corners O(0, 0), L(6, 0), M(5, 3) and N(0, 8). Step 1 shows only the region and its corners. Step 2 lists the profit at each corner in rupees: L 15 000, M 14 300, N 4800, O 0. Step 3 draws the steep dashed profit line 2500x + 600y = 15 000 touching the region only at L, which is highlighted, with the note best: L.

Example 2NCERT Example 2 · p. 400

The canteen at the lowest cost

Solve the canteen problem set up in the formulation example: minimise $Z = 200 x + 50 y$ subject to

\begin{aligned} 2 x + y & \geq 12 \\ x + y & \leq 10 \\ x, y & \geq 0 \end{aligned}

Try it yourself first. Then reveal the solution one step at a time.

3/3The triangle $U V W$ ; the cost line $Z = 800$ touches it at $W (2, 8)$ .

Fig. 12.8A region that does not contain the origin: the least cost is at

W

.NCERT Fig 12.3 · p. 400

Axes from 0 to 12. Step 1 draws the solid protein line 2x + y = 12 and hatches the side away from the origin, with a note that O fails the test. Step 2 adds the dashed stove line x + y = 10 and hatches its origin side. Step 3 shows only the overlap, the triangle with corners U(6, 0), V(10, 0) and W(2, 8), lists the costs 1200, 2000 and 800 rupees, and draws the dashed cost line 200x + 50y = 800 touching the triangle at W, highlighted with least: W.

Try this

A ruler as the profit line

You’ll need

graph paper
a ruler and a set square
Anjali's region $O P Q R$ drawn to scale

Predict first

If boxes earned ₹50 each and jars only ₹20, which corner would give the most profit?

P (25, 0)

Q (20, 10)

R (0, 20)

Draw any one iso-profit line for the first pair of rates, for example $30 x + 40 y = 600$ through (20, 0) and (0, 15).
Hold the set square against it and slide the ruler along, keeping it parallel, away from $O$ .
Note the last corner of $O P Q R$ the ruler touches, and work out the profit there.
Repeat for the other two pairs of rates.

Table 12.3

Rates (box, jar)	Last corner
₹30, ₹40
₹50, ₹20
₹10, ₹40

Your entries are saved automatically.

Quick check

1 of 3

Put the corner point method in order.

Pick the largest or smallest value
Draw the feasible region
Find every corner point
Work out Z at each corner
If unbounded, do the half-plane test

Show answer

Answer

Draw the feasible region
Find every corner point
Work out Z at each corner
Pick the largest or smallest value
If unbounded, do the half-plane test

Region first, then its corners, then the table of values. The half-plane test comes last, and only when the region is unbounded, because it checks the candidate value from the table.

Ties: many optimal solutions

Example 3NCERT Example 3 · p. 401

A minimum shared by two corners

Find the minimum and the maximum of $Z = 4 x + 2 y$ subject to

\begin{aligned} 2 x + y & \geq 8 \\ x + y & \leq 10 \\ x & \leq 6 \\ x, y & \geq 0 \end{aligned}

Try it yourself first. Then reveal the solution one step at a time.

2/3The line $Z = 16$ lies along the edge $E A$ : every point of $E A$ is optimal.

Fig. 12.9When the objective is parallel to an edge, the whole edge can be optimal.NCERT Fig 12.4 · p. 401

Axes from 0 to 12. The solid line 2x + y = 8, the dashed line x + y = 10 and the dotted vertical line x = 6 enclose the shaded five-sided region with corners A(4, 0), B(6, 0), C(6, 4), D(0, 10) and E(0, 8). A panel lists Z = 4x + 2y at the corners: 16, 24, 32, 20 and 16. Step 1 shows the region and the values. Step 2 highlights the whole edge EA with a thick line and notes that the objective line lies along 2x + y = 8, so the minimum 16 is reached all along EA. Step 3 draws the dashed objective line 4x + 2y = 32 touching the region only at C, which is highlighted, with max 32 at C.

Unbounded feasible regions

When the region runs off to infinity, the table of corner values is not the end of the story. Step 4 of the method decides whether the best-looking corner value really is optimal.

Example 4NCERT Example 4 · p. 402

No minimum at all

Find graphically the minimum value, if there is one, of $Z = 2 x - 3 y$ subject to

\begin{aligned} x + 2 y & \geq 6 \\ x & \leq 6 \\ x - y & \leq 3 \\ x, y & \geq 0 \end{aligned}

Try it yourself first. Then reveal the solution one step at a time.

3/3The half-plane $2 x - 3 y < - 9$ shares points with the region: no minimum.

Fig. 12.10The half-plane

Z < - 9

still meets the region, so there is no minimum.NCERT Fig 12.5 · p. 402

Axes from 0 to 12. The dotted line x + 2y = 6, the solid line x − y = 3 and the dashed vertical line x = 6 bound a shaded strip that runs upward without end, with an upward arrow labelled goes on. Its corners are (0, 3), (4, 1) and (6, 3). Step 1 shows the region. Step 2 lists Z = 2x − 3y at the corners: −9, 5 and 3. Step 3 draws the dashed line 2x − 3y = −9 through (0, 3) and hatches the half-plane above it; a large part of the strip lies inside that half-plane, outlined, and the feasible point (2, 6) with Z = −14 is marked. So −9 is not the minimum.

The test does not always fail. In the next problem the region is again unbounded, yet a minimum exists, as a cost problem with sensible prices usually does.

Example

When the half-plane test passes

An office in Pune needs at least 12 GB of extra data and at least 1200 minutes of extra calls for its field staff this month. Voucher A gives 3 GB and 100 minutes for ₹50; voucher B gives 1 GB and 300 minutes for ₹40. How many of each should it buy to spend the least?

Try it yourself first. Then reveal the solution one step at a time.

3/3The half-plane $50 x + 40 y < 270$ shares no point with the region: ₹270 is the minimum.

Fig. 12.11The half-plane

Z < 270

misses the region, so ₹270 at

E

is the least cost.

Axes from 0 to 14. The solid line 3x + y = 12 and the dashed line x + 3y = 12 bound a shaded region that lies away from the origin and runs off to the upper right. Its corners are (0, 12), E(3, 3) and (12, 0). Step 1 shows the region. Step 2 lists the costs 480, 270 and 600 rupees. Step 3 draws the dashed cost line 50x + 40y = 270 through E and hatches the half-plane below it, on the side of the origin; it touches the region only at E, so there is no common point, and the panel reads least: 270 rupees.

When no plan works

Example 5NCERT Example 5 · p. 403

A promise the boxes cannot keep

A tiffin service in Mumbai has promised a client at least 50 tiffins a day, $x$ regular and $y$ large. Regular tiffins go in steel boxes, and only 20 clean boxes are ready each day; large tiffins go in three-tier carriers, and there are 25 of those. Find the plan of least cost, at ₹40 per regular and ₹60 per large tiffin.

Try it yourself first. Then reveal the solution one step at a time.

3/3Nothing satisfies both: the problem has no feasible solution.

Fig. 12.12The two constraints never overlap, so there is no feasible region.NCERT Fig 12.6 · p. 403

Axes from 0 to 60. Step 1 draws the solid line x + y = 50 and hatches the side away from the origin, labelled orders. Step 2 adds the dashed edges x = 20 and y = 25 and hatches the rectangle they make with the axes, labelled boxes; its far corner (20, 25) is marked. Step 3 shades the empty band between the rectangle and the line, labels it gap, and adds the note no overlap, at most 45 tiffins fit.

Two patterns ran through all of these examples. First, every feasible region we drew was convex (उत्तल): along with any two of its points it contains the whole segment joining them, as Fig. 12.13 illustrates. That always happens, because each half-plane is convex and an overlap of convex sets is convex. Second, an optimum, when it exists, sits at a corner; when two corners tie, it spreads along the edge between them.

2/3A notch lets the segment $P^{'} Q^{'}$ leave the region.

Fig. 12.13Feasible regions are overlaps of half-planes, so they are always convex.

Step 1: a five-sided convex region with two points P and Q inside it joined by a segment that stays inside, labelled convex. Step 2: beside it, a region with a triangular notch cut into its left side; the segment joining two of its points P′ and Q′ crosses the notch, and the part outside the region is drawn dashed, labelled not convex. Step 3: the notched shape is replaced by the note overlap of 5 half-planes, always convex, and dashed lines extend the five edges of the convex region, showing it as the overlap of five half-planes, which is why every feasible region is convex.

Kinds of answers

1 of 3

Match each situation with what it tells you.

Tap an item on the left, then its match on the right.

Show answer

Answer

Region is bounded : Max and min both exist
Two corners tie for best : Every point between them is optimal
Constraints never overlap : No feasible solution
Unbounded; a feasible point beats $M$ : No maximum

These are Theorem 2, the remark on ties, the infeasible case (Example 5) and step 4 of the corner point method (Example 4).

Practice · 14 questions

Practice questions with answers (NCERT “Practice 12.1”)

Short answerEasyNCERT Exercise 12.1, Q1
Maximise $Z = 2 x + 5 y$ subject to $2 x + y \leq 6$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMaximum 30 at (0, 6).
The line $2 x + y = 6$ meets the axes at (3, 0) and (0, 6), and the origin side is kept. The region is the triangle with corners (0, 0), (3, 0) and (0, 6), which is bounded.
Table 12.4
Corner $Z$
(0, 0) 0
(3, 0) 6
(0, 6) 30
The maximum is 30, at (0, 6).
Short answerMediumNCERT Exercise 12.1, Q2
Minimise $Z = - 2 x + 5 y$ subject to $x + y \leq 7$ , $2 x + y \leq 10$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMinimum −10 at (5, 0).
$x + y = 7$ meets the axes at (7, 0) and (0, 7); $2 x + y = 10$ at (5, 0) and (0, 10). The origin side of each is kept.
The lines cross where $x = 3$ and $y = 4$ (subtract the first from the second). The bounded region has corners (0, 0), (5, 0), (3, 4) and (0, 7).
Table 12.5
Corner $Z$
(0, 0) 0
(5, 0) −10
(3, 4) 14
(0, 7) 35
The minimum is −10, at (5, 0).
Short answerMediumNCERT Exercise 12.1, Q3
Maximise $Z = 3 x + 4 y$ subject to $2 x + 3 y \leq 12$ , $3 x + y \leq 9$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMaximum $\frac{117}{7}$ at $(\frac{15}{7}, \frac{18}{7})$ .
$2 x + 3 y = 12$ meets the axes at (6, 0) and (0, 4); $3 x + y = 9$ at (3, 0) and (0, 9). The origin side of each is kept.
From $3 x + y = 9$ , $y = 9 - 3 x$ . Then $2 x + 27 - 9 x = 12$ gives $x = \frac{15}{7}$ and $y = \frac{18}{7}$ .
Table 12.6
Corner $Z$
(0, 0) 0
(3, 0) 9
$(\frac{15}{7}, \frac{18}{7})$ $\frac{𝟏𝟏𝟕}{𝟕}$
(0, 4) 16
The region is bounded. The maximum is $\frac{117}{7} \approx 16.7$ , only a little more than 16 at (0, 4), which is why the exact corner matters.
Short answerHardNCERT Exercise 12.1, Q4
Minimise $Z = 2 x + 3 y$ subject to $x + 2 y \geq 4$ , $3 x + y \geq 6$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMinimum $\frac{34}{5}$ at $(\frac{8}{5}, \frac{6}{5})$ .
Both constraints keep the side away from $O$ , so the region is unbounded. $x + 2 y = 4$ meets the axes at (4, 0) and (0, 2); $3 x + y = 6$ at (2, 0) and (0, 6).
Corners: (0, 6), (4, 0), and the crossing point. From $3 x + y = 6$ , $y = 6 - 3 x$ , so $x + 12 - 6 x = 4$ and $x = \frac{8}{5}$ , $y = \frac{6}{5}$ .
Table 12.7
Corner $Z$
(0, 6) 18
$(\frac{8}{5}, \frac{6}{5})$ $\frac{𝟑𝟒}{𝟓}$
(4, 0) 8
Test the open half-plane $2 x + 3 y < \frac{34}{5}$ . Its edge passes through the crossing corner, with slope $- \frac{2}{3}$ , between the slopes $- 3$ and $- \frac{1}{2}$ of the two constraint lines, so it touches the region only there. The half-plane shares no point with the region, and the minimum is $\frac{34}{5}$ .
Short answerMediumNCERT Exercise 12.1, Q5
Maximise $Z = 4 x + 5 y$ subject to $2 x + y \leq 14$ , $x + 3 y \leq 12$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMaximum 34 at (6, 2).
$2 x + y = 14$ meets the axes at (7, 0) and (0, 14); $x + 3 y = 12$ at (12, 0) and (0, 4). The origin side of each is kept.
From $x = 12 - 3 y$ : $24 - 6 y + y = 14$ , so $y = 2$ and $x = 6$ . The bounded region has corners (0, 0), (7, 0), (6, 2) and (0, 4).
Table 12.8
Corner $Z$
(0, 0) 0
(7, 0) 28
(6, 2) 34
(0, 4) 20
The maximum is 34, at (6, 2).
Short answerMediumNCERT Exercise 12.1, Q6
Minimise $Z = 2 x + 3 y$ subject to $2 x + 3 y \geq 12$ , $2 x + y \geq 8$ , $x \geq 0$ , $y \geq 0$ . Show that infinitely many points give the minimum.
Show solution
AnswerMinimum 12 at every point of the segment joining (3, 2) and (6, 0).
Both constraints keep the side away from $O$ ; the region is unbounded. $2 x + 3 y = 12$ meets the axes at (6, 0) and (0, 4); $2 x + y = 8$ at (4, 0) and (0, 8). They cross at (3, 2), since subtracting gives $2 y = 4$ .
Table 12.9
Corner $Z$
(0, 8) 24
(3, 2) 12
(6, 0) 12
The open half-plane $2 x + 3 y < 12$ breaks the first constraint, so no feasible point lies in it: 12 is the minimum.
It is reached at (3, 2) and (6, 0), and therefore at every point of the edge joining them, such as (4.5, 1). That is infinitely many points.
Short answerHardNCERT Exercise 12.1, Q7
Find the minimum and the maximum of $Z = 2 x + 6 y$ subject to $x + 3 y \leq 30$ , $x + y \geq 12$ , $x - 3 y \geq 0$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMinimum 24 at (12, 0); maximum 60 at every point of the segment joining (15, 5) and (30, 0).
$x + 3 y = 30$ meets the axes at (30, 0) and (0, 10), origin side kept. $x + y = 12$ meets them at (12, 0) and (0, 12), side away from $O$ kept. The line $x = 3 y$ passes through $O$ ; testing (3, 0) shows the region lies below it.
Corners: $x = 3 y$ meets $x + y = 12$ at (9, 3) and $x + 3 y = 30$ at (15, 5); the $x$ -axis gives (12, 0) and (30, 0). The region is bounded.
Table 12.10
Corner $Z$
(9, 3) 36
(12, 0) 24
(30, 0) 60
(15, 5) 60
Minimum 24 at (12, 0). The maximum 60 occurs at (30, 0) and (15, 5), so at every point of the segment joining them: $Z = 2 (x + 3 y)$ is constant along $x + 3 y = 30$ .
Short answerHardNCERT Exercise 12.1, Q8
Find the minimum and the maximum of $Z = 2 x + y$ subject to $2 x + y \geq 20$ , $3 x - y \leq 0$ , $x + y \leq 60$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerMinimum 20 at every point of the segment joining (0, 20) and (4, 12); maximum 75 at (15, 45).
$2 x + y = 20$ : side away from $O$ . $x + y = 60$ : origin side. $y = 3 x$ passes through $O$ ; testing (0, 1) shows the region lies above it.
Corners: on the $y$ -axis, (0, 20) and (0, 60); $y = 3 x$ meets $2 x + y = 20$ at (4, 12) and $x + y = 60$ at (15, 45). The region is bounded.
Table 12.11
Corner $Z$
(0, 20) 20
(4, 12) 20
(15, 45) 75
(0, 60) 60
Maximum 75 at (15, 45). Minimum 20 at (0, 20) and (4, 12), hence along the whole segment joining them, which lies on $2 x + y = 20$ .
Short answerHardNCERT Exercise 12.1, Q9
Maximise $Z = - x + 3 y$ subject to $x \geq 1$ , $2 x + y \geq 8$ , $x + 2 y \geq 10$ , $y \geq 0$ .
Show solution
AnswerThere is no maximum.
The region is unbounded. Its corners are (1, 6) on the line $x = 1$ , (2, 4) where $2 x + y = 8$ meets $x + 2 y = 10$ , and (10, 0).
Table 12.12
Corner $Z$
(1, 6) 17
(2, 4) 10
(10, 0) −10
The largest corner value is $M = 17$ . Test the open half-plane $- x + 3 y > 17$ : the point (1, 10) is feasible ( $x = 1$ , $12 \geq 8$ , $21 \geq 10$ ) and gives $Z = 29 > 17$ .
The half-plane meets the region; going up the line $x = 1$ , $Z = 3 y - 1$ grows without limit. So $Z$ has no maximum.
Short answerMediumNCERT Exercise 12.1, Q10
Maximise $Z = x + 3 y$ subject to $- 2 x + y \geq 3$ , $2 x - y \geq 1$ , $x \geq 0$ , $y \geq 0$ .
Show solution
AnswerNo feasible region, so no maximum.
The first constraint says $y - 2 x \geq 3$ and the second says $y - 2 x \leq - 1$ .
No point can satisfy both, since that would need $3 \leq y - 2 x \leq - 1$ . On a graph the two half-planes lie on the far sides of the parallel lines $y = 2 x + 3$ and $y = 2 x - 1$ .
There is no feasible region, so the problem has no feasible solution and $Z$ has no maximum.
11
Long answerHard
A self-help group in Alappuzha weaves coir doormats and coir baskets. A doormat uses 2 kg of fibre and 1 hour of weaving; a basket uses 1 kg and 2 hours. Each week the group has 36 kg of fibre and 48 hours, and its buyer takes at most 15 doormats. A doormat earns ₹60 and a basket ₹50.
1. Formulate the problem as an LPP.
  Show solution
  AnswerMaximise $Z = 60 x + 50 y$ subject to $2 x + y \leq 36$ , $x + 2 y \leq 48$ , $x \leq 15$ , $x, y \geq 0$ .
  Let $x$ be the number of doormats and $y$ the number of baskets. The profit in rupees is $Z = 60 x + 50 y$ , to be maximised.
  Fibre gives $2 x + y \leq 36$ and weaving hours give $x + 2 y \leq 48$ . The buyer adds $x \leq 15$ , and counts give $x, y \geq 0$ as well.
2. Solve it by the corner point method.
  Show solution
  Answer8 doormats and 20 baskets; maximum ₹1480.
  Corners: (0, 0), (15, 0), (15, 6) where $x = 15$ meets $2 x + y = 36$ , (8, 20) where $2 x + y = 36$ meets $x + 2 y = 48$ , and (0, 24).
  Table 12.13
  Corner $Z$ (₹)
  (0, 0) 0
  (15, 0) 900
  (15, 6) 1200
  (8, 20) 1480
  (0, 24) 1200
  The region is bounded, so the maximum is ₹1480 with 8 doormats and 20 baskets. The buyer limit of 15 doormats is not the binding one.
Quick answerEasy
For the constraints $x + y \leq 6$ , $x \leq 4$ , $x, y \geq 0$ , which point is a corner of the feasible region?
(2, 2)(6, 0)(4, 6)(4, 2)
Show answer
Answer (D) (4, 2)
(4, 2) lies on both $x = 4$ and $x + y = 6$ . (6, 0) breaks $x \leq 4$ , (4, 6) breaks $x + y \leq 6$ , and (2, 2) is feasible but inside the region, not a corner.
Quick answerEasy
If the feasible region of an LPP is unbounded, the objective function cannot have a maximum.
TrueFalse
Show answer
Answer False
An unbounded region only may lack an optimum. For example, on the voucher region $Z = - x - y$ has maximum $- 6$ at (3, 3): the half-plane $- x - y > - 6$ means $x + y < 6$ , which misses the region.
Quick answerMedium
Suppose Anjali's profits change to ₹45 a box and ₹30 a jar, with the same wax and time limits. What is her new maximum profit, in rupees?
rupees
Show answer
Answer 1200 rupees
$Z = 45 x + 30 y$ gives 0 at $O$ , 1125 at $P$ , $900 + 300 = 1200$ at $Q$ and 600 at $R$ . The maximum is still at $Q (20, 10)$ : ₹1200.

Corner	$Z$
(0, 0)	0
(3, 0)	6
(0, 6)	30

Corner	$Z$
(0, 0)	0
(5, 0)	−10
(3, 4)	14
(0, 7)	35

Corner	$Z$
(0, 0)	0
(3, 0)	9
$(\frac{15}{7}, \frac{18}{7})$	$\frac{𝟏𝟏𝟕}{𝟕}$
(0, 4)	16

Corner	$Z$
(0, 6)	18
$(\frac{8}{5}, \frac{6}{5})$	$\frac{𝟑𝟒}{𝟓}$
(4, 0)	8

Corner	$Z$
(0, 0)	0
(7, 0)	28
(6, 2)	34
(0, 4)	20

Corner	$Z$
(0, 8)	24
(3, 2)	12
(6, 0)	12

Corner	$Z$
(9, 3)	36
(12, 0)	24
(30, 0)	60
(15, 5)	60

Corner	$Z$
(0, 20)	20
(4, 12)	20
(15, 45)	75
(0, 60)	60

Corner	$Z$
(1, 6)	17
(2, 4)	10
(10, 0)	−10

Corner	$Z$ (₹)
(0, 0)	0
(15, 0)	900
(15, 6)	1200
(8, 20)	1480
(0, 24)	1200

Recap

Linear Programming: key points and summary

An optimisation problem asks for the largest or smallest value of a quantity under limits; an LPP is one in which the quantity and every limit are linear (Section 12.1).
To formulate an LPP, name the decision variables, write the objective $Z = a x + b y$ , translate each limit into a linear constraint, and add $x, y \geq 0$ (Section 12.2.1).
Each constraint keeps a half-plane; the points satisfying all of them form the feasible region, boundary included (Section 12.2.2).
Iso-profit (or iso-cost) lines $a x + b y = k$ are parallel; sliding them shows the optimum is reached at a corner (Where the best plan lives).
Theorem 1: if $Z$ has an optimal value on the feasible region, it occurs at a corner point (Theorem 1).
Theorem 2: on a bounded feasible region, $Z$ always attains a maximum and a minimum, each at a corner (Theorem 2).
Corner point method: find the corners, evaluate $Z$ at each, take the largest $M$ and the smallest $m$ (the method).
On an unbounded region, $M$ is the maximum only if $a x + b y > M$ misses the region, and $m$ the minimum only if $a x + b y < m$ misses it (Example 4).
If two corners tie for the optimum, every point of the segment joining them is optimal (Example 3).
Constraints that never overlap leave no feasible region and no solution (Example 5).
Feasible regions are always convex, because they are overlaps of half-planes (When no plan works).

From historyNCERT Historical Note · p. 404

From wartime planning to every delivery van

Linear programming grew out of very practical worries. In 1939 the Soviet mathematician Leonid Kantorovich showed how to plan production in plywood factories with linear models, and in 1941 the American mathematician Frank Hitchcock studied the cheapest way to ship goods from several sources to several destinations, the transportation problem.

During and just after the Second World War, military planners faced huge questions about supplies, transport and costs, and the subject took off. In 1945 the economist George Stigler asked for the cheapest diet meeting a list of nutritional needs. In 1947 George Dantzig invented the simplex method, which walks from corner to corner of the feasible region, always improving $Z$ , until no better corner exists: the corner point idea of this chapter, made efficient for thousands of variables.

Kantorovich shared the 1975 Nobel Memorial Prize in Economic Sciences with Tjalling Koopmans for this work. In 1984 the Indian mathematician Narendra Karmarkar, then at Bell Labs, published a fast interior-point method that cuts through the inside of the region instead of walking along its edges. Today airlines, railways, refineries and online shops solve linear programmes every day.

Flash cards · 7

Key ideas

1 / 7

Find your NCERT exercise question

Our practice questions are written for ncert.ai and follow the NCERT exercises. Find the one that matches the question in your textbook; its answer is with it.

In your NCERT textbook	Practice question here
NCERT Exercise 12.1, Q1	Practice Q1
NCERT Exercise 12.1, Q2	Practice Q2
NCERT Exercise 12.1, Q3	Practice Q3
NCERT Exercise 12.1, Q4	Practice Q4
NCERT Exercise 12.1, Q5	Practice Q5
NCERT Exercise 12.1, Q6	Practice Q6
NCERT Exercise 12.1, Q7	Practice Q7
NCERT Exercise 12.1, Q8	Practice Q8
NCERT Exercise 12.1, Q9	Practice Q9
NCERT Exercise 12.1, Q10	Practice Q10

Quick check: MCQs on Linear Programming

12.1 Introduction3 questions
12.2.1 Mathematical formulation of the problem3 questions
12.2.2 Graphical method of solving linear programming problems3 questions
The corner point method3 questions
Kinds of answers3 questions

Glossary · 14

Key terms (English–Hindi)

bounded regionपरिबद्ध क्षेत्रparibaddh kshetra: A feasible region that fits inside some circle; one that runs on without end is unbounded.

constraintव्यवरोधvyavarodh: A linear inequality or equation that limits the choices of the decision variables in an LPP.First seen in the chapter →
convex regionउत्तल क्षेत्रuttal kshetra: A region that contains the whole segment joining any two of its points.First seen in the chapter →
corner pointकोणीय बिंदुkoniya bindu: A point of the feasible region where two of its boundary lines meet.

decision variablesनिर्णायक चरnirnayak char: The unknowns we choose in an LPP, such as the numbers $x$ and $y$ of two products to make.First seen in the chapter →

feasible regionसुसंगत क्षेत्रsusangat kshetra: The set of points satisfying all the constraints of an LPP, non-negativity included.First seen in the chapter →
feasible solutionसुसंगत हलsusangat hal: Any point of the feasible region, inside it or on its boundary.

half-planeअर्धतलardhatal: The part of the plane on one side of a straight line; a linear inequality in $x$ and $y$ describes one.First seen in the chapter →

iso-profit line: A line $a x + b y = k$ along which the objective has the constant value $k$ ; such lines are parallel.First seen in the chapter →

linear programming problemरैखिक प्रोग्रामन समस्याrekhik programan samasya: An optimisation problem whose objective function and constraints are all linear, with non-negative decision variables.First seen in the chapter →

non-negativity restrictionsऋणेतर व्यवरोधrinetar vyavarodh: The constraints $x \geq 0$ , $y \geq 0$ .First seen in the chapter →

objective functionउद्देश्य फलनuddeshya phalan: The linear function $Z = a x + b y$ that is to be maximised or minimised.First seen in the chapter →
optimal solutionइष्टतम हलishtatam hal: A feasible solution at which the objective function takes its maximum or minimum value.First seen in the chapter →
optimisation problemइष्टतमीकरण समस्याishtatamikaran samasya: A problem that asks for the largest or smallest value of a quantity, such as profit or cost, subject to limits.First seen in the chapter →

12.1 Introduction

12.2 Linear Programming Problem and its Mathematical Formulation

12.2.1 Mathematical formulation of the problem

12.2.2 Graphical method of solving linear programming problems

Where the best plan lives

The corner point method

Ties: many optimal solutions

Unbounded feasible regions

When no plan works

Find your NCERT exercise question

Quick check: MCQs on Linear Programming

You reached the end