was before, that is, she should purchase no Solido at all and 40 cartons of Liquex
at a total cost of £200, even though she will have 1120 mg of vitamins in excess
of the 880 mg required.
The optimum combination ultimately depends on the relative costs of the
supplements. If the cost per packet of Solido went down to £2 and Liquex went
up to £7 then the bills for the corner point combinations A (0, 40), B (48, 8) and
C (88, 0) would be respectively £280, £152 and £176.
The best purchase for Tanya with these prices is 48 packets of Solido and 8
cartons of Liquex, with a bill of £152.
History
In 1947 the American mathematician George Dantzig, then working for the US
Air Force, formulated a method for solving linear programming problems called
the simplex method. It was so successful that Dantzig became known in the West
as the father of linear programming. In Soviet Russia, cut off during the Cold
War, Leonid Kantorovich independently formulated a theory of linear
programming. In 1975, Kantorovich and the Dutch mathematician Tjalling
Koopmans were awarded the Nobel Prize for Economics for work on the
allocation of resources, which included linear programming techniques.
Tanya only considered only two foods – two variables – but nowadays
problems involving thousands of variables are commonplace. When Dantzig
found his method there were few computers but there was the Mathematical
Tables Project – a decade-long job creation scheme which began in New York in
- It took a team of some ten human calculators working for 12 days with
hand calculators to solve a diet problem in nine ‘vitamin’ requirements and 77
variables.
While the simplex method and its variants have been phenomenally successful,
other methods have also been tried. In 1984 the Indian mathematician Narendra
Karmarkar derived a new algorithm of practical significance, and the Russian
Leonid Khachiyan proposed one of chiefly theoretical importance.
The basic linear programming model has been applied to many situations
other than choosing a diet. One type of problem, the transportation problem,
concerns itself with transporting goods from factories to warehouses. It is of a
special structure and has become a field in its own right. The objective in this