Le problème du régime 183
du simplexe » pour résoudre les problèmes de programmation linéaire. Ce fut une
telle réussite que Dantzig fut reconnu en Occident comme le père de la programmation linéaire. Dans la Russie Soviétique, qui était coupée du monde pendant
la Guerre Froide, Leonid Kantorovich et le mathématicien hollandais Tjalling
Koopmans reçurent le Prix Nobel d’économie pour leurs travaux sur l’allocation
des ressources par la technique de la programmation linéaire.
Tanya ne traitait que deux aliments, deux variables, mais aujourd’hui, les problèmes qui impliquent des milliers de variables sont assez communs. Lorsque
Dantzig découvrit sa méthode, il y avait peu d’ordinateurs mais le « Projet des
Tables Mathématiques » était lancé, programme commencé à New York en 1938
qui nécessita dix ans de travail. Une équipe de quelque dix calculateurs humains
travaillèrent pendant 12 jours pour résoudre un problème de régime avec neuf
« vitamines » et 77 variables.
Alors que la méthode du simplexe et ses variantes sont une réussite phénoménale,
d’autres méthodes furent également essayées. En 1984, le mathématicien indien
Narendra Karmarkar conçut un nouvel algorithme de portée pratique, et le russe
Leonid Khachiyan en proposa une autre qui présentait surtout un intérêt théorique.
On a appliqué le modèle de base de la programmation linéaire à de nombreuses
autres situations que celle du choix d’un régime. Dans le problème du transport par
exemple, il s’agit du transport de produits manufacturés vers des entrepôts. Avec sa
structure spéciale, il est devenu une véritable branche de la programmation linéaire
à lui tout seul. Dans ce type de problème, il faut réduire au maximum le coût
du transport. Dans certains problèmes de programmation linéaire, on recherche
la maximisation (comme pour un profit). Dans d’autres problèmes, les variables
ne prennent que des valeurs entières ou les deux valeurs 0 ou 1 seulement, mais
ces problèmes sont assez différents et font appel à des procédures de résolution
particulières.
Il reste à voir si Tanya Smith gagnera la médaille d’or aux Jeux Olympiques. Si elle
y parvient, ce sera un triomphe de plus pour la programmation linéaire.
l’idée clé
Garder la santé
à tout prix
du simplexe » pour résoudre les problèmes de programmation linéaire. Ce fut une
telle réussite que Dantzig fut reconnu en Occident comme le père de la programmation linéaire. Dans la Russie Soviétique, qui était coupée du monde pendant
la Guerre Froide, Leonid Kantorovich et le mathématicien hollandais Tjalling
Koopmans reçurent le Prix Nobel d’économie pour leurs travaux sur l’allocation
des ressources par la technique de la programmation linéaire.
Tanya ne traitait que deux aliments, deux variables, mais aujourd’hui, les problèmes qui impliquent des milliers de variables sont assez communs. Lorsque
Dantzig découvrit sa méthode, il y avait peu d’ordinateurs mais le « Projet des
Tables Mathématiques » était lancé, programme commencé à New York en 1938
qui nécessita dix ans de travail. Une équipe de quelque dix calculateurs humains
travaillèrent pendant 12 jours pour résoudre un problème de régime avec neuf
« vitamines » et 77 variables.
Alors que la méthode du simplexe et ses variantes sont une réussite phénoménale,
d’autres méthodes furent également essayées. En 1984, le mathématicien indien
Narendra Karmarkar conçut un nouvel algorithme de portée pratique, et le russe
Leonid Khachiyan en proposa une autre qui présentait surtout un intérêt théorique.
On a appliqué le modèle de base de la programmation linéaire à de nombreuses
autres situations que celle du choix d’un régime. Dans le problème du transport par
exemple, il s’agit du transport de produits manufacturés vers des entrepôts. Avec sa
structure spéciale, il est devenu une véritable branche de la programmation linéaire
à lui tout seul. Dans ce type de problème, il faut réduire au maximum le coût
du transport. Dans certains problèmes de programmation linéaire, on recherche
la maximisation (comme pour un profit). Dans d’autres problèmes, les variables
ne prennent que des valeurs entières ou les deux valeurs 0 ou 1 seulement, mais
ces problèmes sont assez différents et font appel à des procédures de résolution
particulières.
Il reste à voir si Tanya Smith gagnera la médaille d’or aux Jeux Olympiques. Si elle
y parvient, ce sera un triomphe de plus pour la programmation linéaire.
l’idée clé
Garder la santé
à tout prix