2. Algorithme du simplexe

L'objectif de ce chapitre n'est pas l'efficacité du calcul (il y a d'excellents logiciels pour cela) mais la compréhension des calculs entrepris.

2.1 Un système facile en dimension 2

Reprenons l'exemple de la Section 1.2.

1. Nous récrivons les données du problème en introduisant trois nouvelles variables, déterminées par le système d'équations :
   $$\left(S\right)\quad\left\{ \begin{array}{ccc} x_{1}+x_{3} & = & 1... ...x_{2}+x_{4} & = & 500\\ 3 x_{1}+6 x_{2}+x_{5} & = & 4200\end{array}\right.$$

2. Les contraintes s'écrivent maintenant $0\leq x_{i}$ pour $1\leq i\leq5$ : chaque $x_{i}$ sert à contrôler que nous sommes dans le bon demi-plan relatif à la contrainte correspondante. Le problème consiste à partir du point $x_{1}=x_{2}=0$, qui est évidemment un point de bon fonctionnement, et à maximiser la fonction de bénéfice $z=4 x_{1}+12 x_{2}$.
3. Du point de vue du sommet $x_{1}=x_{2}=0$, les variables principales sont $x_{1}$ et $x_{2}$, et le système s'écrit préférentiellement :
   $$\left.\begin{array}{ccc} x_{3} & = & 1000-x_{1}\\ x_{4} & = & 50... ... & = & 4200-3 x_{1}-6 x_{2}\end{array}\right\} \quad z=4 x_{1}+12 x_{2}$$
   Nous avons le choix de modifier $x_{1}$ ou $x_{2}$ puisque les deux coefficients $\frac{d z}{d x_{i}}$ sont positifs. Nous choisissons de modifier $x_{1}$, et donc de garder $x_{2}=0$. Les contraintes de positivité imposent $x_{1}\leq1000$ et $x_{1}\leq1400$. Le meilleur mouvement est donc $x_{1}=1000$, qui conduit au sommet :
   $$x_{2}=x_{3}=0\quad;\quad x_{1}=1000, x_{4}=500, x_{5}=1200$$

4. Du point de vue de ce nouveau sommet, le système se récrit
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{3}\\ x_{4} & = & 50... ...& 1200-6 x_{2}+3 x_{3}\end{array}\right\} \quad z=4000+12 x_{2}-4 x_{3}$$
   Vu les coefficients de $z$, le seul mouvement possible est celui consistant à augmenter $x_{2}$ (et donc à garder $x_{3}=0$). Les contraintes de positivité imposent $x_{2}\leq500$ et $x_{2}\leq\frac{1}{6}1200$. Le meilleur mouvement est donc $x_{2}=200$, qui conduit au sommet :
   $$x_{3}=x_{5}=0\quad;\quad x_{1}=1000, x_{2}=200, x_{4}=300$$

5. Du point de vue de ce sommet, le système se récrit
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{3}\\ x_{2} & = & 20... ...1}{2}x_{3}+\frac{1}{6}x_{5}\end{array}\right\} \quad z=6400+2 x_{3}-2 x_{5}$$
   La seule variable modifiable est $x_{3}$. Vu les contraintes de positivité sur les trois autres variables, cette modification doit vérifier $x_{3}\leq1000$, $-400\leq x_{3}$ et $x_{3}\leq600$. Le meilleur mouvement possible est donc $x_{3}=600$, qui conduit au sommet :
   $$x_{4}=x_{5}=0\quad;\quad x_{1}=400, x_{2}=500, x_{3}=600$$

6. Une dernière réécriture conduit à :
   $$\left.\begin{array}{ccc} x_{1} & = & 400+2x_{4}-\frac{1}{3}x_{5}\... ...+\frac{1}{3}x_{5}\end{array}\right\} \quad z=7600-4 x_{4}-\frac{4}{3} x_{5}$$
   Comme tous les coefficients de la fonction de bénéfice sont négatifs, on est arrivé à un sommet optimal (et comme tous les coefficients sont non nuls, ce sommet optimal est le seul). Le bénéfice maximal escompté est donc $z=7600$.
