Chapter 12 · Linear Programming

12.1 Linear Programming Problems and Their Formulation

Every limit on a plan — hours, money, kilograms — is a linear inequality, and the graph of a linear inequality in two variables is a half-plane. Put the half-planes together and you have the feasible region of a linear programming problem.

A furniture workshop makes $x$ tables and $y$ chairs a week. Each table needs 3 hours at the carpentry bench and each chair 1 hour, and the bench is free for only 30 hours (illustrative numbers, used throughout this chapter). So whatever plan is chosen, it must satisfy $3x+y\le30$. That single sentence rules out infinitely many plans — 10 tables and 1 chair, for example — and keeps infinitely many others. Which plans survive? To see them at a glance we need the graph of an inequality in two variables, something Class 11 handled only for one variable on the number line.

This section builds that picture from scratch. The graph of a linear inequality turns out to be a half-plane — everything on one side of a straight line — and one test point tells you which side. With that tool we can state what a linear programming problem is: choose values of the decision variables to make a linear objective function as large or as small as possible, subject to linear constraints. Most of the work in a real problem is formulation — turning a paragraph of English into these inequalities — and the second half of the section is devoted to it. Solving the problems comes in Sections 12.2 and 12.3.

Linear Inequalities in Two Variables and Half-Planes

In Class 11 you solved inequalities such as $5-2x\ge11$ in one variable; the answer was an interval on the number line. With two variables the solutions are points $(x,y)$ of the coordinate plane, and the answer is a region.

📘 Definition 12.1 — Linear inequality in two variables; half-plane

A linear inequality in two variables is one of the forms $$ax+by\lt c,\qquad ax+by\le c,$$ $$ax+by\gt c,\qquad ax+by\ge c,$$ where $a,b,c$ are real numbers and $a,b$ are not both zero. A point $(x_0,y_0)$ is a solution if the inequality is true when $x=x_0,\ y=y_0$.

The line $ax+by=c$ is the boundary line of the inequality. It divides the plane into two parts, each called a half-plane. A half-plane together with its boundary line is closed (used for $\le$ and $\ge$; the line is drawn solid); without the line it is open (used for $\lt$ and $\gt$; the line is drawn dashed).

📐 Theorem 12.1 — The half-plane theorem
Let $a,b$ be real numbers, not both zero, and let $L$ be the line $ax+by=c$. Then at every point of one of the two half-planes determined by $L$ we have $ax+by\lt c$, and at every point of the other half-plane $ax+by\gt c$. Consequently the solutions of $ax+by\le c$ form one closed half-plane, and to find out which one it is enough to test a single point not on $L$.

Why it is true. Suppose first that $b\gt0$. Take any point $(x_0,y_0)$ on $L$, so $ax_0+by_0=c$, and move straight up or down from it to $(x_0,\,y_0+t)$. There $$a x_0+b(y_0+t)=c+bt,$$ which is greater than $c$ when $t\gt0$ (above $L$) and less than $c$ when $t\lt0$ (below $L$). Every point of the plane lies directly above or below exactly one point of $L$ (since $b\ne0$, $L$ is not vertical), so all points above $L$ give $ax+by\gt c$ and all points below give $ax+by\lt c$. If $b\lt0$ the same calculation works with the roles of “above” and “below” exchanged. If $b=0$ then $a\ne0$, $L$ is the vertical line $x=\tfrac ca$, and the same argument works moving left and right instead. $\square$

So the sign of $ax+by-c$ can change only when you cross the boundary line. That is why one test point decides the whole side — the test point method.

🧭 Problem-solving strategy — graphing a linear inequality
  1. Draw the boundary line $ax+by=c$, most easily through its intercepts: put $y=0$ to get $\left(\tfrac ca,0\right)$ and $x=0$ to get $\left(0,\tfrac cb\right)$. Draw it solid for $\le$ or $\ge$, dashed for $\lt$ or $\gt$.
  2. Choose a test point not on the line — the origin $(0,0)$ is easiest, unless the line passes through it (that happens exactly when $c=0$); then use $(1,0)$ or $(0,1)$.
  3. Substitute. If the test point satisfies the inequality, shade the side containing it; if not, shade the other side.
  4. Check with a second point on the shaded side.
