Programmation linéaire, technique de modélisation mathématique dans laquelle une fonction linéaire est maximisée ou minimisée lorsqu'elle est soumise à diverses contraintes. Cette technique a été utile pour guider les décisions quantitatives en planification d'entreprise, en génie industriel et - dans une moindre mesure - en sciences sociales et physiques.
optimisation: programmation linéaire
Bien que largement utilisée aujourd'hui pour résoudre des problèmes de décision quotidiens, la programmation linéaire était relativement inconnue avant 1947. Aucun travail de quelque importance
La solution d'un problème de programmation linéaire se réduit à trouver la valeur optimale (la plus grande ou la plus petite, selon le problème) de l'expression linéaire (appelée la fonction objectif)
soumis à un ensemble de contraintes exprimées en inégalités:
Les a, b et c sont des constantes déterminées par les capacités, les besoins, les coûts, les bénéfices et d'autres exigences et restrictions du problème. L'hypothèse de base dans l'application de cette méthode est que les diverses relations entre la demande et la disponibilité sont linéaires; c'est-à-dire qu'aucun des x i n'est élevé à une puissance autre que 1. Pour obtenir la solution de ce problème, il est nécessaire de trouver la solution du système des inégalités linéaires (c'est-à-dire l'ensemble des n valeurs de les variables x i qui satisfont simultanément toutes les inégalités). La fonction objectif est ensuite évaluée en substituant les valeurs de x i dans l'équation qui définit f.
Les applications de la méthode de programmation linéaire ont d'abord été sérieusement tentées à la fin des années 1930 par le mathématicien soviétique Leonid Kantorovich et par l'économiste américain Wassily Leontief dans les domaines des calendriers de fabrication et de l'économie, respectivement, mais leur travail a été ignoré pendant des décennies. Pendant la Seconde Guerre mondiale, la programmation linéaire a été largement utilisée pour traiter du transport, de la programmation et de l'allocation des ressources soumises à certaines restrictions telles que les coûts et la disponibilité. Ces applications ont beaucoup contribué à établir l'acceptabilité de cette méthode, qui a pris un nouvel élan en 1947 avec l'introduction de la méthode simplexe du mathématicien américain George Dantzig, qui a grandement simplifié la solution des problèmes de programmation linéaire.
Cependant, comme des problèmes de plus en plus complexes impliquant plus de variables ont été tentés, le nombre d'opérations nécessaires a augmenté de façon exponentielle et a dépassé la capacité de calcul même des ordinateurs les plus puissants. Puis, en 1979, le mathématicien russe Leonid Khachiyan a découvert un algorithme à temps polynomial - dans lequel le nombre d'étapes de calcul augmente en fonction du nombre de variables plutôt qu'exponentiellement - permettant ainsi la solution de problèmes jusqu'alors inaccessibles. Cependant, l'algorithme de Khachiyan (appelé méthode ellipsoïde) était plus lent que la méthode simplex lorsqu'il était pratiquement appliqué. En 1984, le mathématicien indien Narendra Karmarkar a découvert un autre algorithme à temps polynomial, la méthode du point intérieur, qui s'est avéré compétitif avec la méthode du simplexe.