7. Le résultat de ce calcul n'est pas la valeur du bénéfice escompté (qui dépend de la validité du modèle et des diverses influences extérieures) mais la décision conseillée, qui est
   $$x_{1}=400, x_{2}=500$$

Exercise 2.1.1   Maximiser $z=3x_{1}+4x_{2}$ sous les contraintes $x_{1}+7x_{2}\leq1000$, $7x_{1}+x_{2}\leq1200$ et $3x_{1}+2x_{1}\leq2000$.

2.2 Un système facile en dimension 3

On se pose le problème suivant :

$$maximiser\quad z=4 x_{1}+12 x_{2}+3 x_{3}\quad sachant\; qu... ... & \leq & 1500\\ 3 x_{1}+6 x_{2}+2 x_{3} & \leq & 6750\end{array}\right.$$

1. On introduit une nouvelle variable par contrainte, et le système devient :
   $$\left.\begin{array}{ccc} x_{4} & = & 1000-x_{1}\\ x_{5} & = & 50... ...}-6 x_{2}-2 x_{3}\end{array}\right\} \quad z=4 x_{1}+12 x_{2}+3 x_{3}$$
   Les trois variables sont modifiables, et nous choisissons de modifier $x_{1}$ (et donc de garder $x_{2}=x_{3}=0$). Les contraintes de positivité imposent $x_{1}\leq1000$ et $x_{1}\leq2250$. Le meilleur mouvement est donc $x_{1}=1000$, qui conduit au sommet :
   $$x_{2}=x_{3}=x_{4}=0\quad;\quad x_{1}=1000, x_{5}=500, x_{6}=1500, x_{7}=3750$$

2. Du point de vue de ce sommet, le système se récrit :
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{4}\\ x_{5} & = & 50... ... x_{2}-2 x_{3}\end{array}\right\} \quad z=4000+12 x_{2}+3 x_{3}-4 x_{4}$$
   Deux variables sont modifiables. Nous choisissons de modifier $x_{2}$ (et de ne pas modifier $x_{3}=x_{4}=0$). Vu les contraintes de positivité, cette modification doit vérifier $x_{2}\leq500$ et $x_{2}\leq3750/6=625$. Le meilleur mouvement possible est donc $x_{2}=500$, qui conduit au sommet :
   $$x_{3}=x_{4}=x_{5}=0\quad;\quad x_{1}=1000, x_{2}=500, x_{6}=1500, x_{7}=750$$

3. Du point de vue de ce sommet, le système se récrit :
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{4}\\ x_{2} & = & 50... ...x_{5}-2 x_{3}\end{array}\right\} \quad z=10000+3 x_{3}-4 x_{4}-12 x_{5}$$
   La seule variable modifiable est $x_{3}$. Les contraintes de positivité imposent $x_{3}\leq1500$ et $x_{3}\leq375$. Le meilleur mouvement possible est donc $x_{3}=375$, qui conduit au sommet :
   $$x_{4}=x_{5}=x_{7}=0\quad;\quad x_{1}=1000, x_{2}=500, x_{3}=375, x_{6}=1125$$

4. Du point de vue de ce sommet, le système se récrit :
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{4}\\ x_{2} & = & 50... ...7}\end{array}\right\} \quad z=11125+\frac{1}{2}x_{4}-3 x_{5}-\frac{3}{2}x_{7}$$
   La seule variable modifiable est $x_{4}$, avec pour contraintes $x_{4}\leq1000$ et $x_{4}\leq1125\times\frac{2}{3}=750$. Le meilleur mouvement est donc $x_{4}=750$, conduisant au sommet :
   $$x_{5}=x_{6}=x_{7}=0\quad;\quad x_{1}=250, x_{2}=500, x_{3}=1500, x_{4}=750$$

5. Du point de vue de ce sommet, le système se récrit :
   $$\left.\begin{array}{ccc} x_{1} & = & 250+2 x_{5}+\frac{2}{3}x_{... ...7}\end{array}\right\} \quad z=11500-4 x_{5}-\frac{1}{3}x_{6}-\frac{4}{3}x_{7}$$
   Il ne reste plus de variables modifiables, provoquant l'arrêt de l'algorithme. La décision proposée est donc :
   $$x_{1}=250, x_{2}=500, x_{3}=1500$$
   qui vérifie toutes les contraintes et conduit à un bénéfice prévisionnel de $11500$.