✏️ Example 1 — The half-plane $2x+3y\le12$
Draw the graph of $2x+3y\le12$ and decide whether the points $(3,1)$ and $(6,4)$ are solutions.
Boundary The line $2x+3y=12$ meets the $x$-axis where $y=0$: $x=6$, and the $y$-axis where $x=0$: $y=4$. Draw the solid line through $(6,0)$ and $(0,4)$ (the sign is $\le$, so the line belongs to the graph).
Test point At $(0,0)$: $2(0)+3(0)=0\le12$ is true, so the solutions form the closed half-plane containing the origin — the side of the line below and to the left.
The points $(3,1)$: $6+3=9\le12$ ✓, a solution. $(6,4)$: $12+12=24\gt12$, not a solution — it lies on the far side of the line.
Check $(6,4)$ is on the opposite side from the origin, and indeed it fails, just as Theorem 12.1 predicts.
✏️ Example 2 — Dashed lines, lines through the origin, and lines parallel to an axis
Describe and sketch the graph of each inequality: (a) $x-2y\gt-4$; (b) $3x-y\ge0$; (c) $y\le3$; (d) $x\ge2$.
(a) Boundary $x-2y=-4$ through $(-4,0)$ and $(0,2)$, drawn dashed because the sign is strict. Test $(0,0)$: $0\gt-4$ is true, so shade the open half-plane containing the origin (below the line). Points on the line, such as $(0,2)$, are not solutions.
(b) Boundary $3x-y=0$, i.e. $y=3x$, through $(0,0)$ and $(1,3)$; solid. The origin is on the line, so test $(1,0)$: $3-0=3\ge0$ is true. Shade the closed half-plane containing $(1,0)$ — the side below the steep line $y=3x$.
(c) $y\le3$ is $0\cdot x+1\cdot y\le3$: the boundary is the horizontal line $y=3$, and the solutions are all points on or below it, whatever $x$ is.
(d) $x\ge2$: the boundary is the vertical line $x=2$, and the solutions are all points on or to the right of it.
Note In (c) and (d) one variable is missing from the inequality. That does not mean it is $0$ — it means it is free to take any value.
Interactive 1 — Half-Plane Shader

Choose an inequality $ax+by\ \square\ c$ (or set $a$, $b$, $c$ and the sign yourself). Press Play: a test point wanders over the plane and leaves a dot wherever it has been — green if the inequality is true there, red if it is false. The green dots always fill exactly one side of the boundary line, as Theorem 12.1 says. A solid line belongs to the solution set; a dashed one does not.

inequality—
boundary meets axes at—
test point—
$ax+by$ there—

What Is a Linear Programming Problem?

Return to the workshop. Besides the carpentry bench, every piece goes through the polishing station: a table needs 1 hour there and a chair 2 hours, and the station is open 20 hours a week. Each table earns a profit of ₹600 and each chair ₹300 (all figures illustrative). The owner must decide how many of each to make. Written in symbols, with $x$ tables and $y$ chairs:

$$\text{Maximise } Z=600x+300y$$ $$\text{subject to}\quad 3x+y\le30,\qquad x+2y\le20,$$ $$x\ge0,\quad y\ge0.$$

The last two conditions say that the workshop cannot make a negative number of tables or chairs. They are easy to forget and they matter: without them the plan “$x=-5$, $y=12$” would pass the other two tests.

📘 Definition 12.2 — Linear programming problem

A linear programming problem (LPP) in two variables asks for the maximum or the minimum value of a linear function $$Z=ax+by,$$ ($a,b$ constants, not both zero), called the objective function, where the variables $x$ and $y$ — the decision variables — must satisfy a finite set of linear inequalities (or equations) called the constraints. The constraints $x\ge0,\ y\ge0$ are called the non-negative constraints.

“Linear” because the objective function and every constraint are of the first degree in $x$ and $y$; “programming” in its old sense of planning. Finding the largest or smallest value is called optimising $Z$.

📘 Definition 12.3 — Feasible region; feasible and infeasible solutions
The set of all points that satisfy every constraint of an LPP, the non-negative constraints included, is its feasible region — the common part of all the half-planes. Each point of the feasible region is a feasible solution. A point that violates at least one constraint is an infeasible solution.

A feasible solution is simply a plan that can be carried out; it need not be a good one. Making nothing at all, $(0,0)$, is feasible for the workshop, and earns nothing. The best feasible solutions — the optimal ones — are the subject of Section 12.2. Notice that “solution” here does not mean “answer”: it means any candidate point.

