Linear ProgrammingIntroduction
Diwali is two weeks away, and Gupta-ji's sweet shop in Lucknow is taking its last bulk orders. He has 18 kg of khoya and 14 kg of sugar left, and he will turn all of it into trays of two sweets.
A tray of kaju katli uses 3 kg of khoya and 1 kg of sugar, and earns him ₹400. A tray of ladoo uses 2 kg of khoya and 2 kg of sugar, and earns him ₹300.
He can sell every tray he makes. How many trays of each should he make to earn as much as possible?
You are Gupta-ji's planner. Drag the two numbers. The bars show how much khoya and sugar your plan needs, and every plan you try leaves a dot on the grid: purple if the shop can make it, a red ring if it runs out of something. Find the plan with the biggest profit.
Trays of kaju katli:
Trays of ladoo:
Two trays of kaju katli and six of ladoo earn ₹2600, and no other plan does better. Now look at the grid. The purple dots — the plans the shop can make — fill a region with straight sides, one side for the khoya limit and one for the sugar limit. The winning dot sits exactly at a corner of that region, where the khoya and the sugar run out at the same moment. That is no accident, and by the end of this chapter you will know why.
Problems That Ask for the Best
Gupta-ji's question has a special shape. He is not asked to find a plan; he wants the best plan out of many possible ones. Problems that ask for the largest profit, the smallest cost or the least use of some resource are called optimisation problems.
In earlier classes you solved systems of linear equations, and in Class XI you met
Which of these is an optimisation problem?
The bus question has many possible answers — any mix of buses with enough seats — and asks for the cheapest one. Its cost and its seat count are both linear expressions in the numbers of buses, like Gupta-ji's profit and his khoya and sugar. A problem of this kind is called a linear programming problem. It is a special but very important class of optimisation problems, used every day in industry, commerce and management. There are several ways to solve such problems; in this chapter we use only one of them, the graphical method.
A Wartime Idea That Won a Nobel Prize
Linear programming problems came to the forefront during the Second World War, when military operations had to be planned to cut costs and make the best use of scarce supplies.
The first such problem was formulated in 1941, by the Russian mathematician L. Kantorovich and the American economist F. L. Hitchcock, working independently: the transportation problem, which asks for the cheapest way to send goods from several factories to several markets. In 1945 the economist G. Stigler described another one: the cheapest diet that still meets a person's daily nutritional needs.
In 1947 the American mathematician G. B. Dantzig found an efficient procedure, the simplex method, that solves any linear programming problem in a finite number of steps. In 1975 Kantorovich and the American mathematical economist T. C. Koopmans were awarded the Nobel Prize in economics for their pioneering work in linear programming. With computers, the same ideas now handle problems with thousands of variables.
Drag these milestones into order, earliest at the top.
The idea that won that prize is the one you are about to learn: the best plan always waits at a corner.