Chapter 12 · Linear Programming

12.2 The Graphical Method: Bounded Feasible Regions

A feasible region holds infinitely many plans, but the best one is always waiting at a corner. Slide the line Z = k across the region to see why, then solve any bounded problem by listing its corner points and comparing a handful of numbers.

In Section 12.1 the workshop's possible weekly plans filled a quadrilateral: every point of it, fractional points included, is a feasible solution. The owner wants the one with the largest profit $Z=600x+300y$. Trying points at random — $(5,5)$ earns ₹4,500, $(9,2)$ earns ₹6,000 — never tells us when to stop. And unlike the optimisation problems of Section 6.4, calculus cannot help: the derivative of a linear function is a constant, never zero, so there are no stationary points to look for.

The way out is geometric. The plans that earn exactly $k$ rupees lie on a straight line, and for different $k$ these lines are parallel. Pushing the line outwards raises the profit, and the last point of the region that the line touches is the best plan — and it is always a corner. Two theorems make this precise, and they turn every LPP with a bounded feasible region into a short calculation: find the corner points, evaluate $Z$ at each, pick the largest or smallest. This is the corner point method.

Optimal Solutions and the Iso-Profit Line

📘 Definition 12.4 — Optimal solution and optimal value

A feasible solution at which the objective function $Z$ takes its maximum value (in a maximisation problem) or its minimum value (in a minimisation problem) over the whole feasible region is an optimal solution (or optimal feasible solution). The corresponding value of $Z$ is the optimal value.

For a fixed number $k$, the plans with $Z=k$ are the points of the line $ax+by=k$. In a profit problem it is called an iso-profit line (“iso” means equal), in a cost problem an iso-cost line. Two facts about these lines do all the work:

They are parallel. Every line $ax+by=k$ has slope $-\tfrac ab$ (or is vertical when $b=0$), whatever $k$ is. Changing $k$ only slides the line.
Increasing $k$ slides the line in the direction of the arrow $(a,b)$. Moving a point $(x,y)$ to $(x+ta,\ y+tb)$ changes $Z$ by $a(ta)+b(tb)=t(a^2+b^2)$, which is positive for $t\gt0$. For $Z=600x+300y$ that direction is up and to the right — away from the origin.

So to maximise $Z$, slide the iso-profit line in the direction of $(a,b)$ for as long as it still meets the feasible region; the last points it touches are the optimal solutions. To minimise, slide the other way.

✏️ Example 1 — The workshop problem, solved by sliding

Maximise $Z=600x+300y$ subject to $3x+y\le30$, $x+2y\le20$, $x\ge0$, $y\ge0$ (the workshop of Section 12.1, corners $O(0,0)$, $A(10,0)$, $B(8,6)$, $C(0,10)$). Use iso-profit lines, and confirm with the values of $Z$ at the corners.

💡 Show solution▶

Lines $600x+300y=k$ is $2x+y=\tfrac k{300}$: slope $-2$ for every $k$. It is steeper than the polishing line $x+2y=20$ (slope $-\tfrac12$) but less steep than the bench line $3x+y=30$ (slope $-3$).

Slide $k=3000$: the line $2x+y=10$ passes through $C(0,10)$ and cuts across the region. $k=6000$: $2x+y=20$ passes through $A(10,0)$ and still meets the region, e.g. at $(9,2)$. Pushing further, the line leaves the region last at $B$, where $k=600(8)+300(6)=6600$: the line $2x+y=22$ meets the region only at $B(8,6)$.

Corner table

corner	$O(0,0)$	$A(10,0)$	$B(8,6)$	$C(0,10)$
$Z=600x+300y$	$0$	$6000$	$6600$ (max)	$3000$

Answer Make 8 tables and 6 chairs a week; the maximum profit is ₹6,600. Both pieces of equipment are then fully used: $3(8)+6=30$ bench-hours and $8+2(6)=20$ polishing hours.

Choose a problem (or change the coefficients of $Z=ax+by$). Press Play or drag $k$: the red line $Z=k$ sweeps across the feasible region, and its green part shows the feasible plans with $Z=k$. The line first touches the region at the minimum and last touches it at the maximum — always at a corner, in agreement with the table. When $Z$ is parallel to an edge, the last contact is a whole edge.

problem:

$a$:$b$:$k$:

objective line—

feasible plans on it—

max / min over corners—

The Corner Point Theorems

📘 Definition 12.5 — Corner point; bounded and unbounded regions

