Filière : Licence d'excellence (CCA)
Module : Recherche opérationnelle.
Semestre : 6
Année universitaire : 2023-2024
TD 3 : Dualité & analyse post-optimale
Exercice 1 :
Formuler le problème dual de chacun des programmes linéaires suivants :
max z 2 x1 4 x2 3 x3 max z 3 x1 x2 2 x3
3 x 4 x 2 x 60
1 2 3 x1 2 x2 10
P1 2 x1 x2 2 x3 40 P2 3 x1 x2 x3 7
x 3 x 2 x 80 x 3x 8
1 2 3
1 3
I
x1 0, x2 0, x3 0 x2 0, x3 0
BR
max z 10 x1 14 x2 max z 400 x1 350 x2 450 x3
x x 12 2 x 3 x 2 x 120
1 2 1 2 3
P3 x1 8 P4 4 x1 3 x2 160
x 6 3 x 2 x 4 x 100
2 1
A 2 3
x1 0, x2 0 x2 0
.S
Exercice 2 :
On considère le programme linéaire ci-dessous :
min z 4 x1 5 x2 2 x3 6 x4
x 3x 2 x 4 x 5
.A
1 2 3 4
(P)
2 x1 x2 3 x3 5 x4 7
x1 , x2 , x3 , x4 0
Pr
1. Donner le dual D du programme linéaire P.
2. Résoudre le programme linéaire dual D à l’aide de la méthode graphique.
3. Trouver la solution du primal en utilisant le théorème des écarts complémentaires.
Exercice 3 :
On considère le PL suivant :
max z 2 x1 x2 1. Calculer la solution optimale par résolution graphique.
3 x 2 x 9 2. Les nouveaux coefficients de la fonction objectif sont
1 2
(3, 5), vérifier que la solution trouvée précédemment est
x2 3 toujours optimal à l’aide du dual et les écarts
3 x x 12 complémentaires.
1 2
x1 , x2 0
Exercice 4 :
[Link] 1/3
Filière : Licence d'excellence (CCA)
Module : Recherche opérationnelle.
Semestre : 6
Année universitaire : 2023-2024
On considère le programme linéaire suivant :
max z 4 x1 12 x2 3 x3
x 1000
1
x2 500
x3 1500
3 x1 6 x2 2 x3 6750
x1 , x2 , x3 0
I
1. Tester l’optimalité de la solution (250, 500, 1500) à l’aide du dual et les écarts
BR
complémentaires.
2. Le nouveau vecteur b (second membre des contraintes) est (950, 550, 1575, 6900).
A l’aide du dual, vérifier si la solution précédente est admissible et s’il s’agit de la solution
optimale.
3. De même avec le vecteur (1000, 500, 1500, 9750).
A
Exercice 5 :
.S
Appliquer le théorème des écarts complémentaires pour vérifier l’optimalité de la solution
proposée dans les deux programmes ci-dessous :
max z 4 x1 5 x2 x3 3 x4 5 x5 8 x6
.A
x 4 x 3x x x 1
max z 7 x1 6 x2 5 x3 2 x4 3 x5 1 3 4 5 6
x 3x 5 x 2 x 2 x 4 5 x1 3 x2 x3 5 x5 3x6 4
1 2 3 4 5
4 x1 2 x2 2 x3 x4 x5 3 4 x1 5 x2 3 x3 3 x4 4 x5 x6 4
Pr
2 x1 4 x2 4 x3 2 x4 5 x5 5 x2 2 x4 x5 5 x6 5
3 x1 x2 2 x3 x4 2 x5 1 2 x1 x2 x3 x4 2 x5 2 x6 7
x1 , x2 , x3 , x4 , x5 0 2 x1 3x2 2 x3 x4 4 x5 5 x6 5
x , x , x , x , x , x 0
1 2 3 4 5 6
Solution proposée :
4 2 5
( x1 , x2 , x3 , x4 , x5 ) (0, , , , 0) Solution proposée :
3 3 3
5 7 1
( x1 , x2 , x3 , x4 , x5 , x6 ) (0, 0, , , 0, )
2 2 2
[Link] 2/3
Filière : Licence d'excellence (CCA)
Module : Recherche opérationnelle.
Semestre : 6
Année universitaire : 2023-2024
Exercice 6 :
On considère le programme linéaire suivant :
min z 3 x1 x2 x3
x 2x 8
1 2
3x1 2 x2 x3 6
x1 , x2 , x3 0
1. Ecrire le dual de ce programme linéaire
2. Trouver la solution optimale du dual.
3. Déduire la solution optimale du primal.
I
BR
Exercice 7 :
1. Résoudre le problème suivant :
max z 6 x1 7 x2 8 x3
x 2 x x 100
1
A 2 3
3 x1 4 x2 2 x3 120
2 x 6 x 4 x 200
1 2 3
.S
x1 , x2 , x3 0
2. Déterminer l’intervalle d’optimalité dans lequel le coefficient de la variable x3 dans la
fonction objectif peut varier sans que la solution optimale change.
.A
3. Déterminer le domaine de validité du second membre de la deuxième contrainte.
Exercice 8 :
Pr
On considère le programme linéaire suivant :
min z 3 x1 4 x2 5 x3
x 2 x 3x 5
1 2 3
2 x1 2 x2 x3 6
x1 , x2 , x3 0
1. Résoudre ce problème en utilisant la méthode simplexe.
2. Appliquer l’analyse post-optimale pour déterminer l’intervalle d’optimalité du coefficient
x2.
3. Appliquer l’analyse post-optimale pour déterminer le domaine de validité du second membre
de la première contrainte.
4. Etudier l’effet du changement de la contrainte 2 x1 2 x2 x3 6 par 2 x1 2 x2 2 x3 6 .
[Link] 3/3