Plan du cours

Partie I : Programmation Linéaire

1. Introduction à la programmation linéaire.
2. Théorie de la programmation linéaire.
3. Algorithme primal du simplexe à une ou deux phases.
4. Dualité en PL.
5. Etude de sensibilité et techniques de post-optimisation.
Partie II: Théorie des graphes
1. Eléments de la théorie des graphes.
2. Problèmes d’arbre couvrant de poids minimum et de plus court
chemin.
3. Problème d’ordonnancement et de gestion de projet.

2014-15
1

Chapitre 4: Dualité en programmation linéaire

Soit le programme linéaire primal (PLP) donné sous la forme de PLC suivante:
Max Z = cx
PLC: s.c. Ax ≤ b Où: c = (c1,c2,..cn) et bT = (b1,b2,..bm) et

x≥0 xT = (x1,x2,..xn) et A = (ai,j)1 ≤ i ≤m,1 ≤j ≤n

Pour tout i  1 ,..., m a i ,1 x 1  a i , 2 x 2 .....  a i , n x n  b i

En multipliant les contraintes par yi ≥ 0 et en faisant la somme:
m m m m


i 1
( y i a i ,1 ) x 1   ( y i a i , 2 ) x 2  ....  ( y i a i , n ) x n 
i 1 i 1

i 1
y ibi
m

Soit le polyèdre c j  
i1
y ia i, j ,1  j  n

xi ≥0, i=1,2,…n  Z  c 1 x 1  .. c n x n 
m m m

 i1
( y ia i ,1 ) x 1  .... i 1
( y ia i,n ) x n  i1
y ib i

1
 Chapitre 4: Dualité en programmation linéaire

Soit le programme linéaire primal (PLP) contenant des inégalités (≤ ou ≥) et des égalités
yi  0
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
yi  0
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
y i  IR
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
En faisant la somme
m m m m


i 1
( y i a i ,1 ) x 1   ( y i a i , 2 ) x 2  ....  ( y i a i , n ) x n 
i 1 i 1
 i 1
y ibi
m
Dans le polyèdre c j   y ia i , j ,1  j  n xi ≥0 i=1,2,…n 
i 1

m m m
Z  c 1 x 1  .. c n x n  
i1
( y ia i ,1 ) x 1  .... 
i 1
( y ia i,n )x n  
i1
y ib i
3

Chapitre 4: Dualité en programmation linéaire

Soit le programme linéaire primal (PLP) contenant des inégalités (≤ ou ≥) et des égalités
yi  0
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
yi  0
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
y i  IR
a i ,1 x 1  .....  a i , n x n  b i y i a i ,1 x 1  ....  y i a i , n x n  y i b i
En faisant la somme
m m m m

i 1
( y i a i ,1 ) x 1   ( y i a i , 2 ) x 2  ....  ( y i a i , m ) x m 
i 1 i 1
i 1
y ibi
m

Dans le polyèdre
 i 1
y ia i, j  c j , 1  j  n , x j  0
m

 i 1
y ia i, j  c j , 1  j  n , x j  0
n m m m
Z  
i1
cixi  i 1
( y ia i ,1 ) x 1  .... i 1
( y ia i,n )x n  
i1
y ib i  W
4

2
 Chapitre 4: Dualité en programmation linéaire

m m m
Z  
i1
( y ia i ,1 ) x 1  ....  i1
( y ia i,m )x m  
i1
y ib i  W
Zopt Wopt
Contraintes sur x Contraintes sur y

Z W
Pour trouver la borne supérieure Wopt, il faut résoudre le PL suivant:
m

 Min W  i  1
y i b i
 m
 
  i  1
y i a i ,1  ,  , ou  c 1
 
( PLD )   .
 sc :  .
 
  .
m
 
   y i a i ,n  ,  , ou  c n
 i  1

Ce problème est appelé problème linéaire dual (PLD) du PLC de départ

5

Chapitre 4: Dualité en programmation linéaire

 Tout PLC d’un problème linéaire primal (PLP) peut être transformé en un
programme dual (PLD)
 Max Z  cx  Min W  yb
( PLP )  ( PLD ) 
 sc sur x  sc sur y

Exemple: Transformer le PL suivant sous forme de PLD et résoudre

graphiquement les deux PL,

 Max Z  x1  x 2
  x1  x 2  2
  2 x  x
( PLC )  1 2  5
sc : 
 x1  0
 
 x 2  0
 
6

3
 Chapitre 4: Dualité en programmation linéaire

Exemples
max z = 2x1 + x2 min w = 2y1 + 3 y2 + y3
s.c. x1 + x2 = 2 s.c. y1 + 2 y2 + y3  2
2 x1 - x2  3 y1 - y2 - y3 = 1
x1 - x2  1 y1 IR, y2  0, y3  0
x1  0, x2 IR

min z = 5x1 - 6 x2 + 7 x3 + x4 max w = -7y1 + 14 y2 – 3y3

