Optimisation and the linearity that makes this class tractable, and how a stated situation becomes decision variables, constraints and an objective

0:00A dealer sells tables and chairs, and nothing else. He has fifty thousand rupees to spend. His shop has room on the shelf for sixty pieces of furniture, counting tables and chairs together. A table costs him two thousand five hundred rupees to buy, and a chair costs him five hundred. When he sells them again he makes two hundred and fifty rupees on a table and seventy five on a chair.

0:30How many of each should he buy? That is the whole question, and the six numbers in it are the only numbers there will ever be. One capital, one shelf, two prices, two profits. Every single thing that appears later has to come from one of those six, and anything that does not is a mistake. The paragraph also ends with an assumption, quietly: that everything he buys, he sells. It is doing real work. Without it the profit on a table would not be a number you could multiply by, and nothing that follows would get off the ground.

1:11Before any of the machinery, guess. Plan one: spend it all on tables. Fifty thousand divided by two thousand five hundred is twenty tables. They fit easily — twenty pieces on a shelf that holds sixty, so forty spaces sit empty. Twenty tables at two hundred and fifty rupees each is five thousand rupees of profit. Plan two: spend it all on chairs. The money would run to a hundred chairs, but the shelf stops him at sixty, and that leaves twenty thousand rupees unspent. Sixty chairs at seventy five is four thousand five hundred.

1:54Plan three, a mixture: ten tables and fifty chairs. That is exactly sixty pieces and exactly fifty thousand rupees — nothing left over on either side. And the profit is six thousand two hundred and fifty. So the mixture beats all tables by one thousand two hundred and fifty, and beats all chairs by one thousand seven hundred and fifty. Which settles one thing immediately: the answer is not at either end. You cannot get it by picking the more profitable item and buying as many as you can.

2:33Three guesses do not tell you the best plan. They tell you that guessing is not going to finish the job. Step back and name what kind of question this is, because the naming is two steps and almost everyone takes only the second. Any question that asks for the largest or the smallest value of something, under stated limits, is an optimisation problem. That is a very large family. The cheapest route, the strongest bridge for a fixed weight of steel, the fastest schedule — all optimisation.

3:12Inside that family sits a much smaller one, and it is the only one this topic can settle by drawing a picture. A linear programming problem is an optimisation problem where everything in sight is a straight-line relation, and where the quantities are not allowed to go negative. The order matters. Meet the special case first and the word linear sounds decorative, like a label somebody stuck on. Meet the family first and it is what it actually is — a condition, to be checked before anything gets drawn.

3:50And the other word of the name misleads in the opposite direction. Programming here means drawing up a programme, a plan of action. The word is older than the machines and has nothing to do with writing code. Anyone who has written code reads the title wrongly on the first page and is never corrected. So: what has to be linear, and how would you know? Not by looking at the algebra. A rule is linear when it does two things. Buy one lot, then buy another, and the rule has to give the same answer as buying both together. And buy three times as much and it has to give three times as much.

4:36Take those two tests to the dealer's three relations. Money spent, shelf used, profit earned: over twenty eight thousand five hundred and sixty one pairs of purchases and eight hundred and forty five scalings, all three pass both tests every time. But look at why each one passes, because each is an assumption about the world and not a fact. Money spent is linear because a table costs the same whether it is the first he buys or the twentieth. Shelf used is linear because a table takes one space and always one. Profit is linear because the profit per table does not fall as the shop fills up.

5:23None of those three is guaranteed by anything. Give him a bulk discount of two hundred rupees a table after the tenth, and the money rule stops adding — it fails at sixteen thousand seven hundred and thirty one of those pairs, and stops scaling at three hundred and thirty eight of the scalings too. Make the shelf harder to pack as it fills, or let the market flood so profit per chair drops, and each of those fails at twenty eight thousand two hundred and twenty four pairs.

5:58Any one of those changes and none of what follows applies to the problem any more. Linear is a condition on the world. Check it first. Now turn the paragraph into symbols, which is where the answer is actually decided. Let x be the number of tables he buys, and let y be the number of chairs he buys. That second half of the sentence — the number of tables he buys — is not decoration, and leaving it out is the most expensive habit in this topic. A letter with no stated meaning gives you constraints you cannot check, an objective nobody can read back, and a final pair of numbers that is not obviously a purchase at all.

6:47Write it down and keep it on the page. Everything for the rest of this video is checked against it. These two are the decision variables — the quantities the dealer is actually free to set. He is not free to choose the price of a table or the size of his shelf. He chooses x and he chooses y, and that is the whole of his freedom. The first limit is money. He spends two thousand five hundred rupees on each table and five hundred on each chair, and the total cannot exceed fifty thousand.

