Linear Programming: Optimising Under Linear Constraints

Linear programming is optimisation where every rule is a straight line and doubling the plan doubles both what it uses and what it brings in. The straight line shape pays off once: on a closed region like this one, a best answer can always be found at a corner, so infinitely many allowed plans collapse into a short list that can be checked by hand. The Amaltas workshop's list runs to five entries.

Three things settled elsewhere are taken as given. The Amaltas workshop is an invented workshop that makes two things and nothing else, the plain crate and the lined crate, and its three daily limits are already written down. ContributionWhat one crate leaves behind after the materials that grow with it are paid for, counted before any of the day's standing costs. is already defined as the money one crate leaves behind. And which rules a best plan is pressed against, rather than merely obeying, is already settled. Enumeration does the rest: every corner is found by hand, every rejected crossing is named with the rule it breaks, and the winner is picked by comparing all of them rather than by pointing at a picture.

What makes a problem linear?

Linear is not a description of how simple the rules look; it is a test run on the arithmetic. Take any plan, double it, and ask three questions. Does it use twice the material? Does it take twice the time? Does it bring in twice the money? If the answer is yes to all three, and yes again for tripling and for halving, the problem is linear. If any answer is no, it is not, however tidy the rules read on paper.

Run the test on the Amaltas workshop. Take a modest day: three plain crates and two lined crates. The day uses three boards for the plain crates and four for the lined, seven boards in all. The day takes six bench hoursOne hour on one work bench. Three benches at eight hours apiece would come to twenty four, but two go every day on getting set up, leaving twenty two. for the plain crates and two for the lined, eight hours in all. The day brings in Rs 900/- from the plain crates and Rs 900/- from the lined, Rs 1,800/- in all. Doubling the day to six plain and four lined gives fourteen boards, sixteen bench hours, Rs 3,600/-. Every one of the three has exactly doubled, and none of them doubled because anybody arranged it. Each of the three doubled because a board per plain crate is a board per plain crate whether one crate is made or a hundred.

Proportional scaling is familiar from ordinary life. A tea stall that uses one measure of leaves and one of milk per cup uses ten measures of each for ten cups and a hundred for a hundred. Nothing about the tenth cup is cheaper than the first. Two things break that, and both are ordinary enough to catch a careful person out. The first is a rate that changes with size: a price breakA lower rate a supplier gives once an order goes above some quantity. Below that quantity the higher rate applies to every unit. from a supplier, a bulk sack of rice that costs less per kilo than a small one, a caterer whose per plate charge falls once a wedding passes two hundred guests. Doubling the order does not double the bill. The second is a rule where two decisions multiply each other rather than adding: a drying rack whose capacity depends on the plain count times the lined count, say. Neither is present at the Amaltas workshop, and that absence is the whole reason a corner can be promised here.

One honest caveat matters later. The doubling test applies to what a plan uses and what it brings in, not to what is left at the end of the day. The Amaltas workshop pays Rs 4,300/- a day in costs that do not moveThe money the day costs whatever gets made: the rent, the wages and the standing board order, none of which changes with the plan., and Rs 4,300/- stays Rs 4,300/- when the plan doubles. Fixed costs are exactly why the quantity being made as large as possible is contribution rather than what survives to the end of the day. Which quantity belongs in that role is covered separately.

What does the whole problem look like written out?

Written out in full, the Amaltas workshop's problem comes to one goal and four limits, and that is the entire document. The goal: push Rs 300/- for each plain crate plus Rs 450/- for each lined crate as high as it will go. The first limit: one board per plain crate and two per lined, never past twenty in a day. The second: two hours per plain crate and one per lined, never past twenty two. The third: one roll of clothA roll of lining cloth. A lined crate takes exactly one and a plain crate takes none at all. per lined crate and none for a plain one, never past eight. The fourth: neither count may go below zero.

The goal and the four limits are the entire problem. There is nothing else. A reader who has only ever met optimisation as something a computer does may find the smallness of it surprising, and the smallness is the point: everything a solver will ever know about the Amaltas workshop is in those four lines, and anything left out of them is invisible to the answer.

Every number in those lines was written down by a person, and each one came from a source that can be checked. The twenty boards is a standing orderA fixed quantity a supplier sends every day without being asked again each morning. with a supplier. The twenty two bench hours is what three benches leave once setting up is paid for: eight hours apiece makes twenty four, and two hours of every day go on getting ready. The eight rolls is what the cloth supplier sends. The Rs 300/- and the Rs 450/- are what each kind of crate leaves behind. None of these is a fact about the world; all of them are choices, and each one is a place where the answer can be quietly wrong because the input was quietly wrong. Reading the four lines and asking who wrote each number is the single most useful thing to do with somebody else's linear programme before looking at its answer.

Why can the best answer always be found at a corner?

Here is the result that makes linear programming worth its own name, and it can be understood without a line of algebra. Because the objective is a straight line relationship, its value slides steadily in one direction across the region of allowed plans, and it never turns back on itself. Walk in any straight line across the region and the contribution changes at a constant rate along the way. Contribution cannot rise, level off and rise again. The climb cannot have a bump in the middle.

