Chapter 12 · Linear Programming

12.3 Unbounded and Empty Feasible Regions

When the feasible region runs off to infinity, the corner point table can lie: its largest value need not be a maximum. One open half-plane settles the question. And when the constraints contradict each other, there is no feasible plan at all.

The farmer of Section 12.1 needs at least 9 kg of nitrogen and 8 kg of phosphate, and buys bags of two fertilisers. Requirements of the form “at least” put no limit on how much can be bought: two hundred bags would certainly meet the need. So the feasible region is unbounded — it stretches out for ever — and Theorem 12.3 of Section 12.2, which promised a maximum and a minimum at the corners, no longer applies. The cost has no largest value at all (buy more and you pay more). Does it have a smallest one, and is it at the corner with the smallest value in the table?

This section answers that question with a single test: draw the objective line through the best corner and look at the open half-plane beyond it. If the feasible region does not reach into that half-plane, the corner really is optimal; if it does, no optimum exists. We also meet the opposite extreme — constraints so demanding that no plan satisfies them all — and put everything together into one complete procedure for any two-variable LPP.

Unbounded Feasible Regions and the Open Half-Plane Test

Recall from Definition 12.5 that a feasible region is unbounded if no circle, however large, encloses it. Theorem 12.2 still holds — if $Z$ has an optimal value, it occurs at a corner — but Theorem 12.3 does not: on an unbounded region the maximum, the minimum, both or neither may fail to exist. The corner table gives the candidates; the following test decides.

📐 Theorem 12.5 — The open half-plane test (unbounded regions)
Let $R$ be an unbounded feasible region with at least one corner point, let $Z=ax+by$, and let $M$ and $m$ be the largest and the smallest values of $Z$ at the corner points of $R$.

(a) If the open half-plane $ax+by\gt M$ has no point in common with $R$, then $M$ is the maximum value of $Z$ on $R$. Otherwise $Z$ has no maximum value on $R$.

(b) If the open half-plane $ax+by\lt m$ has no point in common with $R$, then $m$ is the minimum value of $Z$ on $R$. Otherwise $Z$ has no minimum value on $R$.

Proof of (a). Suppose first that no point of $R$ satisfies $ax+by\gt M$. Then $Z\le M$ at every point of $R$, and $Z=M$ at a corner, so $M$ is the maximum. Now suppose some point $X$ of $R$ has $Z(X)\gt M$. Then $M$ is certainly not the maximum. Could some other number be? By Theorem 12.2, a maximum would have to occur at a corner — but at every corner $Z\le M\lt Z(X)$, so no corner value can be the maximum. Hence $Z$ has no maximum. Part (b) is the same with the inequalities reversed. $\square$

🧭 Problem-solving strategy — applying the test
  1. Find the corners and the candidate value $M$ (for a maximum) or $m$ (for a minimum) from the corner table, exactly as in Section 12.2.
  2. Draw the line $ax+by=M$ (or $=m$) dashed — the half-plane is open — and shade the side where $ax+by\gt M$ (or $\lt m$); a test point tells you which side.
  3. Look: does the shaded half-plane overlap the feasible region? If not, the candidate is optimal. If it does, there is no optimum.
  4. Back it up in writing: to show there is no optimum, give one feasible point beyond the line; to show there is one, explain why no feasible point lies beyond it (often by adding two constraints).