7:25Two thousand five hundred x plus five hundred y is at most fifty thousand. The sign points that way because the words say he has fifty thousand — a cap, not a target. That is worth saying out loud, because every limit in this one paragraph is a cap, and a student who has only ever seen this formulation will assume caps are the only kind there is. The words at least point the other way, and plenty of questions use them.

7:57Now the step the page takes without comment: divide through by five hundred. Five x plus y is at most a hundred. Why is that allowed? Because five hundred is positive. Multiply or divide both sides of an inequality by a positive number and the verdict on every single candidate is unchanged. That is not a thing to take on trust. Every purchase was put to both lines — whole numbers, halves, quarters, and purchases with negative entries, more than seventy five thousand of them in total — and the two lines disagree about exactly none.

8:40It really is the sign that does the work, and not the number. Scale both sides by any of eight different positive factors, fractions included, and the verdict holds at all fifty nine thousand and forty eight trials. Do it with a negative factor and leave the sign where it was, and the verdict reverses at twenty nine thousand four hundred and forty of twenty nine thousand five hundred and twenty four — every purchase except the ones that spend the money exactly.

9:14The second limit is space. The shelf holds sixty pieces. x plus y is at most sixty. Both coefficients are one, and that is worth a pause, because a student who has just written two thousand five hundred and five hundred sees a one and reads it as a number somebody forgot to fill in. It is not missing. It is there because a table takes one space on the shelf and a chair takes one space on the shelf. Count the pieces one at a time instead of multiplying, over every purchase on the grid, and you get the same answer every time.

9:55And notice these two limits are limits of different kinds. One is money and one is room, and they bite in different places. Of the whole purchases on the grid, two hundred and twenty are ones the money allows and the shelf refuses; a thousand and forty are ones the shelf allows and the money refuses; eight hundred and fifty one break neither. If the two limits were really the same kind of limit, one of them would be doing no work. They are not, and neither is redundant. That is precisely why the answer came out a mixture.

10:36Two more conditions, and they come from somewhere different. x is at least nothing, and y is at least nothing. These are the non-negative constraints, and they get a name of their own and are usually written first. They are constraints like any other — the separate name is emphasis, not a different kind of object. That is a reading, and worth saying so. Where they come from is the interesting part. They do not come from the dealer. Nothing in that paragraph forbids a negative table. The money limit and the shelf limit between them let in three thousand nine hundred and six purchases with a negative entry, and not one word of the question rules any of them out.

11:24They come from what the letters count. x counts tables. You cannot buy minus four tables. The floors are arithmetic, not commerce, and they are exactly why you must say what each letter counts before you write anything else. And they do real work. Drop them and four thousand seven hundred and fifty seven purchases become allowed where eight hundred and fifty one were — more than five times as many.

11:55Now, on this particular problem the best answer happens not to move when you drop them, and it is worth being honest about that. That is luck. Give the chair the table's profit and the table the chair's, and with the floors the best is fifteen thousand rupees at sixty chairs; without them the best simply runs away — fifteen thousand, then thirty two thousand five hundred, then sixty seven thousand five hundred as you look further out. Nothing stops it.

12:28One thing left, and it is the one that decides the answer. What is being made large is profit. Two hundred and fifty rupees on every table and seventy five on every chair, so the profit is two hundred and fifty x plus seventy five y. Call it Z. This is the objective function, and it is not a constraint. It has no inequality sign attached and it is not required to be anything in particular — it is the one expression on the page that is being read rather than obeyed.

13:05Students who list it among the inequalities and shade a half plane for it get a smaller region than the problem has. Shade it at five thousand, say, and the region loses a hundred and forty nine of its eight hundred and fifty one purchases — including, as it happens, the best one. Written in general the objective is a constant times x plus another constant times y. Two of those four symbols are fixed by the problem and two are chosen by the solver, and it is worth being clear which is which. The constants come from the paragraph. The variables are his to set.

13:48Which brings us to the single most common formulation mistake there is, and it is invisible once the graph is drawn. The dealer's paragraph gives four rates. Two thousand five hundred and five hundred are what the furniture COSTS. Two hundred and fifty and seventy five are what it EARNS. The costs are already spent — they live inside the money constraint. The objective is built from the other two.

14:18Put the prices in the objective by mistake and you are asking a perfectly sensible question, just not the one you were asked. You are asking which purchase spends the most money. Here is what that gets you. The swapped objective does not even point at one purchase. It comes to fifty thousand at eleven different purchases — the whole edge where the money runs out — and the real profits along that edge run from five thousand at one end to six thousand two hundred and fifty at the other.

14:55So a student who swaps them and reads off the wrong corner, twenty tables and no chairs, loses one thousand two hundred and fifty rupees of profit. And nothing on the page catches it. The graph looks right, the region is right, the arithmetic is right, the answer is wrong. Set the whole thing out now, the way it is meant to be set out. Maximise Z equals two hundred and fifty x plus seventy five y.

