Programmation linéaire - Méthode du SIMPLEX


Dans le cadre des méthodes numériques d'optimisation, certains problèmes peuvent être modélisés :

- par un ensemble de variables numériques représentant les valeurs recherchées ;

- une fonction à optimiser définie par une somme pondérée de ces variables ;

- des contraintes reliant ces variables sous la forme d'équations linéaires.


Une première approche géométrique permet d'introduire la notion de convexe des solutions, et la localisation de celle(s) offrant l'optimum de la fonction économique.

Un lien est fait entre ce convexe des solutions, le système d'équations mis sous sa forme dite "standard", et la notion de "base" associé au système d'égalités représentant les contraintes.


L'algorithme du SIMPLEX est alors présenté. Il est tout d'abord étudié en manipulant le système d'égalités, puis retrouvé sous forme de tableaux permettant sa mise en œuvre aisée.

Le SIMPLEXE à 2 phases est bien entendu présenté, ainsi qu'une révision du SIMPLEX permettant de limiter les calculs effectués.


D'autres éléments sont abordés, notamment le principe de la dualité ou la paramétrisation du problème (étude de l'optimum en fonction de certaines variations dans la modélisation du problème).