Linear Programming from Fibonacci to Farkas

ABSTRACT

At the beginning of the 13th century Fibonacci described the rules for making mixtures of all kinds, using the Hindu-Arabic system of arithmetic. His work was repeated in the early printed books of arithmetic, many of which contained chapters on ‘alligation', as the subject became known. But the rules were expressed in words, so the subject often appeared difficult, and occasionally mysterious. Some clarity began to appear when Thomas Harriot introduced a modern form of algebraic notation around 1600, and he was almost certainly the first to express the basic rule of alligation in algebraic terms. Thus a link was forged with the work on Diophantine problems that occupied mathematicians like John Pell and John Kersey in the 17th century. Joseph Fourier's work on mechanics led him to suggest a procedure for handling linear inequalities based on a combination of logic and algebra; he also introduced the idea of describing the set of feasible solutions geometrically. In 1898, inspired by Fourier’s work, Gyula Farkas proved a fundamental theorem about systems of linear inequalities. This topic eventually found many applications, and it became known as Linear Programming. The theorem of Farkas also plays a significant role in Game Theory.

KEYWORDS:

• Alligation
• inequalities
• indeterminacy
• Farkas Lemma
• Linear Programming

Acknowledgements

I am grateful to Paul Williams for advice on Linear Programming and Fourier-Motzkin Elimination, and Philip Beeley for advice on the literature of the seventeenth century.

Disclosure statement

No potential conflict of interest was reported by the author.

Notes

1 For the background to the Tractatus see Martin Allen, Mints and Money in Medieval England (Cambridge: Cambridge University Press, 2012) and Nicholas Mayhew, ‘From Regional to Central Minting’, in A New History of the Royal Mint, ed. by Christopher Challis (Cambridge: Cambridge University Press, 1992), pp. 81–178. The extract is from the Red Book of the Exchequer, translated by Charles Johnson, The De Moneta of Nicholas Oresme and English Mint Documents (London: Nelson, 1950), p. 71.

2 Jack Williams, ‘Mathematics and the Alloying of Coinage 1202–1700’, Annals of Science, 52 (1995), 212–34, 235–63.

3 For the general background to the Italian bankers in England see Walter Rhodes, ‘The Italian bankers in England and their loans to Edward I and Edward II’, in Historical Essays, ed. by T. F. Tout and J. F. Tait (London: Longmans, 1902). For a more numismatic account, see Mavis Mate, ‘Monetary Policies in England 1272–1307’, British Numismatic Journal, 41 (1972), 34–79.

4 Fibonacci’s work first appeared in 1202 and was revised in 1228. The Latin text has been published by B. Boncompagni, Scritti di Leonardo Pisano (Rome, 1857) and there is an English translation by L. Sigler, Fibonacci’s Liber Abaci (New York: Springer, 2002).

5 Kim Plofker, ‘Mathematics in India’, in The Mathematics of Egypt, Mesopotamia, China, India and Islam, ed. by Victor Katz (Princeton: Princeton University Press, 2007), pp. 435–437.

6 Piero Borgi, Qui Comenza la Nobel Opera de Arithmetica (Venice, 1488). Editions of this work were published in 1484 and 1488, preceding the better-known Summa of Pacioli which appeared in 1494.

7 Johannes Widman, Behennd und hupsch Rechnung auf allen Kaufmanschaften (Leipzig, 1489); Robert Recorde, The Grounde of Artes (London, 1552). The OED attributes the word ‘alligation’ to Richard Taverner, but the context is unclear.

8 Dionis Gray, The Store-House of Breuitie in Woorks of Arithmetic (London: William Norton and John Harrison, 1577).

9 The Harriot papers can be examined online (echo.mpiwg-berlin.mpg.de). The parts relating to alligation and coinage are analysed by Norman Biggs, ‘Thomas Harriot on the Coinage of England’, Archive for the History of the Exact Sciences, 73, no. 4 (2019), 361–83.

10 See note 30/4/9B-18A in the online edition of Samuel Hartlib’s Ephemerides (www.dhi.ac.uk/hartlib).

11 Gerhard de Neufville, Theorica et Practica Arithmetica (Bremen, 1624).

12 The circumstances are described by Noel Malcolm and Jacqueline Stedall, John Pell (1611–1685) and his Correspondence with Sir Charles Cavendish (Oxford: Oxford University Press, 2005), pp. 290–91.