15:28Subject to: two thousand five hundred x plus five hundred y at most fifty thousand; x plus y at most sixty; and x and y both at least nothing. Three parts. An instruction saying what to do with what. The linking phrase, subject to. Then the list. One thing to expect. The order of the list carries no meaning, and you will see it written both ways — the two floors first while the constraints are being built up, and last when the finished programme is set out. Both are correct. Nobody is wrong. It is an ordering, nothing more.

16:10This object has a name too. It is a linear programming problem, and that phrase names both the question and the written thing you have just produced. You have a formulation. Is it right? Once the drawing starts, a wrong constraint looks exactly like a right one, so whatever checking you are going to do has to happen now. There are two checks available, and between them they are the whole of the safety net.

16:41The first is a read-back. Take every number from the paragraph and find it in the programme. Fifty thousand: in the money constraint. Two thousand five hundred and five hundred: in the money constraint. Sixty: in the shelf constraint. Two hundred and fifty and seventy five: in the objective. Six numbers, six homes, each exactly once. Nothing in the paragraph unused, and nothing in the programme unaccounted for once you set aside the two coefficients of one and the two floors, which came from the letters rather than from the question.

17:22Now run that same check on the swapped version. The two prices turn up twice each and the two profits never turn up at all. The read-back catches it instantly. One warning about when to run it. Run it on the form with the true prices in it, not the divided form. Divide first and five, one and a hundred are numbers the paragraph never gave you, and the audit reports three of the six as missing on a formulation that is perfectly correct.

17:57The second check is units, and it is one almost nobody performs. A unit is rarely written beside a term at all, and never checked. Every term in a constraint has to measure the same kind of thing, and so does the number on the right. The money constraint: rupees per table times a count of tables is rupees. Rupees per chair times a count of chairs is rupees. Fifty thousand is rupees. All three agree.

18:30After the division, all three are counted in lots of five hundred rupees instead — which is a neat way of seeing why the division is harmless. Both sides were rescaled the same way. The shelf constraint: pieces, pieces, pieces. The objective: rupees. Now try writing a constraint that puts a price against a shelf space, and it refuses outright. It is wrong before you draw a single line. But here is the honest limit of the test, and it is the reason you need both checks. Profits and prices are both measured in rupees per item. An objective built from the prices passes the units test exactly as cleanly as the right one does. The units test does not catch the swap. The read-back does. They catch different mistakes, which is why neither one replaces the other.

19:32With all of that in hand the formal definition reads as four conditions rather than as one long sentence, and all four have to hold at once. One: an optimal value is wanted — a largest or a smallest. For the dealer, a largest profit, and there is exactly one purchase that reaches it. Two: the thing being optimised is a linear function of the variables. The profit adds and scales, checked, not assumed.

20:04Three: the variables are held at or above nothing. The two floors. Four: a set of linear inequalities has to be satisfied. Money and shelf, and both of those add and scale as well. Four conditions, four matches. And notice the parts get defined before the whole — objective function first, constraints second, and the problem they belong to third. Read them in that order and you are assembling something before you know what it is for. It is worth going the other way round.

20:42A short history, because it explains the strange name. The subject came out of the planning of operations during the Second World War. In nineteen forty one the first problem of this kind was formulated, by a Russian mathematician and an American economist working separately — a question about shipping goods at least cost. In nineteen forty five an English economist asked for the cheapest diet that still met every nutritional requirement. In nineteen forty seven the simplex method arrived, a step-by-step procedure that finishes in finitely many steps. In nineteen seventy five the Nobel prize in economics was shared for this work.

21:32Two things follow from that. The simplex method is how these problems are actually solved at any size, and it is not what you are about to be taught. And the shipping problem and the diet problem are history here rather than exercises — at this level you will not meet either of them worked through. What is taught here is the drawing, and the drawing only works with two variables.

22:01So, what to carry out of this. Optimisation is the family; linear programming is the small part of it where every relation is a straight line and nothing goes negative, and that is a condition to be checked, not a label. Say what each letter counts before you write anything else. Build the objective from what the question wants made large, not from the rates that happen to be lying nearby. Dividing a constraint through by a positive number changes nothing, and by a negative number changes everything.

22:39And run both checks before you draw. The read-back finds numbers in the wrong place. The units test finds terms that cannot belong together. After the drawing starts, neither mistake looks like a mistake. One last thing, and it is about the practice rather than the mathematics. Every worked problem you are about to meet begins with the formulation already done for you. The step this video is about is the one you will be asked for in an examination and the one you will have seen performed exactly once. Take a worded situation, any worded situation, and formulate it yourself.