TD dualité

Exercice 1

On considère le programme linéaire suivant :

Max Z  9 x1  4 x2  4 x3
3x1  2 x2  x3  10

S / C 3x1  x2  2 x3  16
x , x , x  0
 1 2 3

1) Résoudre ce programme linéaire par la méthode de simplexe. (2,5 points)

2) Écrire le dual de ce programme linéaire. (1 point)
3) Déduire le dernier tableau de Dual à partir de celui du primal. (1,5 points)

1. Écrire le Dual de ce programme linéaire. (1 point)

MinW  10 y1  16 y2
3 y1  3 y2  9
2 y  y  4
 1 2
S /C 
 y1  2 y2  4
 y1 , y2  0

2. Résoudre graphiquement le programme dual. (3 points)

La figure suivante montre que la zone des solutions réalisables est non bornée.
Cependant, s’agissant d’une minimisation, la droite représentant la fonction
économique évolue vers la partie bornée et doit quitter la zone des solutions
réalisables par un des sommets A, B, C ou D.
 4.5
4 A
3.5
3
2.5
D3
y2

2 B
D1
1.5
C D2
1
0.5
D
0
0 1 2 3 4 5
y1

Coordonnées Valeur de la fonction

Sommet
y1 y2 économique
A 0 4 64
B 1 2 42
C 2 1 36
D 4 0 40

La solution optimale est atteinte au point C pour W = 36.

 y1   2 
   
 y2   1 
Y   s '1    0 
*

   
 s '2   1 
 s '  0
 3  

3. Donner la solution du primal et son dernier tableau du simplexe déduite de celle du

dual.
(3 points)
D’après le théorème des écarts complémentaires s1 = s2 = x2 = 0, x1 ≠ 0 et x2 ≠ 0.
  x1   4 / 3 
   
 x2   0 
X *   x3    6 
   
 s1   0 
s   0 
La solution optimale est :  2   et Z* = 36
Le tableau optimal est retrouvé en déterminant la matrice inverse de la base optimale
AB.
2 1
1  
3 1 AB  3 3
AB     
3 2  1 1 
Ainsi, et
Le dernier tableau du simplexe s’écrit :
cj 9 4 4 0 0
Quantité
cj VB x1 x2 x3 s1 s2
9 x1 1 1 0 2/3 -1/3 4/3
4 x3 0 -1 1 -1 1 6
zj 9 5 4 2 1
Z = 36
cj - zj 0 -1 0 -2 -1

Exercice 2

Soit le programme linéaire (PL) suivant :

Max Z  9 x1  4 x2  4 x3
3x1  2 x2  x3  10

S / C 3x1  x2  2 x3  16
x , x , x  0
 1 2 3
1. Écrire le Dual de ce programme linéaire. (1 point)
2. Résoudre graphiquement le programme dual. (3 points)
3. Donner la solution du primal et son dernier tableau du simplexe déduite de celle du
dual.
(3 points)
Exercice 3

On considère PL suivant :
 Max Z  10 x1  4 x2  6 x3
 x1  5 x2  2 x3  30

S / C  x1  5 x2  6 x3  40
x , x , x  0
 1 2 3
On vous donne le tableau courant incomplet de ce PL.

10 4 6 -M 0
x1 x2 x3 a1 s2
10 x1 1 5 2 1 0 30
0 s2 0 -10 -8 -1 1 10
zj 10 50 20 10 0
300
cj-zj 0 -46 -14 -M-10 0

1. Compléter le tableau courant de ce programme linéaire et déterminez la solution

optimale.

2. Ecrire le programme dual, déduire la solution optimale et son dernier tableau du

simplexe.

Max Z  10 x1  4 x2  6 x3
 x1  5 x2  2 x3  30

S / C  x1  5 x2  6 x3  40
x , x , x  0
 1 2 3 𝑀𝑖𝑛 𝐶 = 30𝑦1 + 40𝑦2
