Chapitre 8 • La pro gram ma tion linéaire
336
On com plète cette base en intro dui sant dans chaque contrainte de type (Q) ou (R),
une nou velle variable, de coef fi cient égal à 1, nom mée « variable arti fi cielle » dont
la colonne asso ciée est uni taire.
Ainsi pour notre exemple, en notant x ar et x as les deux variables arti fi cielles néces
saires pour consti tuer une base de matrice B 5 I, il vient :
d
x 1 1 2x 2 1 x 3 1 x 1
5 5
2x 1 1 x 2 1 x 3
2 x 2 1 x ar
5 1
x 1 1 x 2
1 x as 5 4
x 1 , x 2 , x 3 , x 1 , x 2 , x ar , x as > 0
Les variables arti fi cielles, comme les autres variables du pro gramme linéaire sont
posi tives ou nulles. Cepen dant remar quons que :
– si x ar n’est pas nulle, on a : 2x 1 1 x 2 1 x 3 2 x 2 2 1 et que,
– si x as n’est pas nulle, on a : x 1 1 x 2 2 4.
Ainsi la positivité d’une variable arti fi cielle fait que la contrainte dans laquelle elle a
été intro duite est vio lée... Indi quons main te nant com ment trai ter un tel cas :
8.5.5 Méthode des deux phases
Il convient alors, par tant d’une base com por tant une ou plu sieurs variables arti
fi cielles, d’obte nir, en ité rant l’algo rithme du sim plexe, si pos sible une base sans
variable arti fi cielle (dans cette solu tion de base les variables arti fi cielles seront nulles
car hors base, et l’on obtien dra un som met admis sible du polyèdre d).
Pour tenter d’atteindre ce but, on subs ti tue à la fonc tion éco no mique z, une autre
fonc tion éco no mique z r qui est la somme des variables arti fi cielles (zr 5 x ar 1 x as )
dans l’exemple. L’objec tif sera de minimi ser z r. À l’opti mum de ce nou veau pro
gramme linéaire, deux cas sont pos sibles :
Puisque pour toute solu tion admis sible, z r est posi tif ou nul :
– soit z r 5 0 : on a obtenu alors un som met du polyèdre d, à par tir duquel on reprend
la réso lu tion du PL ini tial (donc avec la fonc tion éco no mique z, à maxi mi ser) ;
– soit z r . 0 : toute base admis sible du nou veau PL com porte au moins une variable
arti fi cielle de valeur stric te ment posi tive ; alors le PL d’ori gine est impos sible (le
polyèdre d est vide : les contraintes sont contra dic toires).
Ainsi, pour l’exemple, il convient d’abord d’expri mer la fonc tion éco no mique z r en
fonc tion des variables hors base (sachant que la base ini tiale est for mée des variables
x 1 , x ar et x as ) : zr 5 x ar 1 x as 5 (1 2 2x 1 2 x 2 2 x 3 1 x 2 ) 1 (4 2 x 1 2 x 2 ), soit :
zr 5 5 2 3x 1 2 2x 2 2 x 3 1 x 2 . On maxi mi sera donc :
zs 5 2z r 5 25 1 3x 1 1 2x 2 1x 3 2 x 2 .
336
On com plète cette base en intro dui sant dans chaque contrainte de type (Q) ou (R),
une nou velle variable, de coef fi cient égal à 1, nom mée « variable arti fi cielle » dont
la colonne asso ciée est uni taire.
Ainsi pour notre exemple, en notant x ar et x as les deux variables arti fi cielles néces
saires pour consti tuer une base de matrice B 5 I, il vient :
d
x 1 1 2x 2 1 x 3 1 x 1
5 5
2x 1 1 x 2 1 x 3
2 x 2 1 x ar
5 1
x 1 1 x 2
1 x as 5 4
x 1 , x 2 , x 3 , x 1 , x 2 , x ar , x as > 0
Les variables arti fi cielles, comme les autres variables du pro gramme linéaire sont
posi tives ou nulles. Cepen dant remar quons que :
– si x ar n’est pas nulle, on a : 2x 1 1 x 2 1 x 3 2 x 2 2 1 et que,
– si x as n’est pas nulle, on a : x 1 1 x 2 2 4.
Ainsi la positivité d’une variable arti fi cielle fait que la contrainte dans laquelle elle a
été intro duite est vio lée... Indi quons main te nant com ment trai ter un tel cas :
8.5.5 Méthode des deux phases
Il convient alors, par tant d’une base com por tant une ou plu sieurs variables arti
fi cielles, d’obte nir, en ité rant l’algo rithme du sim plexe, si pos sible une base sans
variable arti fi cielle (dans cette solu tion de base les variables arti fi cielles seront nulles
car hors base, et l’on obtien dra un som met admis sible du polyèdre d).
Pour tenter d’atteindre ce but, on subs ti tue à la fonc tion éco no mique z, une autre
fonc tion éco no mique z r qui est la somme des variables arti fi cielles (zr 5 x ar 1 x as )
dans l’exemple. L’objec tif sera de minimi ser z r. À l’opti mum de ce nou veau pro
gramme linéaire, deux cas sont pos sibles :
Puisque pour toute solu tion admis sible, z r est posi tif ou nul :
– soit z r 5 0 : on a obtenu alors un som met du polyèdre d, à par tir duquel on reprend
la réso lu tion du PL ini tial (donc avec la fonc tion éco no mique z, à maxi mi ser) ;
– soit z r . 0 : toute base admis sible du nou veau PL com porte au moins une variable
arti fi cielle de valeur stric te ment posi tive ; alors le PL d’ori gine est impos sible (le
polyèdre d est vide : les contraintes sont contra dic toires).
Ainsi, pour l’exemple, il convient d’abord d’expri mer la fonc tion éco no mique z r en
fonc tion des variables hors base (sachant que la base ini tiale est for mée des variables
x 1 , x ar et x as ) : zr 5 x ar 1 x as 5 (1 2 2x 1 2 x 2 2 x 3 1 x 2 ) 1 (4 2 x 1 2 x 2 ), soit :
zr 5 5 2 3x 1 2 2x 2 2 x 3 1 x 2 . On maxi mi sera donc :
zs 5 2z r 5 25 1 3x 1 1 2x 2 1x 3 2 x 2 .