Now picture the objective as a whole set of parallel lines laid across the region, each line joining every plan worth the same amount. One line joins everything worth Rs 1,500/-, another everything worth Rs 3,000/-, another Rs 4,500/-. The lines are parallel. Their tilt depends only on the two contribution figures, and those two figures are not changing. Push the set of lines steadily in the improving direction. Each one crosses less of the region than the last. Eventually one of them is the last to touch the region at all, and everything beyond it is out of bounds. The last line of contact is the answer, and unless it happens to lie flat along an edge, it touches at exactly one point: a corner.

The practical payoff is enormous and easy to underrate. The region holds infinitely many allowed plans once fractions of a crate are permitted, and eighty four once every count must be a whole crateA crate is either finished or it is not, so a plan calling for half a crate cannot be delivered at the end of the day.. Either way that is far too many to check one by one. The corner result says none of that is necessary. Testing the corners, all of them, settles it. At the Amaltas workshop that means testing five plans instead of eighty four, and being certain rather than hopeful at the end of it.

Two honest qualifications belong here. The first is that this argument assumes the region is closed and has corners at all. Closed with corners holds at the Amaltas workshop and does not hold everywhere; regions that hold nothing, or that run away without limit, are covered separately. The second is that the best corner at the Amaltas workshop happens to call for eight whole plain crates and six whole lined crates. Whole crates are convenient and are not something the method arranges. A corner can easily land on three and a half crates, and then whole crates become a separate problem.

How are the corners actually found?

Finding the corners is the step most explanations skip, and skipping it is what leaves a reader able to nod at the corner result but unable to use it. A corner is not something spotted on a drawing; it is something computed, and a drawing is how the computation is checked afterwards.

Five straight lines bound the region of allowed plans at the Amaltas workshop. The board line, where boards used come to exactly twenty. The bench hours line, where hours used come to exactly twenty two. The cloth line, where lined crates come to exactly eight. And the two zero lines, one where plain crates are zero and one where lined crates are zero. A corner is nothing more than a place where two of those five lines meet, so the procedure writes itself. Pick two lines. Work out the single point they share. Then put that point back through the whole list of rules and see whether it survives.

Five lines make ten pairs, and the ten can be counted off directly: the board line against each of the other four, the bench hours line against each of the remaining three, the cloth line against the remaining two, and the last two against each other. Four plus three plus two plus one is ten. Each pair is two equations in two unknowns, a minute's work on paper. Two lines can meet somewhere the workshop is not permitted to go, so finding the meeting point is only half the job. The second half is three additions per point, one each for the boards, the hours and the cloth. Ten pairs worked, ten points tested, and there is nothing left over to guess at.

One pair, worked all the way through

Descriptions of a method are easy to nod along to, so here is one pair done longhand, with nothing skipped. Take the board line and the bench hours line. The board line collects every plan whose board count lands on exactly twenty, one board going to each plain crate and two to each lined one. The bench hours line does the same thing at exactly twenty two hours, two hours to a plain crate and one to a lined one. Two equations, two unknowns, and school arithmetic from here.

Eight plain and six lined is a corner, found without a drawing anywhere near it. The same five steps run on a pair that does not survive show the difference, and that difference is the whole lesson of this section. Take the bench hours line and the cloth line. The cloth line gives the lined crates straight away at eight. Put into the bench hours line, twice the plain crates plus eight comes to twenty two, so the plain crates are seven. Steps one to four were every bit as sound as before, and seven plain with eight lined is a real point sitting at a real crossing of two real lines.

Step five kills it. Seven plain crates take seven boards and eight lined crates take sixteen. The total is twenty three boards against the twenty that arrive. The only thing separating a corner from a discarded crossing is that last step, and it is the step that costs three additions to run and the whole answer to skip. A reader who does the ten pairs on paper will feel this: the solving is pleasant and rhythmic, the testing is dull, and the testing is what does the work.

Which candidate crossings fail, and why does each one fail?

Each failure has a different shape, so the five pairs that give no corner are more instructive than the five that do. Four pairs cross at a perfectly real point that breaks a named rule, and one pair does not cross at all.

Take them in order. The board line meets the line of no plain crates at zero plain and ten lined. Two lines, one crossing, nothing wrong with the arithmetic. The crossing fails on cloth: ten lined crates need ten rolls and eight arrive. The board line meets the line of no lined crates at twenty plain and zero lined. Twenty plain crates fail on bench hours, and not narrowly: forty hours are needed against twenty two available. Where the bench hours line runs into the cloth line the crossing is seven plain and eight lined, and it fails on boards at twenty three against twenty. And the bench hours line reaches the line of no plain crates at twenty two lined crates. Twenty two lined crates fail on boards at forty four against twenty and on cloth at twenty two against eight, breaking two rules at once.