✏️ Example 1 — The cheapest fertiliser purchase
Minimise $Z=400x+300y$ subject to $3x+y\ge9$, $x+2y\ge8$, $x\ge0$, $y\ge0$ (Example 4 of Section 12.1: $x$, $y$ = bags of $F_1$, $F_2$; costs in ₹, illustrative).
Corners From Section 12.1: $(0,9)$, $(2,3)$, $(8,0)$; the region lies above both lines and is unbounded.
Table
corner$(0,9)$$(2,3)$$(8,0)$
$Z=400x+300y$$2700$$1700$$3200$
Candidate minimum $m=1700$.
Test The open half-plane $400x+300y\lt1700$, i.e. $4x+3y\lt17$, lies below the dashed line through $(2,3)$, $\left(\tfrac{17}4,0\right)$ and $\left(0,\tfrac{17}3\right)$. On the graph it touches the region only at $(2,3)$ and does not overlap it. Why, in algebra: every feasible point satisfies both $3x+y\ge9$ and $x+2y\ge8$; adding them gives $4x+3y\ge17$. So no feasible point has $4x+3y\lt17$.
Answer By Theorem 12.5(b) the minimum cost is ₹1,700: buy 2 bags of $F_1$ and 3 bags of $F_2$. Check: nitrogen $3(2)+3=9$ kg, phosphate $2+2(3)=8$ kg — exactly the requirement.
✏️ Example 2 — No maximum
On the same region, does $Z=400x+300y$ have a maximum?
Candidate The largest corner value is $M=3200$, at $(8,0)$.
Test The point $(10,0)$ is feasible ($30\ge9$, $10\ge8$) and gives $Z=4000\gt3200$, so the open half-plane $400x+300y\gt3200$ meets the region.
Answer By Theorem 12.5(a), $Z$ has no maximum: the cost can be made as large as you like by buying more. The corner value $3200$ is not a maximum, even though it is the largest number in the table.
✏️ Example 3 — An unbounded region on which a maximum does exist
Let $R$ be given by $x+y\ge5$, $y\le4$, $x\ge0$, $y\ge0$. Find the maximum and the minimum of $Z=2y-x$ on $R$, if they exist.
Region A horizontal strip $0\le y\le4$, to the right of the line $x+y=5$. On $x=0$ we would need $y\ge5$ and $y\le4$, so there is no corner on the $y$-axis. Corners: $x+y=5$ meets $y=4$ at $(1,4)$ and $y=0$ at $(5,0)$. The strip runs off to the right without end.
Table $Z(1,4)=8-1=7$, $Z(5,0)=0-5=-5$. Candidates $M=7$, $m=-5$.
Maximum For a feasible point, $y\le4$ and $x\ge5-y$, so $2y-x\le2y-(5-y)=3y-5\le12-5=7$. No feasible point has $2y-x\gt7$: the maximum is $7$, at $(1,4)$.
Minimum $(10,0)$ is feasible and gives $Z=-10\lt-5$: the open half-plane $2y-x\lt-5$ meets $R$, so there is no minimum.
Lesson “Unbounded region” does not mean “no maximum”. What matters is whether the region runs off in the direction in which $Z$ increases. Here it runs off to the right, where $Z=2y-x$ decreases.
✏️ Example 4 — Same region, different objectives
On the region $x+y\ge4$, $x+3y\ge6$, $x\ge0$, $y\ge0$ (Exercise II.3 of Section 12.1, corners $(6,0)$, $(3,1)$, $(0,4)$), find the minimum of (a) $Z=2x+3y$ and (b) $Z=x-y$, if they exist.
(a) Table $Z(6,0)=12$, $Z(3,1)=9$, $Z(0,4)=12$; candidate $m=9$.
(a) Test Look for numbers $p,q\ge0$ with $2x+3y=p(x+y)+q(x+3y)$: $p+q=2$, $p+3q=3$ give $q=\tfrac12$, $p=\tfrac32$. Then on $R$, $2x+3y\ge\tfrac32(4)+\tfrac12(6)=9$. The open half-plane $2x+3y\lt9$ misses $R$: minimum $9$ at $(3,1)$.
(b) Table $Z(6,0)=6$, $Z(3,1)=2$, $Z(0,4)=-4$; candidate $m=-4$.
(b) Test $(0,10)$ is feasible ($10\ge4$, $30\ge6$) and gives $Z=-10\lt-4$. So $Z=x-y$ has no minimum. (Nor a maximum: $(10,0)$ gives $10\gt6$.)
Interactive 1 — The Unbounded-Region Trap

The region runs off the picture. Choose a problem and whether you want the maximum or the minimum. The lab finds the best corner value — the candidate — and draws the open half-plane beyond it (dashed edge). If that half-plane overlaps the region, a red feasible point is shown that beats the candidate: no optimum. Press Play to push the objective line further out and watch it keep meeting the region — or find nothing beyond the candidate.

corner values—
candidate—
open half-plane meets R?—
conclusion—

Empty Feasible Regions

Sometimes the constraints simply cannot all be met — a budget too small for the requirements, a store too small for the minimum stock. Then the half-planes have no point in common.

