2 Méthode du simplexe

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

2.1 Systèmes faciles

1. Contrainte majoration. Une majoration est une inégalité $f\left( M\right) \leq Cte$ avec une constante positive. Dans le cas contraire, on écrit l'inégalité sous la forme $Cte\leq f\left( M\right)$, avec à nouveau une constante positive et l'on parle de minoration.
2. Contrainte égalité. Une égalité $f\left( M\right) =Cte$ ne peut pas être utilisée directement pour réduire le nombre de variables, car il faut conserver la contrainte de positivité sur chaque variable.
3. Variables de faces. Pour chaque contrainte majoration, on introduit une variable supplémentaire, transformant $f\left( M\right) \leq Cte$ en $\left\{ f\left( M\right) +y=Cte\: ;\: 0\leq y\right\}$.
4. Définition. Un système facile est, par définition, un système où il n'y a que des contraintes majoration. Il peut alors se mettre sous la forme d'un système d'égalités, avec uniquement des contraintes de positivité sur les variables.
5. Caractérisation. Un système facile est un système tel que l'origine des coordonnées soit un points acceptable (c.à.d. vérifie l'ensemble des contraintes).

2.2 Un système facile en dimension 2

Reprenons l'exemple du paragraphe 1.3.

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} & = ... ...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\leq 5$ : chaque $x_{i}$ sert à contrôler que nous sommes dans le bon demi-plan relatif à la contrainte correspondante. Le problème consiste à partir d'une solution admissible évidente $x_{1}=x_{2}=0$ 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} & = & ... ...& = & 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}\leq 1000$ et $x_{1}\leq 1400$. 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} & = & ... ... 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}\leq 500$ 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} & = & ... ...}{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}\leq 1000$, $-400\leq x_{3}$ et $x_{3}\leq 600$. 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$$
   exo 6.  Reprendre les calculs en commençant par modifier $x_{2}$ au point 4 ci-dessus exo 7.  Maximiser $z=3x_{1}+4x_{2}$ sous les contraintes $x_{1}+7x_{2}\leq 1000$, $7x_{1}+x_{2}\leq 1200$ et $3x_{1}+2x_{1}\leq 2000$.

2.3 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} & = & ... ...-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}\leq 1000$ et $x_{1}\leq 2250$. 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} & = & ... ...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}\leq 500$ et $x_{2}\leq 3750/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} & = & ... ..._{5}-2 x_{3} \end{array}\right\} \quad z=10000+3 x_{3}-4 x_{4}-12 x_{5}$$
   correction d'une erreur : ce n'est pas $-6 x_{5}$ mais $+6 x_{5}$

   La seule variable modifiables est $x_{3}$. Les contraintes de positivité imposent $x_{3}\leq 1500$ et $x_{3}\leq 375$. 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} & = & ... ...} \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}\leq 1000$ et $x_{4}\leq 1125\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_... ...} \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$.
6. exo 8.  Reprendre les calculs en commençant par modifier $x_{2}$ au point 1 ci-dessus

2.4 Contraintes minoration ou égalité

1. Si l'origine n'est pas un point acceptable, 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 satisfaites par l'origine (contraintes égalité ou minoration). Ainsi
   $x_{1}+2 x_{2}\leq 100$ 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}\geq 100$ devient $x_{1}+2 x_{2}+z_{2}=100+y_{2}$ (contrainte majoration)
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 les $x_{k}$ et les $y_{n}$ issues 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$, nous aurons montré que le problème initial est insoluble (contraintes contradictoires).
7. Si l'on arrive à $\max f=0$, nous aurons 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.5 Programmation effective

Une optimisation évidente de cet algorithme consiste à confier le soin des additions et multiplications à un ordinateur. On sera néanmoins attentif à ne pas sous-traiter la réflexion, qui constitue le coeur du métier d'ingénieur.

Le premier programme mk_simplex (ALG. 1) a pour objectif de créér toutes les variables auxiliaires nécessaires de façon à transformer les inéquations en équations et les contraintes non satisfaites par l'origine du problème initial en contraintes satisfaites par l'origine d'un problème de plus grande taille. Pour des raisons de commodité, les trois sortes de variables s'appellent toutes $x$, l'indice variant de $1$ à $N$ pour les variables naturelles, de $N+1$ à $N+M$ pour les variables "$y$" et de $N+M+1$ à la fin pour les variable"s $z$".

En sortie, $eqs$ contient les équations réécrites, $tous$ est l'ensemble de toutes les variables, $spec$ est l'ensemble des variables "$z$" et $lieu$ est la liste des coordonnées dont l'égalité à $0$ caractérise le point où l'on se trouve.

Le programme pt_vue (ALG. 2) est un programme "cosmétique" destiné à réécrire l'ensemble des équations du point de vue du sommet où l'on se trouve. L'écriture effective de ce programme est tout à fait simple (on utilise $solve$ pour résoudre), mais est loin d'être optimale. En effet, une étape est caractérisée par l'échange de rôles entre une variable "actuellement principale" et une variable "actuellement auxiliaire" : une résolution de proche en proche serait plus rapide.

Le programme avance (ALG. 3) exécute le déplacement consistant en l'échange des rôles entre la variable principale $piv$, choisie par l'utilisateur, et la variable auxiliaire exerçant la contrainte la plus forte. Le cas exceptionnel où l'on trouve un mouvement $x_{piv}=0$ ne se produit qu'en présence de contraintes redondantes.

Enfin, le programme randavance (ALG. 4) détermine quels sont les pivots possibles (variables ayant une influence positive sur la fonction de bénéfice) et en choisit un aléatoirement.

2.6 Un exemple en deux phases

1. Considérons le problème
   $$\max \left( 4 x_{1}+12 x_{2}\right) \quad sachant\: que \le... ... 4200\\ 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} & = & ... ...d{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} & = & 1... ...+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_{... ...\\ 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_{... ...} \end{array}\right\} , z\doteq 4 x_{1}+12 x_{2}=5600+8 x_{7}-4 x_{6}$$
   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-4 x_{6}-\frac{8}{3}x_{5}$$
   La décision à recommander est donc $x_{1}=600$ et $x_{2}=400$, pour un bénéfice escompté de $z=7200$.

2.7 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} & = & ... ...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} & = & ... ...{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}\geq 0$ est une simple conséquence des contraintes $x_{1}\leq 1000$ 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\... ...500\leq \xi _{1}-\xi _{2}\\ 200\leq \xi _{1}-2\, \xi _{2} \end{array}\right.$$
   exo 9.  Résoudre le système ci-dessus. Vérifier qu'il conduit au résultat déja obtenu.
   exo 10.  Représentation et résolution graphiques de ce système