A corner point (or vertex) of a feasible region is a point of the region that lies on two of its boundary lines that cross there — a point where two edges of the region meet. A feasible region is bounded if it can be enclosed in some circle; otherwise it is unbounded.

The feasible region of an LPP is an intersection of half-planes, so it is convex: with any two of its points it contains the whole segment joining them (Exercise IV.3 of Section 12.1). A bounded feasible region with some area is therefore a convex polygon. The key to everything is how a linear function behaves along a segment.

Lemma (a linear function along a segment). If $P(x_1,y_1)$ and $Q(x_2,y_2)$ are two points and $X=\big((1-t)x_1+tx_2,\ (1-t)y_1+ty_2\big)$ with $0\le t\le1$ is a point of the segment $PQ$, then $$Z(X)=(1-t)\,Z(P)+t\,Z(Q).$$ Proof. Expand: $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)$. $\square$ So as $X$ moves from $P$ to $Q$, $Z$ changes steadily from $Z(P)$ to $Z(Q)$; it always lies between these two values and is largest (and smallest) at an end of the segment.

📐 Theorem 12.2 — Corner point theorem (where an optimum can be)

Let $R$ be the feasible region of a linear programming problem, a convex polygon (bounded or unbounded), and let $Z=ax+by$ be the objective function. If $Z$ has an optimal value (maximum or minimum) on $R$, then this optimal value occurs at a corner point of $R$.

📐 Theorem 12.3 — Corner point theorem (bounded regions)

Let $R$ be a bounded feasible region of a linear programming problem, with at least one point. Then the objective function $Z=ax+by$ has both a maximum value and a minimum value on $R$, and each of them occurs at a corner point of $R$.

Why Theorem 12.3 is true. Let $M$ and $m$ be the largest and smallest values of $Z$ at the (finitely many) corners. Take any point $X$ of $R$ and draw the vertical line through it. Because $R$ is a bounded convex polygon, this line meets the boundary of $R$ in two points $U$ and $V$ (possibly equal), and $X$ lies on the segment $UV$. By the lemma, $Z(X)$ lies between $Z(U)$ and $Z(V)$. Each of $U$ and $V$ lies on an edge of $R$, which is a segment between two corners, so by the lemma again $Z(U)$ and $Z(V)$ lie between corner values — between $m$ and $M$. Hence $m\le Z(X)\le M$ for every $X$ in $R$. Since $M$ and $m$ are actually reached at corners, they are the maximum and the minimum. $\square$ Theorem 12.2 — which also covers unbounded regions — is accepted here on the same picture: an optimum, if there is one, is where the sliding objective line leaves the region, and it leaves through a corner (or along an edge, whose ends are corners). Section 12.3 deals with unbounded regions, where an optimum may fail to exist.

🧭 Problem-solving strategy — the corner point method

Draw the feasible region of all the constraints, non-negative constraints included (Section 12.1).
Find every corner point. Corners on the axes come from intercepts. Other corners come from solving the equations of two boundary lines together. If you are unsure which lines meet at a corner, solve every pair and keep only the points that satisfy all the constraints.
Evaluate $Z$ at each corner and set the values out in a table.
Read off the answer. If the region is bounded, the largest value is the maximum and the smallest is the minimum (Theorem 12.3). If it is unbounded, use the test of Section 12.3 before you claim either.
Answer the question asked — the optimal plan and the optimal value, in words and with units.

✏️ Example 2 — A maximum by the corner point method

Maximise $Z=3x+4y$ subject to $x+2y\le10$, $3x+y\le15$, $x\ge0$, $y\ge0$.

💡 Show solution▶

Region $x+2y=10$ meets the axes at $(10,0)$, $(0,5)$; $3x+y=15$ at $(5,0)$, $(0,15)$. Both inequalities hold at the origin, so the region is the part of the first quadrant below both lines: on the axes it ends at $(5,0)$ and $(0,5)$.

Crossing From $3x+y=15$, $y=15-3x$; then $x+30-6x=10$, so $x=4$, $y=3$. Corners $O(0,0)$, $A(5,0)$, $B(4,3)$, $C(0,5)$; the region is bounded.

Table

corner	$(0,0)$	$(5,0)$	$(4,3)$	$(0,5)$
$Z=3x+4y$	$0$	$15$	$24$	$20$

Answer By Theorem 12.3 the maximum is $Z=24$, at $x=4$, $y=3$.

✏️ Example 3 — Both a minimum and a maximum

Find the minimum and the maximum of $Z=2x+3y$ subject to $x+2y\ge4$, $x+y\le6$, $x\le4$, $x\ge0$, $y\ge0$.

💡 Show solution▶