📘 Definition 12.6 — Infeasible problem
If no point satisfies all the constraints of a linear programming problem, its feasible region is empty. The problem then has no feasible solution, and so no optimal solution; it is called an infeasible problem.

Do not confuse the two kinds of failure. On an unbounded region there are plenty of feasible plans, but perhaps no best one. On an empty region there are no plans at all. To show a region is empty, draw it — or better, combine the constraints to reach a contradiction.

✏️ Example 5 — No feasible solution
Maximise $Z=3x+2y$ subject to $x+y\le2$, $2x+3y\ge9$, $x\ge0$, $y\ge0$.
Graph $x+y\le2$ keeps the triangle with corners $(0,0)$, $(2,0)$, $(0,2)$. The line $2x+3y=9$ passes through $(4.5,0)$ and $(0,3)$, entirely beyond that triangle in the first quadrant, and $2x+3y\ge9$ keeps the side away from the origin. The two pieces do not meet.
Algebra For $x\ge0$: $2x+3y\le3x+3y=3(x+y)\le3\cdot2=6\lt9$. So $2x+3y\ge9$ is impossible for a point satisfying the other constraints.
Answer The feasible region is empty; the problem is infeasible and has no optimal solution. (Answering “$\max Z=0$” or listing corners of one of the half-planes would be wrong.)
🧭 Problem-solving strategy — every two-variable LPP, from start to finish
  1. Formulate (Section 12.1) and draw the feasible region $R$.
  2. Is $R$ empty? Then the problem is infeasible — stop.
  3. Find all corners and tabulate $Z$ (Section 12.2).
  4. Is $R$ bounded? Then the largest value is the maximum and the smallest the minimum (Theorem 12.3).
  5. Unbounded? Apply the open half-plane test (Theorem 12.5) to the candidate before you claim it.
  6. If two corners tie for the optimum, every point of the edge between them is optimal (Theorem 12.4).
feasible regionmaximum of $Z$minimum of $Z$
emptynone (no feasible plan)none
bounded, non-emptyexists, at a cornerexists, at a corner
unboundedexists only if $Z\gt M$ misses $R$exists only if $Z\lt m$ misses $R$

Minimum-Cost Problems in Practice

Unbounded regions are the natural home of minimisation problems: requirements say “at least”, and the cheapest way to meet them is the question. When every cost coefficient is positive and the region lies in the first quadrant, the cost cannot drop below $0$. (It can be shown that a minimum then always exists, so by Theorem 12.2 it is the smallest corner value; in an exam, still justify it with the open half-plane test.)

✏️ Example 6 — The cheapest cattle feed
Solve the cattle-feed problem of Exercise III.2 in Section 12.1: minimise $Z=50x+40y$ (₹ per day) subject to $2x+y\ge10$ (protein), $x+2y\ge8$ (minerals), $x\ge0$, $y\ge0$, where $x$, $y$ are kilograms of feeds P and Q (illustrative figures).
Corners $2x+y=10$ through $(5,0)$, $(0,10)$; $x+2y=8$ through $(8,0)$, $(0,4)$. Keep the far sides. On the axes the region starts at $(8,0)$ and $(0,10)$. Crossing: $y=10-2x$, $x+20-4x=8$, so $x=4$, $y=2$.
Table
corner$(0,10)$$(4,2)$$(8,0)$
$Z=50x+40y$$400$$280$$400$
Test Is there a feasible point with $50x+40y\lt280$, i.e. $5x+4y\lt28$? Note $5x+4y=2(2x+y)+(x+2y)$ $\ge2(10)+8=28$ on $R$. So the open half-plane misses $R$.
Answer Feed each cow 4 kg of P and 2 kg of Q a day, at the minimum cost of ₹280. Check: protein $8+2=10$, minerals $4+4=8$ — both requirements met exactly.
Interactive 2 — Feed-Mix Planner

A dairy plans a daily mix of $x$ kg of feed P (2 units protein, 1 unit minerals per kg) and $y$ kg of feed Q (1 unit protein, 2 units minerals per kg). All numbers are illustrative. Move the requirements and the prices; optionally limit the total weight a cow can eat. The planner redraws the feasible region, lists its corners, finds the cheapest mix and checks it with the open half-plane test. Push the weight limit down far enough and the region becomes empty — no mix can work.

