Programmation linéaire - Méthode et applications

De nombreux phénomènes économiques et industriels peuvent se modéliser par des systèmes mathématiques d’inégalités et d’égalités linéaires conduisant à des problèmes d’optimisation linéaire. Dans ces problèmes d’optimisation linéaire, on cherche à minimiser ou maximiser une fonction linéaire sous des contraintes linéaires portant sur les variables du problème. On parle souvent de programmation linéaire (ou encore de programme linéaire ), le terme de programmation faisant référence à l’idée d’organisation et de planification lié à la nature des phénomènes modélisés. Ce terme a été introduit pendant la Seconde Guerre mondiale et systématiquement utilisé à partir de 1947 lorsque G. Dantzig inventa la méthode du simplexe pour résoudre les problèmes de programmation linéaire. Les applications industrielles de la programmation linéaire sont très présentes par exemple dans l’industrie pétrolière (pour l’extraction, le raffinage et la distribution du pétrole), dans l’agroalimentaire (composition optimale des ingrédients de plats cuisinés, etc.), industrie du fer et de l’acier (composition optimale des aciers), l’industrie du papier (problèmes de découpe), les transports (plan de vols d’avions, minimisation des coûts de transport…) et les réseaux (optimisation des réseaux de communication).

Cet article présente les propriétés et les concepts fondamentaux de la programmation linéaire puis expose l’algorithme du simplexe pour résoudre un programme linéaire. L’algorithme du simplexe est mis en œuvre selon deux méthodes, la méthode des dictionnaires et la méthode des tableaux . La première méthode permet de bien comprendre le déroulement du simplexe alors que la méthode des tableaux est plus algébrique et elle conduit à la mise en œuvre effective de l’algorithme du simplexe. Un code MATLAB basé sur la méthode des tableaux est proposé en annexe. Une application de la méthode du simplexe à l’analyse de sensibilité d’un programme linéaire est également présentée ainsi qu’une introduction à la dualité en programmation linéaire.