Optimisation linéaire

Ce cours d'optimisation linéaire est destiné à des étudiants en Mathématiques apliquées ou Informatique, niveau troisième année universitaire. Il est basé essentiellement sur la référence ci-après : {quote} Hédi Nabli, ''Recherche Opérationnelle : Algorithme du Simplexe et ses Applications'', Centre de Publication Universitaire , Tunisie (2006) {quote} Ce livre propose entre autres

1. une nouvelle méthode de recherche d'une base réalisable initiale pour l'algorithme du simplexe. Cette technique ne fait pas intervenir les variables artificielles. De plus il est souvent possible d'aboutir, en une seule itération, à une base réalisable.
2. Grâce aux tableaux formels, une nouvelle alternative, autre que l'algorithme dual-simplexe, est proposée.
3. Pour les problèmes de transport, un algorithme récursif pour la détermination des éléments d'un tableau de transport est mis en oeuvre.

Dans ce document, les résultats mathématiques sont donnés sans démonstration. Pour plus de détails, on peut consulter la référence ci-dessus.

I Programmation linéaire

II Méthode graphique

III Méthode des sommets

IV Méthode du simplexe

V Algorithme du simplexe standard

VI Dualité en programmation linéaire

Vous trouverez ici une version pdf : docquadratic.pdf

Je remercie vivement Sophie Lemaire et Bernadette Perrin-Riou, enseignants-chercheurs à l'université de Paris-Sud, pour leur aide précieuse à réaliser ce document interactif.

Un programme linéaire est un problème dans lequel on est amené à maximiser (ou minimiser) une application linéaire, appelée fonction d'objectif ou fonction économique , sur un ensemble d'équations et/ou d'inéquations linéaires, dites contraintes . Autrement dit, la programmation linéaire est une branche des mathématiques qui a pour but de résoudre des problèmes d'optimisation linéaire de type

