Fiche du document
1973
Copyright PERSEE 2003-2023. Works reproduced on the PERSEE website are protected by the general rules of the Code of Intellectual Property. For strictly private, scientific or teaching purposes excluding all commercial use, reproduction and communication to the public of this document is permitted on condition that its origin and copyright are clearly mentionned.
Sujets proches
Optimización linealCiter ce document
Jean-Pierre Brans et al., « Programmation linéaire — Critères d'optimalité », Bulletins de l'Académie Royale de Belgique, ID : 10.3406/barb.1973.60722
Métriques
Partage / Export
Résumé
Un programme linéaire est un problème dont l'objet est de déterminer un certain nombre d'inconnues réelles non négatives soumises à un système d'inéquations linéaires et qui rendent optimum (maximum ou minimum) une fonction linéaire, appelée fonction économique. Il existe plusieurs algorithmes permettant de résoudre un programme linéaire, le plus important est certainement l'algorithme du Simplexe, mis au point par G. B. Dantzig en 1947. La plupart des propriétés mathématiques de la programmation linéaire sont démontrées à partir de l'algorithme du Simplexe. Il nous a semblé intéressant de les établir de façon directe, sans faire usage des propriétés de récurrence et de convergence de cet algorithme. Pour ce faire, nous avons introduit dès le début la notion de programme dual et établi directement les propriétés essentielles de la dualité. C'est à partir de celles-ci que nous déduisons le critère d'optimalité de Dantzig ainsi que les conditions nécessaires et suffisantes d'optimalité de Kuhn et Tucker pour un programme linéaire. La démonstration des conditions de Kuhn et Tucker est particulièrement simplifiée et tient à présent en quelques lignes.