✏️ Example 3 — The workshop's feasible region
Draw the feasible region of the workshop problem, find its corner points, and decide whether the plans $(9,5)$, $(6,7)$ and $(-1,3)$ are feasible.
Bench $3x+y=30$ meets the axes at $(10,0)$ and $(0,30)$. The origin gives $0\le30$, true: keep the side containing $(0,0)$.
Polishing $x+2y=20$ meets the axes at $(20,0)$ and $(0,10)$. Again the origin satisfies it: keep the origin side.
Non-negative $x\ge0,\ y\ge0$ keep only the first quadrant. The feasible region is the quadrilateral bounded by the two axes and the two lines.
Corners On the axes the region ends at the nearer intercept: $(10,0)$ on the $x$-axis (the bench line; $(20,0)$ breaks the bench limit, $60\gt30$) and $(0,10)$ on the $y$-axis (the polishing line; $(0,30)$ gives $60\gt20$). The fourth corner is where the two lines cross: from $3x+y=30$, $y=30-3x$; substituting, $x+2(30-3x)=20$, so $-5x=-40$, $x=8$, $y=6$. Corners: $O(0,0)$, $A(10,0)$, $B(8,6)$, $C(0,10)$.
Plans $(9,5)$: $27+5=32\gt30$ — infeasible (too many bench hours). $(6,7)$: $18+7=25\le30$ and $6+14=20\le20$ — feasible; it lies on the polishing line, using every polishing hour. $(-1,3)$: violates $x\ge0$ — infeasible, even though it passes both hour limits.
Interactive 2 — Feasible-Region Builder

Pick a system or type up to four constraints $ax+by\le c$ or $\ge c$ (tick the ones you want). Press Play to add the constraints one at a time: each new half-plane is drawn in amber, and the blue region — the part that satisfies everything so far — can only shrink. The table lists every corner point, found by intersecting the boundary lines in pairs and keeping only the intersections that satisfy all the constraints.

$x\ge0,\ y\ge0$ (non-negative constraints)
constraints applied—
corner points—
feasible region—

Formulating a Linear Programming Problem

A Board question on this chapter almost always begins with a paragraph about a factory, a farm, a diet or an investment. Turning that paragraph into an LPP is worth marks on its own, and a mistake here makes every later step wrong, however neatly it is done. Work slowly and use a table.

🧭 Problem-solving strategy — formulating an LPP
  1. Decision variables. Ask “what has to be decided?” and give each quantity a letter with its unit: “let $x$ be the number of bags of fertiliser $F_1$ bought”.
  2. Tabulate the data. One row per resource or requirement, one column per decision variable, and a last column for the amount available or required.
  3. Objective function. Write $Z$ (profit, cost, time…) in terms of $x$ and $y$, and say whether it is to be maximised or minimised.
  4. Constraints. Turn each row of the table into an inequality. “At most”, “not more than”, “available” give $\le$; “at least”, “not less than”, “required” give $\ge$.
  5. Non-negative constraints. Add $x\ge0,\ y\ge0$ (unless a stronger condition such as $x\ge10$ already implies one of them).
  6. Check units. Both sides of every constraint must be in the same unit — hours with hours, kilograms with kilograms.