$\{\begin{array}{c}{\displaystyle \max (\text{ou}\min )[Z(x_1,\dots ,x_p)=\sum _{j=1}^p{c}_j{x}_j]}\\ {\displaystyle \sum _{j=1}^p{a}_{\mathrm{ij}}{x}_j\le (\text{et/ou =)}{b}_i,\text{pour}i=1,\dots ,m.}\end{array}$

Les coefficients $c_j,a_{\mathrm{ij}}$ et $b_i$ sont des réels fixés et les $x_j$ sont des variables réelles. Les contraintes d'inégalités éventuelles sont toutes larges et non strictes. Il se peut qu'une contrainte d'inégalité soit de type '' ''. En multipliant chaque inégalité de type '' '' par $(-1)$, on peut supposer que toutes les contraintes d'inégalité sont de type '' ''.

I-1 Généralités

I-2 Exemple

I-3 Domaine réalisable

I-4 Présentation des méthodes

Dans le contexte de la programmation linéaire, le terme programmation désigne l'organisation des calculs et non la réalisation d'un programme informatique. Du point de vue des applications, l'optimisation linéaire est d'une grande portée. Elle s'applique à des problèmes très variés qui sont issus de l'économie, de l'ingénierie, de la physique ou encore des modèles probabilistes. Dans ce cadre, on peut citer par exemple, les problèmes de type gestion de stock, gestion de production, transport de marchandise, affectation du personnel, systèmes industriels, réseaux de communication , etc. Pour les modèles de programmation linéaire, on est souvent amené à maximiser un gain ou minimiser un coût. Ceci explique d'ailleurs pourquoi la fonction à maximiser s'appelle fonction d'objectif ou économique.

Exemple

Formulation mathématique

Pour un problème d'optimisation linéaire, tout point qui vérifie l'ensemble des contraintes s'appelle point réalisable ou admissible . L'ensemble de tous les points réalisables s'appelle domaine réalisable . Il est facile de vérifier que le domaine réalisable d'un programme linéaire est convexe. On rappelle qu'un ensemble est dit convexe si à chaque fois qu'il contient deux points $x$ et $y$, il contient le segment joignant $x$ et $y$. Ce segment est souvent noté par $[x,y]$ et il est défini par

$[x,y]=\{\lambda x+(1-\lambda )y\cancel{}\lambda \in [0,1]\}$

Un point est dit optimal s'il est admissible et s'il réalise l'optimum de la fonction d'objectif sur le domaine réalisable. Par exemple, pour le problème

$\{\begin{array}{c}\max [Z(x_1,x_2)=x_1-x_2]\\ x_1+x_2\le 1\\ x_2\ge 0,\end{array}$

tout point réalisable $(x_1,x_2)$ vérifie

$Z(x_1,x_2)=x_1-x_2\le x_1\le x_1+x_2\le 1.$

D'autre part, le point $(1,0)$ est réalisable et on a $Z(1,0)=1$. Donc, la solution réalisable $(1,0)$ est optimale et la valeur maximale de $Z$ sur le domaine réalisable est $Z(1,0)=1$.

Nous allons présenter des techniques qui permettent de résoudre les programmes linéaires que l'on convient désormais de noter (PL). Diverses méthodes ont été proposées dans la littérature :

• La méthode graphique : l'utilisation de cette méthode est restreinte aux (PL) ayant un nombre de variables au plus égal à $3$.
• La méthode des sommets : le nombre de sommets étant prohibitif, cette méthode est très coûteuse en temps de calcul.
• La méthode du simplexe : algorithme itératif mis au point par George Dantzig en 1951.

Nous allons décrire la méthode graphique à travers trois exemples représentatifs, ayant chacun deux variables structurelles. Le premier admet une et une seule solution optimale. Le deuxième admet une infinité de solutions optimales. Par contre, le troisième exemple n'admet aucune solution optimale.

La résolution d'un (PL) par la méthode graphique se fait selon une démarche commune, celle-ci peut être résumée en quatre directives :

1. Schématiser le domaine réalisable dans un repère orthonormé.
2. Dans le même repère, représenter l'hyperplan ${\Delta }_0:Z(x)=0$. Noter que tout hyperplan ${\Delta }_r$ d'équation $Z(x)=r$, $r\in ℝ$, est parallèle à ${\Delta }_0$.
3. Si le (PL) considéré est de type maximisation ( resp. minimisation), indiquer, par une flèche, le sens de déplacement parallèle de ${\Delta }_r$ qui fait augmenter ( resp. diminuer) $r$.
4. Déterminer la droite ${\Delta }_{r_{\max }}$ la plus éloignée (dans le sens de la flèche) de ${\Delta }_0$ et qui coupe le domaine réalisable $ℛ$. Tout point de ${\Delta }_{r_{\max }}\cap ℛ$ est une solution optimale. Si une telle droite ${\Delta }_{r_{\max }}$ n'existe pas, cela veut dire que l'optimum est infini.

Appliquons ce principe général sur l'exemple 1 défini dans le paragraphe précédent.

II-1 Exemple 1

II-2 Exemple 2

II-3 Exemple 3

II-4 Remarque

II-5 Exercice

Reprenons l'exemple

$\{\begin{array}{cc}\max [Z(x_1,x_2)& =4x_1+5x_2]\\ 2x_1+x_2& \le 8\\ x_1+2x_2& \le 7\\ x_2& \le 3\\ x_1\ge 0& x_2\ge 0\end{array}$

Représentation graphique pour l'exemple 1

Le domaine réalisable est schématisé en gris sur la Figure. Toute droite ${\Delta }_r$ d'équation $Z(x_1,x_2)=r$, où $r$ est un réel fixé, est parallèle à la droite ${\Delta }_0$ : $Z(x_1,x_2)=0$. On constate aussi que tout déplacement parallèle de ${\Delta }_r$ dans le sens de la flèche (voir dessin ci-après) fait augmenter $r$. Donc maximiser la fonction $Z$, tout en satisfaisant aux contraintes du problème, revient à chercher la droite ${\Delta }_r$ la plus éloignée (dans le sens de la flèche) de ${\Delta }_0$ et qui coupe le domaine réalisable. Du point de vue graphique, il s'agit de la droite ${\Delta }_{r_{\max }}$ passant par le point $(3,2)$ et parallèle à ${\Delta }_0$. Ainsi, on peut conclure que le point $(3,2)$ est la seule solution optimale qui donne une valeur maximale de la fonction d'objectif égale à $Z(3,2)=22$. Autrement dit, le meilleur profit vaut $22$DT obtenu en fabriquant $3$ unités du produit (A) et $2$ unités du produit (B).

On considère le (PL) suivant :

$\{\begin{array}{cc}\max [Z(x_1,x_2)& =-6x_1+15x_2]\\ 2x_1-x_2& \ge 4\\ -2x_1+5x_2& \le 4\\ x_1\ge 0,x_2\ge 0& \end{array}$

Représentation graphique pour l'Exemple 2

Le domaine réalisable est la partie non bornée représentée partiellement en gris sur la Figure. Tout déplacement parallèle de ${\Delta }_r:Z(x_1,x_2)=r$ dans le sens de la flèche (voir dessin ci-après) fait augmenter $r$. Donc tout point de la demi-droite $[A,B)$ est optimal et la valeur maximale de $Z$ vaut $Z(A)=Z(3,2)=12$ (voir dessin ci-après).

On considère maintenant le (PL) suivant :

$\{\begin{array}{cc}\max [Z(x_1,x_2)& =x_1+x_2]\\ -x_1+x_2& \le 1\\ -x_1+2x_2& \le 4\\ x_1\ge 0,x_2\ge 0& \end{array}$

Représentation graphique pour l'Exemple 3

Le domaine réalisable associé à ce (PL) est la partie non bornée représentée partiellement en gris dans la Figure. Dans le graphique, on observe que toute droite ${\Delta }_r$ d'équation $Z(x_1,x_2)=r$, avec $r\ge 0$, coupe le domaine réalisable. Donc, $\sup Z=+\mathrm{\infty }$ et par conséquent, le problème n'admet aucune solution optimale (voir dessin ci-dessous).

Tous les exemples traités ci-dessus possèdent deux variables structurelles $x_1$ et $x_2$. Pour des (PL) en dimension $3$, le raisonnement pour la méthode graphique reste le même. La seule différence est que l'ensemble des points $(x_1,x_2,x_3)$ vérifiant une contrainte se représente par un demi-espace qui est délimité par le plan d'équation

Exercice

La méthode des sommets est simple, elle se base sur la résolution des systèmes linéaires de Cramer . Cependant, elle est dans la pratique inexploitable car le nombre de systèmes à résoudre est en général trop important.

Néanmoins, la méthode des sommets est d'une utilité incontestable : la recherche de l'optimum éventuel sur tout le domaine réalisable se ramène au calcul de l'optimum de la fonction d'objectif restreinte à un sous ensemble fini. Ce résultat sera l'un des outils clé de la méthode du simplexe .

{df} Pour toute contrainte d'inégalité $\sum a_{\mathrm{ij}}{x}_j\le b_i$ ( resp. contrainte de positivité $x_i\ge 0$) d'un (PL) donné, l'hyperplan associé $\sum a_{\mathrm{ij}}{x}_j\le b_i$ ( resp. $x_i=0$) s'appelle hyperplan frontière . {df}

III-1 Résultat préliminaire

III-2 Mise en oeuvre

III-3 Champ d'application

Considérons un (PL) à $p$ variables réelles. Un point $A$ du domaine réalisable est appelé sommet , s'il existe $p$ hyperplans frontières dont l'intersection est réduite à $A$.

Théorème

Sans nul doute, l'intérêt de ce théorème est immédiat :

La méthode des sommets pour la résolution d'un (PL), consiste donc à :

• déterminer tous les sommets du domaine réalisable,
• puis calculer la valeur de $Z$ en chacun de ces sommets.

Le sommet doté de la meilleure valeur de $Z$ serait une solution optimale. Une chose reste à vérifier pour l'application de cette méthode : s'assurer tout d'abord que le (PL) considéré admet bien une solution ( i.e. l'optimum est fini). Cette condition est souvent difficile à vérifier. Néanmoins, lorsque le domaine réalisable est borné, et par suite compact, l'existence d'une solution optimale est certaine.

Exercice

Exercice

Appliquons la méthode des sommets aux trois exemples précédents. Pour l'exemple , les sommets du domaine réalisable sont les points (voir Figure )

$(0,0);(4,0);(1,3);(3,2)\text{et}(0,3).$

La valeur de la fonction d'objectif $Z$ en chacun de ces sommets est

$Z(0,0)=0;Z(4,0)=16;Z(1,3)=19$

$Z(3,2)=22;Z(0,3)=15.$

Il est clair que la plus grande valeur de $Z$ en ces sommets est atteinte au point $(3,2)$ et vaut $Z(3,2)=22$. Pour l'exemple , d'après le graphique, les seuls sommets sont $(2,0)$ et $(3,2)$. De plus, on a

$Z(2,0)=-12<Z(3,2)=12,$

ce qui entraîne que $(3,2)$ est une solution optimale. Concernant l'exemple , les sommets du domaine réalisable sont les points $(0,0)$, $(0,1)$ et $(2,3)$. La valeur de $Z$ en chacun de ces points vaut

$Z(0,0)=0,Z(0,1)=1,Z(2,3)=5.0$

Cependant, on ne peut affirmer que $(2,3)$ est une solution optimale, puisqu'on a déjà vu que la fonction d'objectif n'est pas bornée sur son domaine réalisable.

Exercice

La méthode des sommets peut s'appliquer même pour des (PL) ayant un nombre de variables structurelles strictement supérieur à $3$. Afin de déterminer un sommet, on choisit $p$ hyperplans ( $p$ étant le nombre de variables) parmi les $n$ contraintes du domaine réalisable (y compris les contraintes de positivité : $x_i\ge 0$). On obtient ainsi un système linéaire d'ordre $p$ que l'on résoud. Si ce système admet une et une seule solution $A$, on vérifie si $A$ satisfait les $(n-p)$ contraintes restantes. Dans ce cas, $A$ est un sommet, sinon le choix considéré de ces $p$ équations linéaires ne permet pas d'avoir un sommet et pour ce faire, on effectue un autre choix de $p$ hyperplans frontières parmi les $n$ contraintes. Dans le but d'obtenir tous les sommets, il va falloir balayer tous les choix possibles dont le nombre est égal à ${\displaystyle {(}_p^n)={\displaystyle \frac{n!}{p!(n-p)!}}}$. Chaque choix qui aboutit à un système de Cramer dont la solution est réalisable permet d'obtenir un sommet. Enfin, la solution du problème considéré est obtenue en prenant l'optimum de la fonction d'objectif sur tous les sommets.

Remarque

Exercice

Dans ce chapitre, nous allons étudier une méthode qui évite de parcourir tous les sommets. Plus précisément, le passage d'un sommet à un autre se fait en améliorant la valeur de la fonction à optimiser. De plus, elle fournit un test qui permet d'affirmer le cas échéant que le problème n'admette pas de solution. Nous verrons que les résultats concernant les problèmes de type maximisation, comparés à ceux relatifs aux problèmes de minimisation, sont très similaires.

IV-1 Forme canonique

IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable

IV-5 Algorithme du simplexe

On convient de dire qu'un vecteur $u$ est inférieur à un vecteur $v$ , et on écrit $u\le v$, si pour tout $i$, on a $u_i\le v_i$. Ici, le terme $u_i$ désigne la $i$-ième composante du vecteur $u$. Nous mettons en garde sur le fait que

la négation de $u\le v$ n'est pas $u>v$.

En effet, l'inégalité $u>v$ traduit la propriété $u_i>v_i$ pour toute composante $i$. Par contre, la négation de $u\le v$, que l'on convient de noter $u\neg \le v$, exprime que l'inégalité $u_i>v_i$ ait lieu pour au moins une composante $i$.

{df} Une forme canonique ( resp. forme standard ) est un (PL) où toutes les contraintes sont des inégalités ( resp. égalités) et les variables sont astreintes à être positives. {df}

On a déjà expliqué qu'on peut supposer et sans perte de généralité, que les contraintes d'inégalité sont toutes de type '' ''. Par conséquent, on peut affirmer que tout (PL) sous forme canonique s'écrit sous la forme suivante :

$\{\begin{array}{c}\max (\text{ou}\min )[Z(x)=c^{*}x]\\ \mathrm{Ax}\le b\\ x\ge 0_{{ℝ}^p}\end{array}$

où $c\in {ℝ}^p$, $A$, matrice $(m,p)$ et $b\in {ℝ}^m$ sont fixés.

Le vecteur $x$ a $p$ composantes réelles $x_i$ et ${}^{}$ désigne l'opérateur transposé. Les inégalités

(i.e. $x\ge 0_{{ℝ}^p}$) s'appellent contraintes de positivité . Désormais, on décide de noter un (PL) sous forme canonique par (FC). Remarquer que les trois exemples précédents sont tous écrits sous forme canonique.

La mise sous forme standard d'un (PL) quelconque consiste à transformer les contraintes d'inégalités (mise à part les contraintes de positivité) en égalité tout en imposant aux variables d'être positives. Pour ce faire, on procède comme suit :

• A chaque contrainte de type '' '' (resp. '' ''), ajouter (resp. retrancher) une variable tout en lui imposant d'être positive. Celle-ci s'appelle variable d'écart .
• Remplacer chaque variable $x_i$ sans restriction de signe par la différence de deux variables positives : $x_i=x_i^{+}-x_i^{-}$ avec $x_i^{+}\ge 0$ et $x_i^{-}\ge 0$.
• Si une variable $x_i$ est négative, effectuer le changement de variable $x_{i\prime }=-x_i$.

Soit la forme canonique (FC) suivante :

max $Z=$
sous les contraintes




$x_1$ 0, $x_2$ 0

Les données de la forme standard de cette (FC) sont :

$M=$ $[]$, $b$ = $[]$ $c^{*}$ = $\left(\begin{array}{cccc},0& 0& 0& 0\end{array}\right)$

Exemple

On peut dire à juste titre que ce (PL) n'est pas une forme canonique car la première contrainte est une égalité et la troisième variable $x_3$ n'est pas astreinte à être positive. Pour la mise sous forme standard, la première contrainte, qui est déjà une égalité, reste inchangée. Pour la deuxième, on lui retranche une variable positive $x_4$, elle devient

Quant à la troisième contrainte, on lui ajoute une variable positive $x_5$ pour devenir Concernant la variable $x_3$ qui est sans restriction de signe, elle est remplacée par $x_3^{-x}{}_3{}^{-}$, avec $x_3^{+}\ge 0$ et $x_3^{-}\ge 0$. En conclusion, la forme standard associée à ce (PL) s'écrit

$\{\begin{array}{cc}\max [Z(x)=2x_1-x_2+5x_3^{+}-5x_3^{-}]& \\ x_1-2x_2=& 3\\ x_1-x_3^{+}+x_3^{-}-x_4=& -1\\ x_2+x_3^{+}-x_3^{-}+x_5=& 4\\ x=(x_1,x_2,x_3^{+},x_3^{-},x_4,x_5)\ge 0_{{ℝ}^6}.& \end{array}$

Les variables du (PL) initial s'appellent variables de décision , celles de la forme standard associée s'appellent variables structurelles .

L'écriture d'un (PL) sous forme standard est introduite tout simplement parce que l'algorithme du simplexe ne s'applique qu'aux formes standards. En d'autres termes,

pour résoudre un (PL) par le simplexe, il faut tout d'abord l'écrire sous forme standard.

Etant donné qu'on résoud le (PL) proprement dit et non la forme standard associée, la question naturelle qu'on se pose est de savoir comment retrouver une solution optimale du (PL) de départ à partir d'une solution optimale de sa forme standard . Le théorème suivant établit le lien entre une solution optimale d'un (PL) et celle de sa forme standard, et on se limite au cas où le (PL) considéré est une (FC).

Théorème

Ce théorème se généralise bien évidemment pour tout (PL) quelque soit son type d'écriture. A titre d'illustration, pour l'Exemple qui n'est pas sous forme canonique, si $(v_1,v_2,v_3,v_4,v_5,v_6)$ est une solution optimale de la forme standard associée, compte tenu des variables d'écarts et du changement de variable considérés, on peut dire que $(v_1,v_2,v_3-v_4)$ est une solution optimale du (PL) initial.

Exercice

Désormais, on note tout (PL) écrit sous forme standard par (FS). Par définition, l'écriture matricielle d'un problème (FS) possède la forme suivante :

$\text{(FS)}\{\begin{array}{c}\max (\text{ou}\min )[Z(y)=c^{*}y]\\ \mathrm{My}=b\\ y\ge 0_{{ℝ}^n}\end{array}$

où La matrice $M$ contient toujours plus de colonnes que de lignes (i.e. $n>m$) vu que le nombre de variables structurelles $n$ (variables de décision + variables d'écarts + variables dûes aux variables sans restriction de signe) dépasse le nombre de contraintes $m$. Sans perte de généralité, on suppose que la matrice $M$ est de rang $m$. Sinon,

1. ou bien il y a une (ou plusieurs) équation qui est combinaison linéaire des autres équations, qu'il faut alors enlever,
2. ou bien le système est incompatible et dans ce cas le système linéaire $\mathrm{My}=b$ n'admet aucune solution.

IV-4-1 Système de base

IV-4-2 Optimalité et base réalisable

IV-4-3 Base dégénérée

Notons par $M_i$ la $iieme$ colonne de $M$. Le vecteur colonne $\mathrm{My}$ s'écrit alors

$\mathrm{My}={\sum }_{i=1}^n{y}_i{M}_i$

où $y_i$ est $iieme$ composante de $y$. On appelle système de variables de base tout ensemble de $m$ variables distinctes $y_i$, $i\in J$, prises parmi $y_1,\dots ,y_n$, telles que le déterminant des vecteurs $M_i$, $i\in J$ est différent de zéro. On rappelle que l'entier $m$ désigne le nombre de contraintes d'égalités qui apparaissent dans (FS). La matrice carrée formée par les $m$ colonnes $M_i$, $i\in J$, s'appelle base et les variables $y_i$, $i\notin J$, s'appellent variables hors base . Autrement dit,

une base $B$ du problème (FS) n'est autre qu'une sous matrice carrée de $M$ d'ordre $m$ et inversible.

Pour mieux visualiser une telle base $B$, on effectue des permutations de colonnes de sorte que la base $B$ apparaisse sur les $m$ premières colonnes de $M$. Ainsi, on met $M$ sous la forme suivante :

$M=[BN],$

où $B=(M_i,i\in J)\in {\mathrm{GL}}_m(ℝ)$ et $N=(M_i,i\notin J)\in M_{m,n-m}$.

Les variables $y_i$, $i=1,\dots ,n$, peuvent aussi être classées selon $B$ et $N$ :

$y=({}_{y_N}^{y_B}),\text{où}{y}_B=(y_i,i\in J)\text{et}{y}_N=(y_i,i\notin J).$

Désormais, l'ensemble $J$ des indices de base sera noté par $J_B$ et son complémentaire par $J_N$. En respectant cette partition, le système $\mathrm{My}=b$ vérifie :

$\mathrm{My}=b\iff [BN]\left(\begin{array}{c}{y}_B\\ \end{array}\right)\iff {\mathrm{By}}_B+{\mathrm{Ny}}_N=b$

$\iff y_B=B^{-1}b-B^{-1}{\mathrm{Ny}}_N.$

Par suite, l'ensemble des solutions dans ${ℝ}^n$ du système linéaire $\mathrm{My}=b$ est égal à Parmi les solutions de ce système, nous distinguons les solutions dites de base pour lesquelles $y_N=0_N$ (on écrit $0_N$ à la place de $0_{R^{n-m}}$ pour dire que les variables hors base sont nulles). Une telle solution existe et elle vaut Cette solution de base est réalisable ( i.e. elle vérifie les contraintes $\mathrm{My}=b$ et $y\ge 0_{{ℝ}^n}$) si et seulement si Dans ce cas, on dit que la base $B$ est réalisable .

Noter que toute solution de base réalisable admet $(n-m)$ composantes nulles relatives aux variables hors base et que les autres composantes vérifient un système de Cramer d'ordre $m$.

Par analogie au Théorème , nous allons établir que lorsque (FS) admet une solution, on peut toujours chercher une solution optimale parmi les solutions de base réalisable.

Théorème

Remarque

Une solution de base réalisable $y=\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)$ est dite dégénérée , si en plus des $(n-m)$ composantes nulles relatives à $0_N$, il existe une composante du vecteur $B^{-1}b$ qui est nulle. Elle est non dégénérée dans le cas où toutes les composantes de $B^{-1}b$ sont non nulles et par suite strictement positives. De même, on dit qu'une base réalisable est dégénérée si la solution de base associée est dégénérée. Il est intéressant de noter qu'un point dégénéré est solution de plusieurs bases réalisables. En effet, tout vecteur colonne $u=B^{-1}b$ relatif à une base dégénérée $B$ admet au moins une coordonnée $u_{i_0}$, $i_0\in J_B$, qui est nulle. En considérant que $B=(M_i,i\in J_B)$, on obtient

$u=B^{-1}b\iff \mathrm{Bu}=b\iff {\sum }_{i\in J_B}{u}_i{M}_i=b$

$\iff {\sum }_{i\in J_B\backslash \{i_0\}}{u}_i{M}_i=b$

car $u_{i_0}=0.$ Dans la matrice $B$, nous allons remplacer le vecteur colonne $M_{i_0}$ par un autre vecteur $M_{j_0}$ pour $j_0\in J_N$ de sorte que la matrice $B\prime$ ainsi obtenue soit inversible. Il est clair que $u$ est solution du système linéaire $B\prime x=b$, étant donné que Cette solution est unique en raison de la régularité de la matrice $B\prime$. Donc, les deux bases réalisables $B$ et $B\prime$ donnent toutes les deux la même solution de base $\left(\begin{array}{c}u\\ 0_N\end{array}\right)$.

L'algorithme du simplexe est un procédé itératif qui progresse dans un sens évolutif : il passe d'une solution de base réalisable non optimale à une autre solution ayant une meilleure valeur d'objectif. De cette façon, on évite de parcourir toutes les solutions de base réalisable dont le nombre est en général prohibitif. Pour vérifier la non optimalité d'une solution, un simple test sera effectué. De plus, grâce à l'algorithme du simplexe, on sera capable de détecter, le cas échéant, que l'optimum est infini.

IV-5-1 Condition d'optimalité

IV-5-2 Amélioration de la fonction d'objectif

IV-5-3 Algorithme

IV-5-4 Règle de pivotage

La fonction d'objectif $Z(y)=c^{}y$ est entièrement définie par la donnée du vecteur $c=(c_i,i=1,\dots ,n)$. A chaque base $B=(M_i,i\in J_B)$, on note $c_B=(c_i,i\in J_B)$ et $c_N=(c_i,i\in J_N)$. D'une façon équivalente, le vecteur $c_B$ (resp. $c_N$) s'obtient à partir de $c$ en prenant les coordonnée $c_i$ relatives aux variables de base (resp. hors base) associée à la matrice $B$ (resp. $N$). Le classement du vecteur $c$ selon $J_B$ et $J_N$ donne $c=({}_{c_N}^{c_B})$. Naturellement, on dit qu'une base $B$ est optimale si la solution associée $y={(}_{0_N}^{B^{-1}b})$ est optimale.

Théorème

La condition d'optimalité $w_N^{*}\le 0_N^{*}$ peut être interprétée comme un test d'arrêt des itérations pour l'algorithme du simplexe. Il reste à décrire la technique qui permet de passer d'une solution de base réalisable non optimale à une autre solution de base réalisable ayant une meilleure valeur économique. Cette partie fera l'objet du paragraphe suivant.

Interprétation

Exercice

On se donne une base réalisable $B=(B_1,\dots ,B_m)$. Le vecteur $B_i$ désigne la $iieme$ colonne de $B$ qui est à fortiori une colonne de $M$. On note aussi $N_j$ la colonne d'indice $j$ de la matrice $N$. D'ailleurs, $N_j$ n'est autre ${\mathrm{Ne}}_j$ où $e_j$ est le $j$-ième vecteur de la base canonique de ${ℝ}^{n-m}$.

Théorème

Il est intéressant de remarquer que dans le cas où la base réalisable $B$ est non dégénérée, le paramètre est strictement positif. Sans aucun doute, le point construit $y^{(1)}$ possède, en cas de non dégénérescence, une valeur économique strictement meilleure que celle de $y^{(0)}$.

Dans la pratique, le choix de $w_s$ est souvent multiple, il se peut que plusieurs composantes $w_N^{}$ soient strictement positives. Etant donnée que la nouvelle solution $y^{(1)}$ vérifie :

$Z(y^{(1)})=Z(y^{(0)})\pm \lambda w_s$

il serait commode de choisir la plus grande composante $w_s$ de $w_N^{}$ strictement positive.

Il arrive aussi que le minimum soit atteint pour deux ou plusieurs coordonnées différentes. Dans ce cas de figure, on fixe comme critère de choix pour l'indice $r$, la première coordonnée trouvée $j$ qui réalise le minimum . Pour des raisons de stabilité numérique et par analogie avec la méthode de Gauss avec pivot partiel, un autre critère de choix est souvent considéré. Il consiste à choisir $r$ de façon à ce que ${\gamma }_r$ soit le plus élevé parmi les éléments ${\gamma }_i$ strictement positifs. Le critère qui fixe le choix de $w_s$ et de l'indice $r$ s'appelle règle de pivotage . La règle qui prend systématique la plus grande valeur positive de $w_N^{}$ s'appelle règle du meilleur coût marginal , c'est cette règle que l'on adopte dans ce cours.

Dans ce chapitre, les données mise en oeuvre dans l'algorithme du simplexe seront représentées dans un tableau. A chaque itération correspond un tableau appelé tableau simplexe . Des formules itératives liant les éléments d'un tableau au tableau subséquent seront également établies.

V-1 Tableau simplexe

V-2 Application

V-3 Sommets et solutions de base

V-4 Formules itératives

V-5 Algorithme du simplexe standard

Les éléments qui interviennent dans l'algorithme du simplexe peuvent être récapitulés dans ce qui suit.

• Les variables de base et les variables hors base. La base réalisable $B$ et la matrice $N$ seront immédiatement identifiées à partir des variables de base et hors base.
• La solution $y=\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)$ associée à la base réalisable $B$. Puisque $y_N=0_N$, on ne retient que le vecteur $y_B=B^{-1}b$.
• Le vecteur $w_N^{*}=\pm [c_N^{*}-c_B^{*}{B}^{-1}N]$ pour tester l'optimalité.
• La matrice $B^{-1}N$ afin de calculer $w_N^{}$ et le coefficient .
• La valeur de la fonction $Z$ au point $y=\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)$ qui est égale à
  $Z(y)=c_B^{}{y}_B$

A chaque base réalisable $B$ correspond une itération de l'algorithme du simplexe. Pour rendre pratique l'application manuelle de l'algorithme du simplexe, les éléments décrits ci-dessus sont regroupés dans un tableau de la manière suivante :

$y_{i_{m+1}}\cdots y_{i_n}$
$B^{-1}N$	$B^{-1}b$	$y_{i_1}$ $y_{i_m}$
$w_N^{*}$	$Z$

Les coordonnées $y_{i_1},\dots ,y_{i_m}$ correspondent aux variables de base, et les coordonnées $y_{i_{m+1}},\dots ,y_{i_n}$ correspondent aux variables hors base. Le terme $Z$ désigne la valeur de la fonction d'objectif $Z$ au point réalisable $\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)$. D'après l'indexation des variables de base, on a :

${\displaystyle Z=\sum _{j=1}^m{c}_{i_j}{y}_{i_j}}\text{, avec}{y}_{i_j}=(B^{-1}b{)}_j.$

Comme application de l'algorithme du simplexe, nous allons résoudre les trois exemples du premier chapitre en utilisant les tableaux simplexe.

V-2-1 Exemple 1

V-2-2 Exemple 2

V-2-3 Exemple 3

Reprenons l'Exemple 1 :

• On écrit ce probème sous forme standard.
  En ajoutant les variables d'écart, on obtient :

  $M=\left(\begin{array}{ccccc}2& 1& 1& 0& 0\\ 1& 2& 0& 1& 0\\ 0& 1& 0& 0& 1\end{array}\right),$

  $c^{*}=\left(\begin{array}{ccccc}4& 5& 0& 0& 0\end{array}\right)\text{et}b=\left(\begin{array}{c}8\\ 7\\ 3\end{array}\right).$

• On cherche un système de variables de base réalisable
  Il est clair que $\{y_3,y_4,y_5\}$ forme un système de variables de base réalisable. La base associée est $B=I_3$, elle vérifie bien

  $B^{-1}b=I_{3}b=b\ge 0_{{ℝ}^3}.$

  Pour cette base, on obtient :

  $B^{-1}N=N=\left(\begin{array}{cc}2& 1\\ 1& 2\\ 0& 1\end{array}\right),$

  $w_N^{*}=c_N^{*}=\left(\begin{array}{cc}4& 5\end{array}\right)$

  car $c_B^{}=0_B^{}$ et

  $Z\leftarrow Z(0,0,8,7,3)=0.$

  Rappelons que les coordonnées de chaque solution de base réalisable $\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)$ sont classées selon $B$ et $N$. Pour la base $B=I_3$, si on écrit les coordonnées de la solution réalisable $\left(\begin{array}{c}{B}^{-1}b\\ 0_N\end{array}\right)=\left(\begin{array}{c}b\\ 0_N\end{array}\right)$ dans l'ordre $y_i$, $i=1,\dots ,5$, on obtient exactement le point $(0,0,8,7,3)$.

• Itération 1

  $y_1$	$y_2$
  $2$	$1$	$8$	$y_3$
  $1$	$2$	$7$	$y_4$
  $0$	1	$3$	$y_5$
  $4$	5	$0$

  Le vecteur ligne $w_N^{*}=(45)$ n'est pas négatif, il contient deux composantes strictement positives. Il a été convenu de choisir la plus grande qui est 5. Pour distinguer notre choix, on décide de l'écrire en gras. Faisant référence aux notations utilisées dans le Théorème , on a :

  $w_s=5\text{et}\gamma =B^{-1}{N}_s=\left(\begin{array}{c}1\\ 2\\ 1\end{array}\right).$

  Donc, au cours de l'itération suivante, la variable hors base qui se situe au niveau de $w_s$ va devenir une variable de base. D'après le tableau ci-dessus, il s'agit de la variable $y_2$. Pour déterminer la variable qui prend place, il va falloir calculer le paramètre et en déduire l'indice $r$. D'après le même tableau, on a :

  $\lambda =\min \{{\displaystyle \frac{8}{1}},{\displaystyle \frac{7}{2}},{\displaystyle \frac{3}{1}}\}=3$

  et donc $r=3.0$ L'indice $r$ correspond alors à la variable $y_5$. On décide de mettre en gras l'élément ${\gamma }_r$ qui a permis de réaliser le minimum

  $\lambda ={\displaystyle \frac{(B^{-1}b{)}_r}{{\gamma }_r}}.$

  En résumé, lorsqu'on écrit en gras une composante $w_s$ de $w_N^{}$, cela signifie que la variable, figurant sur la même colonne que $w_s$ du tableau simplexe, entre dans la base. Inversement, l'identification de ${\gamma }_r$ permet de décider que la variable, située sur la même ligne que ${\gamma }_r$ sort de la base. Naturellement, ces deux variables s'appellent respectivement variable entrante et variable sortante .

• Itération 2
  A ce stade de calcul, la base réalisable $B\prime$ est associée aux variables $\{y_3,y_4,y_2\}$. Pour la prochaine itération, on aura besoin de $B″$ à la place de $B\prime$. Afin de ne pas encombrer le texte par les notations, il est naturel de garder les mêmes symboles $B$, $N$ et pour toutes les itérations du simplexe. En tenant compte de l'ordre des indices $J_B=\{3,4,2\}$ des variables de base et de $J_N=\{1,5\}$, on obtient

  $B=\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 2\\ 0& 0& 1\end{array}\right)\text{et}N=\left(\begin{array}{cc}2& 0\\ 1& 0\\ 0& 1\end{array}\right).$

  Par un simple calcul, on vérifie les égalités suivantes :

  $B^{-1}N=\left(\begin{array}{cc}2& -1\\ 1& -2\\ 0& 1\end{array}\right),B^{-1}b=\left(\begin{array}{c}5\\ 1\\ 3\end{array}\right)\text{et}{w}_N^{*}=\left(\begin{array}{cc}4& -5\end{array}\right).$

  Le tableau simplexe relatif à cette itération est

  $y_1$	$y_5$
  $2$	$-1$	$5$	$y_3$
  1	$-2$	$1$	$y_4$
  $0$	$1$	$3$	$y_2$
  4	$-5$	$15$

  Noter que le vecteur $B^{-1}b$ peut être calculé aussi via la formule

  $(B^{-1}b{)}_i$		$\{\begin{array}{cc}(B^{-1}b{)}_i-\lambda {\gamma }_i& \text{pour}i\ne r\\ \lambda & \text{pour}i=r\end{array}$
  	=	$\left(\begin{array}{c}8-3\times 1\\ 7-3\times 2\\ \lambda \end{array}\right)$
  	=	$\left(\begin{array}{c}5\\ 1\\ 3\end{array}\right)$

  De même, la valeur $Z=15$ qui correspond à $Z(0,3,5,1,0)$ peut être obtenue à travers le résultat $Z\leftarrow Z+\lambda w_s=0+3\times 5=15.$ Ces deux constatations restent valables pour les itérations qui suivent et pour n'importe quel exemple.

  Pour ce tableau, le vecteur $w_N^{}$ admet une seule composante strictement positive qui est $w_s=4$. Donc, la variable $y_1$ entre dans la base au cours de l'itération 3. En ce qui concerne le nouveau paramètre , on a :

  $\gamma =B^{-1}{N}_s=\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right),\text{et par suite}\lambda =\min \{{\displaystyle \frac{5}{2}},{\displaystyle \frac{1}{1}}\}=1.$

  Ainsi, la variable $y_4$ devient hors base. Il est intéressant de noter que les matrices $B$ et $N$ peuvent être déduites du tableau simplexe à partir des variables de base et des variables hors base. Dans toute la suite et lors de l'exécution d'une itération simplexe, seul le tableau simplexe sera donné. Bien entendu, on précisera en gras les éléments $w_s$ et ${\gamma }_r$ et on calculera le coefficient , à chaque fois que cela s'avère nécessaire.

• Itération 3

  $y_4$	$y_5$
  $-2$	3	$3$	$y_3$
  $1$	$-2$	$1$	$y_1$
  $0$	$1$	$3$	$y_2$
  $-4$	3	$19$

  $\lambda =\min \{{\displaystyle \frac{3}{3}},{\displaystyle \frac{3}{1}}\}=1.$

• Itération 4

  $y_4$	$y_3$
  $-{\displaystyle \frac{2}{3}}$	${\displaystyle \frac{1}{3}}$	$1$	$y_5$
  $-{\displaystyle \frac{1}{3}}$	${\displaystyle \frac{2}{3}}$	$3$	$y_1$
  ${\displaystyle \frac{2}{3}}$	$-{\displaystyle \frac{1}{3}}$	$2$	$y_2$
  $-2$	$-1$	$22$

• Conclusion
  On a

  $w_N^{*}=(-2-1)\le (00)$

  donc le Théorème assure que $(3,2,0,0,1)$ est une solution optimale pour (FS). D'après le Théorème , le point $(3,2)$ est optimal pour notre (PL) de départ. Il réalise une valeur maximale de $Z$ égale à $22$.