Region $x+2y\ge4$: the origin fails ($0\ge4$ is false), so keep the side away from the origin, above the line through $(4,0)$ and $(0,2)$. $x+y\le6$ and $x\le4$ keep the origin side. The region is the part of the strip $0\le x\le4$ between the two slanting lines — it does not contain the origin.

Corners $x+2y=4$ meets $y=0$ at $(4,0)$ — which is also on $x=4$ — and meets $x=0$ at $(0,2)$. $x=4$ meets $x+y=6$ at $(4,2)$. $x+y=6$ meets $x=0$ at $(0,6)$. Corners: $(4,0)$, $(4,2)$, $(0,6)$, $(0,2)$; bounded.

Table

corner	$(4,0)$	$(4,2)$	$(0,6)$	$(0,2)$
$Z=2x+3y$	$8$	$14$	$18$ (max)	$6$ (min)

Answer Minimum $Z=6$ at $(0,2)$; maximum $Z=18$ at $(0,6)$.

Note The origin is not feasible here, so the minimum is not $0$. Writing $Z(0,0)=0$ in the table is a common slip in problems with a “$\ge$” constraint.

✏️ Example 4 — Three constraints, and an intersection to throw away

On the region $x+y\le8$, $x+3y\le18$, $2x+y\le14$, $x\ge0$, $y\ge0$, maximise (a) $Z_1=x+2y$ and (b) $Z_2=3x+2y$.

💡 Show solution▶

Pairs Call the lines $L_1: x+y=8$, $L_2: x+3y=18$, $L_3: 2x+y=14$. Solving in pairs: $L_1\cap L_2$: subtract, $2y=10$, so $(3,5)$. $L_1\cap L_3$: subtract, $x=6$, so $(6,2)$. $L_2\cap L_3$: $y=14-2x$, $x+42-6x=18$, so $x=\tfrac{24}5$, $y=\tfrac{22}5$.

Filter $\left(\tfrac{24}5,\tfrac{22}5\right)$ gives $x+y=\tfrac{46}5=9.2\gt8$: it breaks $L_1$'s constraint, so it is not a corner. On the axes, the nearest intercepts are $(7,0)$ (from $L_3$) and $(0,6)$ (from $L_2$). Corners: $(0,0)$, $(7,0)$, $(6,2)$, $(3,5)$, $(0,6)$ — a pentagon.

Table

corner	$(0,0)$	$(7,0)$	$(6,2)$	$(3,5)$	$(0,6)$
$Z_1=x+2y$	$0$	$7$	$10$	$13$	$12$
$Z_2=3x+2y$	$0$	$21$	$22$	$19$	$12$

Answer (a) $\max Z_1=13$ at $(3,5)$. (b) $\max Z_2=22$ at $(6,2)$. The same region, different objectives, different optimal corners: the steeper the iso-line, the further right the best corner.

The lab takes the boundary lines two at a time (the axes count too), solves each pair, and tests the crossing point against every constraint: green = feasible, so a corner; red ✗ = it breaks a constraint, so it is thrown away. Press Play or Next. When every pair has been tried, $Z$ is evaluated at the corners and the best one is marked.

problem:

pair of lines—

crossing point—

test—

corners found—

Ties, Multiple Optimal Solutions and Applications

What if two corners give the same best value? On the slider this happens when the objective line is parallel to an edge of the region: at the end of its slide it lies along the whole edge.

📐 Theorem 12.4 — Multiple optimal solutions

Let $R$ be the feasible region of an LPP. If the objective function $Z$ attains its maximum value $M$ on $R$ at two different points $P$ and $Q$, then it attains $M$ at every point of the segment $PQ$; so there are infinitely many optimal solutions. The same holds for a minimum.

Proof. Every point $X$ of $PQ$ is feasible, because $R$ is convex. By the lemma, $Z(X)=(1-t)Z(P)+tZ(Q)$ $=(1-t)M+tM=M$. $\square$ In particular, an LPP can never have exactly two optimal solutions: it has none, one, or infinitely many.

✏️ Example 5 — A tie between two corners

Maximise $Z=6x+3y$ subject to $2x+y\le10$, $x+y\le6$, $x\ge0$, $y\ge0$.

💡 Show solution▶

Corners Intercepts: $(5,0)$, $(0,10)$ and $(6,0)$, $(0,6)$; keep $(5,0)$ and $(0,6)$. Crossing: subtracting, $x=4$, $y=2$. Corners $(0,0)$, $(5,0)$, $(4,2)$, $(0,6)$.

Table