✏️ Example 4 — Buying fertiliser at the lowest cost
A farmer needs at least 9 kg of nitrogen and at least 8 kg of phosphate for a field. A bag of fertiliser $F_1$ contains 3 kg of nitrogen and 1 kg of phosphate and costs ₹400; a bag of $F_2$ contains 1 kg of nitrogen and 2 kg of phosphate and costs ₹300 (illustrative figures). Formulate the problem of meeting the requirement as cheaply as possible as an LPP, and sketch its feasible region.
Variables Let $x$ be the number of bags of $F_1$ and $y$ the number of bags of $F_2$ bought.
Table
$F_1$ (per bag)$F_2$ (per bag)required
nitrogen (kg)31at least 9
phosphate (kg)12at least 8
cost (₹)400300minimise
LPP $$\text{Minimise } Z=400x+300y$$ $$\text{subject to } 3x+y\ge9,\quad x+2y\ge8,$$ $$x\ge0,\quad y\ge0.$$
Region $3x+y=9$ passes through $(3,0)$ and $(0,9)$; $x+2y=8$ through $(8,0)$ and $(0,4)$. The origin fails both inequalities ($0\ge9$ is false), so we keep the sides away from the origin. The feasible region is the part of the first quadrant above both lines; its corners are $(0,9)$, $(8,0)$ and the crossing point: $y=9-3x$ gives $x+18-6x=8$, so $x=2$, $y=3$. The region is unbounded — it stretches out for ever, since buying more bags never breaks an “at least” condition. Section 12.3 shows how to find the minimum cost on such a region.
✏️ Example 5 — Splitting an investment
Mrs Iyer has at most ₹50,000 to invest in two savings schemes: scheme A pays 8% a year and scheme B pays 10% a year (illustrative rates). She wants at least ₹10,000 in scheme A, and, to limit her risk, the amount in B must not exceed 1.5 times the amount in A. Formulate an LPP to maximise her yearly interest.
Variables Work in thousands of rupees: let $x$ be the amount in A and $y$ the amount in B (in ₹ thousand). Large numbers make graphs awkward, so a sensible unit is part of good formulation.
Objective Interest $Z=0.08x+0.10y$ (₹ thousand), to be maximised.
Constraints Total: $x+y\le50$. At least ₹10,000 in A: $x\ge10$. B at most 1.5 times A: $y\le1.5x$, i.e. $3x-2y\ge0$. Non-negative: $y\ge0$ (and $x\ge0$ is already implied by $x\ge10$).
LPP $$\text{Maximise } Z=0.08x+0.1y$$ $$\text{subject to } x+y\le50,\quad x\ge10,$$ $$3x-2y\ge0,\quad y\ge0.$$ (Solved in Section 12.2.)
Watch out “B must not exceed 1.5 times A” is $y\le1.5x$, not $1.5y\le x$. Test the words on numbers: with $x=10$, B may be at most $15$ — and $y\le1.5x$ gives exactly $y\le15$.
✏️ Example 6 — From a picture back to the constraints
A feasible region is the quadrilateral with corners $O(0,0)$, $A(5,0)$, $B(3,4)$ and $C(0,5)$. Write down a set of constraints whose feasible region it is.
Edge $AB$ Slope $\dfrac{4-0}{3-5}=-2$, so $y-0=-2(x-5)$, i.e. $2x+y=10$.
Edge $BC$ Slope $\dfrac{5-4}{0-3}=-\tfrac13$, so $y-5=-\tfrac13x$, i.e. $x+3y=15$.
Which side? The region contains the origin, which gives $0\le10$ and $0\le15$. So the constraints are $$2x+y\le10,\quad x+3y\le15,\quad x\ge0,\ y\ge0.$$
Check $B(3,4)$ lies on both lines: $6+4=10$ ✓, $3+12=15$ ✓. $A(5,0)$: $10\le10$, $5\le15$ ✓; $C(0,5)$: $5\le10$, $15\le15$ ✓.
⚠️ Common mistakes when studying alone

1. Shading the wrong side. Never guess from the look of the inequality (“$\le$ means below”). For $x-y\ge2$ the solutions lie below the line $y=x-2$ (the origin fails: $0\ge2$ is false). Always use a test point.

2. Reversing “at least” and “at most”. A requirement (“at least 9 kg”) gives $\ge$; a limit on a resource (“30 hours available”) gives $\le$.

3. Forgetting the non-negative constraints. Without them the region may spill into the other quadrants and include impossible plans with negative quantities.

4. Mixing units. If one cake needs 200 g of flour and 5 kg are available, write $200x+\dots\le5000$ (grams) — not $\le5$.

5. Ratios written backwards. “$y$ is at most twice $x$” is $y\le2x$. Test the sentence with a number before you write it.

6. Using non-linear expressions. Products such as $xy$, squares such as $x^2$ or quotients such as $\tfrac xy$ are not allowed in an LPP.

Exercises

I
Half-planes. In parts 1–5 draw the graph of the inequality (state whether the boundary is solid or dashed, and which side is shaded).
  • 1 $x+y\le5$
  • 2 $2x-y\gt4$
  • 3 $3x+4y\ge12$
  • 4 $y\lt2x$
  • 5 $x\le-1$
  • 6 Is the point $(2,-1)$ a solution of $4x-3y\le10$?
  • 7 Write the inequality whose graph is the closed half-plane on the origin side of the line through $(0,3)$ and $(4,0)$.
  • 8 For which values of $k$ does the point $(k,2)$ lie in the half-plane $3x-2y\ge5$?