𝑦1 + 𝑦2 ≥ 10
5𝑦 − 5𝑦2 ≥ 4
𝑠. 𝑐 { 1
2𝑦1 − 6𝑦2 ≥ 6
𝑦1 𝑠. 𝑟. 𝑠; 𝑦2 ≥ 0

𝑦1 = 10; 𝑦2 = 0; 𝑠1′ = 0; 𝑠2′ = 46; 𝑠3′ = 14; 𝐶 ∗ = 300

30 40 0 0 0

𝑦1 𝑦2 𝑠1′ 𝑠2′ 𝑠3′ Q

30 𝑦1 1 1 -1 0 0 10

0 𝑠2′ 0 10 -5 1 0 46

0 𝑠3′ 0 8 -2 0 1 14

Zj 30 30 -30 0 0 300

Zj-cj 0 -10 -30 0 0

Exercice 4

Soit le programme linéaire suivant :

Min C  8 X 1  2 X 2  X 3  3 X 4
4 X 1  X 2  X 3 3

S .C. X 1  X 2  X 3  X 4  5
 X  0, i  1, 2, 3, 4
 i

1. Écrire le programme linéaire dual de ce programme linéaire. (1 point)

𝑀𝑎𝑥 𝑍 = 3𝑦1 + 5𝑦2

𝑠. 𝑐.
4𝑦1 + 𝑦2 ≤ 8
−𝑦1 − 𝑦2 ≤ −2
𝑦1 − 𝑦2 ≤ 1
𝑦2 ≤ 3
{ 𝑦1 , 𝑦2 ≥ 0

𝑀𝑎𝑥 𝑍 = 3𝑦1 + 5𝑦2

𝑠. 𝑐.
4𝑦1 + 𝑦2 ≤ 8
𝑦1 + 𝑦2 ≥ 2
𝑦1 − 𝑦2 ≤ 1
𝑦2 ≤ 3
{ 𝑦1 , 𝑦2 ≥ 0

2. Résoudre graphiquement le programme linéaire dual. (3 points)

 4𝑦1 + 𝑦2 + 𝑠1′ = 8
𝑦1 + 𝑦2 − 𝑠2′ = 2 ; 𝑠2′ = 𝑦1 + 𝑦2 − 2
𝑦1 − 𝑦2 + 𝑠3′ = 1
𝑦2 + 𝑠4′ = 3

3. En utilisant le théorème des écarts complémentaires, donner la solution optimale du

programme primal. (2.5 points)

Min C  8 X 1  2 X 2  X 3  3 X 4
4 X 1  X 2  X 3 3

S .C. X 1  X 2  X 3  X 4  5
 X  0, i  1, 2, 3, 4
 i Base optimale primale : {x1,x4}
 4𝑥1 = 3
{
𝑥1 + 𝑥4 = 5

4. Donnez le tableau optimal du primal. (2,5 points)

On utilise la méthode matricielle pour passer de la base de départ {a1,a2} vers la

base optimale {x1,x4}

4 0
𝐴𝐵 = ( ) ; det(𝐴𝐵) = 4
1 1
1
1 1 0 0
𝐴𝐵 −1 = ( )=( 4 );
4 −1 4 −1
1
4
1
0
4 −1 1 0
𝐴𝐵 −1 ∗ 𝐴𝑝 = ( 4 )∗( )
−1 1 −1−1 1
1
4
1 1
1 − 0
=( 4 4 )
3 5
0 − − 1
4 4

1 1
0 − 0
−1 0
𝐴𝐵 −1 ∗ 𝐴𝑠 = ( 4 )∗( )=( 4 )
−1 0 −1 1
1 −1
4 4
1 3
0
3
𝐴𝐵 −1 ∗ 𝐴𝑠 = ( 4 )∗( )=(4 )
−1 5 17
1
4 4

Exercice 5

Soit le programme linéaire suivant :

 Max Z  5 X 1  X 2  6 X 3  2 X 4
4 X 1  4 X 2  4 X 3  X 4  44

S .C. 8 X 1  6 X 2  4 X 3  3 X 4  60
 X  0, i  1, 2,3, 4
 i  

1. Écrire le programme linéaire dual de ce programme linéaire. (1 point)

2. Résoudre graphiquement le programme linéaire dual. (2 points)

3. En utilisant le théorème des écarts complémentaires, donner la solution optimale du

programme primal. (2 points)

4. Donnez le tableau optimal du primal. (2 points)

Exercice 6

Soit le programme linéaire (PL) suivant :

Min C  2 X 1  X 2  X 3
 X 1  X 2  X 3  2

S .C.  X 1  X 2  2 X 3  1
 X  0, i  1, 2,3
 i  

4. Résoudre par la méthode du simplexe (3 points)

5. Donnez le tableau optimal du programme linéaire dual (2 points)

Exercice 7

Le 1er tableau incomplet d’un programme linéaire est représenté ci-dessous :

1 1 0 0 -M -M
VB
𝑥1 𝑥2 𝑠1 𝑠3 𝑎1 𝑎2 Q
𝑎1 1 2 -1 2
𝑎2 -5 15 0 5
𝑠3 3 6 0 12
zj
zj
 1. Complétez le tableau du simplexe et déduire le programme linéaire

2. Résoudre graphiquement ce PL

3. Ecrivez le programme linéaire dual

Exercice 8

Soit le programme linéaire suivant :

Min C  X 1  4 X 2  X 3
 X 1  X 2  2 X 3  16

S .C. 2 X 1  X 2  4 X 3  8
 X  0, i  1, 2,3
 i  
1. Ecrivez le premier tableau du simplexe de ce programme linéaire. (1 points)

2. Donnez le tableau du simplexe pour la base {X2, S2} en ayant recours à la méthode
matricielle. (2 points)

3. Retrouvez le tableau optimal du simplexe (2 points)

4. Donnez le programme linéaire dual (1 points)

5. Déduisez la solution optimale duale à partir du tableau optimal primal (1 point)

6. Déduisez le tableau optimal dual à partir du tableau optimal primal (2 points)