corner	$(0,0)$	$(5,0)$	$(4,2)$	$(0,6)$
$Z=6x+3y$	$0$	$30$	$30$	$18$

Answer The maximum value is $30$, attained at $(5,0)$, at $(4,2)$ and — by Theorem 12.4 — at every point of the segment joining them, which is part of the line $2x+y=10$. For instance the midpoint $(4.5,\,1)$ gives $27+3=30$.

Why $Z=6x+3y=3(2x+y)$ is parallel to the boundary line $2x+y=10$, so the sliding line leaves the region along that whole edge. If $x$ and $y$ must be whole numbers (items, people), only $(5,0)$ and $(4,2)$ remain.

✏️ Example 6 — Mrs Iyer's investment

Solve the LPP of Example 5 in Section 12.1: maximise $Z=0.08x+0.1y$ (interest, ₹ thousand) subject to $x+y\le50$, $x\ge10$, $3x-2y\ge0$, $y\ge0$, where $x$ and $y$ are the amounts (₹ thousand) in schemes A and B.

💡 Show solution▶

Region The constraint $3x-2y\ge0$ is $y\le1.5x$: the region lies below the line $y=1.5x$ through the origin. Together with $x\ge10$ (right of the vertical line), $x+y\le50$ and $y\ge0$ it is a quadrilateral.

Corners $x=10,\ y=0$: $(10,0)$. $x+y=50,\ y=0$: $(50,0)$. $x+y=50$ and $y=1.5x$: $2.5x=50$, so $(20,30)$. $x=10$ and $y=1.5x$: $(10,15)$.

Table

corner	$(10,0)$	$(50,0)$	$(20,30)$	$(10,15)$
$Z=0.08x+0.1y$	$0.8$	$4$	$4.6$	$2.3$

Answer Invest ₹20,000 in scheme A and ₹30,000 in scheme B; the maximum yearly interest is ₹4,600 (with the illustrative rates). Notice that all the money is used and B is exactly 1.5 times A: both of these constraints are “tight” at the optimum.

⚠️ Common mistakes when studying alone

1. Missing a corner. Count edges: a region bounded by $n$ edges has $n$ corners. If your table has fewer, look again — often a corner on an axis has been forgotten.

2. Keeping an infeasible intersection. Two boundary lines always cross somewhere (unless parallel), but the crossing need not be in the region. Test every candidate against every constraint (Example 4).

3. Putting the origin in the table when it is not feasible (Example 3).

4. Evaluating $Z$ at the intercepts of the objective line. The line $Z=k$ is a tool for picturing; the numbers that matter are the values of $Z$ at the corners of the region.

5. Stating only the value. “Maximum $=6600$” is half an answer. Say where: “8 tables and 6 chairs, profit ₹6,600”.

6. Reporting one point when there is a tie. If two corners share the best value, say that every point of the segment between them is optimal.

Exercises

Maximise by the corner point method. In every part $x\ge0,\ y\ge0$ as well.

1 $Z=5x+2y$ subject to $2x+y\le8$, $x+2y\le10$.
2 $Z=x+3y$ subject to the constraints of part 1.
3 $Z=3x+2y$ subject to $x+y\le6$, $x\le4$.
4 $Z=4x+3y$ subject to $x+2y\le10$, $x-y\le1$.
5 $Z=x+y$ subject to $2x+y\le10$, $x+3y\le15$.
6 $Z=10x+7y$ subject to $x+y\le10$, $x\le6$, $y\le8$.
7 $Z=2x+5y$ on the region of Example 4.

💡 Show solutions▶

1 Corners $(0,0)$, $(4,0)$, $(2,4)$, $(0,5)$ (Exercise II.2 of Section 12.1). $Z$: $0,\ 20,\ 18,\ 10$. Maximum $20$ at $(4,0)$.

2 Same corners; $Z$: $0,\ 4,\ 14,\ 15$. Maximum $15$ at $(0,5)$.

3 Corners $(0,0)$, $(4,0)$, $(4,2)$, $(0,6)$; $Z$: $0,\ 12,\ 16,\ 12$. Maximum $16$ at $(4,2)$.

4 Corners $(0,0)$, $(1,0)$, $(4,3)$, $(0,5)$; $Z$: $0,\ 4,\ 25,\ 15$. Maximum $25$ at $(4,3)$.

5 Corners $(0,0)$, $(5,0)$, $(3,4)$, $(0,5)$ (Example 6 of Section 12.1); $Z$: $0,\ 5,\ 7,\ 5$. Maximum $7$ at $(3,4)$.