Exercise 2.2.1   Reprendre les calculs en commençant par modifier $x_{2}$ au point 1 ci-dessus

2.3 Système général

1. Si l'origine n'est pas un point de bon fonctionnement, un travail supplémentaire doit être effectué. Il faut ou bien trouver un sommet acceptable, ou bien démontrer qu'il n'en existe pas. Dans le premier cas, on pourra partir de ce sommet et appliquer l'algorithme décrit ci-dessus. Dans le deuxième cas, il faut évidemment obtenir une démonstration de non existence, et pas seulement un constat d'échec.
2. Méthode des variables auxiliaires. En plus des variables naturelles $x_{k}$ du problème, on introduit autant de variables $y_{n}$ que d'inégalités (comme ci-dessus), puis autant de variables $z_{m}$ que de relations non vérifiées par l'origine. Ainsi
   $x_{1}+2 x_{2}\leq100$ devient $x_{1}+2 x_{2}+y_{1}=100$ (contrainte majoration)
   $x_{1}+2 x_{2}=100$ devient $x_{1}+2 x_{2}+z_{1}=100$ (contrainte égalité)
   $x_{1}+2 x_{2}\geq100$ devient $x_{1}+2 x_{2}+z_{2}=100+y_{2}$ (contrainte minoration)
3. Un sommet acceptable du problème initial est caractérisé par $\forall m : z_{m}=0$, et nous sommes dans une situation où l'origine ne vérifie pas cette condition.
4. Nous nous posons alors un nouveau problème, dont
   • les variables principales sont tous les $x_{k}$ et ceux des $y_{n}$ qui sont issus d'une contrainte minoration.
   • les équations linéarisées sont celles du problème initial
   • la fonction de bénéfice est $f=-\sum z_{m}$
5. La nouvelle origine (la dimension ayant augmenté, ce n'est plus le même espace) est un point acceptable pour le nouveau problème.
6. Si l'on arrive à $\max f<0$, il est alors prouvé que le problème initial est insoluble (contraintes contradictoires).
7. Si l'on arrive à $\max f=0$, on a nécessairement $\forall m : z_{m}=0$ puisque ces variables sont positives. Et alors les variables $x_{k}$ et $y_{n}$ sont caractéristiques d'un sommet acceptable du problème initial.

2.4 Un exemple en deux phases

1. Considérons le problème
   $$\max\left(4 x_{1}+12 x_{2}\right)\quad sachant\: que \left\{... ...}\leq4200\\ 1000\leq x_{1}+x_{2}\\ 1200\leq x_{1}+2 x_{2}\end{array}\right.$$

2. La procédure mk_simplex permet de le récrire en :
   $$\left.\begin{array}{ccc} x_{3} & = & 1000-x_{1}\\ x_{4} & = & 50... ...nd{array}\right\} , f\doteq-x_{8}-x_{9}=-2200+2 x_{1}+3 x_{2}-x_{6}-x_{7}$$
   Les variables $x_{3}\cdots x_{7}$ sont les variables de contrôle des faces et les variables $x_{8}, x_{9}$ ont été introduites pour tenir compte du non respect des contraintes par le point $\left(x_{1}=x_{2}=0\right)$. Le problème comportant le même nombre d'équations qu'avant, le nombre de variables principales augmente de $2$, et l'on part du point $\left(x_{1}=x_{2}=x_{6}=x_{7}=0\right)$.
3. On choisit la variable $x_{2}$ comme pivot, et on obtient :
   $$\left.\begin{array}{ccc} x_{2} & = & 500-x_{4}\\ x_{3} & = & 100... ...}+2 x_{4}+x_{7}\end{array}\right\} , f=-700+2 x_{1}-3 x_{4}-x_{6}-x_{7}$$

