Module D108  : Programmation mathématique et optimisation
Programmation Linéaire
L'algorithme du simplexe

L'idée géométrique
Calcul efficace d'une solution réalisable adjacente
Les détails du calcul
Trouver une solution réalisable initiale
Un problème : les solutions dégénérées
Exercices


Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 30 Janvier 2006

Dans cette section nous allons regarder un algorithme performant conçu par G. Dantzig en 1947. Il est performant d'une part parce qu'il effectue assez peu d'itérations de son opération de base (avancer d'une solution réalisable de base à une autre meilleure) et d'autre part parce que chacune de ces opérations est effectuée par des calculs algébriques simples.

L'idée géométrique

A chaque itération l'algorithme a une solution réalisable de base (nous allons voir comment la première est trouvée) et essaie de trouver une autre solution réalisable de base qui est adjacente en tant que sommet du polytope de solutions réalisables et meilleure (possède une meilleure valeure de la fonction économique). S'il n'existe pas de telle solution meilleure adjacente, la solution actuelle est forcément optimale.

Bien que théoriquement ce processus puisse parcourir un nombre exponentiel de sommets du polytope, en pratique on trouve que le nombre réellement parcourus est petit, ce qui permet à l'algorithme de résoudre facilement des programmes avec des centaines de variables.

Une solution de base étant donnée par l'intersection de $ n$ des (hyper)plans définis par les contraintes, une arête du polytope passant par cette solution est donnée par l'intersection de $ n-1$ parmi ces hyperplans et, donc, une solution adjacente est donnée par l'intersection de $ n-1$ des hyperplans plus un nouveau. Si on choisit l'hyperplan à supprimer de telle façon que l'arête va dans une bonne direction (valeur de la fonction économique augmentante), une bonne solution adjacente est donnée par la prochaine intersection entre cette arête et un autre hyperplan donné par une nouvelle contrainte.

Calcul efficace d'une solution réalisable adjacente

Le calcul d'une bonne solution adjacente s'avère très simple dans le cas où la solution actuelle a $ x_j=0$ pour tout $ j$. Notons d'abord que dans ce cas $ (0,0,\cdots,0)$ étant une solution réalisable, chaque contrainte $ \sum_{j=1} a_{i,j}x_j\le b_i$ a forcément $ b_i \ge 0$.

Les arêtes du polytope passant par cette solution sont les $ n$ droites sur lesquelles $ n-1$ des variables restent nulles. Prenons par exemple celle sur laquelle toutes les variables sauf $ x_j$ sont nulles; si la fonction économique est $ \sum_{i=1}^n c_ix_i$, sa valeur sur cette ligne est donnée par $ c_jx_j$ et, donc, devient positive si $ c_j>0$. C'est-à-dire qu'il faut choisir un $ c_j$ positif; parmi les $ c_j$ positifs, on peut choisir arbitrairement. Toujours sur cette ligne, une contrainte comme $ \sum_{j=1} a_{i,j}x_j\le b_i$ devient simplement $ a_{i,j}x_j\le b_i$ et, si $ a_{i,j}\le 0$, $ x_j$ n'est pas contrainte; si $ a_{i,j}>0$, on sait que $ x_j$ ne peut pas dépasser $ b_i/a_{i,j}$ sans sortir du polytope. Enfin le minimum parmi ces rapports $ b_i/a_{i,j}$ pour les $ a_{i,j}$ positifs doit donner la valeur de $ x_j$ à la solution adjacente.

Ainsi, si la solution actuelle est $ (0,0,\cdots,0)$, trouver une bonne solution adjacente est facile et rapide. L'astuce de l'algorithme du simplexe est d'ajouter de nouvelles variables de telle façon que toute solution de base est
$ (0,0,\cdots,0)$ par rapport à un sous-ensemble bien choisi de $ n$ variables.

Concrètement, pour chaque contrainte
$ \sum_{j=1} a_{i,j}x_j\le b_i$ on ajoute une variable d'écart $ x_{n+i}$ définie par $ \sum_{j=1} a_{i,j}x_j + x_{n+i} = b_i$; $ x_{n+i}$ sera forcément nulle à une solution de base située sur l'hyperplan $ \sum_{j=1} a_{i,j}x_j = b_i$ et sera positive à chaque autre solution réalisable.