1 Solid line through $(5,0)$ and $(0,5)$. Origin: $0\le5$ true — shade the origin side.
2 Dashed line through $(2,0)$ and $(0,-4)$. Origin: $0\gt4$ false — shade the side away from the origin (it contains $(3,0)$: $6\gt4$ ✓).
3 Solid line through $(4,0)$ and $(0,3)$. Origin: $0\ge12$ false — shade the side away from the origin.
4 Dashed line $y=2x$ through $(0,0)$ and $(1,2)$. The origin is on the line, so test $(1,0)$: $0\lt2$ true — shade the side containing $(1,0)$, below the line.
5 Solid vertical line $x=-1$; shade everything on or to the left of it (the origin fails: $0\le-1$ is false).
6 $4(2)-3(-1)=8+3=11\gt10$: no, it is not a solution.
7 Intercept form $\tfrac x4+\tfrac y3=1$, i.e. $3x+4y=12$. The origin gives $0\lt12$, so the half-plane is $3x+4y\le12$.
8 $3k-4\ge5$, so $3k\ge9$: $k\ge3$.
II
Feasible regions. In parts 1–4 shade the region satisfying all the inequalities, list its corner points and say whether it is bounded.
  • 1 $x+y\le6,\ x\le4,\ x\ge0,\ y\ge0$
  • 2 $2x+y\le8,\ x+2y\le10,\ x\ge0,\ y\ge0$
  • 3 $x+y\ge4,\ x+3y\ge6,\ x\ge0,\ y\ge0$
  • 4 $2x+3y\le6,\ x+y\ge4,\ x\ge0,\ y\ge0$
  • 5 For the system of part 2, decide which of $(2,3)$, $(3,3)$, $(1,4.5)$ are feasible solutions.
  • 6 Find constraints whose feasible region is the quadrilateral with corners $(0,0)$, $(6,0)$, $(4,3)$, $(0,4)$.
  • 7 $x+2y\le10,\ x-y\le1,\ x\ge0,\ y\ge0$
Check: is a point feasible?
x =y =
—

Each constraint is evaluated at your point; one ✗ is enough to make the point infeasible. Values may be fractions such as 7/2.

1 Both $x+y\le6$ and $x\le4$ keep the origin side. The line $x=4$ meets $x+y=6$ at $(4,2)$. Corners $(0,0)$, $(4,0)$, $(4,2)$, $(0,6)$; bounded.
2 Intercepts $(4,0),(0,8)$ and $(10,0),(0,5)$; keep the nearer ones. Crossing: $y=8-2x$, $x+16-4x=10$, $x=2$, $y=4$. Corners $(0,0)$, $(4,0)$, $(2,4)$, $(0,5)$; bounded.
3 The origin fails both, so keep the far sides. Intercepts $(4,0),(0,4)$ and $(6,0),(0,2)$: on the $x$-axis the region starts at $(6,0)$, on the $y$-axis at $(0,4)$. Crossing: $x=4-y$, $4-y+3y=6$, $y=1$, $x=3$. Corners $(6,0)$, $(3,1)$, $(0,4)$; unbounded — it extends without end up and to the right.
4 Empty. If $x,y\ge0$ and $x+y\ge4$, then $2x+3y\ge2x+2y=2(x+y)\ge8\gt6$, so no point satisfies all four constraints. There are no corner points and no feasible solutions.
5 $(2,3)$: $7\le8$, $8\le10$ — feasible. $(3,3)$: $9\gt8$ — infeasible. $(1,4.5)$: $6.5\le8$, $10\le10$ — feasible (on the line $x+2y=10$).
6 Edge $(6,0)$–$(4,3)$: slope $-\tfrac32$, line $3x+2y=18$. Edge $(4,3)$–$(0,4)$: slope $-\tfrac14$, line $x+4y=16$. The origin is inside, so: $3x+2y\le18,\ x+4y\le16,\ x\ge0,\ y\ge0$. Check $(4,3)$: $12+6=18$ ✓, $4+12=16$ ✓.
7 $x-y=1$ passes through $(1,0)$ and $(0,-1)$; the origin gives $0\le1$, so keep the origin side (above the line $y=x-1$). Crossing with $x+2y=10$: $x=y+1$, $3y+1=10$, $y=3$, $x=4$. Corners $(0,0)$, $(1,0)$, $(4,3)$, $(0,5)$; bounded.
III
Formulation. Formulate each problem as an LPP (decision variables with units, objective function, constraints). All figures are illustrative. You will solve several of them in Sections 12.2 and 12.3.
  • 1 Home bakery. A batch of muffins uses 2 kg of flour and 1 kg of sugar; a batch of cookies uses 1 kg of flour and 1 kg of sugar. There are 40 kg of flour and 25 kg of sugar in stock. A batch of muffins earns ₹500 and a batch of cookies ₹400. How many batches of each maximise the profit?
  • 2 Cattle feed. 1 kg of feed P contains 2 units of protein and 1 unit of minerals; 1 kg of feed Q contains 1 unit of protein and 2 units of minerals. A cow needs at least 10 units of protein and 8 units of minerals a day. P costs ₹50 per kg and Q ₹40 per kg. Find the cheapest daily mix.
  • 3 Weekend revision. Asha has at most 10 hours for revising Maths and Physics. She wants at least 4 hours of Maths, and at least half as much time on Physics as on Maths. She estimates that each hour of Maths gains her 6 marks and each hour of Physics 5 marks. Maximise her estimated gain.
  • 4 Savings. A family can invest at most ₹1,00,000 in a fixed deposit paying 7% a year and in bonds paying 9% a year. They want at least ₹20,000 in the fixed deposit and at most ₹40,000 in bonds. Maximise the yearly interest.
  • 5 Tailoring unit. A kurta takes 1 hour of cutting and 3 hours of stitching; a shirt takes 1 hour of cutting and 2 hours of stitching. Each week 40 cutting hours and 100 stitching hours are available, and an order requires at least 10 shirts. The profit is ₹250 per kurta and ₹200 per shirt. Maximise the weekly profit.
  • 6 A student formulates Example 4 as “Minimise $Z=400x+300y$ subject to $3x+y\le9$, $x+2y\ge8$.” Find the two errors, and give a plan that the student's model wrongly accepts.