4. La variable $x_{1}$ s'impose comme pivot, et on obtient :
   $$\left.\begin{array}{ccc} x_{1} & = & 200+2 x_{4}+x_{7}-x_{9} ... ...{4}+x_{6}-x_{7}+x_{9}\end{array}\right\} , f=-300+x_{4}-x_{6}+x_{7}-2 x_{9}$$

5. Puis, $x_{4}$ étant pris comme pivot :
   $$\left.\begin{array}{ccc} x_{1} & = & 800+2 x_{6}-x_{7}-2 x_{8... ...9}\\ x_{5} & = & 600-3 x_{7}+3 x_{9}\end{array}\right\} , f=-x_{8}-x_{9}$$
   Le fait remarquable n'est pas que $f=-x_{8}-x_{9}$ (cette égalité à lieu depuis le début, puisque c'est la définition de $f$ !) mais que ces deux variables (qui expriment la violation des contraintes) soient enfin nulles.
6. Ainsi, nous venons d'atteindre un sommet admissible pour le problème initial, à savoir $x_{6}=x_{7}=0$. Nous pouvons donc nous débarrasser des variables "$z$" (i.e. $x_{8}$ et $x_{9}$) et revenir au problème initial, qui s'écrit désormais :
   $$\left.\begin{array}{ccc} x_{1} & = & 800+2 x_{6}-x_{7}\\ x_{2}... ...{7}\end{array}\right\} , z\doteq4 x_{1}+12 x_{2}=5600-4 x_{6}+8 x_{7}$$
   et se résout par la méthode usuelle.
7. On trouve, en une étape,
   $$\left.\begin{array}{ccc} x_{1} & = & 600+2 x_{6}+\frac{1}{3}x_{... ...& 200-\frac{1}{3}x_{5}\end{array}\right\} , z=7200-\frac{8}{3}x_{5}-4 x_{6}$$
   La décision à recommander est donc $x_{1}=600$ et $x_{2}=400$, pour un bénéfice escompté de $z=7200$.

2.5 Un exemple de contraintes redondantes

1. Reprenons le système du paragraphe précédent, à savoir :
   $$\left.\begin{array}{ccc} x_{3} & = & 1000-x_{1}\\ x_{4} & = & 50... ...-2 x_{2}+x_{7}\end{array}\right\} , z=-2200+2 x_{1}+3 x_{2}-x_{6}-x_{7}$$

2. Si nous choisissons maintenant $x_{1}$ comme pivot, au lieu de $x_{2}$, nous obtenons :
   $$\left.\begin{array}{ccc} x_{1} & = & 1000-x_{3}\\ x_{4} & = & 50... ..._{2}+x_{3}+x_{7}\end{array}\right\} , z=-1200+3 x_{2}-2 x_{3}-x_{6}-x_{7}$$
   Une fois arrivé là, il n'est plus possible de bouger. En effet, la variable $x_{2}$ est la seule à influer positivement sur la fonction de bénéfice, et d'autre part $x_{8}=-x_{2}+x_{3}+x_{6}$ avec $x_{3}=x_{6}=0$ et $0\leq x_{2}$, $0\leq x_{8}$ impose $x_{2}=x_{8}=0$.
3. L'équation $x_{2}=x_{3}+\left(x_{6}-x_{8}\right)$ exprime que l'information véhiculée par la contrainte $x_{2}\geq0$ est une simple conséquence des contraintes $x_{1}\leq1000$ et $1000\leq x_{1}+x_{2}$. On peut donc se ramener à un système avec une inconnue de moins et une contrainte de moins par la substitution $\xi_{1}=x_{1}$, $\xi_{2}=500-x_{2}$. Il vient :
   $$\max\left(6000+4 \xi_{1}-12 \xi_{2}\right)\quad sachant\: que ... ...eq1200\\ 500\leq\xi_{1}-\xi_{2}\\ 200\leq\xi_{1}-2 \xi_{2}\end{array}\right.$$

Exercise 2.5.1   Résoudre le système ci-dessus. Vérifier qu'il conduit au résultat déjà obtenu.

Exercise 2.5.2   Représentation et résolution graphiques de ce système.

Exercise 2.5.3   Reprendre ce système en modifiant légèrement une équation, de façon à rompre la liaison. Comparer les résultats obtenus.