Programmation linéaire et algorithme du simplexe
Un problème de programmation linéaire est un problème de mathématiques d'optimisation d'une fonction linéaire sous des contraintes d'inégalités affines. Plus précisémént, il s'agit de déterminer le maximum d'une fonction du type $$a_1 x_1+\dots+a_n x_n$$ où les variables $x_1,\dots, x_n$ vérifient des inégations du type $$c_{i,1}x_1+\dots+c_{i,n}x_n\leq b_i,$$ pour $1\leq i\leq p$. De tels problèmes arrivent fréquemment en économie.
Il existe plusieurs algorithmes pour résoudre de tels problèmes. Le plus connu est l'algorithme du simplexe. Nous nous proposons d'étudier son fonctionnement sur un exemple. On dispose de trois variables, $x_1$, $x_2$ et $x_3$ et on souhaite maximiser la quantité $$5x_1+4x_2+3x_3$$ (qu'on appellera fonction de bénéfice) sous les contraintes suivantes : $$\left\{ \begin{array}{l} 2x_1+3x_2+x_3\leq 5\\ 4x_1+x_2+2x_3\leq 11\\ 3x_1+4x_2+2x_3\leq 8\\ x_1,x_2,x_3\geq 0 \end{array}\right.$$ Il est commode de se ramener à des contraintes qui s'écrivent sous formes d'équations. Pour cela, on introduit de nouvelles variables (autant que d'inéquations), appelées variables d'écart, que nous notons $x_4,x_5$ et $x_6$ et on remarque qu'il suffit de maximiser la même quantité sous les contraintes : $$\left\{ \begin{array}{l} 2x_1+3x_2+x_3+x_4= 5\\ 4x_1+x_2+2x_3+x_5=11\\ 3x_1+4x_2+2x_3+x_6= 8\\ x_1,x_2,x_3,x_4,x_5,x_6\geq 0 \end{array}\right.$$ (remarquer ici la justification du nom "variables d'écart").
On commence par partir d'un choix des variables compatibles avec le système d'inéquations. Le plus facile est $x_1=0$, $x_2=0$, $x_3=0$ qui entraîne $x_4=5$, $x_5=11$ et $x_6=8$. On part donc de (0,0,0,5,11,8). Bien sûr, il n'est pas du optimal puisqu'alors la fonction de bénéfice est nulle. Prenons justement cette fonction de bénéfice. Augmenter $x_1$ (sans toucher ni à $x_2$, ni à $x_3$), permet d'augmenter la fonction de bénéfice. On va augmenter $x_1$ autant que c'est possible. Bien sûr, si on augmente $x_1$, on doit diminuer $x_4,x_5$ et $x_6$ pour que les égalités de contraintes restent respectées. On peut le faire jusqu'à ce que l'une des variables d'écart s'annule. La première équation nous dit qu'on ne peut pas aller plus loin que $x_1=5/2$, la deuxième que $x_2=11/4$ et la troisième que $x_1=8/3$. La plus petite de ces valeurs est $5/2$.
On va alors refaire une itération de l'algorithme en partant de la solution réalisable avec $x_1=5/2$, $x_2=0$, $x_3=0$ qui donne $x_4=0$, $x_5=3$, $x_6=1/2$. Mais on va échanger le rôle joué par $x_1$ et $x_4$ puisque désormais on a saturé $x_4$. On va donc remplacer $x_1$ par son expression en fonction de $x_4$, $x_2$ et $x_3$ dans toutes les équations. On doit maintenant maximiser $$\frac{25}2-\frac 72x_2+\frac 12x_3-\frac 52x_4$$ sous les contraintes $$\left\{ \begin{array}l \frac 32 x_2+\frac 12x_3+\frac 12 x_4+x_1=\frac 52\\ \frac -5x_2-2x_4+x_5=1\\ -\frac 12x_2+\frac 12x_3-\frac32x_4+x_6=\frac 12\end{array} \right.$$ Si on remarque maintenant la fonction de bénéfice, qui s'écrit désormais $\frac{25}2-\frac 72x_2+\frac 12x_3-\frac 52x_4$, on ne peut plus choisir n'importe quelle variable. En effet, seule une augmentation de $x_3$ va augmenter le bénéfice. On procède donc comme précédemment, en augmentant $x_3$ (et en modifiant parallèlement $x_1$, $x_5$ et $x_6$) tant que cela est possible. Ici, la contrainte est donnée par la troisième équation, et quand $x_3=1$, on obtient $x_6=0$ (et $x_1=2$, $x_5=1$). La solution réalisable que l'on a obtenu désormais est $(2,0,1,0,1,0)$, qui conduit à une valeur de fonction bénéfice égale à 13.
On recommence à nouveau à partir de cette solution réalisable, en prenant bien soin de permuter le rôle joué par $x_3$ et $x_6$, et donc en exprimant $x_3$ en fonction de $x_6$ grâce à la dernière équation. La fonction de bénéfice est donc maintenant $$13-3x_2-x_4-x_6$$ et les contraintes s'écrivent : $$\left\{ \begin{array}l 2x_2 +2x_4 -x_6+x_1 = 2 \\ -5x_2 -2x_4+x_5 = 1 \\ -x2 -3x_4 +2x_6+x_3 = 1\\ \end{array}\right. $$ On se rend compte ici que l'on a terminé. Augmenter une des trois variables libres à ce stade de l'algorithme ($x_2$, $x_4$ ou $x_6$) ne pourra que diminuer le bénéfice. On a donc trouvé la solution optimale.
Cet algorithme fonctionne toujours, et permet même de détecter s'il est impossible de maximiser la fonction bénéfice. Il porte le nom d'algorithme du simplexe, car les contraintes définissent (dans certains cas) un simplexe (plus généralement, un polyèdre), et l'algorithme consiste à partir d'un sommet de ce simplexe et à se rendre sur un autre sommet pour lequel la fonction bénéfice prend une valeur plus élevée.
Grâce au petit formulaire suivant, vous allez pouvoir résoudre vos problèmes de programmation linéaire grâce à l'algorithme du simplexe.
L'exemple ci-dessus est issu de l'excellent polycopié de Didier Smets.
L'algorithme du simplexe
est dû à Dantzig en 1947. Etonamment, il n'est pas toujours polynômial, alors qu'il existe des algorithmes polynomiaux pour résoudre ces problèmes de programmation linéaire. Néanmoins, sur la plupart des données, il est très efficace.