off
model—
region—
cheapest mix—
⚠️ Common mistakes when studying alone

1. Trusting the table on an unbounded region. The largest corner value is only a candidate for the maximum. Without the open half-plane test (or a feasible point that beats it) the answer earns no marks.

2. Using a closed half-plane. The test uses $ax+by\gt M$, not $\ge M$: the line $ax+by=M$ itself always touches $R$ (at the candidate corner), so the closed half-plane always “meets” $R$.

3. “Unbounded, so no solution.” An unbounded region can have a maximum (Example 3), a minimum (Example 1), both, or neither. And it always has feasible solutions.

4. Calling an empty region “unbounded”, or giving it an optimal value. If no point satisfies all the constraints, the only correct answer is “no feasible solution”.

5. Drawing the half-plane on the wrong side. For a maximum the test half-plane is where $Z$ is larger than $M$; check with a test point, exactly as in Section 12.1.

Exercises

I
Minimum on an unbounded region. Find the minimum (with justification by the open half-plane test). In parts 1–3, 5 and 7 the constraints are $x+2y\ge6$, $2x+y\ge6$, $x\ge0$, $y\ge0$.
  • 1 $Z=3x+2y$
  • 2 $Z=x+y$
  • 3 $Z=5x+y$
  • 4 $Z=2x+5y$ subject to $x+3y\ge9$, $x+y\ge5$, $x\ge0$, $y\ge0$.
  • 5 Show that $Z=x+y$ has no maximum on the region.
  • 6 $Z=x-3y$ subject to $x+y\ge4$, $y\le3$, $x\ge0$, $y\ge0$. Does $Z$ have a maximum?
  • 7 $Z=x+4y$
Region For parts 1–3, 5, 7: the lines meet at $(2,2)$; on the axes the region starts at $(6,0)$ and $(0,6)$. Corners $(0,6)$, $(2,2)$, $(6,0)$; unbounded.
1 $Z$: $12$, $10$, $18$; $m=10$. Since $3x+2y=\tfrac13(x+2y)+\tfrac43(2x+y)$ $\ge2+8=10$ on $R$, the half-plane $3x+2y\lt10$ misses $R$. Minimum $10$ at $(2,2)$.
2 $Z$: $6$, $4$, $6$; $m=4$. Adding the constraints, $3x+3y\ge12$, so $x+y\ge4$ on $R$. Minimum $4$ at $(2,2)$.
3 $Z$: $6$, $12$, $30$; $m=6$. On $R$, $5x+y\ge2x+y\ge6$ (as $x\ge0$). Minimum $6$ at $(0,6)$.
4 Crossing of $x+3y=9$ and $x+y=5$: $(3,2)$. Corners $(0,5)$, $(3,2)$, $(9,0)$; $Z$: $25$, $16$, $18$; $m=16$. $2x+5y=\tfrac32(x+3y)+\tfrac12(x+y)$ $\ge\tfrac{27}2+\tfrac52=16$. Minimum $16$ at $(3,2)$.
5 The largest corner value is $6$. But $(10,0)$ is feasible ($10\ge6$, $20\ge6$) with $x+y=10\gt6$, so the open half-plane $x+y\gt6$ meets $R$: no maximum.
6 Corners $(4,0)$ and $(1,3)$ (no corner on the $y$-axis, since $y\ge4$ and $y\le3$ clash); $Z$: $4$, $-8$. On $R$, $x\ge4-y$, so $x-3y\ge4-4y\ge4-12=-8$: minimum $-8$ at $(1,3)$. No maximum: $(10,0)$ is feasible with $Z=10\gt4$.
7 $Z$: $24$, $10$, $6$; $m=6$. On $R$, $x+4y\ge x+2y\ge6$ (as $y\ge0$). Minimum $6$ at $(6,0)$.
II
Maximum or minimum? In parts 1, 2, 4 and 5 the region $R$ is $x+y\ge4$, $-x+y\le2$, $x\ge0$, $y\ge0$.
  • 1 Find the corners of $R$, and the maximum of $Z=y-2x$ on $R$ if it exists. Is there a minimum?
  • 2 Does $Z=x+y$ have a maximum on $R$? A minimum? Where?
  • 3 Find the minimum of $Z=4x+3y$ subject to $x+y\ge3$, $x\ge0$, $y\ge0$, and explain why there is no maximum.
  • 4 Show that $Z=-x+y$ has maximum value $2$ on $R$, attained at infinitely many points.
  • 5 Find the minimum of $Z=3x+y$ on $R$.
  • 6 Show that $Z=x-2y$ has neither a maximum nor a minimum on the region $x+2y\ge6$, $2x+y\ge6$, $x\ge0$, $y\ge0$.
