Free while we finish the books. A book in review is free to read and use, and so is its PDF. Once the book is finished, its PDF is ₹299.
How many tables, how many chairs
Think of the school canteen on sports day, deciding how many samosas and how many sandwiches to make from limited money and oven trays. Here is a problem of that same shape, with exact numbers.
The dealer’s storeroom has room for 60 pieces. He has Rs 50,000 to spend, on tables at Rs 2500 and chairs at Rs 500.
Here it is, in numbers. A furniture dealer has Rs 50,000 to spend. He has room to store at most 60 pieces. A table costs Rs 2500, and he earns Rs 250 on it when it is sold. A chair costs Rs 500, and he earns Rs 75 on it. How many tables and how many chairs should he buy, to earn the most?
The shaded region holds every purchase within both limits. Four tables, 40 chairs: Rs 4000. Twelve and 30: Rs 5250. Eighteen and 8: Rs 5100.
Three purchases the dealer can afford and store. They earn different profits, and many other purchases also fit.
The figure shades every purchase that fits both limits. Three of them are marked. Four tables and 40 chairs earn Rs 4000. Twelve tables and 30 chairs earn Rs 5250. Eighteen tables and 8 chairs earn Rs 5100. So the mix matters.
a straight edge
a curved edge
A linear limit has a straight edge. A limit on a product, like xy ≤ 100, curves, and this chapter does not use those.
A question of this kind is a LINEAR PROGRAMMING PROBLEM, or LPP. There is one amount to make as large, or as small, as possible. There are limits it must obey. And each of them is linear: no squares, no products, just numbers times the amounts.
Each dot is a purchase the dealer can make: 851 of them. Checking every one is not the method.
Here is the question to carry to the last page. Far too many mixes fit. How can you find the best one without trying them all?
A SCHOLAR INDIA REMEMBERS
Aryabhata wrote the Aryabhatiya at Kusumapura, near modern Patna, in 499 CE, when he was $23$. It gave one general method for a whole class of equations: does the same method work for every case of that kind, not just one? Ask that question of the dealer. Three mixes gave Rs $4000$, Rs $5250$ and Rs $5100$, and hundreds more fit. Trying them answers one problem, slowly. A method that works for every case is the one worth having.
Aryabhata · the hoopoe
Check yourself
The furniture dealer can afford many different combinations of tables and chairs within his budget and storage limit. What is he actually trying to find among them?
the combination that makes total profit largest
the combination that spends the whole budget exactly
the combination that buys the most furniture pieces
the cheapest combination that still fills the storage limit
Check your answer
✓ the combination that makes total profit largest — (A) The dealer wants the one feasible combination that makes his total profit largest.
the combination that spends the whole budget exactly — Spending every rupee of the budget does not by itself make profit largest, a combination that leaves some budget unspent can still earn more.
the combination that buys the most furniture pieces — Buying the most pieces in total says nothing about profit: a table earns Rs 250 profit and a chair only Rs 75, so piece count and profit do not move together.
the cheapest combination that still fills the storage limit — The dealer is maximising profit, not minimising cost, the cheapest option is the opposite of what he is looking for.
Why can the dealer not just check every feasible combination of tables and chairs by hand?
the profit earned per table or chair changes from one combination to the next
the budget of Rs 50,000 is not actually known in advance
tables and chairs must always be bought in matching pairs
there are hundreds of feasible combinations, far too many to check one by one
Check your answer
the profit earned per table or chair changes from one combination to the next — The profit per table (Rs 250) and per chair (Rs 75) is fixed throughout the problem , it does not change from one combination to the next, so that cannot be the obstacle.
the budget of Rs 50,000 is not actually known in advance — The budget, Rs 50,000, is given as a fixed number from the very start of the problem, nothing about it is unknown.
tables and chairs must always be bought in matching pairs — Nothing in the problem ties tables and chairs together in pairs, the dealer chooses each quantity independently, subject only to the budget and storage limits.
✓ there are hundreds of feasible combinations, far too many to check one by one — (D) The budget and storage limits allow 851 different whole-number purchases, far too many to check one by one by hand.
In the furniture dealer’s problem, what does the storage limit of 60 restrict?
the number of chairs bought, on its own
the total number of tables and chairs combined
the total money spent on tables and chairs combined
the total profit the dealer can earn
Check your answer
the number of chairs bought, on its own — The limit of 60 applies to the combined total of tables and chairs, not to the chair count on its own, a dealer could still buy up to 60 chairs if he bought zero tables.
✓ the total number of tables and chairs combined — (B) The storage limit of 60 restricts the combined total of tables and chairs, not either one alone.
the total money spent on tables and chairs combined — Total spending is capped by the Rs 50,000 budget, a separate limit from the storage count of 60 pieces.
the total profit the dealer can earn — Profit is the quantity being maximised, not something any single constraint directly caps at a fixed number.
An LPP has four parts. Let us name them on the dealer’s problem.
The two things the dealer chooses: how many tables, x, and how many chairs, y.
The DECISION VARIABLES are the numbers you choose. Here $x$ is the number of tables, and $y$ is the number of chairs.
The profit is the objective function. Every purchase on one line earns the same, and the lines are parallel.
The OBJECTIVE FUNCTION is the amount to make largest or smallest. Here it is the profit, $Z = 250 x + 75 y$. Its general form is $Z = a x + b y$, where $a$ and $b$ are fixed numbers.
Each constraint keeps one side of its line. Money is one limit and room is another.
The CONSTRAINTS are the limits, written as linear inequalities. The money gives $2500 x + 500 y \leq 50000$. Divide both sides by 500, and it is $5 x + y \leq 100$. The storage gives $x + y \leq 60$.
The NON-NEGATIVE CONSTRAINTS: no negative tables, no negative chairs. Together they keep the first quadrant.
The NON-NEGATIVE CONSTRAINTS are $x \geq 0$ and $y \geq 0$. They are also called the non-negativity restrictions. Nobody buys minus two tables. So these two hold even when a problem does not write them.
Constraint 2x + 3y = 12 meets the axes at (6, 0) and (0, 4). Dashed: the objective at 3. Non-negativity keeps one quadrant.
The figure puts the parts on one picture. The solid line $2 x + 3 y = 12$ is the edge of one constraint. It meets the axes at $(6, 0)$ and $(0, 4)$. The dashed line is the objective $Z = x + y$ at the value 3. The non-negative constraints keep every answer in the first quadrant.
Check yourself
In an LPP, what are the DECISION VARIABLES?
the values found at the very end as the optimal solution
the coefficients written in the objective function
the quantities actually being chosen
the limits a fixed budget or storage space imposes
Check your answer
the values found at the very end as the optimal solution — The decision variables are defined the moment the LPP is set up, the optimal solution is just one particular pair of values they happen to take at the end.
the coefficients written in the objective function — The coefficients in $Z = a x + b y$ are fixed numbers the problem hands you, not quantities you are choosing.
✓ the quantities actually being chosen — (C) The decision variables are the quantities actually being chosen, always restricted to $x \geq 0$, $y \geq 0$ since a negative quantity is not meaningful.
the limits a fixed budget or storage space imposes — A fixed budget or storage limit is expressed by a constraint, not by the decision variables themselves, the variables are what gets chosen subject to those limits.
What is the OBJECTIVE FUNCTION of an LPP?
the boundary line of the feasible region
a linear inequality restricting a limited resource
the expression $Z = a x + b y$ to optimise
the restriction that $x \geq 0$ and $y \geq 0$
Check your answer
the boundary line of the feasible region — A boundary line is drawn from a constraint’s equation, the objective function is a separate expression, evaluated at points, not plotted as a boundary.
a linear inequality restricting a limited resource — A linear inequality restricting a resource is a constraint, a separate piece of vocabulary from the objective function.
✓ the expression $Z = a x + b y$ to optimise — (C) The objective function is the linear expression $Z = a x + b y$ that the LPP maximises or minimises.
the restriction that $x \geq 0$ and $y \geq 0$ — $x \geq 0$, $y \geq 0$ is the non-negativity restriction, it limits the variables, but it is not the expression being maximised or minimised.
Why are the non-negativity restrictions $x \geq 0$, $y \geq 0$ included even when a word problem never states them?
every LPP is required to have exactly two constraints besides them
a negative $x$ or $y$ would not be meaningful
a negative value makes the objective function undefined
the corner-point method needs exactly four corners to work
Check your answer
every LPP is required to have exactly two constraints besides them — An LPP can carry any number of constraints, nothing in the vocabulary fixes the count at two.
✓ a negative $x$ or $y$ would not be meaningful — (B) A negative quantity of tables, chairs, or whatever $x$ and $y$ count is not meaningful, so the restriction is included by default.
a negative value makes the objective function undefined — $Z = a x + b y$ is still a well-defined number at negative $x$ or $y$, the restriction is about meaning in context, not about the formula breaking down.
the corner-point method needs exactly four corners to work — The corner-point method works with however many corners the feasible region actually has, nothing about it requires exactly four.
A company chooses how many units of product P ($x$) and product Q ($y$) to make, subject to a labour-hour limit and a material limit, to maximise revenue. Which of these is a resource constraint, a limit on something the company has only so much of?
maximise total revenue
$x \geq 0$, $y \geq 0$
let $x$ = units of P, $y$ = units of Q, defining the two decision variables
the labour hours used must not exceed the hours available
Check your answer
maximise total revenue — Maximising total revenue is what the objective function does, it is not itself a constraint.
$x \geq 0$, $y \geq 0$ — $x \geq 0$, $y \geq 0$ is a constraint too, but it limits no resource: it only says a count cannot be negative.
let $x$ = units of P, $y$ = units of Q, defining the two decision variables — Naming $x$ and $y$ defines the decision variables, a setup step, not a linear inequality restricting a resource.
✓ the labour hours used must not exceed the hours available — (D) The labour-hour limit caps a resource the company has only so much of, so it is a resource constraint.
▲CONCEPT
x ≤ 3
x ≥ −1
both
1
4
In one variable, two limits overlap on a stretch of the number line. With two variables the overlap is a region.
In Class 11 you solved inequalities in one variable, and marked the answers on a number line. Take “the number is at most 3”. It is true on one side of the point 3 and false on the other. With two inequalities at once, you kept the part of the line where both are true.
A purchase is feasible when it keeps every limit. 70 chairs fit the money but not the room.
One point keeps x + y ≤ 6 and one breaks it. The feasible region is every point that keeps all the limits.
An LPP asks the same thing in two variables. Now each answer is a pair of numbers, a point of the plane. A point $(x, y)$ that satisfies every constraint, the non-negative ones included, is a FEASIBLE SOLUTION. A point that fails even one constraint is an INFEASIBLE SOLUTION. All the feasible solutions together make the FEASIBLE REGION.
(2, 2) passes both constraints: feasible. (1, 6) meets the second constraint exactly but gives 7 for the first, over 6: infeasible.
Let us test two points on the figure. Its constraints are $x + y \leq 6$ and $2 x + y \leq 8$, with $x \geq 0$ and $y \geq 0$. At $(2, 2)$, $x + y = 4$ and $2 x + y = 6$. Both constraints hold, so $(2, 2)$ is feasible. At $(1, 6)$, $2 x + y = 8$, so the second one holds. But $x + y = 7$, and 7 is more than 6. So $(1, 6)$ is infeasible. One failed constraint is enough.
Four feasible points, four profits. The region holds infinitely many more, so testing points one by one never ends.
A feasible solution that gives the objective function its best value is an OPTIMAL SOLUTION. Best means the largest value, when the problem asks for a maximum. It means the smallest, when the problem asks for a minimum. This feasible region holds infinitely many points, so testing them one by one cannot work.
Your turn: is $(5, 1)$ feasible for these constraints? Test both of them.
Check yourself
What is a FEASIBLE SOLUTION to an LPP?
the point giving the largest value of the objective function
the point where two boundary lines happen to cross
a point satisfying every constraint of the LPP at once
a point satisfying most of the constraints
Check your answer
the point giving the largest value of the objective function — The point giving the largest objective value is the optimal solution, one particular feasible solution, not the definition of ‘feasible’ itself.
the point where two boundary lines happen to cross — A point where two boundary lines cross is a candidate corner point, a different idea from a feasible solution, which can be anywhere inside the region.
✓ a point satisfying every constraint of the LPP at once — (C) A feasible solution is any point that satisfies every constraint of the LPP at once, including the non-negativity restrictions.
a point satisfying most of the constraints — Failing even a single constraint makes a point infeasible, satisfying most of them is not enough.
A point satisfies four out of five constraints in an LPP but violates the fifth. Is it a feasible solution?
yes, provided the violated constraint is the non-negativity restriction
yes, since a majority of the constraints hold
only if the violated constraint is an equation rather than an inequality
no: failing even one constraint makes a point infeasible
Check your answer
yes, provided the violated constraint is the non-negativity restriction — The non-negativity restriction is a constraint like any other in this test, violating it disqualifies a point exactly as violating any other constraint would.
yes, since a majority of the constraints hold — The definition requires every constraint to hold, not a majority, one violation disqualifies the point regardless of how many others it satisfies.
only if the violated constraint is an equation rather than an inequality — The rule draws no line between an equation and an inequality, violating either one disqualifies the point the same way.
✓ no: failing even one constraint makes a point infeasible — (D) No, failing even one constraint, out of any number, makes a point infeasible; satisfying the other four does not rescue it.
Every feasible solution of an LPP gives some value of the objective function. What singles out the OPTIMAL solution from the rest?
the feasible solution making the objective largest or smallest
it is the feasible solution satisfying the most constraints with equality
it is the first feasible solution found while plotting
it is the feasible solution closest to the origin
Check your answer
✓ the feasible solution making the objective largest or smallest — (A) The optimal solution is the feasible solution (or solutions) that makes the objective function largest or smallest, whichever the LPP asks for.
it is the feasible solution satisfying the most constraints with equality — The number of constraints a point satisfies exactly (as an equation rather than a strict inequality) is not what optimality measures, the objective function’s value is.
it is the first feasible solution found while plotting — The order in which a feasible solution happens to be found has no bearing on whether it is optimal , every value must actually be compared.
it is the feasible solution closest to the origin — Distance from the origin plays no role in the definition of optimal, only the value of the objective function does.
A student claims: “the feasible region is the set of every point that satisfies at least one constraint of the LPP.” What is wrong with this claim?
it should say every constraint, not at least one
the feasible region should be defined only by the objective function, not the constraints
the feasible region should be called a curve, not a region, so ‘set of points’ is wrong
nothing is wrong; the statement is correct as written
Check your answer
✓ it should say every constraint, not at least one — (A) The claim should say every constraint, not at least one, a point in the feasible region must satisfy all of them simultaneously.
the feasible region should be defined only by the objective function, not the constraints — It is the constraints that define the feasible region, the objective function only decides which point inside that region is optimal.
the feasible region should be called a curve, not a region, so ‘set of points’ is wrong — The feasible region is usually a two-dimensional area bounded by lines, not a one-dimensional curve, ‘set of points’ correctly describes it.
nothing is wrong; the statement is correct as written — The definition requires every constraint to hold at once, ‘at least one’ is a much weaker, and wrong, standard.
Two solutions fix a line, as in Class 10: here (1, 5) and (4, 2) on x + y = 6.
In Class 10 you drew the line of a linear equation in two variables. You found two of its solutions, plotted them and joined them. In Class 11 an inequality in one variable held on one side of a point on the number line. In two variables, a line does that job: an inequality holds on one side of it. So you draw a constraint in two steps. First draw its boundary line. Then test a point, to find which side to shade.
Three purchases that spend exactly Rs 50,000. All of them sit on the boundary line of the money limit.
Put y = 0, then x = 0. The two axis points fix the boundary line of 5x + y ≤ 100.
Let us draw the dealer’s money constraint, $5 x + y \leq 100$. First treat it as the equation $5 x + y = 100$. Two points fix a line. Put $y = 0$, and you get $x = 20$: the point $(20, 0)$. Put $x = 0$, and you get $y = 100$: the point $(0, 100)$. Join them.
Line 5x + y = 100 through (20, 0) and (0, 100), drawn solid. The origin’s side is shaded. (16, 60) gives 140: wrong side.
Which side to shade
The line cuts the plane into two HALF-PLANES. Only one of them satisfies the inequality. To find it, test a point that is not on the line. The origin is the easiest. At $(0, 0)$, $5 x + y = 0$, and $0 \leq 100$ is true. So shade the side that holds the origin. A point on the other side fails. At $(16, 60)$, $5 x + y = 140$, and 140 is more than 100.
With ≤ the line belongs to the region and is drawn solid. With a strict < it is dotted, and (10, 50) is out.
The sign $\leq$ keeps the line itself in the region, so draw it solid. A strict sign, $<$, leaves the line out, and the line is drawn dotted.
When the line runs through the origin, test another point. (1, 0) gives 2 ≥ 0, so its side is shaded.
If the line passes through the origin, the origin cannot be the test point. Use any point off the line instead.
Shade one yourself
Your turn: shade $x - 2 y \leq 0$. Which test point will you use?
Check yourself
To plot the boundary line of $5x + y \leq 100$, what is the first step?
treat it as the equation $5x + y = 100$ and plot its line
plot only the point $(20, 0)$, since one point is enough
substitute the origin directly into the inequality without plotting anything
treat it as $5x + y \geq 100$ instead
Check your answer
✓ treat it as the equation $5x + y = 100$ and plot its line — (A) The first step is to treat $5x + y \leq 100$ as the equation $5x + y = 100$ and plot that line.
plot only the point $(20, 0)$, since one point is enough — A single point does not fix a line, two points are needed, such as $(0,100)$ and $(20,0)$.
substitute the origin directly into the inequality without plotting anything — Testing the origin comes after the boundary line is plotted, it decides which half-plane to shade, not whether to plot a line at all.
treat it as $5x + y \geq 100$ instead — Flipping the inequality changes which half-plane will later be shaded, it does not change which line gets plotted, which always comes from the original equation.
After plotting the line for $5x + y = 100$, how is the correct half-plane for $5x + y \leq 100$ chosen?
shade whichever half-plane looks smaller on the graph
always shade the half-plane above the line
substitute the test point into the equation of the line, not the inequality
test a point not on the line against the original inequality
Check your answer
shade whichever half-plane looks smaller on the graph — How large a half-plane looks on the page plays no part in the rule, only substituting a test point into the original inequality decides.
always shade the half-plane above the line — Which side is wanted depends on testing a point against this specific inequality, not on a fixed rule that always picks ‘above’.
substitute the test point into the equation of the line, not the inequality — Substituting into the equation only ever tells you whether the test point sits exactly on the line, the ORIGINAL inequality is what decides which half-plane is wanted.
✓ test a point not on the line against the original inequality — (D) The correct half-plane is found by substituting a test point not on the line, usually the origin, into the original inequality, not the equation.
A student tests the origin in $5x + y \leq 100$, finds $5(0) + 0 = 0 \leq 100$ true, then shades the half-plane on the FAR side of the line, away from the origin. What went wrong?
nothing went wrong; both halves are correct to shade
the inequality should have been reversed before testing
the origin satisfies it, so its half-plane should be shaded
the test should have used the point $(20,0)$ instead of the origin
Check your answer
nothing went wrong; both halves are correct to shade — Only one half-plane actually satisfies the inequality, shading both, or shading the wrong one, is an error either way.
the inequality should have been reversed before testing — The inequality is tested exactly as given, nothing in the method calls for reversing it before substituting the test point.
✓ the origin satisfies it, so its half-plane should be shaded — (C) Since the origin satisfies $5(0)+0=0\leq 100$, the half-plane CONTAINING the origin should be shaded, not the far side.
the test should have used the point $(20,0)$ instead of the origin — $(20,0)$ lies exactly on the line, since $5(20) + 0 = 100$, a valid test point must not lie on the line being tested.
For the constraint $3x + 3y \leq 0$, the boundary line passes through the origin itself. What must be done differently when deciding which half-plane to shade?
use a convenient point other than the origin as the test point
conclude the constraint has no feasible half-plane at all
plot the line using only one point, since a second point is not needed
shade both half-planes, since no test is possible
Check your answer
✓ use a convenient point other than the origin as the test point — (A) When the boundary line passes through the origin, another convenient point is used as the test point instead, since the origin lies on the line and cannot decide anything.
conclude the constraint has no feasible half-plane at all — The constraint still has a perfectly valid half-plane, only the choice of test point needs to change when the line runs through the origin.
plot the line using only one point, since a second point is not needed — A line still needs two points to plot correctly, passing through the origin does not reduce that requirement.
shade both half-planes, since no test is possible — A test is still possible, it just needs a different point, since the origin itself cannot serve as a test point on its own line.
▲CONCEPT
One purchase breaks the money limit, one breaks the room limit, and one keeps both.
Shade each constraint’s side, then keep the part every shading covers. That overlap is the feasible region.
The feasible region is the set of points that satisfy every constraint at once. You draw it in three steps. Shade the half-plane of each constraint. Keep $x \geq 0$ and $y \geq 0$, which is the first quadrant. The region is the part you have shaded every time: the overlap.
Three panels shade one constraint each. The fourth keeps their overlap, with corners (0, 0), (4, 0), (2, 4) and (0, 6).
Let us build it on the figure. The first panel shades $x + y \leq 6$. The second shades $2 x + y \leq 8$. The third keeps the first quadrant. The last panel lays all three on top of one another. What is left is a region with four corners: $(0, 0)$, $(4, 0)$, $(2, 4)$ and $(0, 6)$.
A third limit, y ≤ 5, trims the top. The region keeps its shape rules and gains a corner.
More constraints mean more lines to draw. Each one is drawn the same way, and the region is still the overlap.
Check yourself
For a two-variable LPP, what is the feasible region on the graph?
the single largest shaded half-plane
the area outside every shaded half-plane, where at least one constraint always fails to hold
the intersection of every shaded half-plane together with $x \geq 0$, $y \geq 0$
the union of all the shaded half-planes
Check your answer
the single largest shaded half-plane — Picking out just the largest half-plane ignores every other constraint, the feasible region must respect all of them together.
the area outside every shaded half-plane, where at least one constraint always fails to hold — A point outside a shaded half-plane is exactly a point that fails that constraint , the opposite of what the feasible region needs.
✓ the intersection of every shaded half-plane together with $x \geq 0$, $y \geq 0$ — (C) The feasible region is the intersection of every shaded half-plane together with the non-negativity restrictions.
the union of all the shaded half-planes — A union would include points that fail some constraints, the feasible region needs every constraint satisfied at once, which means an intersection, not a union.
Why does $x \geq 0$, $y \geq 0$ confine the feasible region to the first quadrant?
together they force non-negative $x$ and $y$
the objective function is only defined for positive $x$ and $y$
the corner-point method only works in the first quadrant
every constraint line happens to cross at the origin
Check your answer
✓ together they force non-negative $x$ and $y$ — (A) $x \geq 0$ and $y \geq 0$ together allow only points with non-negative coordinates, which is exactly the first quadrant.
the objective function is only defined for positive $x$ and $y$ — The objective function $Z = a x + b y$ is well-defined for any $x, y$ at all, the restriction to the first quadrant has nothing to do with the objective’s own definition.
the corner-point method only works in the first quadrant — The corner-point method works on whatever feasible region it is given, it is the non-negativity restriction, not the method, that fixes the region to the first quadrant.
every constraint line happens to cross at the origin — Constraint lines can cross anywhere on the plane, the confinement to the first quadrant comes from the non-negativity restriction, not from where the lines happen to cross.
An LPP has five constraints instead of two. What changes about the graphical method itself?
a third decision variable must be introduced
the corner-point method no longer applies past two constraints
nothing changes: just more lines to plot and intersect
the feasible region can no longer be convex
Check your answer
a third decision variable must be introduced — The number of constraints and the number of decision variables are unrelated , a two-variable LPP can carry any number of constraints.
the corner-point method no longer applies past two constraints — The corner-point method applies to a feasible region with any number of constraints , nothing caps it at two.
✓ nothing changes: just more lines to plot and intersect — (C) Nothing about the graphical method changes with more constraints , there are simply more lines to plot and intersect on the same picture.
the feasible region can no longer be convex — An intersection of convex half-planes stays convex no matter how many half-planes are intersected, more constraints do not threaten convexity.
Halfway between two purchases that fit is another purchase that fits: 11 tables and 24 chairs.
Join any two points of the region and the whole segment stays inside. That is what convex means.
A region is CONVEX when the segment joining any two of its points lies wholly inside it. A convex region has no dents.
A segment that stays in each half-plane stays in their overlap. So cutting with straight lines never makes a dent.
The feasible region of an LPP is always convex. Here is why. One constraint keeps one side of a straight line. Take two points on that side. The segment between them never crosses the line. So one half-plane is convex. The feasible region is the overlap of such half-planes. Take two points in the overlap. Their segment lies in every one of the half-planes, so it lies in the overlap too.
Left: one constraint, segment PQ inside. Middle: corners (0, 0), (5, 0), (2, 3), (0, 3), still no dent. Right: a dented shape, ruled out.
The figure shows it in three panels. In the first, $x + y \leq 5$ holds the points $P$ and $Q$, and the whole segment between them. The second adds $y \leq 3$. Now the region has corners $(0, 0)$, $(5, 0)$, $(2, 3)$ and $(0, 3)$, and it is still convex. The third panel has a dent. A segment between two of its points leaves the shape. Linear constraints can never make that shape.
What convexity buys
Two facts give the region its shape. Its edges are straight, because every constraint is linear. It has no dents, because it is convex. Convexity and a linear objective together put the optimum at a corner, when an optimum exists. The corner-point method is built on that.
Check yourself
What does it mean for the feasible region of an LPP to be CONVEX?
the region is bounded on every side, with no direction stretching to infinity
the region has exactly four corners
the whole segment joining any two of its points lies inside it
the region contains the origin
Check your answer
the region is bounded on every side, with no direction stretching to infinity — An unbounded region can still be convex, bounded and convex are two different properties, and this chapter’s own unbounded examples stay convex.
the region has exactly four corners — Convexity says nothing about how many corners a region has, a convex region can have three corners, or far more.
✓ the whole segment joining any two of its points lies inside it — (C) A region is convex when the entire segment joining any two of its points also lies inside it.
the region contains the origin — A feasible region can be convex without containing the origin at all, the two ideas are unrelated.
Why is the feasible region of an LPP always convex, when non-empty?
convex half-planes intersect to stay convex
the non-negativity restrictions force the region into the first quadrant
every LPP has exactly two decision variables
the objective function is linear
Check your answer
✓ convex half-planes intersect to stay convex — (A) Each constraint’s half-plane is itself convex, and the intersection of convex sets is always convex, so the feasible region inherits convexity from its constraints.
the non-negativity restrictions force the region into the first quadrant — Confining a region to the first quadrant is a separate fact from proving it convex , quadrant placement alone does not establish the segment property that convexity requires.
every LPP has exactly two decision variables — The number of decision variables is unrelated to convexity, the region’s convexity comes from the constraints’ half-planes, not from having exactly two variables.
the objective function is linear — The objective function is a separate piece of the LPP entirely, it plays no part in shaping the feasible region, which comes from the constraints alone.
Why does the feasible region’s convexity matter for the corner-point method?
it guarantees there is exactly one optimal solution
it guarantees the region is bounded, so a maximum always exists
with a linear objective, the optimum sits at a corner point
it guarantees the objective function is also convex
Check your answer
it guarantees there is exactly one optimal solution — This chapter’s own multiple-optimal-solutions worked example shows a convex region can still tie two corners for the optimum, convexity does not guarantee uniqueness.
it guarantees the region is bounded, so a maximum always exists — Convexity does not guarantee boundedness, this chapter’s own unbounded worked examples are convex regions that still have no finite maximum.
✓ with a linear objective, the optimum sits at a corner point — (C) With a linear objective, convexity puts the optimum, when one exists, at a corner point. The straight edges come from the constraints being linear, not from convexity.
it guarantees the objective function is also convex — The objective function’s own shape is a separate fact entirely, the feasible region being convex says nothing about the objective function.
Every corner is where two boundary lines meet. Name the two lines and the corner follows.
A CORNER POINT is a point of the feasible region where two of its boundary lines meet. The axes count as boundary lines, since $x \geq 0$ and $y \geq 0$ are constraints too.
Two kinds of crossing: a line meets an axis, or two constraint lines meet each other.
So corners come from two kinds of crossing. A constraint’s line meets an axis: put $x = 0$ or $y = 0$ in its equation. Or two constraint lines cross: solve their two equations together.
Six crossings, but only four are corners. Each candidate is checked against every constraint before it counts.
Two crossings of the dealer’s lines that are not real purchases: one needs 100 places, one costs Rs 1,50,000.
Each crossing is only a candidate. Test it against every other constraint. A crossing that fails another constraint is not a corner.
The real corners are (0, 0), (4, 0), (2, 4) and (0, 6). The crossings at (0, 8) and (6, 0) break the other constraint.
Let us test the crossings on the figure. Its constraints are $x + y \leq 6$ and $2 x + y \leq 8$, with $x \geq 0$ and $y \geq 0$. The line $2 x + y = 8$ meets the $y$-axis at $(0, 8)$. There $x + y = 8$, and 8 is more than 6. So $(0, 8)$ is not a corner. The line $x + y = 6$ meets the $x$-axis at $(6, 0)$. There $2 x + y = 12$, and 12 is more than 8. So $(6, 0)$ is not a corner either. Four crossings pass every test: $(0, 0)$, $(4, 0)$, $(2, 4)$ and $(0, 6)$. These are the corners you check.
The worked example below solves two lines together.
Check yourself
What is a corner point (vertex) of the feasible region?
a point where two of the region’s boundary lines meet
the midpoint of the feasible region
any point that satisfies the objective function exactly
the point farthest from the origin in the feasible region
Check your answer
✓ a point where two of the region’s boundary lines meet — (A) A corner point is a point of the feasible region where two of its boundary lines meet.
the midpoint of the feasible region — A feasible region has no single defined ‘midpoint’, corner points are specifically the points where boundary lines cross.
any point that satisfies the objective function exactly — The objective function can be evaluated at every feasible point, corner or not , that has nothing to do with what makes a point a corner.
the point farthest from the origin in the feasible region — Distance from the origin plays no role in the definition of a corner point, the definition is about where boundary lines meet.
What are the two ways a corner point of the feasible region can arise?
the origin, or the point farthest from it
a constraint line meeting an axis, or two constraint lines crossing each other
the midpoint of each constraint line
a constraint line meeting the objective function’s own line, or two axes crossing
Check your answer
the origin, or the point farthest from it — These name two specific points rather than the two general mechanisms, axis meetings and line crossings, that actually produce corner points.
✓ a constraint line meeting an axis, or two constraint lines crossing each other — (B) Corner points arise either where a constraint line meets an axis, or where two constraint lines cross each other.
the midpoint of each constraint line — The midpoint of a constraint line plays no role in the corner-point method at all, corners come from axis meetings and line crossings, never from midpoints.
a constraint line meeting the objective function’s own line, or two axes crossing — The objective function is never plotted as a boundary line, and two axes only ever cross at one fixed point, the origin, neither is the general source of corner points.
Two constraint lines of an LPP cross at a point $P$. A student concludes $P$ must be a corner of the feasible region. What check is missing?
$P$ must additionally give the largest value of the objective function
$P$ must additionally lie on the $x$-axis
nothing is missing; any two lines crossing is automatically a corner
whether $P$ also satisfies every OTHER constraint of the LPP
Check your answer
$P$ must additionally give the largest value of the objective function — Whether a point is a corner is a purely geometric fact, separate from whether that corner later turns out to give the largest or smallest objective value.
$P$ must additionally lie on the $x$-axis — A corner point formed by two constraint lines crossing each other need not touch either axis at all, that is only one of the two ways corners arise.
nothing is missing; any two lines crossing is automatically a corner — An intersection that violates some other constraint lies outside the feasible region entirely, it does not count as a corner of that region.
✓ whether $P$ also satisfies every OTHER constraint of the LPP — (D) The missing check is whether $P$ also satisfies every other constraint of the LPP, an intersection failing one of them lies outside the feasible region.
Two boundary lines of an LPP’s feasible region cross at $(6, -2)$. Given the non-negativity restrictions, is $(6, -2)$ a corner point of the feasible region?
no, because corner points must always lie on an axis
yes, any intersection of two boundary lines is automatically a corner point
yes, since $x = 6$ is non-negative that is enough
no: it fails $y \geq 0$, so it lies outside the feasible region
Check your answer
no, because corner points must always lie on an axis — A corner formed by two constraint lines crossing away from any axis is still perfectly valid, provided it satisfies every constraint, the real problem with $(6,-2)$ is $y \geq 0$ failing, not its distance from an axis.
yes, any intersection of two boundary lines is automatically a corner point — An intersection that fails another constraint, here $y \geq 0$, lies outside the feasible region, it is not a corner of it, however cleanly the two lines cross.
yes, since $x = 6$ is non-negative that is enough — Both coordinates must satisfy non-negativity together, a non-negative $x$ does not excuse a negative $y$, which still fails $y \geq 0$ on its own.
✓ no: it fails $y \geq 0$, so it lies outside the feasible region — (D) No, $(6,-2)$ fails $y \geq 0$, so despite being an intersection of two boundary lines, it lies outside the feasible region and is not a corner of it.
The lines x + 2y = 10 and 3x + y = 15 cross at (4, 3). Both equations hold exactly there.
The determinant is −5, not 0, so the lines cross once. Solving gives (4, 3), and both equations check.
Worked example
Find where $x + 2y = 10$ and $3x + y = 15$ cross
$x + 2y = 10$ and $3x + y = 15$ These are two boundary lines of a region. Find the point where they cross.
$y = 15 - 3x$ Solve the second equation for $y$.
$x + 2(15 - 3x) = 10$ Put this $y$ into the first equation.
$x + 30 - 6x = 10 \to -5x = -20 \to x = 4$ Expand, collect the terms in $x$, and divide by $-5$.
$y = 15 - 3(4) = 3$ Put $x = 4$ back into $y = 15 - 3x$.
*The corner point is $(4, 3)$* Both lines pass through this point, found by solving the two equations together.
Check: $4 + 2(3) = 10$ and $3(4) + 3 = 15$ The point lies on both lines. Each equation holds exactly.
Check yourself
To find where the boundary lines $x + 2y = 10$ and $3x + y = 15$ cross, what is the first algebraic step in the worked method?
substitute $x = 0$ into both equations and compare
solve one equation for one variable, then substitute into the other
graph both lines and estimate the crossing point by eye
add the two equations directly, without solving for either variable first
Check your answer
substitute $x = 0$ into both equations and compare — There is no reason to assume the crossing point has $x = 0$, the worked method solves for the actual crossing, not a guessed value.
✓ solve one equation for one variable, then substitute into the other — (B) The first step is to solve one equation for one variable, here, $y = 15 - 3x$ from the second equation, then substitute that into the other.
graph both lines and estimate the crossing point by eye — The worked method finds the crossing point algebraically and exactly, it does not rely on reading an estimate off a sketch.
add the two equations directly, without solving for either variable first — Adding the two equations gives $4x + 3y = 25$, a new equation that still has two unknowns, it does not by itself locate the crossing point.
Solving $x + 2y = 10$ and $3x + y = 15$ simultaneously gives the corner point $(4,3)$. How is this answer checked?
substitute the answer into only one of the two equations
check that $x = 4$ is larger than $y = 3$
check that $(4,3)$ lies in the first quadrant, without testing either equation
substitute back into both original equations and check
Check your answer
substitute the answer into only one of the two equations — Checking just one equation cannot catch an arithmetic slip made while solving the other, both equations must be confirmed.
check that $x = 4$ is larger than $y = 3$ — Which coordinate happens to be larger has nothing to do with whether the point is actually the correct intersection of the two lines.
check that $(4,3)$ lies in the first quadrant, without testing either equation — Lying in the first quadrant only confirms non-negativity, it says nothing about whether the point actually satisfies either boundary line’s equation.
✓ substitute back into both original equations and check — (D) The answer is checked by substituting $x=4, y=3$ back into both original equations and confirming each one holds exactly.
Two boundary lines $2x + y = 12$ and $x + y = 9$ are given. Following the same method used for $x + 2y = 10$ and $3x + y = 15$, which variable is most convenient to isolate first?
isolate $y$ from $x+y=9$, then substitute into the other equation
isolate $x$ from $2x + y = 12$ by dividing every term by $y$
solve both equations for $x$ and set the two expressions apart without equating them
multiply both equations together before isolating anything
Check your answer
✓ isolate $y$ from $x+y=9$, then substitute into the other equation — (A) Isolating $y = 9 - x$ from $x + y = 9$ is the convenient first move, the same role $y = 15 - 3x$ played in the original worked example, before substituting into the other equation.
isolate $x$ from $2x + y = 12$ by dividing every term by $y$ — Dividing every term by $y$ is not a valid way to isolate $x$, a variable cannot be divided out of an equation this way.
solve both equations for $x$ and set the two expressions apart without equating them — The method works by setting the two expressions for the same variable equal to each other, leaving them unequated finds nothing at all.
multiply both equations together before isolating anything — Multiplying the two equations together produces a new, non-linear expression , not a step in this substitution method at all.
Three different purchases, one profit: Rs 3000 each. They all lie on one straight line.
Raise the profit and the line slides, staying parallel. How far can it slide and still touch the region?
Go back to the dealer. Every purchase in his region earns some profit. Pick one amount of profit, say Rs 3000. The purchases that earn exactly that much lie on one straight line. A larger profit gives a line parallel to it, further from the origin. So raising the profit slides the line across the region. The last place it touches before it leaves is the best purchase. On a region with straight edges and no dents, that place is a corner. Or it is a whole edge, and then its two ends are corners. If the region runs on without end, the line may never leave it.
Dashed lines: Z = 6, 10, 14. The last touches the region only at the corner (2, 4). The inside point (1, 2) gives 7.
Let us watch it on the figure. Its constraints are $x + y \leq 6$ and $2 x + y \leq 8$, with $x \geq 0$ and $y \geq 0$. The objective is $Z = 3 x + 2 y$. The dashed lines are $Z = 6$, $Z = 10$ and $Z = 14$. They are parallel, and $Z$ grows up and to the right. The line $Z = 14$ touches the region at one point, the corner $(2, 4)$. A larger value misses the region. A point inside, $(1, 2)$, gives only $Z = 7$.
Work out Z at every corner. The largest, 14 at (2, 4), is the maximum.
At the corners, $Z$ is 0 at $(0, 0)$, 12 at $(4, 0)$, 14 at $(2, 4)$ and 12 at $(0, 6)$. The largest corner value, 14, is the maximum.
A BOUNDED region fits inside a circle. An unbounded one runs off the page in some direction.
A region is BOUNDED if a circle can be drawn round it. Otherwise it is UNBOUNDED: it runs on without end in some direction. Now the two results can be stated. Let $R$ be the feasible region of an LPP, and $Z = a x + b y$ its objective function.
Both a maximum and minimum exist on a bounded region. On an unbounded one, either may fail to exist, so check each.
THEOREM 1. If $Z$ has an optimal value, maximum or minimum, then it occurs at a corner point of $R$.
THEOREM 2. If $R$ is bounded, then $Z$ has both a maximum and a minimum on $R$. Each of them occurs at a corner point of $R$. The same sliding-line argument gives the minimum too: slide the level line the other way, toward the lowest value instead of the highest.
The method in four steps. On an open region the fourth step, the half-plane test, decides whether the best corner counts.
So the CORNER-POINT METHOD has four steps.
Draw the feasible region and find all its corner points.
Work out $Z$ at every corner.
If $R$ is bounded, the largest value is the maximum, and the smallest is the minimum.
If $R$ is unbounded, let $M$ be the largest corner value. $M$ is the maximum only if the open half-plane $a x + b y > M$ has no point in $R$. Otherwise $Z$ has no maximum. For the smallest corner value $m$, test $a x + b y < m$ the same way.
The half-plane above 18 meets the region, so no maximum. The one below 12 misses it, so 12 is the minimum.
When the objective’s line is parallel to an edge, both corners tie and so does every point between them.
If two corners give the same optimal value, every point on the segment joining them gives it too.
Try a second objective
Your turn: on the figure’s region, work out $Z = x + y$ at the four corners. Which corners give the largest value?
A SCHOLAR INDIA REMEMBERS
How big is the dealer’s region? Put a bound on it. Its corners are $(0, 0)$, $(20, 0)$, $(10, 50)$ and $(0, 60)$. The farthest from the origin is $(0, 60)$, at $60$. So a circle of radius $60$ round the origin holds every corner. The region has no dents, so the circle holds all of it. That is what BOUNDED means. No circle holds the open region of $x + y \geq 3$ and $x \leq 4$.
Aryabhata · the hoopoe
Check yourself
According to Theorem 1, where does $Z$ take its optimal value, if it has one?
anywhere on the boundary, not necessarily a corner
at the centre of the feasible region
at a corner point, never beaten by an interior point
at the point closest to the objective function’s own line
Check your answer
anywhere on the boundary, not necessarily a corner — The theorem narrows the claim to corner points specifically, a whole edge is only optimal when the two corners bounding it already tie, which is the multiple-optimal case, not a general rule about the whole boundary.
at the centre of the feasible region — A feasible region has no single defined ‘centre’ for the theorem to point to, the theorem names corner points specifically.
✓ at a corner point, never beaten by an interior point — (C) Theorem 1: if $Z$ has an optimal value, it occurs at a corner point of $R$. A point inside can at most tie with the best corner; it never does better.
at the point closest to the objective function’s own line — The objective function’s own line is not part of the feasible region at all, the theorem never refers to distance from it.
What does the corner-point method actually do to find the maximum or minimum of $Z$?
solve the objective function algebraically for its own maximum, with no reference to the region
plot the objective function and read off its own vertex
list every corner, evaluate $Z$, take the best value; check the open half-plane if unbounded
evaluate $Z$ only at the origin and the farthest corner
Check your answer
solve the objective function algebraically for its own maximum, with no reference to the region — The objective function alone, with no feasible region to bound it, generally has no maximum or minimum at all, the region is what makes a finite answer possible.
plot the objective function and read off its own vertex — For any fixed value of $Z$, the objective function is a straight line with no vertex of its own, the vertices belong to the feasible region, not to the objective function.
✓ list every corner, evaluate $Z$, take the best value; check the open half-plane if unbounded — (C) The corner-point method lists every corner point of the feasible region, evaluates $Z$ at each one, and takes the largest value as the maximum or the smallest as the minimum. If the region is unbounded, it checks the open half-plane before calling that value the optimum.
evaluate $Z$ only at the origin and the farthest corner — The method evaluates $Z$ at every corner, not a chosen pair, skipping corners can miss the actual optimum, exactly as this chapter’s own misconception example shows.
The corner-point method finds the largest $Z$ among all corners and calls it the maximum. Under what condition does this conclusion actually hold?
only if all the corner coordinates are positive
only if bounded, or the open half-plane check passes
only if the feasible region has exactly four corners
only if the objective function has two variables
Check your answer
only if all the corner coordinates are positive — The sign of the corner coordinates does not matter. What matters is whether the region is bounded or, on an unbounded one, whether the open half-plane check passes.
✓ only if bounded, or the open half-plane check passes — (B) On a bounded region the largest corner value is always the maximum. On an unbounded region it is the maximum only once the open half-plane check passes: the half-plane where $Z$ is larger than that value has no point in the region.
only if the feasible region has exactly four corners — The method works with however many corners a bounded region actually has, nothing requires exactly four.
only if the objective function has two variables — The two-variable setting is already assumed throughout this method. The extra condition is boundedness, or the open half-plane check on an unbounded region.
If two corner points, $(2,6)$ and $(5,3)$, both give the same maximum value of $Z$, what else follows?
the LPP actually has no feasible region at all
one of the two points must actually be an interior point, not a corner
$Z$ must be a constant function
every point on the segment joining $(2,6)$ and $(5,3)$ is optimal too
Check your answer
the LPP actually has no feasible region at all — Two corners tying for the maximum is direct evidence of a well-defined, non-empty feasible region, the opposite of there being no region at all.
one of the two points must actually be an interior point, not a corner — Both named points are corners by assumption, and a tie between them does not reclassify either one as an interior point.
$Z$ must be a constant function — $Z$ can be a genuine linear function of $x$ and $y$ and still tie at two particular corners, that does not make it a constant function everywhere on the plane.
✓ every point on the segment joining $(2,6)$ and $(5,3)$ is optimal too — (D) When two corner points tie for the optimum, every point on the segment joining them is optimal too.
In the worked example maximising $Z = x + y$ subject to $x + y \leq 4$, $x \leq 3$, $y \leq 3$, both $(3,1)$ and $(1,3)$ score $Z = 4$. By the rule for tied corners, what follows about the point $(2,2)$, which lies on the segment between them?
the rule for tied corners says nothing about points that are not corners
$(2,2)$ cannot be optimal since it is not itself a corner
$(2,2)$ is optimal too, on the segment joining tied corners
$(2,2)$ gives a strictly smaller value of $Z$ than either tied corner
Check your answer
the rule for tied corners says nothing about points that are not corners — The rule for tied corners is about the segment between two tied corners, a segment made up of exactly the non-corner points the theorem is being asked about here.
$(2,2)$ cannot be optimal since it is not itself a corner — The rule for tied corners extends optimality to every point on the segment between two tied corners, being a corner is not a requirement for the points in between.
✓ $(2,2)$ is optimal too, on the segment joining tied corners — (C) Since $(3,1)$ and $(1,3)$ tie for the maximum, the rule for tied corners makes every point on the segment between them optimal too, including $(2,2)$.
$(2,2)$ gives a strictly smaller value of $Z$ than either tied corner — $(2,2)$ lies exactly on $x+y=4$, the same edge as the two tied corners, so $Z = x + y = 4$ there too, matching them exactly, not falling short.
Plot both lines from their intercepts. Shade the overlap: corners (0, 0), (20, 0), (10, 50), (0, 60). Largest: Z = 6250 at (10, 50).
The three corners as real purchases. Ten tables and fifty chairs use all the money and all the room.
Worked example
Maximise profit for the furniture dealer
$x$ = number of tables, $y$ = number of chairs Name the decision variables first.
Maximise $Z = 250x + 75y$ A table earns Rs 250 and a chair earns Rs 75. The profit is the objective function.
$2500x + 500y \leq 50000$, i.e. $5x + y \leq 100$ This is the money limit. Divide both sides by 500.
$x + y \leq 60$, $x \geq 0$, $y \geq 0$ This is the storage limit, with the non-negative constraints.
Corners: $(0, 0)$, $(20, 0)$, $(10, 50)$, $(0, 60)$ Plot both lines and shade the side of each that holds the origin. For $(10, 50)$, subtract $x + y = 60$ from $5x + y = 100$. That gives $4x = 40$, so $x = 10$ and $y = 50$.
$Z = 0$ at $(0, 0)$; $Z = 5000$ at $(20, 0)$; $Z = 6250$ at $(10, 50)$; $Z = 4500$ at $(0, 60)$ Work out $Z$ at every corner.
*The maximum is $Z = 6250$ at $x = 10$, $y = 50$* The region is bounded, so the largest corner value is the maximum. The dealer buys 10 tables and 50 chairs.
Check: $(0, 0)$: $0 \leq 100$, $0 \leq 60$; $(20, 0)$: $100 \leq 100$, $20 \leq 60$; $(10, 50)$: $5(10) + 50 = 100 \leq 100$, $10 + 50 = 60 \leq 60$; $(0, 60)$: $60 \leq 100$, $60 \leq 60$ Every corner satisfies both limits, with $x \geq 0$ and $y \geq 0$. So all four are corners of the region, and the table of $Z$ is complete.
Check yourself
In the furniture dealer’s LPP, why does the budget constraint $2500x + 500y \leq 50000$ simplify to $5x + y \leq 100$?
dividing every term by $500$ gives the same inequality in smaller numbers
subtracting $500$ from both sides gives this simplified form
dividing every term by $2500$ gives this simplified form
the two inequalities are not actually equivalent; the simplification is an approximation
Check your answer
✓ dividing every term by $500$ gives the same inequality in smaller numbers — (A) Dividing every term of $2500x + 500y \leq 50000$ by $500$ gives the equivalent, smaller-number inequality $5x + y \leq 100$.
subtracting $500$ from both sides gives this simplified form — Subtracting a constant from both sides leaves the coefficients on $x$ and $y$ unchanged, but those coefficients are exactly what changed here, from $2500$ and $500$ down to $5$ and $1$.
dividing every term by $2500$ gives this simplified form — Dividing every term by $2500$ turns $2500x$ into $x$, not $5x$, that division does not produce this particular simplified form.
the two inequalities are not actually equivalent; the simplification is an approximation — Dividing every term of an inequality by the same positive number produces an exactly equivalent inequality, nothing here is approximate.
How is the corner $(10,50)$ of the dealer’s feasible region actually found?
average the two axis corners $(20,0)$ and $(0,60)$
set $x=0$ in the budget line and $y=0$ in the storage line separately
solve $5x+y=100$ and $x+y=60$ together: $4x=40$, so $x=10, y=50$
read it directly off the storage constraint alone, without the budget line
Check your answer
average the two axis corners $(20,0)$ and $(0,60)$ — Averaging the two axis corners’ coordinates gives $(10,30)$, not $(10,50)$, there is no such averaging step in the corner-point method.
set $x=0$ in the budget line and $y=0$ in the storage line separately — Setting $x=0$ and $y=0$ separately in two different equations produces two different, unrelated points, not the single point where the two lines actually cross.
✓ solve $5x+y=100$ and $x+y=60$ together: $4x=40$, so $x=10, y=50$ — (C) The corner $(10,50)$ is found by solving the budget line $5x+y=100$ and the storage line $x+y=60$ simultaneously, subtracting the two equations gives $4x=40$, so $x=10$, then $y=50$.
read it directly off the storage constraint alone, without the budget line — The storage line $x+y=60$ by itself has infinitely many points on it, finding $(10,50)$ specifically needs the budget line too, to pin down where the two cross.
The dealer’s storage limit is raised from $60$ to $70$. The budget line $5 x + y = 100$ stays. Which corners of the feasible region move?
$(0, 60)$ only
$(10, 50)$ only
$(20, 0)$ and $(10, 50)$
$(10, 50)$ and $(0, 60)$
Check your answer
$(0, 60)$ only — $(0, 60)$ moves to $(0, 70)$, but it is not the only one. $(10, 50)$ is where the storage line crosses the budget line, so it moves too, to $(7.5, 62.5)$.
$(10, 50)$ only — $(10, 50)$ moves to $(7.5, 62.5)$, but it is not the only one. $(0, 60)$ is where the storage line meets the $y$-axis, so it moves too, to $(0, 70)$.
$(20, 0)$ and $(10, 50)$ — $(20, 0)$ lies on the budget line and the $x$-axis, not on the storage line. It stays where it is. The two corners on the storage line move.
✓ $(10, 50)$ and $(0, 60)$ — (D) Both corners on the storage line move. $(10, 50)$ moves to $(7.5, 62.5)$, where $5 x + y = 100$ meets $x + y = 70$. $(0, 60)$ moves to $(0, 70)$. $(0, 0)$ and $(20, 0)$ stay.
In the dealer’s worked example, what does the corner $(0,0)$ represent in terms of tables and chairs?
buying the maximum number of chairs the storage allows
the point giving the maximum profit
buying the maximum number of tables the budget allows
buying zero tables and zero chairs
Check your answer
buying the maximum number of chairs the storage allows — The maximum-chairs corner is $(0,60)$, where $y=60$, at $(0,0)$, $y=0$, meaning zero chairs, not the maximum.
the point giving the maximum profit — $(0,0)$ gives $Z = 0$, the smallest of the four corner values in this problem, not the maximum.
buying the maximum number of tables the budget allows — The maximum-tables corner is $(20,0)$, where $x=20$, at $(0,0)$, $x=0$, meaning zero tables, not the maximum.
✓ buying zero tables and zero chairs — (D) The corner $(0,0)$ represents buying zero tables and zero chairs, $x=0$ tables, $y=0$ chairs.
In the dealer’s LPP, what are the decision variables, and what do they represent?
the corner points themselves, such as $(10,50)$
$x$ and $y$: the number of tables and the number of chairs to buy
the coefficients $250$ and $75$ in the objective function
$Z$ and the budget $50000$: the profit and the total spending limit
Check your answer
the corner points themselves, such as $(10,50)$ — A corner point is a specific candidate pair of values the decision variables can take, not the decision variables’ own definition, which is set up before any corner is even found.
✓ $x$ and $y$: the number of tables and the number of chairs to buy — (B) The decision variables are $x$ and $y$, the number of tables and the number of chairs the dealer chooses to buy.
the coefficients $250$ and $75$ in the objective function — $250$ and $75$ are the fixed profit-per-item numbers multiplying $x$ and $y$ in the objective function, they are not themselves quantities being chosen.
$Z$ and the budget $50000$: the profit and the total spending limit — $Z$ is the objective function, and $50000$ is a fixed number appearing in a constraint , neither one is a quantity being chosen, which is what a decision variable is.
✕MISCONCEPTION
Quick guess
all tables
Rs 5000
Quick guess
all chairs
Rs 4500
Corner
10 tables, 50 chairs
Rs 6250
Rs 1250 more
The quick guess checks only the two ends. The marked corner, where both limits meet, beats them both.
A quick guess at the dealer’s best buy picks an end: all tables, or all chairs. Work out $Z$ at every corner, and the guess fails.
Corner profits for the dealer.
The mixed corner earns Rs 1250 more than all tables. It is where the two limits meet. A guess at the ends never looks there.
Same region, three objectives, three different winning corners. No corner can be skipped.
Theorem 1 says that an optimal value, when there is one, occurs at some corner. It does not say which corner. So you work out $Z$ at every corner, every time.
A SCHOLAR INDIA REMEMBERS
How big can the best profit be? Put bounds on it before you trust a guess. Twelve tables and $30$ chairs fit, and earn Rs $5250$. That beats both ends, so neither end is the best. Now the top. A chair earns $15$ paise on each rupee it costs, and a table only $10$. So the whole budget earns at most Rs $7500$. The mixed corner, Rs $6250$, sits between the bounds.
Aryabhata · the hoopoe
Check yourself
A student checks only $(20,0)$ (all tables) and $(0,60)$ (all chairs) in the furniture dealer’s problem and picks whichever gives the larger profit. What mistake does this make?
the mistake is comparing profits at all, since profit should be read off the coefficients directly
it skips the corner $(10,50)$, which actually gives the largest profit
no mistake: the two axis corners always include the maximum
the mistake is using $(20,0)$ at all, since only $(0,60)$ can ever be optimal
Check your answer
the mistake is comparing profits at all, since profit should be read off the coefficients directly — The coefficients alone, $250$ and $75$, say nothing about which combination of tables and chairs maximises $Z$, the corners have to be evaluated one by one.
✓ it skips the corner $(10,50)$, which actually gives the largest profit — (B) Checking only the two axis corners skips $(10,50)$, which actually gives the largest profit, $Z = 6250$, every corner must be evaluated, not only the obvious-looking ones.
no mistake: the two axis corners always include the maximum — $(10,50)$ gives $Z = 6250$, beating both axis corners’ values of $5000$ and $4500$ , the axis corners do not always include the maximum.
the mistake is using $(20,0)$ at all, since only $(0,60)$ can ever be optimal — $(0,60)$ gives only $Z = 4500$, the lowest of the three corners checked here , it is not singled out as the only possible optimum, any more than $(20,0)$ is.
Why does checking only the two axis corners of the dealer’s feasible region fail to find the true maximum profit?
because $(10,50)$ is not actually a corner of the region
because the objective function is undefined at axis corners
because axis corners never give a feasible solution
the optimum can be at any corner, not an obvious one
Check your answer
because $(10,50)$ is not actually a corner of the region — $(10,50)$ is exactly where the budget and storage lines cross, and it satisfies every other constraint too, that makes it a genuine corner of the region.
because the objective function is undefined at axis corners — $Z = 250x + 75y$ evaluates to an ordinary number at any corner, axis or otherwise , $5000$ at $(20,0)$ and $4500$ at $(0,60)$.
because axis corners never give a feasible solution — $(20,0)$ and $(0,60)$ are both perfectly feasible points, satisfying every constraint , the problem is only that neither one happens to be the best.
✓ the optimum can be at any corner, not an obvious one — (D) Theorem 1 only promises that the optimum sits at some corner, never at an obvious-looking one. Here that corner is $(10,50)$, giving $Z=6250$.
In a different LPP, a student is tempted to check only the corners using exclusively one product, none of the other. Based on the dealer’s example, is this shortcut safe in general?
yes, provided the objective function has only two variables
yes, exclusive-use corners always dominate in profit-maximising LPPs
no, but only because the dealer’s specific numbers happen to be unusual
no, every corner must still be evaluated
Check your answer
yes, provided the objective function has only two variables — The dealer’s LPP already has exactly two variables, and the shortcut still fails there, having two variables does not make the shortcut safe.
yes, exclusive-use corners always dominate in profit-maximising LPPs — The dealer’s own example is a direct counterexample: the winning corner, $(10,50)$, uses both tables and chairs, not one product exclusively.
no, but only because the dealer’s specific numbers happen to be unusual — The general lesson is Theorem 1’s own promise: the optimum is at some corner, not necessarily an obvious one, and that holds for any LPP’s numbers, not just this one.
✓ no, every corner must still be evaluated — (D) No, the same trap applies generally: the optimum can be at any corner, including one that is not an exclusive-use extreme, so every corner must be evaluated.
One best corner, (3, 2) with Z = 13. A tied edge, Z = 4. An unbounded region, open at the top. An empty region.
An LPP asks for a maximum, or for a minimum. For that one question there are four ways it can turn out. The figure shows you one of each.
ONE BEST CORNER. On $x + y \leq 5$ and $2 x + y \leq 8$, $Z = 3 x + 2 y$ is largest at one corner only, $(3, 2)$, where $Z = 13$.
A TIED EDGE. Two corners next to each other give the same best value. Then every point of the edge between them gives it too. The level lines of $Z$ run parallel to that edge. These are MULTIPLE OPTIMAL SOLUTIONS. In the panel, $Z = 4$ all along the edge.
NO OPTIMUM. The region is unbounded, and $Z$ grows without limit across it, or falls without limit. The panel’s region is $x + y \geq 3$ with $x \leq 4$, open at the top. On such a region the maximum can fail to exist, or the minimum can.
NO FEASIBLE POINT. The constraints cannot all hold at once. In the panel, $x + y \leq 2$ and $x + y \geq 6$ never meet. The region is empty, so there is nothing to optimise.
An unbounded region does not by itself mean there is no optimum. Next you meet a minimum that exists on one.
Check yourself
An LPP’s feasible region is empty: no point satisfies every constraint at once. Which of the four solution types is this?
INFEASIBLE
UNBOUNDED
MULTIPLE OPTIMAL
UNIQUE OPTIMAL
Check your answer
✓ INFEASIBLE — (A) An empty feasible region, where no point satisfies every constraint at once, is the INFEASIBLE case.
UNBOUNDED — Unbounded describes a region that stretches to infinity but still contains points , an empty region has none at all, which is a different situation entirely.
MULTIPLE OPTIMAL — Multiple optimal describes two corners tying for the best value inside a non-empty region, an empty region has no corners at all to tie.
UNIQUE OPTIMAL — Unique optimal describes one single winning corner in a non-empty region, an empty region has no corner at all to win.
Under what condition does an LPP have MULTIPLE OPTIMAL solutions rather than one unique corner?
the objective’s level line runs parallel to a tied edge
whenever two constraints happen to be equations rather than inequalities
whenever the feasible region has more than four corners
whenever the objective function has a negative coefficient
Check your answer
✓ the objective’s level line runs parallel to a tied edge — (A) An LPP has multiple optimal solutions when the objective function’s level line is parallel to the edge on which the optimum lies, so the two corners of that edge tie for the best value.
whenever two constraints happen to be equations rather than inequalities — Whether a constraint is written as an equation rather than an inequality has no bearing on whether the objective function happens to tie two corners.
whenever the feasible region has more than four corners — Corner count alone decides nothing about a tie, a region with many corners can still have a single unique optimum, exactly like a four-corner one.
whenever the objective function has a negative coefficient — The sign of a coefficient does not decide a tie. What decides it is whether the level line is parallel to the edge on which the optimum lies.
An LPP’s feasible region stretches to infinity in a direction where $Z$ keeps improving without bound. Which solution type is this, and what follows?
UNBOUNDED: no finite optimal value exists in that direction
INFEASIBLE: there is no feasible solution at all
MULTIPLE OPTIMAL: every point in that direction ties for the best value
UNIQUE OPTIMAL: the farthest visible corner is the answer
Check your answer
✓ UNBOUNDED: no finite optimal value exists in that direction — (A) This is the UNBOUNDED case, since $Z$ keeps improving without limit in that direction, no finite optimal value exists.
INFEASIBLE: there is no feasible solution at all — A region stretching to infinity still has plenty of feasible points in it, it is not empty, so infeasible does not describe this case.
MULTIPLE OPTIMAL: every point in that direction ties for the best value — The objective keeps improving without bound in that direction, there is no single best value for anything to tie at.
UNIQUE OPTIMAL: the farthest visible corner is the answer — There is no farthest corner in a direction that stretches to infinity, and no finite optimum for such a corner to represent.
A student says: “if a feasible region is unbounded, the LPP always has multiple optimal solutions, since there are infinitely many points to check.” What is wrong with this claim?
nothing is wrong; the statement is correct as written
multiple optimal solutions can never occur in any LPP, bounded or not
unboundedness and multiple-optimal are different solution types
an unbounded region always means the LPP is infeasible
Check your answer
nothing is wrong; the statement is correct as written — An unbounded region more often means the objective has no finite optimum in that direction at all, a different outcome from two corners tying for one finite best value.
multiple optimal solutions can never occur in any LPP, bounded or not — This chapter’s own worked example shows a bounded region tying two corners for the maximum, multiple optimal solutions clearly do occur.
✓ unboundedness and multiple-optimal are different solution types — (C) The claim conflates two different solution types, an unbounded region more often means no finite optimum exists in the improving direction, which is not the same as two corners tying.
an unbounded region always means the LPP is infeasible — An unbounded region still contains feasible points, infeasible specifically means the region is empty, an unrelated situation.
The four solution types are all found with the same corner-point method. Which single step distinguishes a UNIQUE OPTIMAL corner from a MULTIPLE OPTIMAL edge?
evaluate $Z$ at every corner; a tie signals multiple optimal
count how many constraints are equations rather than inequalities
check whether the origin is itself a corner point
check whether the feasible region is bounded or unbounded
Check your answer
✓ evaluate $Z$ at every corner; a tie signals multiple optimal — (A) The same evaluate-and-compare step that runs the corner-point method also shows a tie. If the two corners of an edge tie for the best value, the case is multiple optimal. On a bounded region, if one corner strictly beats the rest, it is unique optimal.
count how many constraints are equations rather than inequalities — The count of equation-constraints has no bearing on whether two corners happen to tie for the objective function’s value.
check whether the origin is itself a corner point — Whether the origin happens to be a corner of the region says nothing about whether some other pair of corners ties for the optimum.
check whether the feasible region is bounded or unbounded — Boundedness decides whether a finite optimum can exist at all, it does not by itself tell unique optimal apart from multiple optimal once a finite optimum is known to exist.
Two foods, each with some vitamin A and some vitamin C. The plan needs at least 8 units of A and 10 of C.
Buying more food always meets the limits, and always costs more. The question is how little will do.
A meal plan has to give at least 8 units of vitamin A. It must also give at least 10 units of vitamin C. Adding more food never breaks those rules. So the mixes that fit run on without end, away from the origin. The feasible region is unbounded, and the cost has no largest value.
First thought
?
Check
the region never ends
a least cost
Answer
cheapest meal
Rs 380
An open region can still have a best point. The meal plan’s cheapest mix is Rs 380.
On this open region x + 2y grows for ever upward, but it has a smallest value: 3, at (3, 0).
What decides it is the way $Z$ grows. Take the region $x + y \geq 3$, $x \leq 4$, $x \geq 0$, $y \geq 0$. It is open at the top. For $Z = x + 2 y$, going up the region makes $Z$ as large as you like. So $Z$ has no maximum. But going up never makes $Z$ smaller. Its minimum is 3, at $(3, 0)$, as the worked example below shows.
Flip the objective and it flips: x − 3y has a largest value, 4, but no smallest.
A minimum can fail to exist as well. On the same region, $Z = x - 3 y$ falls without limit as $y$ grows.
When a corner value counts
So on an unbounded region, run the half-plane test for each question asked. A corner value is the optimum only if the open half-plane beyond it has no point in the region.
Your turn: on the same region, the corners give $Z = x + 2 y$ the values 6, 3 and 4. Is $(0, 4)$ in the region? What does that say about the largest corner value, 6?
Check yourself
A student says: “the feasible region is unbounded, so this LPP has no finite optimal value.” What is wrong with this claim, in general?
the claim is right, but only for maximisation, never for minimisation
the claim is right, but only for minimisation, never for maximisation
it depends on which way the objective function increases
nothing is wrong; unbounded regions never have a finite optimum, ever
Check your answer
the claim is right, but only for maximisation, never for minimisation — A minimum can fail too. Minimise $Z = x - 3 y$ on $x + y \geq 3$, $x \leq 4$, $x \geq 0$, $y \geq 0$. As $y$ grows, $Z$ falls without limit, so there is no minimum.
the claim is right, but only for minimisation, never for maximisation — An unbounded region can just as easily strip away a finite maximum instead of a minimum, depending entirely on which way the objective function grows.
✓ it depends on which way the objective function increases — (C) Whether a finite optimum exists depends on which direction the objective function increases, checked against the region’s own unbounded direction, not on unboundedness by itself.
nothing is wrong; unbounded regions never have a finite optimum, ever — This chapter’s own worked example has an unbounded region whose minimum, $Z = 3$, is perfectly finite, ‘never’ is too strong a claim.
For the region $x + y \geq 3$, $x \leq 4$, $x \geq 0$, $y \geq 0$ (unbounded upward), why does $Z = x + 2y$ have no maximum but a minimum of $3$?
unbounded $y$ sends $Z$ to infinity, yet the corners still confirm a minimum
because $x \leq 4$ makes the region bounded after all
because $Z = x + 2y$ is not actually linear
because minimum values never require checking the unbounded direction, only maximums do
Check your answer
✓ unbounded $y$ sends $Z$ to infinity, yet the corners still confirm a minimum — (A) Increasing $y$ without bound sends $Z$ arbitrarily high, so there is no maximum. The smallest corner value is 3, and the open half-plane $x + 2y < 3$ has no point in the region, so the minimum $Z = 3$ still holds.
because $x \leq 4$ makes the region bounded after all — $x \leq 4$ only caps $x$, $y$ can still increase without limit, which is exactly what keeps both the region and $Z$ unbounded upward.
because $Z = x + 2y$ is not actually linear — $Z = x + 2y$ is a perfectly standard linear expression in $x$ and $y$, linearity was never in question here.
because minimum values never require checking the unbounded direction, only maximums do — The minimum still has to be checked against the unbounded direction. Showing that the open half-plane $x + 2y < 3$ has no point in the region is that check, done for a minimum.
A different LPP’s feasible region is unbounded in the direction where $x$ increases without bound, while $y$ stays bounded within the region. For the objective $Z = x - y$, would you expect a finite maximum to exist?
yes, because $y$ is bounded so $Z$ must be bounded too
no, since $Z$ keeps rising as $x$ grows, though a minimum might exist
no maximum AND no minimum, since unbounded regions never have either
yes, because every LPP has a finite maximum regardless of the region’s shape
Check your answer
yes, because $y$ is bounded so $Z$ must be bounded too — $Z = x - y$ grows with $x$ regardless of $y$ staying bounded, a bounded $y$ does not stop the unbounded $x$ from carrying $Z$ upward without limit.
✓ no, since $Z$ keeps rising as $x$ grows, though a minimum might exist — (B) No finite maximum should be expected, since $Z=x-y$ keeps increasing as $x$ grows without bound along the region’s unbounded direction, though a finite minimum could still exist, the same way one survived in this chapter’s own example.
no maximum AND no minimum, since unbounded regions never have either — This chapter’s own worked example keeps a finite minimum on an unbounded region, unboundedness in one direction does not rule out a finite minimum existing here.
yes, because every LPP has a finite maximum regardless of the region’s shape — This chapter’s own worked example already shows an unbounded region can genuinely have no finite maximum, ‘every LPP has one regardless of shape’ is not a safe rule.
What must be checked before concluding an unbounded feasible region has no finite optimal value?
whether the region has at least three corners
whether the constraints are equations or inequalities
which way the objective moves along that direction
whether the objective function has positive coefficients only
Check your answer
whether the region has at least three corners — Corner count has no bearing on whether an unbounded direction breaks the optimum , the actual check is about how the objective function behaves along that direction, not how many corners the region has.
whether the constraints are equations or inequalities — Whether the constraints are written as equations or inequalities has no bearing on whether the objective function keeps improving along the region’s unbounded direction.
✓ which way the objective moves along that direction — (C) What must be checked is which direction the objective function’s value moves, compared against the region’s own unbounded direction, not any fixed count or sign condition.
whether the objective function has positive coefficients only — The sign of the coefficients alone does not decide this, what matters is comparing the region’s own unbounded direction against how the objective function behaves along it.
Open at the top: Z = x + 2y has no maximum. Corners (0, 3), (3, 0), (4, 0) give 6, 3, 4. Minimum: 3.
Climb the y-axis and Z keeps rising: 6, 12, 18. There is no largest value.
Worked example
Find the minimum where no maximum exists
$x + y \geq 3$, $x \leq 4$, $x \geq 0$, $y \geq 0$ Find the maximum and the minimum of $Z = x + 2y$ on this region. The region runs upward without end.
Corners: $(0, 3)$, $(3, 0)$, $(4, 0)$ The line $x + y = 3$ meets the axes at $(0, 3)$ and $(3, 0)$. The line $x = 4$ meets the $x$-axis at $(4, 0)$. The lines $x + y = 3$ and $x = 4$ cross at $(4, -1)$, which fails $y \geq 0$, so it is not a corner.
Along $x = 0$, increasing $y$ sends $Z = x + 2y$ arbitrarily high Every point $(0, y)$ with $y \geq 3$ is in the region. There $Z = 2y$, which grows without limit.
*$Z$ has NO MAXIMUM over this region* So no value of $Z$ is the largest.
$Z = 6$ at $(0, 3)$; $Z = 3$ at $(3, 0)$; $Z = 4$ at $(4, 0)$ Work out $Z$ at every corner. The smallest value is 3.
The open half-plane $x + 2y < 3$ has no point in the region In the region, $x + 2y = (x + y) + y \geq 3 + 0 = 3$. So no point of the region has $x + 2y < 3$.
*The minimum is $Z = 3$ at $(3, 0)$, even though no maximum exists* The open half-plane holds no point of the region, so 3 is the minimum. An unbounded region can lose its maximum and keep its minimum.
Check: $(0, 3)$: $3 \geq 3$, $0 \leq 4$; $(3, 0)$: $3 \geq 3$, $3 \leq 4$; $(4, 0)$: $4 \geq 3$, $4 \leq 4$ Each corner satisfies every constraint, with $x \geq 0$ and $y \geq 0$. So the table of $Z$ covers every corner.
Check yourself
For the region $x+y\geq 3$, $x\leq 4$, $x,y\geq 0$, why does $Z=x+2y$ have NO MAXIMUM?
because $x\leq 4$ makes $Z$ automatically unbounded
because $Z=x+2y$ is not linear
along $x=0$, unbounded $y$ sends $Z$ arbitrarily high
because the corners $(0,3)$, $(3,0)$, $(4,0)$ do not exist
Check your answer
because $x\leq 4$ makes $Z$ automatically unbounded — $x \leq 4$ caps $x$, not $y$, it is $y$ increasing without limit that drives $Z$ upward, not the cap on $x$.
because $Z=x+2y$ is not linear — $Z = x + 2y$ is an ordinary linear expression in $x$ and $y$, linearity was never the issue here.
✓ along $x=0$, unbounded $y$ sends $Z$ arbitrarily high — (C) Along $x=0$, letting $y$ increase without bound sends $Z=x+2y$ arbitrarily high, since the region stretches upward without limit, so no maximum exists.
because the corners $(0,3)$, $(3,0)$, $(4,0)$ do not exist — These three corners are exactly the ones the worked method finds and evaluates in order to confirm the minimum, they exist and are used, not absent.
The worked example finds corners $(0,3)$, $(3,0)$, $(4,0)$ and evaluates $Z=x+2y$ there, getting $6$, $3$, and $4$. Why is $3$ confirmed as the true minimum, rather than just the smallest of the three?
because the region is bounded, so the smallest corner is automatically the minimum
because $(3,0)$ is the corner closest to the origin
because $3$ is the smallest of the three numbers, which is always sufficient on its own
the open half-plane $x+2y<3$ has no point in the feasible region
Check your answer
because the region is bounded, so the smallest corner is automatically the minimum — This region is unbounded upward, and that is why the check is needed here: the open half-plane $x + 2y < 3$ must have no point in the region.
because $(3,0)$ is the corner closest to the origin — Distance from the origin plays no role in confirming a minimum. The confirming step is the open half-plane beyond that value: it must have no point in the region.
because $3$ is the smallest of the three numbers, which is always sufficient on its own — On an unbounded region, the smallest corner value found so far is not automatically the true minimum without an extra check, unlike on a bounded region, where the corner-point method’s comparison alone is enough.
✓ the open half-plane $x+2y<3$ has no point in the feasible region — (D) The open half-plane $x + 2y < 3$ has no point in the feasible region, and that confirms 3 as the true minimum. On an unbounded region the smallest corner value needs this check.
The worked example on $x+y\geq 3$, $x\leq 4$ shows a region with no maximum but a finite minimum. What general lesson about unbounded regions does this illustrate?
an unbounded region can lose its maximum but keep its minimum
whether a maximum exists depends only on the number of corners, not the objective function
unbounded regions never have either a maximum or a minimum
unbounded regions always have both a maximum and a minimum
Check your answer
✓ an unbounded region can lose its maximum but keep its minimum — (A) The general lesson is that an unbounded region can lose its maximum while keeping its minimum, entirely depending on which way the objective function grows along the region’s unbounded direction.
whether a maximum exists depends only on the number of corners, not the objective function — The region’s three corners stay fixed throughout, what actually decides whether a maximum exists is which way the objective function grows along the unbounded direction, not the corner count.
unbounded regions never have either a maximum or a minimum — This very example keeps a finite minimum, $Z = 3$, on an unbounded region, directly contradicting a blanket claim that unbounded regions never have either a maximum or a minimum.
unbounded regions always have both a maximum and a minimum — This example specifically has no maximum at all, so ‘unbounded regions always have both’ is contradicted by the very case being illustrated.
Both limits say at least: the region is open, away from the origin. Corners cost Rs 560, 500 and 380. The cheapest is (2, 4).
The three corner meals. The mixed one meets both limits exactly and costs least.
Nothing in the region costs less than Rs 380: the cheaper side of the line misses the shading.
Worked example
Food I has 2 units of vitamin A and 1 unit of vitamin C per kg, at Rs 50 a kg. Food II has 1 unit of A and 2 units of C per kg, at Rs 70 a kg. Find the cheapest mix with at least 8 units of A and 10 of C
$x$, $y$ = kg of Food I, Food II Name the decision variables: the kilograms of each food.
Minimise $Z = 50x + 70y$ Food I costs Rs 50 a kg, and Food II costs Rs 70 a kg. The cost is the objective function.
$2x + y \geq 8$, $x + 2y \geq 10$, $x \geq 0$, $y \geq 0$ Vitamin A: a kg of Food I gives 2 units, and a kg of Food II gives 1. The mix needs 8. Vitamin C: 1 unit and 2 units, and the mix needs 10.
Corners: $(10, 0)$, $(2, 4)$, $(0, 8)$ Solve $2x + y = 8$ and $x + 2y = 10$ together to get $(2, 4)$. The line $x + 2y = 10$ meets the $x$-axis at $(10, 0)$. The line $2x + y = 8$ meets the $y$-axis at $(0, 8)$. The other two axis crossings, $(4, 0)$ and $(0, 5)$, fail the other constraint.
$Z = 500$ at $(10, 0)$; $Z = 380$ at $(2, 4)$; $Z = 560$ at $(0, 8)$ Work out $Z$ at every corner. The smallest value is 380.
The open half-plane $50x + 70y < 380$ has no point in the feasible region Divide by 10. The line $5x + 7y = 38$ meets the region only at $(2, 4)$. It cuts the axes at $(7.6, 0)$ and $(0, 38/7)$, and both are outside the region. The test point $(10, 0)$ gives $Z = 500$, more than 380. So the whole region lies on the side $50x + 70y \geq 380$. Or find $a$ and $b$ with $a(2x + y) + b(x + 2y) = 50x + 70y$, namely $2a + b = 50$ and $a + 2b = 70$, giving $a = 10$ and $b = 30$. Then $50x + 70y = 10(2x + y) + 30(x + 2y) \geq 10(8) + 30(10) = 380$.
*The minimum cost is $Z = 380$ at $x = 2$, $y = 4$* So the cheapest mix is 2 kg of Food I and 4 kg of Food II.
Check: $(10, 0)$: $20 \geq 8$, $10 \geq 10$; $(2, 4)$: $2(2) + 4 = 8 \geq 8$, $2 + 2(4) = 10 \geq 10$; $(0, 8)$: $8 \geq 8$, $16 \geq 10$ Each corner meets both vitamin needs, with $x \geq 0$ and $y \geq 0$. So the table of $Z$ covers every corner.
A SCHOLAR INDIA REMEMBERS
Write the method down for someone else. Does it work for the next case too? Try the meal plan. Now the question is a minimum, and the region is open. The same steps run. The corners are $(10, 0)$, $(2, 4)$ and $(0, 8)$. They cost Rs $500$, Rs $380$ and Rs $560$. The region is open, so one step is added: $50 x + 70 y < 380$ misses the region. So Rs $380$ is the minimum.
Aryabhata · the hoopoe
Check yourself
In the diet problem, why is the objective $Z = 50x + 70y$ MINIMISED rather than maximised?
because minimising is always the default whenever an LPP involves two foods
$Z$ is the mix’s total cost, and the cheapest one is wanted
because the constraints use $\geq$ instead of $\leq$, so minimisation is always required then
because $x$ and $y$ represent costs, not quantities
Check your answer
because minimising is always the default whenever an LPP involves two foods — The number of foods or ingredients in a problem has no bearing on whether its objective is maximised or minimised, that depends on what is being optimised, here cost.
✓ $Z$ is the mix’s total cost, and the cheapest one is wanted — (B) $Z=50x+70y$ is the total cost of the mix, and the dietician wants the cheapest combination that still meets the vitamin requirements, hence minimising, not maximising.
because the constraints use $\geq$ instead of $\leq$, so minimisation is always required then — The direction of the constraints’ inequalities does not decide whether an LPP maximises or minimises, that comes from what the objective function represents, here, cost.
because $x$ and $y$ represent costs, not quantities — $x$ and $y$ represent kilograms of Food I and Food II bought, the costs, Rs 50 and Rs 70 per kg, are separate fixed numbers multiplying them, not what $x$ and $y$ themselves represent.
How are the corners $(10,0)$ and $(0,8)$ of the diet problem’s feasible region found?
both are found by solving $2x+y=8$ and $x+2y=10$ simultaneously, the same way as $(2,4)$
both are read directly off the vitamin requirements without using either constraint line
each is where one constraint line meets an axis, satisfying the other already
both are found by setting the objective function equal to zero
Check your answer
both are found by solving $2x+y=8$ and $x+2y=10$ simultaneously, the same way as $(2,4)$ — $(2,4)$ is specifically the point where the two constraint lines cross, $(10,0)$ and $(0,8)$ are each found on just one of the two lines, at an axis, not from solving both together.
both are read directly off the vitamin requirements without using either constraint line — The vitamin requirement numbers, $8$ and $10$, only enter the corner-finding through the constraint lines’ own equations, they are not read off directly on their own.
✓ each is where one constraint line meets an axis, satisfying the other already — (C) $(10, 0)$ is where $x + 2y = 10$ meets the $x$-axis, and $(0, 8)$ is where $2x + y = 8$ meets the $y$-axis. Each already satisfies the other constraint. $(2, 4)$ is different: it needs both lines solved together.
both are found by setting the objective function equal to zero — $Z = 50x + 70y = 0$ only at $(0,0)$, which fails both vitamin constraints and is not even a feasible point here.
In the diet problem, the corner $(2,4)$ gives $Z=380$, while $(10,0)$ gives $500$ and $(0,8)$ gives $560$. The worked solution stops at these three corners and concludes the minimum is $380$. What justifies stopping there?
the open half-plane $50x+70y<380$ has no feasible point, so nothing beats it
any three corners are always enough to conclude a minimum, regardless of the region’s shape
the objective function’s coefficients are both positive, which alone guarantees $(2,4)$ is optimal
the region is bounded, so only the largest corner value needs checking
Check your answer
✓ the open half-plane $50x+70y<380$ has no feasible point, so nothing beats it — (A) The open half-plane $50x + 70y < 380$ has no point in the feasible region, so no feasible point does better than 380.
any three corners are always enough to conclude a minimum, regardless of the region’s shape — The number three has no special status here. What justifies stopping is the open half-plane below the smallest value: it has no point in the region.
the objective function’s coefficients are both positive, which alone guarantees $(2,4)$ is optimal — Positive coefficients alone say nothing about which corner wins. The reason is that the open half-plane $50x + 70y < 380$ has no point in the feasible region.
the region is bounded, so only the largest corner value needs checking — The diet problem’s feasible region is actually unbounded away from the origin, and this is a minimisation problem, its smallest value is the one that needs confirming, not its largest.
In the diet problem’s final answer, what do $x=2$ and $y=4$ mean in context?
the minimum and maximum possible cost
2 kg of Food I and 4 kg of Food II
a total cost of Rs 2 and Rs 4
2 units of vitamin A and 4 units of vitamin C
Check your answer
the minimum and maximum possible cost — $380$ is the single minimum cost found in this problem, $x=2$ and $y=4$ are quantities of food, not two different cost figures at all.
✓ 2 kg of Food I and 4 kg of Food II — (B) $x=2$ and $y=4$ mean 2 kg of Food I and 4 kg of Food II, the quantities the decision variables were defined to represent.
a total cost of Rs 2 and Rs 4 — The total cost is the single number $Z = 380$, $x = 2$ and $y = 4$ are the two foods’ quantities in kilograms, not separate cost figures.
2 units of vitamin A and 4 units of vitamin C — $x$ and $y$ are defined as kilograms of the two foods bought, not the vitamin units those foods happen to supply, which are $8$ and $10$ at minimum, not $2$ and $4$.
Two more things can happen to an LPP. Several corners can tie for the best value, so the optimum is not one point alone. Or no point at all can satisfy every constraint, so there is nothing to optimise.
The thick edge from (3, 1) to (1, 3) gives Z = 4, midpoint (2, 2) included. Corners (3, 0) and (0, 3) give 3.
Change the objective and the tie breaks. 2x + y has one best corner, (3, 1), worth 7.
Worked example
Find a maximum tied along an entire edge
Maximise $Z = x + y$ subject to $x + y \leq 4$, $x \leq 3$, $y \leq 3$, $x \geq 0$, $y \geq 0$ Find the corners, then work out $Z$ at each one.
Corners: $(0, 0)$, $(3, 0)$, $(3, 1)$, $(1, 3)$, $(0, 3)$ The line $x + y = 4$ meets $x = 3$ at $(3, 1)$, and meets $y = 3$ at $(1, 3)$.
$Z = 0$ at $(0, 0)$; $Z = 3$ at $(3, 0)$; $Z = 4$ at $(3, 1)$; $Z = 4$ at $(1, 3)$; $Z = 3$ at $(0, 3)$ Work out $Z$ at every corner.
Both $(3, 1)$ and $(1, 3)$ score $Z = 4$, and so does $(2, 2)$ The level lines of $Z = x + y$ run parallel to the edge $x + y = 4$. So the point $(2, 2)$ on that edge gives $Z = 4$ as well.
*The LPP has MULTIPLE optimal solutions: the whole edge from $(3, 1)$ to $(1, 3)$* The region is bounded, so the corner values decide it. Every point of the edge gives the maximum, 4.
Check: $(3, 1)$: $3 + 1 = 4 \leq 4$, $3 \leq 3$, $1 \leq 3$; $(1, 3)$: $1 + 3 = 4 \leq 4$, $1 \leq 3$, $3 \leq 3$ Both ends of the tied edge satisfy every constraint. The other corners, $(0, 0)$, $(3, 0)$ and $(0, 3)$, pass as well.
Check yourself
In the worked example maximising $Z=x+y$, why do both $(3,1)$ and $(1,3)$ give the maximum value $Z=4$?
because $x\leq 3$ and $y\leq 3$ force the two values to be equal
because $(3,1)$ and $(1,3)$ happen to have the same coordinates in reverse order
because the feasible region has exactly five corners
$Z=x+y$ runs exactly parallel to the edge $x+y=4$ joining those two corners
Check your answer
because $x\leq 3$ and $y\leq 3$ force the two values to be equal — Those two constraints simply cap $x$ and $y$ separately, the actual tie comes from $Z=x+y$ running parallel to the edge $x+y=4$, not from either cap on its own.
because $(3,1)$ and $(1,3)$ happen to have the same coordinates in reverse order — The tie comes from the objective function’s own direction matching the edge between the two points, not from any coincidence in how their coordinates happen to be written.
because the feasible region has exactly five corners — The total number of corners in the region has no bearing on which, if any, pair of adjacent corners ties for the optimum.
✓ $Z=x+y$ runs exactly parallel to the edge $x+y=4$ joining those two corners — (D) $(3,1)$ and $(1,3)$ tie because $Z=x+y$ runs exactly parallel to the edge $x+y=4$ joining them, so every point along that edge scores the same.
The worked example concludes the LPP has MULTIPLE optimal solutions, not one. What exactly counts as ‘the solution’ in this case?
only the single corner with the larger $x$-coordinate, $(3,1)$
the whole edge from $(3,1)$ to $(1,3)$, every point on that segment
the midpoint of the segment, $(2,2)$, alone
only the two endpoint corners, $(3,1)$ and $(1,3)$, and no point between them
Check your answer
only the single corner with the larger $x$-coordinate, $(3,1)$ — $(1,3)$ scores exactly the same $Z=4$ as $(3,1)$, nothing about which corner has the larger $x$-coordinate singles out one over the other.
✓ the whole edge from $(3,1)$ to $(1,3)$, every point on that segment — (B) The solution is the whole edge from $(3,1)$ to $(1,3)$, every point on that segment, including both corners and every point between them.
the midpoint of the segment, $(2,2)$, alone — $(2,2)$ is one optimal point among many along the edge, the solution is the whole edge, not a single representative point standing in for it.
only the two endpoint corners, $(3,1)$ and $(1,3)$, and no point between them — The worked example specifically credits every point between the two corners too, such as $(2,2)$, not just the two named corners themselves.
How would you recognise, before evaluating any corners, that an LPP might have multiple optimal solutions?
check whether the objective function’s coefficients are both positive
check whether all constraints are inequalities rather than equations
check whether the objective’s level line is parallel to an edge
check whether the feasible region has an odd number of corners
Check your answer
check whether the objective function’s coefficients are both positive — The sign of the objective function’s coefficients does not by itself decide whether its level line happens to run parallel to a particular edge.
check whether all constraints are inequalities rather than equations — Whether the constraints are written as inequalities rather than equations has no bearing on whether the objective’s level line runs parallel to an edge.
✓ check whether the objective’s level line is parallel to an edge — (C) Multiple optimal solutions can happen only when the objective’s level line is parallel to one of the region’s edges. If it is parallel to no edge, any optimum is at a single corner.
check whether the feasible region has an odd number of corners — Whether the feasible region has an odd or even number of corners has no bearing on whether the objective function’s level line happens to run parallel to one of its edges.
Shaded: x + y at most 2, and x + y at least 6. The band between fails both limits.
s ≤ 2
s ≥ 6
4
Read the total as one number. No number is both at most 2 and at least 6.
Worked example
Recognise a region with no feasible points
$x + y \leq 2$ together with $x + y \geq 6$, $x \geq 0$, $y \geq 0$ Both constraints are about the same total, $x + y$.
The first restricts $x + y$ to at most $2$; the second requires $x + y$ to be at least $6$ Read what each one allows on its own.
$2 < 6$ leaves no overlap A total cannot be at most 2 and at least 6 at once.
Plotting both confirms it: the two shaded half-planes never touch The picture agrees. The two shaded half-planes have a gap between them.
The feasible region is EMPTY, so the LPP is INFEASIBLE There is no feasible point, so there is no optimal solution to find.
Check: $(1, 1)$ gives $x + y = 2$, and $2 \geq 6$ is false; $(3, 3)$ gives $x + y = 6$, and $6 \leq 2$ is false A point that meets the first constraint fails the second, and the other way round. So the feasible region is empty.
Check yourself
Why do $x+y\leq 2$ and $x+y\geq 6$ together give an INFEASIBLE LPP?
because two constraints can never both involve $x+y$
because $x$ and $y$ cannot both be positive at the same time
because $x+y$ cannot be both at most $2$ and at least $6$
because the non-negativity restrictions rule out every point in this region
Check your answer
because two constraints can never both involve $x+y$ — Many LPPs have several constraints all written in terms of the same combination of variables, there is no general rule against two constraints sharing an expression like $x+y$.
because $x$ and $y$ cannot both be positive at the same time — Both constraints happily allow $x$ and $y$ to be positive, the actual problem is the two incompatible totals required for $x+y$, not the individual signs of $x$ and $y$.
✓ because $x+y$ cannot be both at most $2$ and at least $6$ — (C) The first constraint caps $x+y$ at $2$ while the second requires $x+y$ to be at least $6$, since $2<6$, no value of $x+y$ can satisfy both at once.
because the non-negativity restrictions rule out every point in this region — $x \geq 0$, $y \geq 0$ still allow plenty of points, such as $(1,1)$, the actual conflict is between the two $x+y$ constraints themselves, not the non-negativity restrictions.
How does plotting confirm that $x+y\leq 2$ and $x+y\geq 6$ have no common feasible region?
the two shaded half-planes never touch on the graph
the graph shows a single feasible point at the origin
the two boundary lines turn out to be parallel and coincide exactly
the two half-planes overlap completely, covering the whole plane
Check your answer
✓ the two shaded half-planes never touch on the graph — (A) Plotting shows the half-plane shaded for $x+y\leq 2$ and the half-plane shaded for $x+y\geq 6$ never touch each other on the graph, confirming there is no common feasible region.
the graph shows a single feasible point at the origin — The origin gives $x+y=0$, which fails $x+y\geq 6$, it is not a feasible point for this system at all.
the two boundary lines turn out to be parallel and coincide exactly — $x+y=2$ and $x+y=6$ are parallel but distinct lines, they cross the axes at different points, so they do not coincide with each other.
the two half-planes overlap completely, covering the whole plane — An infeasible system’s shaded regions do the opposite of overlapping completely , here they never touch each other at all.
If an LPP’s feasible region turns out to be empty, what does that mean for the objective function?
the objective function becomes undefined as a formula
there is no feasible point to evaluate it at
the objective function’s minimum is automatically zero
the objective function must be evaluated at the origin instead
Check your answer
the objective function becomes undefined as a formula — $Z = a x + b y$ remains a perfectly well-defined formula whatever the region looks like, what an empty region removes is a feasible point to plug into it, not the formula itself.
✓ there is no feasible point to evaluate it at — (B) An empty feasible region leaves no feasible solution to evaluate the objective function at, so no optimal solution exists either.
the objective function’s minimum is automatically zero — An empty region has no points at all to evaluate the objective function at, so there is no minimum value of any kind for it, not even zero.
the objective function must be evaluated at the origin instead — The origin is only a valid point to evaluate the objective at if it happens to be feasible, with an empty region, it likely is not, and evaluating there proves nothing.
Eight idea cards from vocabulary to ties and empty regions. An arrow means the later card uses the earlier one.
The first page asked a question. A seller has two things to stock and limits on money and space. Far too many mixes fit. How can you find the best one without trying them all?
Here is the answer, in four steps.
Write the DECISION VARIABLES $x$ and $y$, the OBJECTIVE FUNCTION $Z = a x + b y$ and the CONSTRAINTS, with $x \geq 0$ and $y \geq 0$. Each limit is a linear inequality.
Draw the boundary line of each constraint, and test a point to choose the side you shade. The overlap is the FEASIBLE REGION. Its edges are straight, and it has no dents.
Find every CORNER POINT: a point of the region where two boundary lines meet. Work out $Z$ at each one.
If the region is BOUNDED, the largest corner value is the maximum, and the smallest is the minimum. If it is UNBOUNDED, take the largest corner value, $M$. It is the maximum only if $a x + b y > M$ has no point in the region. For the smallest, $m$, test $a x + b y < m$. If two corners tie for the best value, so does the edge between them. If the region is empty, there is no solution.
One wrong sign gives a different triangle, and its best corner costs more money than the dealer has.
Once you have drawn the region, the rest is the same few steps each time. The hard step comes first: turning the words into variables, an objective and constraints. A wrong constraint draws the region of a different problem.
The whole method in one picture: slide the profit line until it last touches the region, at a corner.
What the dealer buys
Back to the dealer. His corners are $(0, 0)$, $(20, 0)$, $(10, 50)$ and $(0, 60)$. His region is bounded. The profit $Z = 250 x + 75 y$ is largest at $(10, 50)$. So he buys 10 tables and 50 chairs, and he earns Rs 6250.
Check yourself
What is the genuinely hard step in solving a two-variable LPP?
listing every corner point of the feasible region
evaluating the objective function at each corner
setting up the variables, objective, and constraints
comparing the computed values to find the largest or smallest
Check your answer
listing every corner point of the feasible region — Listing corners is routine once the region is drawn correctly, not the genuinely hard step.
evaluating the objective function at each corner — Evaluating $Z$ at each corner is straightforward arithmetic once the corners are known, part of the routine work, not the genuinely hard step.
✓ setting up the variables, objective, and constraints — (C) The hard step comes first: turning the words into variables, an objective and constraints. After that, the rest is the same few steps each time.
comparing the computed values to find the largest or smallest — Comparing a short list of already-computed numbers is the easiest part of the whole method, part of the routine work, not the hard step.
Once a two-variable LPP’s feasible region is drawn correctly, the rest of the process is routine. What three steps does that cover?
re-derive the constraints, re-plot the region, and re-check non-negativity
guess the answer, verify it once, and stop
identify the decision variables, name the objective function, and translate the word problem
list every corner, evaluate the objective, compare, check the open half-plane if unbounded
Check your answer
re-derive the constraints, re-plot the region, and re-check non-negativity — The routine part comes after the region is drawn correctly; it does not redo the drawing.
guess the answer, verify it once, and stop — The corner-point method evaluates every corner methodically, nothing about it involves guessing an answer first and only verifying it afterward.
identify the decision variables, name the objective function, and translate the word problem — These are the hard translation steps that come before the routine part. The routine part comes after the translation is done.
✓ list every corner, evaluate the objective, compare, check the open half-plane if unbounded — (D) The routine part covers three steps: list every corner, evaluate the objective function at each one, and compare the values. If the region is unbounded, the open half-plane check comes before calling a value the optimum.
Check yourself: the whole chapter
This chapter’s graphical method only ever draws two axes, $x$ and $y$. Does that mean an LPP itself can only ever have two decision variables?
No. An LPP allows any number of variables; the method here just stops at two.
Yes. The definition of an LPP restricts it to exactly two decision variables.
No, but only when the objective function has degree two or higher than that.
Yes, because a linear expression can only ever be plotted in two dimensions.
Check your answer
✓ No. An LPP allows any number of variables; the method here just stops at two. — (A) An LPP can have any number of decision variables. The graphical method is limited to two only because a two-variable region fits on a flat page.
Yes. The definition of an LPP restricts it to exactly two decision variables. — The definition of an LPP places no cap on the number of decision variables. The graphical method here is limited to two only because a flat page can show two axes.
No, but only when the objective function has degree two or higher than that. — The objective function is always linear in every LPP, no matter how many decision variables it has. Degree is not the issue.
Yes, because a linear expression can only ever be plotted in two dimensions. — Plottability is a limit of the METHOD available, not of what counts as a valid LPP. Problems with three or more variables are still legitimate LPPs.
A point lies inside the feasible region of an LPP. It sits away from every corner and every boundary line. Is this point a feasible solution?
No. Only points on the boundary or at a corner count as feasible solutions.
Yes. Every point in the feasible region is feasible. It need not be a corner.
No. A feasible solution must also be the point where the objective function is optimised.
Only if the point also happens to lie on the axis $x = 0$ or $y = 0$.
Check your answer
No. Only points on the boundary or at a corner count as feasible solutions. — Feasibility has nothing to do with position inside the region. Interior points, boundary points and corners are all feasible solutions equally.
✓ Yes. Every point in the feasible region is feasible. It need not be a corner. — (B) Every point that satisfies all the constraints is a feasible solution , an interior point is feasible exactly as much as a corner or a boundary point.
No. A feasible solution must also be the point where the objective function is optimised. — Feasible and optimal are different questions. Every feasible solution is a candidate; only one, or a tied few, is also optimal.
Only if the point also happens to lie on the axis $x = 0$ or $y = 0$. — Lying on an axis plays no part in the definition. Any point satisfying every constraint is a feasible solution, axis or not.
A student claims the feasible region of an LPP is convex only when it is bounded. An unbounded region, they say, cannot be convex. Is this claim correct?
Yes: an unbounded region always has some dent that breaks its convexity.
Yes, but only when the feasible region also happens to be empty.
No: convexity and boundedness are separate; an unbounded region can be convex too.
No: actually, only unbounded regions are ever convex; a bounded region always has a dent.
Check your answer
Yes: an unbounded region always has some dent that breaks its convexity. — Stretching to infinity does not create a dent. An unbounded feasible region is built from the same convex half-planes as any other, so it stays convex.
Yes, but only when the feasible region also happens to be empty. — Whether the region is empty plays no part here. An empty region has no points to test convexity on, and is a separate case entirely.
✓ No: convexity and boundedness are separate; an unbounded region can be convex too. — (C) Boundedness and convexity are unrelated. Every LPP feasible region is convex, bounded or unbounded, the same intersection-of-half-planes reasoning applies either way.
No: actually, only unbounded regions are ever convex; a bounded region always has a dent. — It is the other way round: convexity has nothing to do with boundedness at all. Bounded and unbounded feasible regions are both always convex.
A student finds a point strictly inside a bounded feasible region, not on any boundary. There, $Z$ looks higher than at every corner. What does Theorem 2 say about this?
It is possible. Interior points can beat every corner. All of them must be checked too.
It is possible if the point is close enough to an edge.
It can happen, provided $Z$ is linear and the region is bounded.
It cannot happen. No interior point does better than the best corner.
Check your answer
It is possible. Interior points can beat every corner. All of them must be checked too. — Interior points never need checking. If $Z$ has an optimal value, Theorem 1 puts it at a corner point, so some corner already achieves it.
It is possible if the point is close enough to an edge. — Being close to an edge does not help. On a bounded region, $Z$ at any point is never more than its largest corner value.
It can happen, provided $Z$ is linear and the region is bounded. — That is exactly the case Theorem 2 covers. In every LPP $Z$ is linear, and on a bounded region its maximum occurs at a corner point, so no point inside beats every corner.
✓ It cannot happen. No interior point does better than the best corner. — (D) Theorem 2: on a bounded region $Z$ has a maximum, and it occurs at a corner point. So no point inside can beat every corner. On an unbounded region an interior point can beat every corner, and then $Z$ has no maximum.
An LPP can have no feasible region at all. Or its feasible region can stretch to infinity, with $Z$ improving forever. A student treats both as the same kind of failure. Are they actually the same situation?
No. INFEASIBLE and UNBOUNDED are two separate types. Each has a different cause.
Yes: both are just called INFEASIBLE, since neither one has a usable answer.
Yes: both are just called UNBOUNDED, since neither one stays inside a fixed region.
No, but only UNBOUNDED can actually happen; an empty feasible region is impossible.
Check your answer
✓ No. INFEASIBLE and UNBOUNDED are two separate types. Each has a different cause. — (A) INFEASIBLE (no feasible region at all) and UNBOUNDED (a region stretching to infinity where $Z$ keeps improving) are separate outcomes among the four, with different causes.
Yes: both are just called INFEASIBLE, since neither one has a usable answer. — INFEASIBLE means the feasible region is empty. UNBOUNDED means the region exists but stretches to infinity where $Z$ keeps improving. Different causes, not one label.
Yes: both are just called UNBOUNDED, since neither one stays inside a fixed region. — UNBOUNDED specifically means the region exists and extends to infinity. An empty region is a separate case, INFEASIBLE, not an instance of unboundedness.
No, but only UNBOUNDED can actually happen; an empty feasible region is impossible. — An empty feasible region is entirely possible, it is one of the four catalogued outcomes, INFEASIBLE, and it happens whenever no point satisfies every constraint at once.
Exercise 12.1 practises the graphical method. You shade the feasible region, find its corner points and work out $Z$ at each one. Some regions are unbounded, some give a tie, and one is empty.
Exercise 12.1: The graphical method
practice Maximise $Z = 2 x + 3 y$ subject to $x + y \leq 4$, $x \geq 0$, $y \geq 0$.
practice Minimise $Z = 5 x + 4 y$ subject to $2 x + y \geq 10$, $x + y \geq 6$, $x \geq 0$, $y \geq 0$.
practice Maximise $Z = x + 2 y$ subject to $x + y \leq 6$, $x \leq 4$, $x \geq 0$, $y \geq 0$.
practice Maximise $Z = 40 x + 30 y$ subject to $2 x + y \leq 40$, $x + 2 y \leq 50$, $x \geq 0$, $y \geq 0$.
practice The region $x + y \geq 5$, $x \leq 6$, $x \geq 0$, $y \geq 0$ is unbounded upward. Find the minimum of $Z = x + 3 y$.
practice Consider the constraints $x + y \leq 3$ and $x + y \geq 8$, together with $x \geq 0$, $y \geq 0$. Does a feasible region exist for this LPP? Justify.
practice For the LPP maximise $Z = 2 x + 2 y$ subject to $x + y \leq 5$, $x \leq 4$, $y \leq 4$, $x \geq 0$, $y \geq 0$, which best describes the solution?
A unique optimal corner
Multiple optimal solutions along an edge
The region is unbounded
The region is infeasible
practice Minimise and maximise $Z = 3 x + 9 y$ subject to $x + 3 y \leq 60$, $x + y \geq 10$, $x \leq y$, $x \geq 0$, $y \geq 0$.
practice Maximise $Z = -x + 2 y$ subject to $x \geq 3$, $x + y \geq 5$, $x + 2 y \geq 6$, $y \geq 0$.
practice The corner points of the feasible region of an LPP are $(0, 0)$, $(5, 0)$, $(3, 4)$ and $(0, 5)$. Let $Z = p x + q y$, where $p, q > 0$. Find the condition on $p$ and $q$ so that the maximum of $Z$ occurs at both $(3, 4)$ and $(0, 5)$.
Answers
$Z = 12$ at $(0, 4)$
$Z = 28$ at $(4, 2)$
$Z = 12$ at $(0, 6)$
$Z = 1000$ at $(10, 20)$
$Z = 5$ at $(5, 0)$
No. The two constraints cannot hold together, since $3 < 8$ leaves no overlap. The feasible region is empty.
(B) Multiple optimal solutions along an edge.
Minimum $Z = 60$ at $(5, 5)$. Maximum $Z = 180$ at every point of the segment joining $(15, 15)$ and $(0, 20)$.
$Z$ has no maximum. The largest corner value, 1 at $(3, 2)$, is beaten by $(3, 3)$, where $Z = 3$.
The applied problems start from words. You turn each one into decision variables, an objective function and constraints, then solve it by the corner-point method. They cover a workshop, a snack mix, a dealer’s stock, a farmer’s fertiliser and two warehouses.
Applied problems
practice A workshop makes wooden lamps and stools. Cutting and assembly together take 1 hour per lamp and 1 hour per stool, with 20 hours available a day. Finishing takes 1 hour per lamp and 2 hours per stool, with 28 hours available a day. Profit is Rs 50 per lamp and Rs 40 per stool. How many of each should be made daily to maximise profit?
practice A shop mixes two snack items to provide at least 12 units of protein and at least 20 units of iron per pack, at minimum cost. Item A gives 3 units of protein and 1 unit of iron per packet, at Rs 20 a packet. Item B gives 1 unit of protein and 3 units of iron per packet, at Rs 15 a packet. How many packets of each minimise the cost?
practice A dealer has Rs 15,000 to invest in two items and shelf space for at most 80 items in total. Type X costs Rs 300 each and profits Rs 40; Type Y costs Rs 150 each and profits Rs 25. How many of each should the dealer stock to maximise profit?
practice A farmer needs at least 10 kg of nitrogen and at least 8 kg of phosphorus for a field, bought from two fertiliser mixes. Mix P supplies 2 kg nitrogen and 1 kg phosphorus per bag, at Rs 250 a bag. Mix Q supplies 1 kg nitrogen and 2 kg phosphorus per bag, at Rs 200 a bag. How many bags of each minimise the cost?
practice A company’s LPP has feasible region defined by $x + y \geq 20$ and $x + y \leq 8$, with $x \geq 0$, $y \geq 0$. What kind of solution does this LPP have?
Unique optimal solution
Multiple optimal solutions
Unbounded solution
Infeasible, no solution
practice A transportation problem: warehouse P stocks 40 units and warehouse Q stocks 30 units. Store A needs 30 units and store B needs 40 units. Shipping one unit costs Rs 4 (P to A), Rs 6 (P to B), Rs 5 (Q to A), Rs 3 (Q to B). If $x$ units go from P to A, then P sends $40-x$ to B, Q sends $30-x$ to A, and Q sends $x$ to B. Find the value of $x$, with $0 \leq x \leq 30$, that minimises the total shipping cost.
Answers
$Z = 1000$ at $x = 20$ lamps, $y = 0$ stools
$Z = 130$ at $x = 2$, $y = 6$ packets
$Z = 2300$ at $x = 20$, $y = 60$
$Z = 1400$ at $x = 4$, $y = 2$ bags
(D) Infeasible, no solution.
$x = 30$ units from P to A; minimum cost Rs 270.
Board paper practice
practice The corner points of the bounded feasible region of an LPP are $(0, 0)$, $(6, 0)$, $(4, 3)$ and $(0, 5)$. The objective function $Z = 3 x + 4 y$ is maximum at ______. (1 mark)
$(0, 0)$
$(6, 0)$
$(4, 3)$
$(0, 5)$
practice Assertion (A). The maximum value of $Z = 3 x + 2 y$, subject to $x + y \leq 4$, $x \geq 0$, $y \geq 0$, is 12, at $(4, 0)$. Reason (R). On a bounded feasible region, a linear objective function takes its maximum value at a corner point. (1 mark)
Both A and R are true and R is the correct explanation of A.
Both A and R are true but R is not the correct explanation of A.
A is true but R is false.
A is false but R is true.
practice A tailor makes shirts and trousers. A shirt needs 2 m of cloth and 3 hours of stitching; a pair of trousers needs 3 m of cloth and 2 hours of stitching. He has at most 60 m of cloth and 72 hours of stitching time. He earns a profit of Rs 150 on a shirt and Rs 200 on a pair of trousers. Formulate the problem as an LPP to maximise his profit. Do not solve it. (2 marks)
practice Solve the following LPP graphically. Maximise $Z = 3 x + 5 y$ subject to $x + y \leq 6$, $x - y \geq -2$, $x \geq 0$, $y \geq 0$. (3 marks)
practice A workshop makes two products, A and B. Each unit of A needs 2 hours of cutting and 1 hour of polishing; each unit of B needs 1 hour of cutting and 2 hours of polishing. There are 16 hours of cutting and 14 hours of polishing a day, and at most 6 units of B can be sold a day. The profit is Rs 300 on a unit of A and Rs 400 on a unit of B. How many units of each should be made a day to maximise the profit? Find the maximum profit. (5 marks)
practice A dealer sells tables and chairs. A table costs him Rs 3000 and a chair Rs 1000. He has Rs 60,000 to spend and room for at most 40 pieces. He makes a profit of Rs 300 on a table and Rs 150 on a chair. Let $x$ be the tables and $y$ the chairs he buys. (i) Write the money and room constraints. (1 mark) (ii) Find the corner points of the feasible region. (1 mark) (iii) Find how many tables and chairs he should buy for the most profit, and that profit. (2 marks)
Answers
(C) $(4, 3)$.
(A) Both A and R are true and R is the correct explanation of A.
Maximise $Z = 150 x + 200 y$ subject to $2 x + 3 y \leq 60$, $3 x + 2 y \leq 72$, $x \geq 0$, $y \geq 0$.
$Z = 26$ at $(2, 4)$.
6 units of A and 4 units of B a day; maximum profit Rs 3400.
(i) $3 x + y \leq 60$, $x + y \leq 40$, $x \geq 0$, $y \geq 0$. (ii) $(0, 0)$, $(20, 0)$, $(10, 30)$, $(0, 40)$. (iii) 10 tables and 30 chairs; profit Rs 7500.