The last pair is different in kind. The cloth line says lined crates equal eight. The zero line says lined crates equal zero. Both are horizontal lines at different heights, so they are parallel and there is no crossing to test. A pair of parallel rules produces no candidate at all. Parallel rules are the one case where the arithmetic gives nothing rather than something to reject. Anyone working the ten pairs by hand and expecting ten answers would suspect a mistake at exactly this point.

How is the winner chosen from the five that survive?

By putting all five side by side, and by nothing else at all. Five multiplications and a single comparison take about a minute, so no shortcut remains at this stage and none is wanted. Attach Rs 300/- to each plain crate and Rs 450/- to each lined one, work out what every survivor comes to, and lay the results out in a row.

Eight plain crates and six lined crates, worth Rs 5,100/- a day, is the best allowed plan at the Amaltas workshop. Nothing is level with it, and the row of five figures above is the entire proof; no part of it rests on somebody drawing a shape and pointing at a promising looking spot. The winner's own row: eight plain crates take eight boards and six lined take twelve, twenty in all against twenty. Eight plain take sixteen bench hours and six lined take six, twenty two against twenty two. Six lined crates take six rolls of the eight that arrive.

The runner up is four plain and eight lined at Rs 4,800/-, so the winning margin is Rs 300/- a day. The margin happens to be the same number as a plain crate's contribution, and the two have nothing to do with each other: the gap is four extra plain crates less two lined ones, Rs 1,200/- against Rs 900/-, and it coming out at Rs 300/- is arithmetic rather than meaning. Watch for that kind of coincidence in any set of figures. Two numbers matching is not a relationship.

A comparison run over five corners leans on the very corner result it is supposed to support, so the winner was checked a second time by main force. Every plan on a fine mesh laid over the whole region, stepping an eighth of a crate at a time, was priced: four thousand five hundred and twenty nine of them, and not one came to more than Rs 5,100/-. The elegant argument and the stubborn one land in the same place. Agreement between two methods that share no reasoning is the only kind worth anything.

What happens to the answer when the objective is tilted?

Leave the plain crate where it is, at Rs 300/-, and turn the figure attached to a lined crate up and down instead. Nothing about the three daily limits changes, so the region keeps its shape and its five corners stay exactly where they were. All that changes is the tilt of the objective line sliding across them. The striking thing, and the least intuitive consequence of linearity, is that the answer does not drift as the dial turns: it sits completely still and then jumps from one corner to another in a single step.

There are two such jumps. Below Rs 150/- a lined crate, lined crates are simply not worth the two boards they eat, so the best plan is eleven plain crates and no lined ones at Rs 3,300/-. Between Rs 150/- and Rs 600/- the best plan is eight plain and six lined, and it stays there for that whole stretch without moving a single crate. Above Rs 600/- the best plan is four plain and eight lined. The Amaltas workshop's own Rs 450/- sits comfortably inside the middle stretch. The answer at Rs 400/- and at Rs 500/- is exactly the same plan as at Rs 450/-.

At the two switch points themselves, two corners are worth exactly the same and there is no single answer at all. At exactly Rs 150/-, eleven plain and no lined comes to Rs 3,300/- and eight plain and six lined comes to Rs 2,400/- plus six times Rs 150/-. Both come to Rs 3,300/-. At exactly Rs 600/-, eight plain and six lined comes to Rs 6,000/- and four plain and eight lined comes to Rs 1,200/- plus eight times Rs 600/-. Both come to Rs 6,000/-. When two corners tie, every plan along the whole edge between them is worth the same as well, so the honest report at those two settings is that an entire edge wins. A solver will print one plan and say nothing about the other. The silence is the solver's, not the mathematics'.

How is a linear programming answer checked by hand?

Linear programming answers arrive from elsewhere. A supplier sends a schedule, an analyst hands over a production plan, a spreadsheet somebody built two years ago prints a recommended split. On a problem with two decisions, the complete check takes about five minutes and settles the question rather than softening it. There are four steps and none of them needs a computer.

First, the answer is confirmed to be allowed at all: the plan runs through every rule, one at a time, including the ones that look obviously satisfied. Second, what it actually consumes is added up and set beside what arrives. Third, the rules used to the last unit are separated from those with something spare. The split is what shows what is holding the plan back. Fourth, and this is the step people skip, the neighbouring corners are found and priced. If the answer really is the best corner, it beats both of its neighbours; if it does not, the fault has been found without any need to know how the answer was produced.

Run all four on the Amaltas workshop's answer of eight plain and six lined. Every rule holds. The plan draws twenty boards from a delivery of twenty, twenty two bench hours from the twenty two available, and six rolls from eight. Boards and bench hours are used to the last unit and two rolls of cloth sit idle. Its two neighbours along the edges of the region are eleven plain and no lined at Rs 3,300/-, and four plain and eight lined at Rs 4,800/-, and Rs 5,100/- beats both. Five minutes, no software, and a conclusion that can be defended to whoever handed the plan over. Where only two things are being decided, the list of candidates is short enough to work through on the back of the delivery note, so accepting the answer on faith is a choice rather than a necessity.