s.c. x1 + 2 x2 - x3 - x4 = -7 s.c. y1 + 6y2 – 2y3  5
6 x1 - 3x2 + x3 + 7 x4  14 2y1 – 3y2 – 17 y3  -6
-2 x1 -17 x2 + 4 x3 + 2 x4  -3 -y1 + y2 + 4y3 = 7
x1 0 , x2  0; x3 IR, x4 IR -y1 + 7y2 + 2y3 = 1
y1 IR, y3  0, y2  0 7

Chapitre 4: Dualité en programmation linéaire

Règles de dualisation Remarques:

1/ Le sens d’optimisation est toujours
• Problème de Max  Problème de Min
inversé.
• xj ≥ 0  jéme contrainte de type « ≥ » 2/ Si un PL a n variables et m
• xj IR  jéme contrainte de type « = » contraintes, son dual a m variables et
• xj ≤ 0  jéme contrainte de type « ≤ » n contraintes.
3/ Chaque variable du dual
• iéme contrainte de type « ≤ »  yi ≥ 0
correspond à une contrainte du
• iéme contrainte de type « = »  yi IR problème de départ, et
• iéme contrainte de type « ≥ »  yi ≤ 0 réciproquement.
4/ Le dual du dual est le primal.

4
 Chapitre 4: Dualité en programmation linéaire

Théorème de Dualité faible:

Soit x une solution admissible d’un PL canonique et y une solution admissible de
son dual alors: cx ≤ yb.
Preuve:  Max Z  cx  Min W  yb
 sc sur x  sc sur y
( PLC )  ( PLD ) 
 x  ,  , ou  0  y  ,  , ou  0
m m m
Z  c 1 x 1  .. c n x n  
i1
( y ia i ,1 ) x 1  .... 
i 1
( y ia i,m )x m  
i1
y ib i

Donc: cx ≤ (yA).x = y(Ax) ≤yb

Corollaire: Soit x une solution admissible de (PLP) de valeur Z et y une solution admissible
de (PLD) de valeur W. Si Z = W alors x et y sont optimales pour leurs problèmes respectifs.

Chapitre 4: Dualité en programmation linéaire

Théorème de dualité forte:

Si un programme linéaire standard possède une solution optimale x* = (x*D| x*E) de
valeur Z*=cDx*D alors son dual possède aussi une solution optimale y* = (y*D| y*E) de
valeur W*=y*Db = Z*.
Remarque: Si un PL possède une solution optimale finie, il en est toujours de même pour
son dual. En revanche, s’il ne possède pas d’optimum fini, son dual ne peut posséder de
solutions admissibles sans contredire le théorème de dualité faible.
Théorème des écarts complémentaires:
Soit x = (xD|xE) une solution admissible d’un PL standard et y = (yD|yE) une solution
admissible de son dual. Ces solutions sont optimales pour leur PL respectif ssi:
yDxE = 0 et yExD = 0

10

5
 Chapitre 4: Dualité en programmation linéaire

Résolution du problème dual:

1/ A tout tableau est associé non seulement une base primale et sa solution basique
mais également une base duale et sa solution basique.
2/ Les valeurs de la solution basique duale se lisent dans la dernière ligne du
tableau. Les valeurs des variables basiques primales se lisent dans la dernière
colonne du tableau.
3/ La paire de solutions basiques (primale et duale) associées à un tableau ont la
même valeur et vérifient les conditions d’orthogonalité des écarts
complémentaires.

11

Chapitre 4: Dualité en programmation linéaire

Algorithme dual du simplexe (phase II)

Données: Un tableau dual admissible

Résultat: Un tableau optimal ou un certificat d’absence de solutions admissibles
1/ Choix de variable sortante:
 Choisir une ligne i tel que: bi < 0, la variable basique xj quitte la base (où j est
l’indice de la variable basique dans la base B)
 S’il n’existe pas de variables sortantes: STOP le tableau courant est optimal
2/ Choix de la variable entrante:
 Choisir une colonne hors base r maximisant les quotients caractéristiques duaux:
  a m 1,k  a m 1, j 
r  k  N ,  max , a i, j  0 
 a i,k a i, j 
 S’il n’existe pas de variable entrante: STOP le dual est non borné et le primal est
sans solutions admissibles
3/ Mise à jour de la base et du tableau: Pivoter autour de air et retourner à (1).
12

6
 Chapitre 4: Dualité en programmation linéaire

Application:
Résoudre le PL suivant en appliquant l’algorithme dual du simplexe (phase II)

 Max Z   x1  2 x 2
  2 x1  x 2  6
   x 
 x 2   4
( PLC )   1

sc :  x1  0

 
 
  x 2  0

13

Chapitre 4: Dualité en programmation linéaire

Algorithme dual du simplexe (phase II)

Exemple  min Z  3 x1  4 x 2  6 x 3  7 x 4  x5
  2 x1  x 2  x 3  6 x 4  5 x 5  6

 sc :  x  x  2 x  x  2 x  3
  1 2 3 4 5

  x1, x 2 , x 3 , x 4 , x5  0


 max Z ' 6 y1  3 y 2
  2 y1  y 2  3
   y  y  4
  1 2
Le dual est: 
 sc :  y 1  2 y 2  6
 
  6 y1  y 2  7
   5 y1  2 y 2  1
 
  y1, y 2  0