6 $x=6$ meets $x+y=10$ at $(6,4)$; $y=8$ meets it at $(2,8)$. Corners $(0,0)$, $(6,0)$, $(6,4)$, $(2,8)$, $(0,8)$; $Z$: $0,\ 60,\ 88,\ 76,\ 56$. Maximum $88$ at $(6,4)$.

7 Corners $(0,0)$, $(7,0)$, $(6,2)$, $(3,5)$, $(0,6)$; $Z$: $0,\ 14,\ 22,\ 31,\ 30$. Maximum $31$ at $(3,5)$.

Minimum and maximum (with $x\ge0,\ y\ge0$ throughout).

1 Find the minimum and maximum of $Z=3x+5y$ subject to $x+y\ge2$, $x\le3$, $y\le3$.
2 Find the minimum and maximum of $Z=x-2y$ on the region of part 1.
3 Find the minimum and maximum of $Z=5x+y$ on the region of Example 3.
4 Find the minimum and maximum of $Z=4x+6y$ subject to $x+2y\ge8$, $3x+2y\le30$.
5 The corner points of a bounded feasible region are $(0,2)$, $(3,0)$, $(6,0)$, $(6,8)$ and $(0,5)$. Find the maximum and minimum of $Z=4x+6y$.
6 For which values of $k$ does $Z=x+ky$ attain its maximum over the workshop region (Example 1) at the corner $(8,6)$?
7 Find the minimum and maximum of $Z=-x+y$ subject to $x+2y\le10$, $x-y\le1$.

💡 Show solutions▶

1 The square $0\le x\le3$, $0\le y\le3$ with the corner below $x+y=2$ cut off. Corners $(2,0)$, $(3,0)$, $(3,3)$, $(0,3)$, $(0,2)$; $Z$: $6,\ 9,\ 24,\ 15,\ 10$. Minimum $6$ at $(2,0)$; maximum $24$ at $(3,3)$.

2 Same corners; $Z$: $2,\ 3,\ -3,\ -6,\ -4$. Minimum $-6$ at $(0,3)$; maximum $3$ at $(3,0)$.

3 Corners $(4,0)$, $(4,2)$, $(0,6)$, $(0,2)$; $Z$: $20,\ 22,\ 6,\ 2$. Minimum $2$ at $(0,2)$; maximum $22$ at $(4,2)$.

4 The region lies above $x+2y=8$ and below $3x+2y=30$. Corners $(8,0)$, $(10,0)$, $(0,15)$, $(0,4)$; $Z$: $32,\ 40,\ 90,\ 24$. Minimum $24$ at $(0,4)$; maximum $90$ at $(0,15)$.

5 $Z$: $12,\ 12,\ 24,\ 72,\ 30$. Maximum $72$ at $(6,8)$. Minimum $12$, attained at both $(0,2)$ and $(3,0)$ — hence (Theorem 12.4) at every point of the segment joining them.

6 Corner values: $Z(0,0)=0$, $Z(10,0)=10$, $Z(8,6)=8+6k$, $Z(0,10)=10k$. We need $8+6k\ge10$, i.e. $k\ge\tfrac13$, and $8+6k\ge10k$, i.e. $k\le2$ (and $8+6k\ge0$, which then holds). So $\tfrac13\le k\le2$. At the ends there is a tie with a neighbouring corner.

7 Corners $(0,0)$, $(1,0)$, $(4,3)$, $(0,5)$; $Z$: $0,\ -1,\ -1,\ 5$. Maximum $5$ at $(0,5)$. Minimum $-1$ at both $(1,0)$ and $(4,3)$, so at every point of the segment of $x-y=1$ joining them.

III

Applications. Solve the LPPs you formulated in Exercise III of Section 12.1, and two problems from its Exam corner (all figures illustrative).

1 The home bakery: maximise $Z=500x+400y$ subject to $2x+y\le40$, $x+y\le25$, $x,y\ge0$.
2 The tailoring unit: maximise $Z=250x+200y$ subject to $x+y\le40$, $3x+2y\le100$, $y\ge10$, $x\ge0$.
3 Asha's revision: maximise $Z=6x+5y$ subject to $x+y\le10$, $x\ge4$, $x-2y\le0$, $y\ge0$. Give the times in hours and minutes.
4 The family's savings: maximise $Z=0.07x+0.09y$ (₹ thousand) subject to $x+y\le100$, $x\ge20$, $y\le40$, $y\ge0$.
5 The school bags of Exam corner E5 (Section 12.1), but with a profit of ₹150 on each type B bag: maximise $Z=100x+150y$ subject to $2x+3y\le120$, $x+y\le50$, $x,y\ge0$. How many whole-number plans are optimal?
6 The canteen of Exam corner E6 (Section 12.1) makes a profit of ₹15 per roll and ₹10 per sandwich. Find the most profitable morning plan.