1 $x$, $y$ = batches of muffins, cookies. Maximise $Z=500x+400y$ subject to $2x+y\le40$ (flour, kg), $x+y\le25$ (sugar, kg), $x\ge0,\ y\ge0$.
2 $x$, $y$ = kg of P, Q per day. Minimise $Z=50x+40y$ subject to $2x+y\ge10$ (protein), $x+2y\ge8$ (minerals), $x\ge0,\ y\ge0$.
3 $x$, $y$ = hours of Maths, Physics. Maximise $Z=6x+5y$ subject to $x+y\le10$, $x\ge4$, $y\ge\tfrac x2$ (i.e. $x-2y\le0$), $y\ge0$.
4 $x$, $y$ = amounts (₹ thousand) in the deposit, bonds. Maximise $Z=0.07x+0.09y$ subject to $x+y\le100$, $x\ge20$, $y\le40$, $y\ge0$.
5 $x$, $y$ = kurtas, shirts per week. Maximise $Z=250x+200y$ subject to $x+y\le40$ (cutting), $3x+2y\le100$ (stitching), $y\ge10$ (order), $x\ge0$.
6 (i) Nitrogen is a requirement, “at least 9 kg”, so it must be $3x+y\ge9$, not $\le$. (ii) The non-negative constraints $x\ge0,\ y\ge0$ are missing. The faulty model accepts, for example, $(0,4)$ — four bags of $F_2$ for ₹1200 — which supplies only 4 kg of nitrogen. (It even accepts $(-2,5)$, which makes no sense at all.)
IV
Reasoning.
  • 1 Which of these may appear in an LPP (as a constraint or as the objective function)? (a) $3x-2y\le7$ (b) $xy\le5$ (c) $x^2+y\ge1$ (d) $Z=4x-y$ (e) $|x|\le2$ (f) $Z=\dfrac xy$
  • 2 Why can the origin not be used as the test point for $2x+5y\le0$? Graph the inequality using another test point.
  • 3 Show that if $P(x_1,y_1)$ and $Q(x_2,y_2)$ both satisfy $ax+by\le c$, then so does every point $\big((1-t)x_1+tx_2,\ (1-t)y_1+ty_2\big)$ with $0\le t\le1$ — every point of the segment $PQ$. Deduce that a feasible region never has a “dent” (it is convex).
  • 4 Describe the feasible region of $x+y\le3,\ x+y\ge3,\ x\ge0,\ y\ge0$.
  • 5 For which values of $k$ is the feasible region of $x+y\le k,\ x\ge0,\ y\ge0$ (a) a triangle, (b) a single point, (c) empty?
