La programmation linéaire traite des problèmes de formulation apparemment élémentaire : optimiser des fonctions du premier degré sur un ensemble défini par des inéquations aussi du premier degré. Cette théorie admet en fait de nombreuses applications très concrètes.


La programmation linéaire est née dans les années 1930 des travaux de l’économiste et mathématicien soviétique Leonid Vitalievitch Kantorovitch (1912–1986), qui reste le seul chercheur soviétique ayant reçu à ce jour le « prix Nobel » d’économie, en 1975.

Dans un processus de décision, on est souvent amené à devoir choisir, parmi un ensemble de solutions possibles, celle qui va rendre optimale une certaine fonction f de variables assujetties à des contraintes. Par exemple, on cherche à rendre maximal un rendement de production en présence de ressources limitées, ou à payer un coût minimal pour un achat d’une qualité satisfaisante, ou encore à composer un mélange de qualité dont le prix de revient soit minimal.

En pratique, et tout spécialement dans les applications économiques, des problèmes concrets se traduisent donc mathématiquement par l’optimisation (maximisation ou minimisation) d’une fonction f dont les variables, notées Lire la suite