💡 Show solutions▶

1 Corners $(0,0)$, $(20,0)$, $(15,10)$, $(0,25)$ (crossing: subtract, $x=15$); $Z$: $0,\ 10000,\ 11500,\ 10000$. Bake 15 batches of muffins and 10 of cookies: maximum profit ₹11,500.

2 Corners $(0,10)$, $\left(\tfrac{80}3,10\right)$, $(20,20)$, $(0,40)$; $Z$: $2000$, $\tfrac{26000}3\approx8666.67$, $9000$, $8000$. Make 20 kurtas and 20 shirts: maximum profit ₹9,000.

3 Corners $(4,2)$, $(4,6)$, $\left(\tfrac{20}3,\tfrac{10}3\right)$; $Z$: $34$, $54$, $\tfrac{170}3\approx56.7$. Maths $\tfrac{20}3$ h $=$ 6 h 40 min, Physics $\tfrac{10}3$ h $=$ 3 h 20 min; estimated gain about $56.7$ marks.

4 Corners $(20,0)$, $(100,0)$, $(60,40)$, $(20,40)$; $Z$: $1.4,\ 7,\ 7.8,\ 5$. Invest ₹60,000 in the deposit and ₹40,000 in bonds: maximum interest ₹7,800 a year.

5 Corners $(0,0)$, $(50,0)$, $(30,20)$, $(0,40)$; $Z$: $0,\ 5000,\ 6000,\ 6000$. The maximum ₹6,000 is attained along the whole segment of $2x+3y=120$ from $(30,20)$ to $(0,40)$ — $Z=50(2x+3y)$ is parallel to it. Whole-number plans on it: $x=0,3,6,\dots,30$ with $y=40-\tfrac{2x}3$ — that is 11 plans.

6 Maximise $Z=15x+10y$ over the corners $(0,0)$, $(50,0)$, $(30,40)$, $(0,70)$: $Z$ $=0,\ 750,\ 850,\ 700$. Make 30 rolls and 40 sandwiches: maximum profit ₹850.

Reasoning.

1 Give an example from this section in which an optimal value is attained at a point that is not a corner. Does this contradict Theorem 12.2?
2 The feasible region $R$ is bounded and contains the origin, and $Z=ax+by$ with $a\gt0$, $b\gt0$. Explain why the minimum of $Z$ on $R$ is $0$.
3 Use the lemma of this section to show that if $Z(P)=5$ and $Z(Q)=11$, then $Z=9$ at the point of $PQ$ that is two-thirds of the way from $P$ to $Q$.
4 A student claims: “My LPP has exactly two optimal solutions, $(2,3)$ and $(4,1)$.” Explain why this is impossible, and name a third optimal solution.
5 A bounded feasible region has corners $O(0,0)$, $A(5,0)$, $B(4,3)$, $C(0,4)$, and $Z=px+qy$ with $p,q\gt0$. Find the condition on $p$ and $q$ for the maximum to occur at both $A$ and $B$.

💡 Show solutions▶

1 Example 5: the maximum $30$ is attained at $(4.5,1)$, which is not a corner. No contradiction — Theorem 12.2 says the optimum occurs at a corner (here at $(5,0)$ and $(4,2)$), not that it occurs only there.

2 Every feasible point has $x\ge0$, $y\ge0$, so $Z=ax+by\ge0$ on $R$; and $Z(0,0)=0$ with $(0,0)$ feasible. So the smallest value is $0$, at the origin.

3 Two-thirds of the way means $t=\tfrac23$: $Z=\tfrac13(5)+\tfrac23(11)=\tfrac{5+22}3=9$.

4 By Theorem 12.4 every point of the segment between two optimal solutions is optimal, so there are infinitely many. The midpoint $(3,2)$ is a third one.

5 $Z(A)=5p$, $Z(B)=4p+3q$, $Z(C)=4q$, $Z(O)=0$. A tie at $A$ and $B$ needs $5p=4p+3q$, i.e. $p=3q$. Then $Z(A)=15q\gt4q=Z(C)$, so $A$ and $B$ really are the best corners. Condition: $p=3q$.

🎯 Exam corner Board · 1 markBoard · 3 marksBoard · 5 marksBoard · Case study

