PROGRAMMATION LINEAIRE   FORME USUELLE D'UN PL   FORME NON USUELLE D'UN PL   METHODE DES PENALITES   METHODE DES DEUX PHASES  ( SUITE )

4) METHODE DES DEUX PHASES

Cette méthode permet de tenir compte des variables artificielles. Dans une première phase on rend nulles les variables artificielles : pour cela on minimise la somme des variables artificielles sous les contraintes du programme initial. Comme les variables artificielles sont forcément positives ou nulles le minimum est atteint quand elles sont nulles (si ce n'est pas le cas, c'est qu'il n'y a pas de solution). Une fois les variables artificielles annulées, on a une solution de base admissible qui nous permet dans une seconde phase de résoudre le programme initial.

Soit à résoudre le programme linéaire suivant
          x1 + x2 ³ 6
          x1 ³ 4
          x2 £ 3
Max  z = 5 x1 + 7 x2
         x1 ³ 0 ;  x2 ³ 0

PHASE 1

* Forme standard
              1 x1 + 1 x2 - 1 t1 + 0 t2 + 0 t3 + 1 e1  +  0 e2 = 6
              1 x1 + 0 x2 + 0 t1 - 1 t2 + 0 t3 +  0 e1  +  1 e2 = 4
              0 x1 + 1 x2 + 0 t1 + 0 t2 +1 t3 +  0 e1  +  0 e2 = 3
Min   z' = e1 +  e2
                     x1 ³ 0 ;  x2 ³ 0 ;  t1 ³ 0 ;  t2 ³ 0;  t3 ³ 0 ; e1 ³ 0 ;  e2 ³ 0

* Tableau 0

HB B	x1	x2	t1	t2	t3	e1	e2	C
e1	1	1	-1	0	0	1	0	6
e2	1	0	0	-1	0	0	1	4
t3	0	1	0	0	1	0	0	3
D'	0	0	0	0	0	1	1	0

La ligne D' donne les coefficients de la fonction économique, mais pas les valeurs marginales des variables HB; de plus les variables artificielles sont dans la base et devraient donc avoir des valeurs marginales nulles.
De manière générale, dans tout tableau du simplexe, si on note ck les coefficients de la fonction économique et aik les coefficients du tableau,
les valeurs marginales mj sont
     - nulles pour les variables dans la base
     - égales à cj - S aik ck   , la sommation étant faite sur toutes les variables de la base (les lignes du tableau)
la valeur de la fonction économique est égale à - S aik

d'où le tableau 0 (les calculs annexes ont été rajoutés)

cj	0	0	0	0	0	1	1				aik ck
HB B	x1	x2	t1	t2	t3	e1	e2	C	ck		x1	x2	t1	t2	C
e1	1	1	-1	0	0	1	0	6	1		1	1	-1	0	6
e2	1	0	0	-1	0	0	1	4	1		1	0	0	-1	4
t3	0	1	0	0	1	0	0	3	0		0	0	0	0	0
D	-2	-1	1	1	0	0	0	-10		S aik ck	2	1	-1	-1	10

* Tableau 1
Puisqu'on recherche un minimum, la variable entrante est celle qui a le plus grand coefficient négatif, c.à.d. x1.

HB B x1  x2 t1  t2  t3 e1  e2 C  R  e1 1  1 -1 0 0 1  0 6  6  e2 1 0 0 -1 0 0  1 4 4   t3  0  1 0 0 1 0 0 3 + infini   D -2  -1 1 1 0  0 0 -10	variable sortant
variable entrant

la variable artificielle sortant de la base, va prendre une valeur nulle, ce que l'on désire; il n'est donc pas question de la faire rentrer de nouveau dans la base et on peut donc supprimer la colonne correspondante dans la suite des itérations, d'où le tableau 1
  

* Tableau 2

HB B x1  x2 t1  t2  t3 e1     C  R  e1 0 1 -1 1 0 1     2 2  x1 1 0 0 -1 0 0   4 + infini   t3  0  1 0 0 1 0     3 3   D 0 -1 1 -1 0  0     -2	variable sortant
variable entrant

d'où le tableau 2

HB B	x1	x2	t1	t2	t3			C
x2	0	1	-1	1	0			2
x1	1	0	0	-1	0			4
t3	0	0	1	-1	1			1
D	0	0	0	0	0			0

L'optimum est atteint. Une solution de base admissible est donc x1 = 4 ; x2 = 2 ; t1 = 0 ; t2 = 0 ; t3 = 1

PHASE 2

* Tableau 0

A partir de cette solution de base admissible, on poursuit les itérations en reprenant la fonction objectif initiale
Max  z = 5 x1 + 7 x2       
La ligne D des valeurs marginales est bien sûr modifiée puisqu'on n'a plus la même fonction économique

cj	5	7	0	0	0				aik ck
HB B	x1	x2	t1	t2	t3	C	ck		t1	t2	C
x2	0	1	-1	1	0	2	7		-7	7	14
x1	1	0	0	-1	0	4	5		0	-5	20
t3	0	0	1	-1	1	1	0		0	0	0
D	0	0	7	-2	0	-34		S aik ck	-7	2	34

d'où le tableau 0

HB B x1  x2 t1  t2  t3 C  R  x2 0  1 -1 1 0 2 -2  x1 1 0 0 -1 0 4 + infini   t3  0  0 1 -1 1 1 1   D 0 0 7 -2 0 -34	variable sortant
variable entrant

* Tableau 1

HB B	x1	x2	t1	t2	t3	C
x2	0	1	0	0	1	3
x1	1	0	0	-1	0	4
t1	0	0	1	-1	1	1
D	0	0	0	5	-7	-41

La solution optimale obtenue est donc infinie puisqu'une variable HB a une valeur marginale positive et tous ses coefficients négatifs ou nuls dans le tableau.
Il suffit de prendre x1 infini et  x2 £ 3