1 $x+y=4$ meets $-x+y=2$ at $(1,3)$ and $y=0$ at $(4,0)$; on $x=0$ we would need $y\ge4$ and $y\le2$, so no corner there. Corners $(1,3)$, $(4,0)$; $R$ is unbounded to the right. $Z$: $1$, $-8$. On $R$: $4-x\le y\le x+2$ forces $x\ge1$, and $y-2x\le(x+2)-2x=2-x\le1$. So the maximum is $1$ at $(1,3)$. No minimum: $(10,0)$ gives $-20\lt-8$.
2 $Z$: $4$, $4$. Minimum $4$, since $x+y\ge4$ is itself a constraint — attained at both corners and so along the whole segment from $(1,3)$ to $(4,0)$. No maximum: $(10,0)$ gives $10\gt4$.
3 Corners $(3,0)$, $(0,3)$; $Z$: $12$, $9$. On the region $4x+3y\ge3x+3y\ge9$: minimum $9$ at $(0,3)$. No maximum: $(10,0)$ gives $40\gt12$.
4 $Z$: $2$ at $(1,3)$, $-4$ at $(4,0)$. The constraint $-x+y\le2$ says $Z\le2$ on $R$, so $Z\gt2$ misses $R$: maximum $2$. It is attained at every point of the boundary ray $y=x+2$, $x\ge1$ — e.g. $(5,7)$ — infinitely many optimal solutions.
5 $Z$: $6$ at $(1,3)$, $12$ at $(4,0)$. On $R$, $y\ge4-x$ and $x\ge1$, so $3x+y\ge2x+4\ge6$: minimum $6$ at $(1,3)$.
6 Corners $(0,6)$, $(2,2)$, $(6,0)$; $Z$: $-12$, $-2$, $6$. $(10,0)$ is feasible with $Z=10\gt6$: no maximum. $(0,10)$ is feasible with $Z=-20\lt-12$: no minimum.
III
Empty regions and classification.
  • 1 Show that “maximise $Z=x+y$ subject to $x+2y\le4$, $x+y\ge5$, $x,y\ge0$” has no feasible solution.
  • 2 Show that $x-y\ge1$ and $y-x\ge1$ have no common solution, with or without $x,y\ge0$.
  • 3 Is the region $3x+2y\le6$, $x\ge3$, $y\ge1$ empty?
  • 4 Classify, and give the optimal value where it exists: (a) maximise $Z=2x+3y$ on a non-empty bounded region; (b) minimise $Z=x+2y$ subject to $x+y\ge2$, $x,y\ge0$; (c) maximise $Z=x+y$ subject to $x+y\le-1$, $x,y\ge0$.
  • 5 A student writes: “The feasible region is unbounded, so the LPP has no solution.” Correct the statement.
  • 6 For which values of $k$ is the region $x+y\ge k$, $x+2y\le8$, $x\ge0$, $y\ge0$ non-empty?
