Chapitre 2 : Qu'est ce que la programmation linéaire ? ☝

La programmation linéaire est un programme d'optimisation consistant à  maximiser ou à  minimiser une fonction objectif linéaire de $n$ variables de décisions qui sont soumises à  un ensemble de $m$ contraintes, elles-mêmes exprimées sous la forme d'équations ou d'inéquations linéaires.

La programmation linéaire est née pendant la campagne d'Égypte sous la plume de Joseph Fourier qui tentait de résoudre un certain nombre d'inégalités linéaires. Mais, son travail est demeuré méconnu, même si Augustin Cournot en a fait l'exposition dès 1826. Pour tout dire, l'édition d'une partie des travaux de Fourier par Gaston Darboux n'a pas aidé, puisque la partie consacrée aux inégalités a été mise de côté. Pourtant, une autorité comme Jean-Pierre Kahane, membre de l'Institut, pense que si les travaux de Fourier avaient été publiés, ils apparaîtraient comme l'une des sources les plus importantes de la programmation linéaire.

Cette dernière est réellement apparue dans l'esprit de Leonid Vital'evich Kantorovich en URSS vers la fin des années 30 et, finalement, c'est l'américain Georges Bernard Dantzig qui, définitivement, lui a associé son nom en publiant le fameux algorithme dit du simplex qui est au c œur de la programmation linéaire. Mais de quoi s'agit-il ?