How this is examined: the graphical method is the heart of the chapter's Board questions. 1-mark items give a corner table or a region and ask for an optimal value; the 3- and 5-mark questions ask you to draw the region, label every corner, tabulate $Z$ and state the optimal plan — marks are given for each of these steps, so show them all.

E1. Board · 1 mark The corner points of the feasible region of an LPP are $(0,0)$, $(5,0)$, $(3,4)$ and $(0,5)$. The maximum value of $Z=3x+2y$ is (A) $15$ (B) $17$ (C) $10$ (D) $19$

💡 Show solution▶

Idea $Z$ at the corners: $0$, $15$, $9+8=17$, $10$. The region is bounded (it is a quadrilateral), so the largest corner value is the maximum.

Answer (B). Trap (A): $15$ at $(5,0)$ looks largest if you check only the axis corners. (D) $=3\cdot5+2\cdot2$ comes from a point that is not a corner.

E2. Board · 1 mark The feasible region of an LPP is the rectangle with corners $(1,1)$, $(3,1)$, $(3,4)$, $(1,4)$. The maximum and minimum values of $Z=4x-y$ are (A) $11$ and $0$ (B) $11$ and $3$ (C) $8$ and $0$ (D) $12$ and $0$

💡 Show solution▶

Idea $Z(1,1)=3$, $Z(3,1)=11$, $Z(3,4)=8$, $Z(1,4)=0$.

Answer (A). Trap (B): $3$ at $(1,1)$ is the value at the corner nearest the origin, not the smallest — the negative coefficient of $y$ makes $(1,4)$ smaller. (D) uses $4\cdot3$ and forgets the $-y$.