1 Allowed: (a) and (d). Not allowed: (b) $xy$, (c) $x^2$ and (f) $\tfrac xy$ are not of the first degree. (e) is not itself of the form $ax+by\le c$, but it is equivalent to the two linear constraints $x\le2$ and $x\ge-2$, so it can be used once rewritten.
2 $(0,0)$ lies on the boundary $2x+5y=0$ (here $c=0$), so it cannot tell the two sides apart. Test $(1,0)$: $2\le0$ is false, so shade the closed half-plane not containing $(1,0)$ — the side containing $(-1,0)$ and $(0,-1)$, below the line $y=-\tfrac25x$.
3 $a\big((1-t)x_1+tx_2\big)+b\big((1-t)y_1+ty_2\big)$ $=(1-t)(ax_1+by_1)+t(ax_2+by_2)$ $\le(1-t)c+tc=c$, using $1-t\ge0$ and $t\ge0$ to multiply the two inequalities. So each half-plane contains the whole segment between any two of its points. A point of the segment between two feasible points lies in every half-plane, so it is feasible: the feasible region contains every segment joining two of its points.
4 The two inequalities together force $x+y=3$. With $x,y\ge0$ the feasible region is the line segment from $(3,0)$ to $(0,3)$ — a region need not have any area.
5 (a) $k\gt0$: the triangle with corners $(0,0)$, $(k,0)$, $(0,k)$. (b) $k=0$: only $(0,0)$. (c) $k\lt0$: $x+y\ge0$ for all feasible points, so $x+y\le k\lt0$ is impossible — empty.
🎯 Exam corner Board · 1 markBoard · 3 marksBoard · Case study

How this is examined: linear programming is a Board-only chapter (it is not in the JEE Main or JEE Advanced syllabus). Expect 1-mark MCQs and Assertion–Reason items on half-planes, feasibility and corner points, a 3-mark formulation, and a case study that walks through formulating, testing a plan and listing corners before the solving step of Section 12.2.

E1. Board · 1 mark Which of the following points lies in the half-plane $2x+3y\le6$?  (A) $(3,1)$  (B) $(1,1)$  (C) $(0,3)$  (D) $(2,1)$

Idea Substitute each point: (A) $6+3=9$; (B) $2+3=5$; (C) $0+9=9$; (D) $4+3=7$. Only $5\le6$.
Answer (B). Trap (D): $(2,1)$ looks close to the line, but $7\gt6$ puts it just outside.

E2. Board · 1 mark The number of corner points of the feasible region of $x+y\le4,\ x\le3,\ x\ge0,\ y\ge0$ is  (A) $2$  (B) $3$  (C) $4$  (D) $5$

Idea The line $x=3$ cuts off the corner $(4,0)$ of the triangle $x+y\le4$, replacing it by $(3,0)$ and $(3,1)$. Corners: $(0,0)$, $(3,0)$, $(3,1)$, $(0,4)$.
Answer (C). Trap (B): the triangle's three corners, forgetting that $x\le3$ removes $(4,0)$ and adds two new corners.

E3. Board · 1 mark Assertion–Reason. Assertion (A): $(0,0)$ is a feasible solution of the LPP with constraints $x+y\ge2$, $x\ge0$, $y\ge0$. Reason (R): a feasible solution must satisfy every constraint of the problem, including the non-negative constraints.  (A) Both A and R are true and R is the correct explanation of A  (B) Both A and R are true but R is not the correct explanation of A  (C) A is true but R is false  (D) A is false but R is true

Idea R is Definition 12.3, so it is true. $(0,0)$ satisfies $x\ge0,\ y\ge0$ but gives $0\ge2$, which is false; so A is false.
Answer (D). Trap (A): $(0,0)$ is feasible for most “$\le$” problems, but not when a constraint says “at least”.

E4. Board · 1 mark The corner points of the feasible region of $3x+2y\le12$, $x\ge0$, $y\ge0$ are  (A) $(0,0),(4,0),(0,6)$  (B) $(0,0),(6,0),(0,4)$  (C) $(4,0),(0,6)$ only  (D) $(0,0),(3,0),(0,2)$

Idea $y=0$ gives $x=4$; $x=0$ gives $y=6$. The region is the triangle with corners $(0,0)$, $(4,0)$, $(0,6)$.
Answer (A). Trap (B) swaps the intercepts ($12\div2$ on the $x$-axis); (C) forgets the origin, which is a corner where the two axes meet; (D) divides by the wrong numbers.

E5. Board · 3 marks A shopkeeper stocks two kinds of school bag. Type A costs her ₹600 and type B ₹900; she can spend at most ₹36,000 and has room for at most 50 bags. She earns ₹100 on each type A bag and ₹120 on each type B bag (illustrative figures). Formulate an LPP to maximise her profit, and find the corner points of the feasible region.

