Méthode M

➢ Rappelons que l’application de l’algorithme du simplexe à la

résolution d’un programme linéaire suppose la connaissance
préalable d’une solution de base réalisable de départ !!

➢ La méthode M permet d’obtenir une solution de base réalisable de

départ lorsque celle-ci ne peut être calculée d’une manière simple

➢ Elle repose sur l’introduction des variables artificielles et décrite par

l’organigramme suivant :
Organigramme de la méthode M

Mettre les contraintes

sous forme d’égalité

Rendre positif le deuxième

membre des contraintes
 Introduire des variables artificielles
dans les contraintes :

n
 aij x j + vi = bi
 j =1
*
 x j  0 ; j = 1,..., n
 vi  0 ; i = 1,..., m

 n m
Résoudre le PL :
Max  c j x j −  Mvi
j =1 i =1
sous les contraintes (*)
(M>0 assez grand)

vi = 0 FIN
non
Pour tout i = 1,..., m Pas de solution
réalisable.

oui
La solution optimale du PL
de départ est atteinte.
Exemple :

Soit le programme linéaire :

Max ( Z = 5 x1 + 7 x2 ) sous les contraintes

 x1 + x2  6

x  4
 1

 x2  3

 x1 ; x2  0

Max ( Z = 5 x1 + 7 x2 ) sous les contraintes

−t1 + x1 + x2 = 6

 − t2 + x1 =4


 t3 + x2 = 3

 x1 ; x2 ; t1 ; t2 ; t3  0


Puisque nous ne disposons pas de solution de base réalisable de départ,

nous allons introduire des variables artificielles en nombre suffisant. Le
programme linéaire à résoudre est donc le suivant :
Max ( Z = 5 x1 + 7 x2 − Mv1 − Mv2 ) sous les contraintes

v1 + − t + x +x =6

1 1 2


 v2 + −t + x =4

2 1


 t + x =3
 3 2



v1 ; v2 ; x ; 1
x 2
;t 1
; t 2
; t = 0 3

Maintenant nous disposons d’une solution de base réalisable.

On applique alors l’algorithme du simplexe :
 variables de base

-M -M 0 0 0 5 7

Base cJ xJ v1 v2 t1 t2 t3 x1 x2
J
v1 -M 6 1 0 -1 0 0 1 1
v2 -M 4 0 1 0 -1 0 1 0
t3 0 3 0 0 0 0 1 0 1

10 0 0 -M -M 0 5+ 7+
M 2M M
 variables de base

-M -M 0 0 0 5 7

Base cJ xJ v1 v2 t1 t2 t3 x1 x2
J
v1 -M 2 1 -1 1 0 0 1
x1 5 4 0 0 -1 0 1 0
t3 0 3 0 0 0 1 0 1

-20 0 -M 5+ 0 0 7+
+2M M
M
 variables de base

-M -M 0 0 0 5 7

Base cJ xJ v1 v2 t1 t2 t3 x1 x2
J
x2 7 2 -1 1 0 0 1
x1 5 4 0 -1 0 1 0
t3 0 1 1 -1 1 0 0

-34 7 -2 0 0 0
 variables de base

-M -M 0 0 0 5 7

Base cJ xJ v1 v2 t1 t2 t3 x1 x2
J
x2 7 3 0 0 1 0 1
x1 5 4 0 -1 0 1 0
t1 0 1 1 -1 1 0 0

-41 0 5 -7 0 0

La solution optimale est donc infinie .

 Programme primal et dual

Soit le programme linéaire (P) suivant :

n
Max ( Z1 =  cjxj) sous les contraintes :
j = 1

 n
 aij x j  bi ; i = 1,....m
 j =1
( P)

 xj  0 ; j = 1,...., n


Ce programme sera appelé programme primal.

Par définition, le dual (D) de ce PL est :

 n
Min ( Z 2 =  b j y j ) sous les contraintes :
i =1


 aij y j  c j ; j = 1,....m
n

i =1

( D)


 y  0i
; i = 1,...., n
Exemple

Max ( Z1 = 3x − 2 y ) sous les contraintes

 x +y 3


( P)− x − y  −2

 x ; y 0

Min ( Z 2 = 3x − 2 y ) sous les contraintes

 x − y 3



( D) x − y  −2


 x ; y  0
 2

0 2 3
Domaine réalisable
du primal

Z
Domaine réalisable
du dual
−3
Théorème fondamental de la dualité

Soit (P) un programme linéaire admettant une solution optimale.

Le dual (D) de (P) est réalisable et admet une solution optimale.

D’autre part la valeur optimale de (P) est égale à la valeur optimale de

de (D) :

Max 𝑍1 = Min 𝑍2
 Passage du dernier tableau simplexe du primal au dernier
tableau simplexe du dual

➢ Lorsque le programme linéaire primal (P) admet une solution optimale finie,
il
est facile de construire le dernier tableau simplexe de son dual (D) à partir du
dernier tableau simplexe du primal (et vice-versa).

➢ Il existe en effet une relation très étroite entre les deux tableaux
simplexe finals que nous allons décrire ci-dessous. Au signe près ;
 x j u j
* ligne  en base = colonne  hors − base
ti  yi

x j u j
* colonne  hors − base = ligne  en base
ti  yi

* ligne cj − zj = colonne yJ '

* colonne xJ = ligne z 'i −bi

 Exemple précédent

Max ( Z = x1 + 3 x2 ) sous les contraintes

 x1 + x2  14

− 2 x1 + 3 x2  12


 2 x1 − x2  12


 x1 ; x2  0
Tableau optimal de (P)
𝑦1 𝑦2 𝑦3 𝑢1 𝑢2

base xJ t1 t2 t3 x1 x2
J
x1 6 3/5 -1/5 0 1 0
x2 8 2/5 1/5 0 0 1
t3 8 -4/5 3/5 1 0 0

-30 -9/5 -2/5 0 0 0

Tableau optimal de son dual (D)

base y1 y2 u1 u2 y3
J' yJ '
y1 9/5 1 0 -3/5 -2/5 4/5

y2 2/5 0 1 1/5 -1/5 -3/5

-30 0 0 6 8 8
 Règles de transformation du primal vers le dual et inversement

Problème de maximisation Problème de minimisation

e
Variable x j  0 j contrainte de type 
e
Variable x j  IR j contrainte de type =
e
Variable x j  0 j contrainte de type 
e
i contrainte de type  Variable yi  0
e
i contrainte de type = Variable yi  IR
e
i contrainte de type  Variable yi  0