E3. Board · 1 mark Assertion–Reason. For the LPP “maximise $Z=6x+3y$ subject to $2x+y\le10$, $x+y\le6$, $x,y\ge0$”: Assertion (A): the maximum of $Z$ is attained at infinitely many points. Reason (R): if the maximum of $Z$ is attained at two points of the feasible region, it is attained at every point of the segment joining them. (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

💡 Show solution▶

Idea R is Theorem 12.4. The corner values are $0$, $30$, $30$, $18$ at $(0,0)$, $(5,0)$, $(4,2)$, $(0,6)$ (Example 5): the maximum $30$ is attained at two corners, so by R at every point of the segment between them.

Answer (A).

E4. Board · 3 marks Solve graphically: maximise $Z=5x+4y$ subject to $x+2y\le16$, $3x+2y\le24$, $x\ge0$, $y\ge0$.

💡 Show solution▶

Region $x+2y=16$ through $(16,0)$, $(0,8)$; $3x+2y=24$ through $(8,0)$, $(0,12)$. Both hold at the origin; the region is the quadrilateral below both lines in the first quadrant. (1 mark for the correct shaded graph)

Corners Subtracting the equations: $2x=8$, $x=4$, $y=6$. Corners $(0,0)$, $(8,0)$, $(4,6)$, $(0,8)$. (1 mark)

Table $Z$: $0$, $40$, $20+24=44$, $32$. (½ mark)

Answer The region is bounded, so $\max Z=44$ at $x=4$, $y=6$. (½ mark)

E5. Board · 5 marks Solve graphically: find the minimum and maximum of $Z=3x+2y$ subject to $x+y\ge5$, $x+2y\le14$, $2x+y\le16$, $x\ge0$, $y\ge0$.

💡 Show solution▶

Lines $L_1: x+y=5$ through $(5,0)$, $(0,5)$ — the origin fails $x+y\ge5$, so keep the far side. $L_2: x+2y=14$ through $(14,0)$, $(0,7)$, and $L_3: 2x+y=16$ through $(8,0)$, $(0,16)$ — keep the origin sides. (1½ marks for the graph)

Corners On the $x$-axis the region runs from $(5,0)$ to $(8,0)$; on the $y$-axis from $(0,5)$ to $(0,7)$. $L_2\cap L_3$: $y=16-2x$, $x+32-4x=14$, so $x=6$, $y=4$; check $6+4=10\ge5$ ✓. The other crossings are not corners: $L_1\cap L_2$ is $(-4,9)$ and $L_1\cap L_3$ is $(11,-6)$, both outside the first quadrant. Corners: $(5,0)$, $(8,0)$, $(6,4)$, $(0,7)$, $(0,5)$. (1½ marks)

Table

corner	$(5,0)$	$(8,0)$	$(6,4)$	$(0,7)$	$(0,5)$
$Z=3x+2y$	$15$	$24$	$26$	$14$	$10$

(1 mark)

Answer The region is bounded: minimum $Z=10$ at $(0,5)$, maximum $Z=26$ at $(6,4)$. (1 mark)

E6. Board · Case study A farmer has at most 20 hectares for wheat and mustard. Each hectare of wheat needs 4 units of irrigation water and each hectare of mustard 2 units; 60 units are available for the season. The expected profit is ₹30,000 per hectare of wheat and ₹20,000 per hectare of mustard (illustrative figures). Let $x$ and $y$ hectares be sown. (i) Formulate the LPP and find the corner points of the feasible region. (2 marks) (ii) Find the most profitable plan and the profit. (1 mark) (iii) If the water available rises to 80 units, which constraint becomes redundant, and what is the new best plan? (1 mark)

💡 Show solution▶

(i) Maximise $Z=30x+20y$ (₹ thousand) subject to $x+y\le20$, $4x+2y\le60$ (i.e. $2x+y\le30$), $x,y\ge0$. Crossing: subtracting, $x=10$, $y=10$. Corners $(0,0)$, $(15,0)$, $(10,10)$, $(0,20)$.

(ii) $Z$: $0$, $450$, $500$, $400$. Sow 10 ha of each: profit ₹5,00,000.

(iii) Water becomes $2x+y\le40$. For $x,y\ge0$ with $x+y\le20$ we get $2x+y=x+(x+y)\le20+20=40$ automatically, so the water constraint is now redundant. Corners $(0,0)$, $(20,0)$, $(0,20)$; $Z$: $0$, $600$, $400$. Sow 20 ha of wheat: profit ₹6,00,000.

🔬 Research–Teaching NexusMini project · about 60 minutes

Research question. How sensitive is the best plan to the numbers in the model? If a price or a resource changes a little, does the optimal corner change — and when does it suddenly jump to another corner?

Why it matters. Prices of wheat, petrol or cotton change every week, and the hours a workshop has depend on who turns up. Planners in industry and agriculture do not just solve one LPP: they ask how far the data can move before the answer changes. This “sensitivity analysis” is what makes an LP model useful rather than merely precise.

What to do.

Take the workshop problem (Example 1). In a spreadsheet, list the four corners in rows and compute $Z=px+300y$ at each for a profit per table $p$ from ₹100 to ₹1,200 in steps of ₹50, using MAX to find the best corner for each $p$.
Record the values of $p$ at which the best corner changes. Check them by hand: a change happens exactly when the iso-profit line is parallel to an edge of the region (compare Exercise II.6).
Now keep $p=600$ and change the bench-hours from 20 to 40. Recompute the crossing corner each time (solve the two equations in the spreadsheet) and plot the maximum profit against the bench-hours. Is the graph a straight line, a curve, or straight pieces?
Do the same for your own LPP from the Section 12.1 mini project, if you made one.

Tools: Spreadsheet (MAX, INDEX/MATCH, simple formulas); graph paper or the slider in Interactive 1 to check.

Hand in: Your table of best corners against $p$, the graph of maximum profit against bench-hours, and a paragraph of advice to the workshop owner: “if the price of a table rises above … , then …”.

Going further. Find out about the simplex method, the algebraic procedure that moves from corner to corner of a feasible region in many dimensions, and why it is still used by airlines and power companies.

Instructor note: with $Z=px+300y$ the corner $(0,10)$ is best for $p\le150$, $(8,6)$ for $150\le p\le900$, and $(10,0)$ for $p\ge900$ (ties at $p=150$ and $p=900$, where the iso-profit line is parallel to $x+2y=20$ and to $3x+y=30$). With bench-hours $h$ between 20 and 40, the crossing corner is $\left(\tfrac{2h-20}5,\tfrac{60-h}5\right)$ and the maximum profit is $\tfrac{900h+6000}5$ — a straight line until a corner disappears.

🧪 Self-check quiz

0/5 correct

Q1. A bounded feasible region has corners $(0,0)$, $(6,0)$, $(4,3)$, $(0,5)$. The maximum of $Z=2x+3y$ is

Q2. The iso-profit lines of $Z=3x+2y$ all have slope

Q3. If the feasible region of an LPP is bounded and non-empty, then $Z=ax+by$

Q4. On a feasible region, $Z$ has maximum value $12$ at both $(2,4)$ and $(4,2)$. Then

Q5. For the constraints $x+y\le8$, $x+3y\le18$, $2x+y\le14$, $x,y\ge0$, which crossing point of two boundary lines is not a corner of the feasible region?

← 12.1 Linear Programming Problems and Their Formulation 12.3 Unbounded and Empty Feasible Regions →