Formulate Let $x$, $y$ be the numbers of type A and type B bags. Maximise $Z=100x+120y$ subject to $600x+900y\le36000$, i.e. $2x+3y\le120$; $x+y\le50$; $x\ge0,\ y\ge0$. (1½ marks)
Region $2x+3y=120$ meets the axes at $(60,0)$, $(0,40)$; $x+y=50$ at $(50,0)$, $(0,50)$. Both keep the origin side, so on the axes the corners are the nearer intercepts $(50,0)$ and $(0,40)$. (½ mark)
Crossing From $x=50-y$: $100-2y+3y=120$, so $y=20$, $x=30$. (½ mark)
Answer Corner points $(0,0)$, $(50,0)$, $(30,20)$, $(0,40)$. (½ mark) (For the record: $Z$ there is $0$, $5000$, $5400$, $4800$, so by the method of Section 12.2 the best plan is 30 bags of A and 20 of B, profit ₹5,400.)

E6. Board · Case study A school canteen makes veg rolls and sandwiches for the lunch break. A roll needs 2 minutes of preparation and 1 minute on the grill; a sandwich needs 1 minute of preparation and 1 minute on the grill. Each morning there are 100 minutes of preparation time and 70 minutes of grill time (illustrative figures). Let $x$ rolls and $y$ sandwiches be made.  (i) Write the constraints. (2 marks)  (ii) Is the plan of 20 rolls and 30 sandwiches feasible? What about 40 rolls and 30 sandwiches? (1 mark)  (iii) Find the corner points of the feasible region. (1 mark)

(i) Preparation: $2x+y\le100$; grill: $x+y\le70$; non-negative: $x\ge0,\ y\ge0$.
(ii) $(20,30)$: $40+30=70\le100$ and $50\le70$ — feasible. $(40,30)$: $80+30=110\gt100$ — infeasible (not enough preparation time), even though $70\le70$ for the grill.
(iii) Intercepts $(50,0)$, $(0,100)$ and $(70,0)$, $(0,70)$: the axis corners are $(50,0)$ and $(0,70)$. Crossing: subtracting the equations, $x=30$, then $y=40$. Corners $(0,0)$, $(50,0)$, $(30,40)$, $(0,70)$.
🔬 Research–Teaching NexusMini project · about 60 minutes

Research question. What really limits a small local business — and can its daily decisions be written as a linear programming problem?

Why it matters. Large companies, Indian Railways and airlines solve LPPs with thousands of variables every day, but the first and hardest step is always the same as in this section: deciding what the variables are and which limits are real. A wrong constraint gives a confident, precise and useless answer.

What to do.

  1. Choose a small business you can observe or ask about — a tea stall, a tailor, a tiffin service, a school stationery shop — that makes or sells (at least) two products.
  2. Collect real data (with permission): the time, ingredients or money each unit uses, what is available per day, and the profit per unit. Record your sources; where you have to estimate, say so.
  3. Formulate an LPP with two decision variables and two or three constraints. Draw its feasible region on graph paper and list the corner points.
  4. Check your model against reality: is the owner's actual daily plan a feasible point? Which constraint is the owner closest to breaking?

Tools: Graph paper, a calculator, and optionally a free graphing tool such as GeoGebra to check the region.

Hand in: Your data table (with sources), the LPP, the graph with corner points, and a paragraph on one limit that your model leaves out (demand, weather, staff absence…) and how it might be added as a constraint.

Going further. Keep the model: in Section 12.2 you will find the corner that maximises profit and compare it with what the owner actually does.

Instructor note: the most common error is a constraint with mismatched units (minutes against hours, grams against kilograms) — ask students to write the unit beside every number. Encourage “at least” constraints from customer demand as well as “at most” ones from resources, so that some groups meet regions that do not contain the origin.

🧪 Self-check quiz

0/5 correct

Q1. To graph $3x-4y\lt12$ you draw the line $3x-4y=12$

Q2. Which of these cannot be a constraint of a linear programming problem?

Q3. For the constraints $2x+y\ge6$, $x+y\le4$, $x\ge0$, $y\ge0$, the point $(2,1)$ is

Q4. A transport company decides to run $x$ buses and $y$ vans. The non-negative constraints are

Q5. The feasible region of $x+y\ge2$, $x+y\le1$, $x\ge0$, $y\ge0$ is

← Chapter 12 — Linear Programming12.2 The Graphical Method: Bounded Feasible Regions →