1 For $y\ge0$: $x+y\le x+2y\le4\lt5$, so $x+y\ge5$ is impossible. The region is empty — no feasible solution.
2 Adding the two inequalities gives $0\ge2$, which is false. So they have no common solution at all, whatever other constraints are added.
3 Yes: $x\ge3$ and $y\ge1$ give $3x+2y\ge9+2=11\gt6$.
4 (a) Both optima exist, at corners (Theorem 12.3). (b) Unbounded; corners $(2,0)$, $(0,2)$ with $Z=2$, $4$; on the region $x+2y\ge x+y\ge2$, so the minimum is $2$ at $(2,0)$ (there is no maximum, but none was asked). (c) Empty, since $x+y\ge0$ for $x,y\ge0$: no feasible solution.
5 An unbounded region has infinitely many feasible solutions. The objective function may still have an optimal value (as in Example 1); only the open half-plane test can tell. “No feasible solution” describes an empty region.
6 On $x+2y\le8$, $x,y\ge0$ (a triangle with corners $(0,0)$, $(8,0)$, $(0,4)$) the largest value of $x+y$ is $8$, at $(8,0)$. So some point has $x+y\ge k$ exactly when $k\le8$.
IV
Applications (all figures illustrative).
  • 1 In Example 6 the price of P rises to ₹60 per kg and Q falls to ₹30 per kg. Find the cheapest mixes.
  • 2 In Example 1 the price of a bag of $F_2$ rises to ₹500. Find the new cheapest purchase.
  • 3 A tablet X contains 4 units of vitamin A and 1 unit of vitamin C; a tablet Y contains 1 unit of each. A daily course needs at least 12 units of A and 6 units of C. X costs ₹3 and Y ₹2. Find the cheapest combination. (An illustrative model only — not medical advice.)
  • 4 A TV advert reaches 6 lakh people, 2 lakh of them young; a radio advert reaches 2 lakh people, 1 lakh of them young. A campaign must reach at least 24 lakh people in total and at least 10 lakh young people. A TV advert costs ₹50,000 and a radio advert ₹15,000. Find the cheapest campaign.
  • 5 A firm must make at least 10 units in total of two products, at least 4 of them of product A; the profit is ₹20 per unit of A and ₹30 per unit of B. Show that “maximise profit” has no answer, explain what is missing from the model, and solve it again with the extra constraint that at most 15 units can be made.
  • 6 In Example 6 a cow can eat at most (a) 8 kg, (b) 5 kg of feed a day. Solve the problem in each case.
1 $Z=60x+30y$ at $(0,10)$, $(4,2)$, $(8,0)$: $300$, $300$, $480$. Since $60x+30y=30(2x+y)\ge300$ on $R$, the minimum ₹300 is attained along the whole segment of $2x+y=10$ from $(0,10)$ to $(4,2)$.
2 $Z=400x+500y$ at $(0,9)$, $(2,3)$, $(8,0)$: $4500$, $2300$, $3200$. $4x+5y=\tfrac35(3x+y)+\tfrac{11}5(x+2y)$ $\ge\tfrac{27}5+\tfrac{88}5=23$, so $Z\ge2300$ on $R$. Cheapest: 2 bags of $F_1$, 3 of $F_2$, ₹2,300.
3 $4x+y\ge12$, $x+y\ge6$; corners $(0,12)$, $(2,4)$, $(6,0)$; $Z=3x+2y$: $24$, $14$, $18$. $3x+2y=\tfrac13(4x+y)+\tfrac53(x+y)$ $\ge4+10=14$. Cheapest: 2 of X and 4 of Y, ₹14.
4 $x$ TV, $y$ radio adverts; $6x+2y\ge24$ (i.e. $3x+y\ge12$), $2x+y\ge10$; cost $Z=50x+15y$ (₹ thousand). Corners $(0,12)$, $(2,6)$, $(5,0)$; $Z$: $180$, $190$, $250$. On $R$, $50x+15y=15(3x+y)+5x\ge180$. Cheapest: 12 radio adverts, no TV, ₹1,80,000.
5 Maximise $Z=20x+30y$ subject to $x+y\ge10$, $x\ge4$, $y\ge0$: unbounded, and $(4,100)$ is feasible with $Z=3080$ — no maximum. The model lacks a capacity constraint. With $x+y\le15$: corners $(10,0)$, $(15,0)$, $(4,11)$, $(4,6)$; $Z$: $200$, $300$, $410$, $260$. Make 4 of A and 11 of B: profit ₹410.
6 (a) Add $x+y\le8$: corners $(4,2)$, $(2,6)$, $(8,0)$ — bounded; $Z$: $280$, $340$, $400$. The minimum is still ₹280 at $(4,2)$ (which uses only 6 kg). (b) Adding the two requirements gives $3x+3y\ge18$, so $x+y\ge6\gt5$: the region is empty — no mix meets the requirements within 5 kg.
🎯 Exam corner Board · 1 markBoard · 3 marksBoard · 5 marksBoard · Case study