13 The ‘ordinary’ method of elimination was rarely mentioned in the early books on algebra. Joseph Grear, ‘How Ordinary Elimination Became Gaussian Elimination’, Historia Mathematica, 38 (2011), 163–218. But it was in fact well known. A very clear example from the middle of the sixteenth century, using old notation can be found in the Logistica of Jean Borrel. It has been reprinted with an English translation by Jacqueline Stedall, Mathematics Emerging (Oxford: Oxford University Press, 2008), pp. 548–51. Pell’s notes for Cavendish contained an example taken from Gosselin’s De Arte Magna of 1577, with modernised notation.

14 See the reference in note 12. The original sources are: Letter 51 (page 459) BL Add MS 4278 f.238–39; Letter 52 (page 461) BL Add MS 4278 f.241; Letter 55 (page 470) BL Add MS 4280 f.117.

15 The details are described by Jacqueline Stedall, A Discourse Concerning Algebra (Oxford: Oxford University Press, 2002), pp. 135–39.

16 BL Harleian Ms 6755.

17 See note 28/1/60B-71A in the online edition of Samuel Hartlib’s Ephemerides (www.dhi.ac.uk/hartlib).

18 For an analysis of Reynolds’ method, see Norman Biggs, ‘John Reynolds of the Mint: A Mathematician in the Service of King and Commonwealth’, Historia Mathematica, 48 (2019), 1–28.

19 Pierre Hérigone, Cursus Mathematicus Tomus Secundus (Paris, 1634).

20 John Kersey, Mr Wingate’s Arithmetick (London, 1662).

21 John Kersey, The Elements of that Mathematical Art commonly Called Algebra (London, 1673). John Collins considered this book to be ‘much better’ than others being offered for publication in the early 1670s. See Stephen Rigaud, Correspondence of Scientific Men of the Seventeenth Century, Volume 1 (Oxford: Oxford University Press, 1841).

22 B. Boncompagni, Scritti di Leonardo Pisano II (Rome, 1857–62), p. 247.

23 Alexander Malcolm, A New System of Arithmetick (London: J. Osborn and T, Longman, 1730), pp. 568–69.

24 Fourier’s publications on this topic are conveniently collected in the second volume of his Oeuvres, ed. by G. Darboux (Paris: Gauthier-Villars, 1890), pp. 317–28. His 1798 Mémoire appears in the same volume.

25 In the diagram $OX$represents the line $y=0$, and $OY$ represents the line $x=0$. The line $XY$ (not drawn) represents $x+y=1$ (that is, $z=0$) and so all the positive solutions lie inside the triangle $OXY.$

26 Gyula Farkas, ‘Applications of the Mechanical Principle of Fourier’ and ‘Algebraic Basis of the Mechanical Principle of Fourier’ [Hungarian], Mathematikai es Termeszettudomanyi Ertesito, 12 (1894), 457–72 and 16 (1898), 361–64.

27 Theodore Motzkin, Beitrage zur Theorie der Lineaaren Ungleichungen (Doctoral thesis, Basel/Jerusalem, 1936). Fourier’s method of eliminating variables from a system of linear inequalities is now known as ‘Fourier-Motzkin Elimination’; see Paul Williams, ‘Fourier’s Method of Linear Programming’, American Mathematical Monthly, 33, no. 9 (1986), 681–75.

28 Alexander Schrijver, ‘On the History of Combinatorial Optimisation (till 1960)’, in Handbooks in Operations Research: Discrete Optimisation, ed. by K. Ardaal et al. (Amsterdam: North-Holland, 2005).

29 George Dantzig, ‘Linear Programming’, Operations Research, 50, no. 1 (2002), 42–47. Von Neumann had also worked on the Leontief model, where the prices of commodities occur naturally as the ‘dual’ variables. Essentially the same idea is now regarded as fundamental in financial mathematics, where the ‘no free lunch’ principle is equivalent to the existence of a consistent system of prices: this is a direct consequence of the Farkas Lemma.

30 We denote the transpose of $u$ by $u^T$and follow the usual conventions about inequalities between vectors.

31 The Farkas Lemma is now often regarded as a corollary of a more general principle, the Separating Hyperplane Theorem for convex sets, but that is another story.