Maintenant on a $ m+n$ variables et $ m$ équations (contraintes d'égalité) et les seules autres contraintes sont que toutes les variables sont $ \ge 0$; à une solution réalisable de base, on a toujours $ n$ des variables nulles et les autres (les variables de base), en général, sont positives. A chaque itération on va choisir une nouvelle base afin de garder les deux conditions qui rendaient facile le calcul d'une solution adjacente:

Un calcul assez simple calcule ces expressions linéaires pour la nouvelle base permettant de commencer la prochaine itération.

Les détails du calcul

On a une matrice $ A$ de $ m$ lignes et $ m+n$ colonnes un vecteur colonne $ b$ et un vecteur ligne $ c$; les contraintes d'égalité sont $ Ax=b$ et la fonction économique est $ cx+constante$; les colonnes de $ A$ correspondant aux variables de la base constituent une matrice de permutation, c'est-à-dire une matrice carrée ($ m$ par $ m$) où tous les éléments sont nuls sauf un élément égal à $ 1$ en chaque ligne et chaque colonne; les éléments de $ c$ correspondant à ces mêmes variables sont tous nuls.

Et on a réproduit les conditions énoncées pour la nouvelle base.

On peut noter que si, quand on cherche les $ c_i$ positifs, il n'y en a pas, on a trouvé un cas ou la fonction objective n'admette aucune borne supérieure finie.

Trouver une solution réalisable initiale

Si $ (0,0,\cdots,0)$ n'ést pas une solution réalisable, une astuce permet de trouver une solution de base réalisable (s'il y'en a) avec une première application du simplexe à un programme auxiliaire et ensuite de continuer directement à la solution souhaitée avec une deuxième application (méthode en deux phases.)

$ (0,0,\cdots,0)$ n'ést pas une solution réalisable parce que quelques uns des $ b_j$ sont strictement négatifs; on ajoute une nouvelle variable artificielle (disons $ x_a$) avec sa contrainte implicite $ x_a>=0$, et pour chaque $ j$ avec $ b_j<0$ on modifie la contrainte numéro $ j$ en ajoutant $ -x_a$ à gauche, les autres contraintes restant inchangées; maintenant les contraintes sont faisables avec (par exemple) $ x_a=-min(b_j)$ et toutes les autres variables nulles.

Avec ces contraintes et la solution initiale réalisable de base $ x_a=-min(b_j),~ x_i=0 ~(1\le i\le n)$ on maximise la fonction $ -x_a$; ceci est le programme auxiliaire. Si on trouve une solution optimale avec $ x_a=0$, on a trouvé une solution réalisable du programme initial; sinon il n'existe pas de telle solution.

Qui plus est, quand on a trouvé une solution avec $ x_a=0$, en supprimant la variable artificielle $ x_a$ et en modifiant la fonction objective de départ (avec les mêmes pivotages utilisés dans la première phase), on a directement une solution réalisable de base du programme initial et le tableau qu'il faut pour y appliquer la méthode du simplexe.
(On va voir un exemple au lieu de démonstration.)

Un problème : les solutions dégénérées

Un petit problème embêtant est celui des solutions dégénérées: quand une solution de base est l'intersection d'un nombre strictement supérieur à $ n$ de contraintes, il est possible que l'opération de pivotage remplace une de ces contraintes par une autre, produisant une amélioration nulle dans la fonction objective, et même que celui-ci se réproduit dans une boucle de façon que l'algorithme ne termine pas. Parmi plusieurs solutions possibles à ce problème est la règle de Bland: parmi les candidats pour la colonne ou la ligne du pivot, quand il y'en a plusieurs, choisir toujours celui de l'indice minimum. Cette règle est opposée à l'intuition qui dit qu'il faudrait choisir le coefficient maximum dans la fonction objective mais le risque de non terminaison est sérieux; en effet des programmes réels sont souvant de type dégénéré.


 

Exercices

Questionnaire de compréhension immédiate

3 exercices