How this is examined: minimisation problems on unbounded regions are a Board favourite, and the mark scheme expects the open half-plane check written out — “the open half-plane $ax+by\lt m$ has no point in common with the feasible region, so the minimum is $m$”. MCQs and Assertion–Reason items test whether you know when an optimum can fail to exist.

E1. Board · 1 mark The feasible region of an LPP is unbounded, and the values of $Z$ at its corner points are $5$, $8$ and $12$. Which statement is necessarily true?  (A) The maximum of $Z$ is $12$  (B) The minimum of $Z$ is $5$  (C) If the open half-plane $Z\lt5$ has no point in common with the region, the minimum of $Z$ is $5$  (D) $Z$ has no minimum

Idea On an unbounded region the corner values give only candidates. (A), (B) and (D) may each be true or false depending on the region; (C) is exactly Theorem 12.5(b).
Answer (C). Trap (A): $12$ is the largest corner value, which is a maximum only for a bounded region or after the test.

E2. Board · 1 mark The LPP “maximise $Z=x+y$ subject to $x+y\le1$, $x+y\ge3$, $x\ge0$, $y\ge0$” has  (A) a unique optimal solution  (B) infinitely many optimal solutions  (C) no feasible solution  (D) an unbounded maximum

Idea No point can have $x+y$ at most $1$ and at least $3$: the feasible region is empty.
Answer (C). Trap (B): $Z=x+y$ is parallel to both boundary lines, which suggests a tie — but there is nothing feasible for $Z$ to be optimal on.

