Learning outcomes
- Plot a feasible region using intercepts and the origin test.
- State and use the Corner-Point (Extreme-Point) Theorem, and sketch its proof.
- Solve LPs by corner enumeration and by the iso-profit line.
- Diagnose the four things an LP can do — unique optimum, multiple optima, unbounded, infeasible — and recognise degeneracy.
- Identify binding constraints and compute slack and surplus.
- Read an objective-coefficient sensitivity range off the graph.
Start here
Picture each constraint as a fence: it rules out everything on one side of itself. What survives all the fences at once is a plot of land, and every point of that plot is a production plan you are allowed to run. There are infinitely many such points, so you cannot test them one by one.
Profit is not a place on the plot; it is a direction across it. Because the objective is linear, there is one fixed bearing labelled more money, and the rate of gain never changes however far you walk. So the search has an obvious strategy: set off along that bearing and keep going until a fence stops you.
Where you come to rest is always a corner post, and it is worth seeing why before the algebra arrives. You cannot stop in the middle of the plot, because from there the profitable direction is still wide open. You cannot stop in the middle of a fence either — sliding along it towards one end still pays, unless profit happens to run exactly parallel to that fence, in which case the end of the fence is just as good and you may as well take the corner. So the answer sits at a corner, an infinite search collapses into a check of a handful of points, and that is the whole trick.
Real problems have ten thousand variables and no picture. The geometry is identical; only the drawing is impossible. That is why the two-variable picture is worth learning properly: it is the mental model you will carry into every method that follows.
1. The feasible region and how to draw it
A warning before anything else, so that you know what you are buying. Drawing an LP works only when there are two variables — a sheet of paper has two axes — so as a practical solver the method is worthless. Its value is that it lets you see a thing you will otherwise only ever compute. The simplex method of L04 solves LPs with any number of variables by pure algebra, and every one of its moves is a move on the picture drawn here: it walks from corner to corner of exactly the shape you are about to shade in.
The set of points satisfying all constraints simultaneously, non-negativity included.
Procedure for plotting.
- Draw each constraint as an equation. Replace the ≤ or ≥ by =, which turns the inequality into a straight line — the exact boundary of what it allows. Two points fix a line, and the quickest two are where it crosses the axes: setting x₂ = 0 in a₁x₁ + a₂x₂ = b gives the point (b/a₁, 0), and setting x₁ = 0 gives (0, b/a₂). These are the intercepts.
- Test the origin to find the correct side. The line splits the plane into two half-planes, and the inequality allows exactly one of them. Substitute (0, 0) into the original inequality: if it comes out true, shade the side the origin is on; if false, shade the other side. If the line passes through the origin the test is useless, so substitute any other convenient point instead.
- Apply non-negativity: x₁, x₂ ≥ 0 are constraints like any other, and together they confine everything to the first quadrant.
- Intersect the shaded half-planes. A plan must satisfy every constraint, not merely some of them, so only the overlap survives: what remains is the feasible region.
The shape you get is never accidental. It always has one property, and that property is the reason linear programming is easy while most optimisation is hard.
A set is convex if, for every pair of points in it, the whole straight segment joining them also lies in it. A disc and a triangle are convex; a crescent and a star are not, because you can pick two points whose connecting segment leaves the shape.
The feasible region of an LP is a convex set — a possibly unbounded polygon, or in general a polyhedron.
Proof sketch. First, a single half-plane a₁x₁ + a₂x₂ ≤ b is convex. Take two points that satisfy it and walk along the segment between them; because the left-hand side is linear, its value along the walk moves steadily from one endpoint value to the other and never overshoots either. Both endpoint values are at most b, so every value in between is at most b, and the whole segment satisfies the constraint. Second, the feasible region is the intersection of finitely many such half-planes. Take two points of the intersection: each half-plane contains both, so by the first part each half-plane contains the whole segment, so the intersection does too. ∎
The figure below is the problem solved in full as Problem 1. Start by reading only the shaded polygon and the four labelled corners; then press play and watch the dashed line — an iso-profit line, the set of all plans earning some fixed profit Z — sweep upwards. The thing to notice is that the line leaves the polygon at a single corner, and that this last point of contact is the answer. The rest of the page is an unpacking of that one observation.
2. The Corner-Point Theorem
Corners have been mentioned loosely; here is what one actually is. The definition is deliberately not "a place where two lines cross", because that description does not survive into higher dimensions — and the theorem below has to.
A point of the feasible region is an extreme point (a corner, a vertex) if it does not lie strictly between any two other points of the region. Equivalently: it cannot be written as λu⃗ + (1 − λ)v⃗ with u⃗ and v⃗ feasible, u⃗ ≠ v⃗ and 0 < λ < 1. A point in the interior fails this at once, and so does a point in the middle of an edge, since its two neighbours along the edge sandwich it. Only the sharp turns of the polygon survive.
If an LP has an optimal solution, then at least one optimal solution occurs at an extreme point of the feasible region.
Read the statement carefully: it says at least one optimum is a corner, not that every optimum is. That wording is doing real work — when a whole edge is optimal, most of the optimal points are not corners, but the two ends of the edge still are, so checking corners never misses the optimal value.
Proof sketch. Argue by contradiction: suppose the optimum x⃗* is not an extreme point. By the definition just given, that means it can be written as a point strictly between two other feasible points:
Apply Z to both sides. Because Z is linear it passes straight through the combination, giving Z(x⃗*) = λZ(u⃗) + (1 − λ)Z(v⃗) — a weighted average of the two endpoint values with strictly positive weights. An average of two different numbers always lies strictly between them, so it is strictly smaller than the larger one. Hence if Z(u⃗) ≠ Z(v⃗), whichever endpoint has the larger value beats Z(x⃗*), and x⃗* was not optimal after all — a contradiction. The only escape is Z(u⃗) = Z(v⃗) = Z(x⃗*).
So Z is constant along the whole segment, and we may walk from x⃗* to either end without losing a rupee of profit. Keep walking in that direction until the region stops you; you are then on the boundary. If that boundary point is still not a corner, it lies on an edge, so repeat the argument within the edge and slide to one of its ends. Each repetition confines you to a lower-dimensional piece of the region — region, then edge, then point — so the process halts, and it halts at an extreme point which is optimal. ∎
The diagram below replays that argument one box at a time. Press next and read the note under each box before moving on; the point to notice is that no step ever mentions how many variables there are, which is why the same proof works in fifty dimensions where no picture exists.
3. Two solution methods
The theorem hands you two different ways to cash in the same fact. They always agree; they differ in what they tell you along the way.
Corner-point enumeration takes the theorem literally. Plot the region; find every corner by solving each pair of constraint equations simultaneously; check that each candidate is actually feasible; evaluate Z at every feasible corner; take the best. It is mechanical, needs no judgement, and is exactly what you would program a computer to do.
The iso-profit (iso-cost) line works the other way round: instead of hunting for the answer, you watch it arrive. Pick any convenient value k and draw the line Z = k, that is c₁x₁ + c₂x₂ = k. Every plan on that line earns exactly k, which is what "iso" means — equal profit. Now raise k. Rearranging c₁x₁ + c₂x₂ = k into x₂ = k/c₂ − (c₁/c₂)x₁ shows that k appears only in the intercept, never in the coefficient of x₁: the slope is fixed at −c₁/c₂ whatever k is. So changing k slides the line parallel to itself, and the last point at which it still touches the region is the optimum, because beyond it no feasible plan earns that much.
Which way is up? The gradient ∇Z = (c₁, c₂) — simply the vector of objective coefficients — is the direction in which Z increases fastest. Push the line along ∇Z to maximise and against it to minimise. For a minimisation this means the first contact as k rises from below is what you want, not the last. Comparing the fixed slope −c₁/c₂ against the slopes of the constraint edges is, as later sections will show, the whole of graphical sensitivity analysis.
The two columns below set the methods side by side. Read across each row rather than down each column: the point to notice is that enumeration is what you use to get the number, while the sliding line is what you use to explain it — including questions enumeration cannot answer, such as how far a price may move before the plan changes.
4. The four special cases, and a fifth
An LP does not always have one tidy answer. Exactly four things can happen, and each announces itself in the drawing before you compute anything. The table pairs each visual signature with the way the same situation shows up later in the simplex tableau.
| Case | Graphical signature | Algebraic signature (L06) |
|---|---|---|
| Unique optimum | iso-profit line touches one corner | all non-basic reduced costs strictly favourable |
| Multiple optima | iso-profit line parallel to an edge | a non-basic variable has zero reduced cost at optimality |
| Unbounded | region open in the improving direction | no positive entry in the pivot column |
| Infeasible | no common shaded region | an artificial variable positive at optimality |
The same four cases are laid out below as a diagram worth returning to. Read the top row first — those are the four pictures you will actually be looking at — then follow each arrow down to see what the algebra will say about the same situation. Notice that the two red cases are the ones with no answer to report.
Multiple optima. A constraint is called binding at a solution when it holds with equality there — the resource is used up exactly, with nothing to spare. (The formal definition, together with slack and surplus, comes in the next section.) Now suppose the iso-profit line happens to have the same slope as one of the binding constraints. Sliding it outwards, it does not touch the region at a point and stop; it comes down flat onto the entire edge at once. Every plan along that edge earns the identical optimal Z, so there is a continuum of optimal solutions, with the two corners at the ends of the edge among them. That is why the theorem said at least one optimum is a corner.
This is good news rather than a defect. The decision-maker gets free choice among equally profitable plans and can settle the choice on grounds the model never captured — ease of scheduling, robustness to a late order, which customer is easier to keep. A solver reports only one of them, so always check for and report alternate optima yourself; the check costs nothing once you know the signature.
In the figure below, the objective coefficients are 4 and 3 and so are the coefficients of the first constraint, which is the extreme version of the same slope. Slide the line and watch what happens at the top of its travel: instead of a single corner lighting up, the whole edge from (1.5, 6) to (5, 1.333) is reached at once.
Unbounded and infeasible are opposite failures, and in practice both are almost always modelling errors rather than genuine answers. An unbounded LP claims you can earn infinite profit, which no real business can, so the model is missing a limit — find the capacity, budget or demand ceiling you forgot to write down. An infeasible LP demands more than the constraints jointly permit; commercial solvers report the Irreducible Infeasible Subsystem, meaning the smallest set of constraints that already conflict, and the fix is to relax one of them.
The two columns below diagnose one example of each. Read the first three items of each column as the story of that example, and the last two as what to do about it. What to notice: the failures happen at opposite ends — one has too much region and no answer, the other has no region to have an answer in.
Degeneracy, the fifth case. This one is not a fifth kind of answer but a fifth kind of geometry, and it can accompany any of the four above. In two dimensions a corner normally needs exactly two constraint lines to pin it down; degeneracy is when three or more lines happen to pass through the same corner, so one of them is redundant there. Algebraically that surplus condition forces one of the variables the simplex method is currently tracking to sit at zero, and the consequence is that simplex can perform a pivot that changes its bookkeeping without moving the point or improving Z. In contrived examples it can even return to a description it has already used and cycle forever; anti-cycling rules exist to prevent exactly this. In practice degeneracy is extremely common in real models and cycling is almost unheard of, so the honest summary is: expect degeneracy, do not fear cycling.
5. Binding constraints, slack and surplus
A constraint is binding at a solution if it holds with equality there: the plan sits exactly on the line, using the resource up to the last unit. For a ≤ constraint the unused amount b − (a₁x₁ + a₂x₂) is called the slack; for a ≥ constraint the amount by which the requirement is overshot, (a₁x₁ + a₂x₂) − b, is called the surplus. Both are non-negative on any feasible plan, and a constraint is binding precisely when its slack or surplus is zero.
Geometrically this is just a restatement of where the answer sits: the optimal corner lies on the lines of its binding constraints and strictly inside every other half-plane. Which constraints are binding is the most useful thing the picture tells a manager, because it identifies what is actually holding the business back. Buying more of a resource that already has slack changes nothing — the idle capacity simply grows. This is the idea behind the shadow price of L07: the amount an extra unit of a resource is worth, which is zero for a non-binding resource and generally positive for a binding one.
6. Solved problems
6x₁ + 4x₂ = 24 has intercepts (4, 0) and (0, 6); x₁ + 2x₂ = 6 has intercepts (6, 0) and (0, 3). At (0, 0), 0 ≤ 24 ✓ and 0 ≤ 6 ✓, so shade towards the origin.
The region is bounded by four lines — the two constraints and the two axes — so its corners are where consecutive pairs of them meet. Take them in turn.
A is where the two axes meet: the origin, (0, 0).
B is on the x₂-axis, so x₁ = 0. How far up may we go? Putting x₁ = 0 into constraint 2 leaves 2x₂ ≤ 6, that is x₂ ≤ 3; putting it into constraint 1 leaves 4x₂ ≤ 24, that is x₂ ≤ 6. Both ceilings apply at once, so the lower one is the real one: B = (0, 3). Confirm with the constraint that did not produce it — 6(0) + 4(3) = 12 ≤ 24 ✓.
D is on the x₁-axis, so x₂ = 0. Constraint 1 leaves 6x₁ ≤ 24, that is x₁ ≤ 4; constraint 2 leaves x₁ ≤ 6. Again the lower ceiling wins: D = (4, 0). Confirm with constraint 2 — 4 + 2(0) = 4 ≤ 6 ✓.
C is where the two constraint lines cross, so solve them simultaneously. The x₂ coefficients are 4 and 2, so doubling the second equation makes them match and lets us eliminate x₂ by subtraction:
C is produced by both constraints at once, so there is no third one left to check here — but in a problem with more constraints there would be, and it would have to be checked.
| Corner | (x₁, x₂) | Z = 5x₁ + 4x₂ |
|---|---|---|
| A | (0, 0) | 0 |
| B | (0, 3) | 12 |
| C | (3, 1.5) | 21 |
| D | (4, 0) | 20 |
Both resources are fully used, so there is no idle capacity to report. Two binding constraints and two variables: the count matches, so this is a non-degenerate optimum at a genuine single corner. That is what you would expect, since the winning corner was the one where both lines cross.
Enumeration has given the answer; the sliding line explains it. Use the same rearrangement as before, now on any line: a₁x₁ + a₂x₂ = b becomes x₂ = b/a₂ − (a₁/a₂)x₁, so its slope is −a₁/a₂. That gives −6/4 = −1.5 for the first constraint, −1/2 = −0.5 for the second, and −5/4 = −1.25 for the iso-profit line.
Why does lying strictly between the two settle it? Picture the profit line pressed against corner C, with one edge running away on each side. Because the profit line is flatter than the steep edge, sliding along that edge loses money; because it is steeper than the flat edge, sliding along that one loses money too. Both directions are downhill, so C is the last point of contact and the optimum is unique. Had the profit slope equalled one of the edge slopes, that edge would have been flat in profit terms and the whole edge optimal — the multiple-optima case. This comparison is exactly the machinery reused in Problem 5.
x₁ + x₂ = 8 has intercepts (8, 0) and (0, 8); 3x₁ + 5x₂ = 30 has intercepts (10, 0) and (0, 6). At (0, 0), 0 ≥ 8 is false, so shade away from the origin; the upper bounds close the region into a pentagon.
On the x₂-axis (x₁ = 0). The first constraint becomes x₂ ≥ 8 and the second becomes 5x₂ ≥ 30, that is x₂ ≥ 6. Both must hold, so the larger floor wins here — the opposite of Problem 1, because these are lower bounds rather than upper ones. So x₂ ≥ 8, and with the ceiling x₂ ≤ 10 the axis contributes the two corners (0, 8) and (0, 10).
Where the two ≥ lines cross. From x₁ + x₂ = 8 we get x₁ = 8 − x₂; substituting into 3x₁ + 5x₂ = 30 gives 3(8 − x₂) + 5x₂ = 24 − 3x₂ + 5x₂ = 24 + 2x₂ = 30, so x₂ = 3 and x₁ = 5. Check this candidate against the constraints that did not produce it: 5 ≤ 10 ✓ and 3 ≤ 10 ✓, so (5, 3) is a genuine corner.
On the boundary x₁ = 10. Here both ≥ constraints are satisfied automatically for any x₂ ≥ 0: the first gives 10 + x₂ ≥ 8, true even at x₂ = 0, and the second gives 30 + 5x₂ ≥ 30, likewise. So this edge runs the full height of the box and contributes (10, 0) and (10, 10). Five corners in all.
| Corner | Z = 3x₁ + 2x₂ |
|---|---|
| (0, 8) | 16 |
| (0, 10) | 20 |
| (5, 3) | 21 |
| (10, 0) | 30 |
| (10, 10) | 50 |
So the first requirement is met exactly and the second is overshot by 10 units for free. Nothing was paid to exceed it; it simply came along with meeting the first.
Why the optimum sits on an axis rather than at the crossing. Compare the two variables on the constraint that actually binds, x₁ + x₂ ≥ 8. Each unit of either variable contributes the same 1 towards it — but a unit of x₂ costs 2 while a unit of x₁ costs 3. So x₂ buys the same progress more cheaply, and there is no reason to use any x₁ at all: the cheapest way to reach 8 is 8 units of x₂, at a cost of 16. The other constraint then looks after itself. Whenever one variable is at least as good on every binding constraint and strictly cheaper, expect the optimum to sit on an axis.
Two figures for that problem. In the first, slide the iso-cost line up from Z = 0 and note which corner it reaches first — for a minimisation the first contact wins, not the last, because you are trying to spend as little as possible. Watch it pass (0, 8) at Z = 16 well before it reaches the intersection (5, 3) at Z = 21.
The second figure turns the surplus calculation of Step 4 into a picture. Each pair of bars is one constraint: the dark bar is what the plan (0, 8) actually delivers, the gold bar is what the constraint demands. Look for the gap between them — where there is none the constraint is binding, and where there is one that gap is the surplus.
Look at the objective and the first constraint side by side: 4x₁ + 3x₂ appears in both. So the quantity being maximised is the quantity being capped at 24. That immediately gives Z ≤ 24 for every feasible plan, and Z = 24 for every feasible plan that sits on the line 4x₁ + 3x₂ = 24. There is no need to guess whether ties will occur — the structure guarantees them.
| Corner | How obtained | Z |
|---|---|---|
| (0, 0) | origin | 0 |
| (0, 6) | x₁ = 0, x₂ = 6 | 18 |
| (1.5, 6) | x₂ = 6 ∩ 4x₁ + 18 = 24 | 24 |
| (5, 1.333) | x₁ = 5 ∩ 20 + 3x₂ = 24 | 24 |
| (5, 0) | x₂ = 0, x₁ = 5 | 20 |
Two corners tie at Z = 24, and that is enough to force infinitely many more. The reasoning uses both facts established earlier. The region is convex, so the entire segment joining the two tied corners is feasible. Z is linear, so at any point of that segment Z is the weighted average of the two endpoint values — and the average of 24 and 24 is 24. Every point on the segment is therefore feasible and scores 24, so every point on it is optimal.
Write the segment down explicitly. Sweeping λ from 0 to 1 walks from (5, 4/3) across to (1.5, 6):
Test the claim at the midpoint λ = 0.5: x₁ = 5 − 1.75 = 3.25 and x₂ = 4/3 + 7/3 = 11/3 ≈ 3.667. Check both the objective and every constraint:
A feasible plan, neither of the two corners, earning exactly the optimal profit.
All of this could have been predicted from slopes alone. The iso-profit line 4x₁ + 3x₂ = k has slope −4/3 for every k, and constraint 1 has slope −4/3 as well. The profit line is therefore parallel to a binding edge, and a line sliding parallel to an edge does not meet it at a point — it lands flat along its whole length. Parallel to a binding constraint ⟹ contact along an entire edge ⟹ infinitely many optima. This is the only signature you need to look for.
To show a problem is unbounded you do not need the whole picture — you need one escape route: a single direction along which you can travel forever, staying feasible, with Z rising the whole way. Choosing it is guided by the constraints themselves. The awkward one is x₁ − x₂ ≤ 2, which limits how far x₁ may run ahead of x₂; so if the two variables grow together the difference never changes and that constraint can never be violated. That suggests the ray x₁ = t, x₂ = t. Test it:
Both hold for all t ≥ 2, so the whole ray is feasible, and along it
No plan is best, because whatever plan you name, doubling t beats it. Graphically the region extends forever to the upper right and the objective improves in exactly that direction — the two conditions that must coincide. Note that the same region is perfectly well behaved for a minimisation: it is the pairing of the open direction with the improving direction that breaks the problem. In practice this is a report about the model, not about the numbers: some real capacity limit was left out.
Here no search is needed at all, because the two constraints speak about the same quantity x₁ + x₂ and disagree about it. The second demands that it be at least 8; the first demands that it be at most 3. Chaining them:
Since 8 ≤ 3 is false, no pair (x₁, x₂) whatsoever can satisfy both, and the feasible region is empty. Graphically the two shaded half-planes lie on opposite sides of a gap and never overlap, so there is nothing to slide a profit line across; the objective is never evaluated at all. The requirements are over-constrained and one of them must be relaxed.
Neither case needs a drawing to be caught, which matters because real problems have no drawing. In the language of L04 and L06 — vocabulary you meet there, not here — unbounded shows up as an entering column with no positive entry, so the ratio test has nothing to choose and cannot stop the variable growing; infeasible shows up as an artificial variable still positive at optimality, meaning the algorithm never managed to satisfy every constraint at once. The visual diagnosis and the algebraic one are the same fact seen twice.
The axis corners come from the intercepts: (0, 22.5) from 4x₂ = 90 on finishing, and (24, 0) from 5x₁ = 120 on carpentry. Each survives the other constraint — 3(22.5) = 67.5 ≤ 120 ✓ and 2(24) = 48 ≤ 90 ✓ — so both are genuine. For the interior corner, solve the two constraint lines together. From 2x₁ + 4x₂ = 90, divide by 2 to get x₁ + 2x₂ = 45, so x₁ = 45 − 2x₂; substituting into carpentry, 5(45 − 2x₂) + 3x₂ = 225 − 10x₂ + 3x₂ = 225 − 7x₂ = 120, which gives 7x₂ = 105, so x₂ = 15 and x₁ = 45 − 30 = 15.
| Corner | (x₁, x₂) | Z |
|---|---|---|
| origin | (0, 0) | 0 |
| finishing binding | (0, 22.5) | 6,750 |
| both binding | (15, 15) | 11,250 |
| carpentry binding | (24, 0) | 10,800 |
Now ask a different question: suppose the profit per table were not ₹450 but something else. At what point would the firm want to build a different mix? Changing c₁ does not move a single constraint, so the polygon and its four corners are untouched; all that changes is the slope of the iso-profit line, which is −c₁/c₂ = −c₁/300. And by the argument of Problem 1, the corner (15, 15) is the last point of contact precisely while that slope sits between the slopes of the two edges meeting there — steeper than one, flatter than the other, so that both directions away from the corner are downhill. Tilt the line past either edge and that edge stops being downhill, so the winner slides to the corner at its far end.
So table profit may fall as low as ₹150 or rise as high as ₹500 and the firm should still make 15 tables and 15 chairs. Note carefully what does and does not stay fixed: the plan is unchanged across the range, while the profit Z changes with every rupee of c₁. The range also assumes c₂ stays at ₹300; it is a statement about one coefficient moving alone.
A range is only trustworthy if its endpoints behave as the theory predicts. At each endpoint the objective slope should exactly equal an edge slope, which is the multiple-optima signature — so the current corner should tie with its neighbour along that edge rather than simply lose. Check both.
At c₁ = 500 the slope is −500/300 = −5/3 ≈ −1.667, exactly the carpentry slope. Predicted consequence: a tie along the carpentry edge, which runs from (15, 15) to (24, 0).
At c₁ = 150 the slope is −150/300 = −0.5, exactly the finishing slope. Predicted consequence: a tie along the finishing edge, from (0, 22.5) to (15, 15).
Both endpoints tie, so the range is exactly right: inside it (15, 15) wins outright, at the ends it shares, and outside it the winner changes hands — above ₹500 to (24, 0), where tables are lucrative enough to abandon chairs, and below ₹150 to (0, 22.5), where they are not worth making at all. A recommendation that survives that much movement in an estimated price is what is meant by calling a plan robust, and it is far more useful to management than the single number ₹11,250.
This last figure lets you test that range yourself, and it is the one to spend time on. Drag the slider to change c₁ while c₂ stays at 300, and watch two things: the profit line tilting, and the highlighted corner. Start at 450 and move down — the corner should stay put all the way to 150, announce a tie exactly there, and only then jump to (0, 22.5). Do the same upwards and you should find the tie at 500 and a jump to (24, 0). Seeing the corner refuse to move over such a wide range is the whole point of sensitivity analysis.
7. Where this is used
Product mix
Two lines competing for machine hours and labour: the picture says what to build and which department to expand — the binding one.
Blending and diet
Feed, fuel and alloy blends are minimisations with ≥ constraints; surplus shows which specification is met for free.
Debugging large models
When a fifty-variable LP returns unbounded or infeasible, the analyst reaches for the two-variable picture: the causes are identical at any size.
Pricing and negotiation
A range such as 150 ≤ c₁ ≤ 500 is what a sales manager needs before agreeing a discount.
8. Common mistakes
9. Practice problems
- max 3x₁ + 2x₂ s.t. x₁ + x₂ ≤ 4, x₁ + 3x₂ ≤ 6, x₁ ≤ 3. [Ans: (3, 1), Z = 11]
- min 2x₁ + 3x₂ s.t. x₁ + x₂ ≥ 6, 2x₁ + x₂ ≥ 8, x₁, x₂ ≥ 0. [Ans: (6, 0), Z = 12; the corner (2, 4) gives 16 — check all corners]
- Show that max 2x₁ + 2x₂ s.t. x₁ + x₂ ≤ 5 has multiple optima, and describe them.
- Diagnose: max x₁ s.t. x₁ − x₂ ≤ 1, x₁, x₂ ≥ 0. [Ans: unbounded]
- Diagnose the constraint set x₁ ≥ 5, x₁ ≤ 3. [Ans: infeasible]
- For problem 1 above, find the range of c₁ keeping the optimum unchanged.
- Explain why an LP optimum can never occur strictly inside the feasible region, unless the objective is constant.
10. Summary
Given any two-variable linear programme, you can now do the following without help.
- Draw its feasible region. Plot each constraint as a line through its two intercepts, pick the correct side with the origin test, keep to the first quadrant, and take the overlap. You can also say what the resulting shape always is — a convex polyhedron — and why that matters: convexity is what makes a local optimum global, and it is what non-linear problems give up.
- Justify checking only the corners. You can state the Corner-Point Theorem and reproduce its proof: a non-extreme optimum sits between two feasible points, linearity makes its value an average of theirs, and an average is beaten by the larger unless the two are equal — so you can always slide to a corner without losing anything.
- Solve it two ways and know when to use each. Corner enumeration to get the number, verifying every candidate against all constraints before scoring it; the iso-profit line, slid parallel along ∇Z, to explain why that corner won and to answer questions enumeration cannot.
- Recognise which of the four outcomes you have, from the drawing alone. One corner touched means a unique optimum; a line landing flat on an edge means multiple optima, which you should report rather than hide, since they hand the decision-maker a free choice; a region open in the improving direction means unbounded, so go and find the capacity limit you omitted; no overlap at all means infeasible, so relax one of the conflicting requirements. You can also spot degeneracy — three or more lines through one corner — and say why it worries algorithm designers more than practitioners.
- Read the resource story off the answer. Compute slack and surplus, name the binding constraints as the ones actually limiting the business, and use the count of them — equal to the number of variables at a non-degenerate optimum — as a check that the answer is the kind of answer you think it is.
- Produce a sensitivity range and interpret it honestly. The optimal corner survives while the objective slope −c₁/c₂ stays between the slopes of the binding edges, which gave 150 ≤ c₁ ≤ 500 for the furniture problem, confirmed by the ties at Z = 12,000 and Z = 6,750 at the two endpoints. You can also say what the range does not claim: it fixes the plan, not the profit, and only while the other coefficient holds still.
All of this is geometry that survives losing the picture. In L04 the same corners become algebra, and the sliding line becomes a rule for choosing which corner to visit next.