E3. Board · 1 mark Assertion–Reason. Consider “minimise $Z=3x+2y$ subject to $x+y\ge8$, $x\ge0$, $y\ge0$”. Assertion (A): the minimum value of $Z$ is $16$. Reason (R): the feasible region is unbounded, so $Z$ has no minimum value.  (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 Corners $(8,0)$ and $(0,8)$ give $Z=24$ and $16$. On the region $3x+2y\ge2(x+y)\ge16$, so $Z\lt16$ misses it: A is true. R is false — an unbounded region can still have a minimum.
Answer (C).

E4. Board · 3 marks Solve graphically: minimise $Z=3x+5y$ subject to $x+3y\ge12$, $x+y\ge6$, $x\ge0$, $y\ge0$.

Region $x+3y=12$ through $(12,0)$, $(0,4)$; $x+y=6$ through $(6,0)$, $(0,6)$. The origin fails both, so the region lies beyond both lines; it is unbounded. Crossing: subtracting, $2y=6$, $y=3$, $x=3$. Corners $(12,0)$, $(3,3)$, $(0,6)$. (1 mark)
Table $Z$: $36$, $24$, $30$; candidate $m=24$. (1 mark)
Test Draw the dashed line $3x+5y=24$ and the open half-plane $3x+5y\lt24$ (origin side). It has no point in common with the region — indeed $3x+5y=(x+3y)+2(x+y)$ $\ge12+12=24$ there. (½ mark)
Answer Minimum $Z=24$ at $x=3$, $y=3$. (½ mark)

E5. Board · 5 marks Solve graphically: minimise $Z=4x+5y$ subject to $x+2y\ge8$, $3x+y\ge9$, $x\le6$, $x\ge0$, $y\ge0$. Show also that $Z$ has no maximum on the feasible region.

Region $x+2y=8$ through $(8,0)$, $(0,4)$; $3x+y=9$ through $(3,0)$, $(0,9)$; both “$\ge$”, so keep the far sides. $x\le6$ keeps the strip left of $x=6$. The region is open upwards — unbounded. (1½ marks for the graph)
Corners $3x+y=9$ meets $x=0$ at $(0,9)$. $x+2y=8$ and $3x+y=9$: $y=9-3x$, $x+18-6x=8$, so $(2,3)$. $x+2y=8$ meets $x=6$ at $(6,1)$. (The intercept $(8,0)$ is cut off by $x\le6$, and $(3,0)$ fails $x+2y\ge8$.) Corners $(0,9)$, $(2,3)$, $(6,1)$. (1½ marks)
Minimum $Z$: $45$, $8+15=23$, $24+5=29$; candidate $m=23$. Since $4x+5y=\tfrac{11}5(x+2y)+\tfrac35(3x+y)$ $\ge\tfrac{88}5+\tfrac{27}5=23$ on the region, the open half-plane $4x+5y\lt23$ misses it. Minimum $Z=23$ at $(2,3)$. (1½ marks)
No maximum $(0,20)$ is feasible ($40\ge8$, $20\ge9$, $0\le6$) and $Z=100\gt45$, so $4x+5y\gt45$ meets the region: no maximum. (½ mark)

E6. Board · Case study A hostel mess blends two dals. Each kg of dal A provides 2 units of protein and 1 unit of fibre; each kg of dal B provides 1 unit of protein and 3 units of fibre. The day's menu needs at least 12 units of protein and 11 units of fibre. Dal A costs ₹20 per kg and dal B ₹25 per kg (illustrative figures).  (i) Formulate the LPP. (1 mark)  (ii) Find the corner points of the feasible region. (1 mark)  (iii) Find the cheapest blend, justifying that it is a minimum. (2 marks)

(i) $x$, $y$ = kg of dal A, B. Minimise $Z=20x+25y$ subject to $2x+y\ge12$, $x+3y\ge11$, $x\ge0$, $y\ge0$.
(ii) $2x+y=12$ through $(6,0)$, $(0,12)$; $x+3y=11$ through $(11,0)$, $\left(0,\tfrac{11}3\right)$. Crossing: $x=11-3y$, $22-6y+y=12$, so $y=2$, $x=5$. Corners $(0,12)$, $(5,2)$, $(11,0)$; the region is unbounded.
(iii) $Z$: $300$, $150$, $220$; candidate $m=150$. Since $20x+25y=7(2x+y)+6(x+3y)$ $\ge84+66=150$ on the region, the open half-plane $20x+25y\lt150$ has no point in common with it. Cheapest blend: 5 kg of A and 2 kg of B, costing ₹150.
🔬 Research–Teaching NexusMini project · about 60 minutes

Research question. What is the cheapest way to meet a family's daily protein and fibre needs from two everyday foods — and how close is the family's real diet to that cheapest plan?

Why it matters. Minimum-cost “mix” problems were among the first uses of linear programming, and they are still used to plan animal feed, hospital menus and school meal schemes such as India's PM POSHAN mid-day meals. They also show the limits of a model: the cheapest plan may be one no one wants to eat.

What to do.

  1. Choose two foods your family eats (for example a dal and a cereal). From food packets or a reliable nutrition table, record the protein and fibre per 100 g; record local prices per kg. Note your sources.
  2. Choose daily targets for protein and fibre from a published guideline (state which one) — or use illustrative targets and say so.
  3. Formulate the LPP “minimise cost subject to protein ≥ …, fibre ≥ …”, draw the (unbounded) feasible region, find the corners and the minimum, and justify it with the open half-plane test.
  4. Add a realistic “at most” constraint (total weight, or a limit on one food) and solve again. Does the region become bounded? Could it become empty?

Tools: Graph paper or GeoGebra; a spreadsheet for the corner table; Interactive 2 to check your answers.

Hand in: The data table with sources, both LPPs with graphs and answers, and a paragraph comparing the cheapest plan with what your family actually eats — what does the model leave out (taste, variety, other nutrients)?

Going further. Real diet models use dozens of foods and nutrients. Find out how they are solved without drawing graphs, and why adding “variety” constraints changes the answer.

Instructor note: insist on consistent units (grams per 100 g versus per kg is the usual slip). Groups whose foods have similar nutrient ratios will get nearly parallel constraint lines and a corner far away — a good moment to discuss sensitivity. This is a modelling exercise, not dietary advice.

🧪 Self-check quiz

0/5 correct

Q1. On an unbounded feasible region, the objective function $Z$

Q2. On an unbounded region, $m$ is the smallest value of $Z$ at the corners. To conclude that $m$ is the minimum you must check that

Q3. The LPP with constraints $x+y\le2$, $x+y\ge4$, $x,y\ge0$

Q4. On the region $x+y\ge4$, $x,y\ge0$, the objective $Z=x+y$ has

Q5. The minimum of $Z=2x+y$ subject to $x+y\ge3$, $x\ge0$, $y\ge0$ is

← 12.2 The Graphical Method: Bounded Feasible RegionsChapter 13 — Probability →