Corrigé de l'Examen de Rattrapage de Programmation Linéaire

Universit´e A. MIRA de B´ejaia2±LicenceFacult´e des Sciences Exactes
D´epartement de Recherche Op´erationnelle
Ann´ee Universitaire 2015-2016
Corrig´e de l"Examen de Rattrapage de Programmation Lin´eaire
Exercice 1(12 points) Consid´erons le probl`eme lin´eaire suivant :
maxZ= 3x1
+x2¡2x3
x
1+ 2x2¸10
3x1¡x2+x3= 7
x
1+ 3x3·8
x
3·2
x
2;x3¸0(1)
1.
´
Ecrire le probl`eme (1) sous forme standard
2.
R´esoudre le probl`eme (1)
3.
´
Ecrire le probl`eme Dual not´e(D)du probl`eme (1).
4.
D´eduire la solution Optimale du probl`eme(D)si elle existe.
Corrig´e de l"exercice 1
1.
Comme la variablex12R, alors on fait le changement de variable suivant :
x
1=z1¡z2; z1¸0; z2¸0:
Le probl`eme (1) s"´ecrit alors sous la forme
maxZ= 3z1¡3z2+x2¡2x3
z
1¡z2+ 2x2¸10
3z1¡3z2¡x2
+x3= 7
z
1¡z2+ 3x3·8
x
3·2
z
1;z2;x2;x3¸0(2)
Le probl`eme standard associ´e au probl`eme (2) est
maxZ= 3z1¡3z2+x2¡2x3
z
1¡z2+ 2x2¡x4= 10
3z1¡3z2¡x2+x3= 7
z
1¡z2+ 3x3+x5= 8
x
3+x6= 2
z
1;z2;x2;x3
;x4;x5;x6¸0(3)
2.
On peut r´esoudre le probl`eme (1) par la m´ethode des deux phases. La forme auxiliaire associ´ee au
probl`eme (3) est :
maxZ=¡x7¡x8
z
1¡z2+ 2x2¡x4+x7= 10
3z1¡3z2¡x2+x3+x8= 7
z
1¡z2+ 3x3+x5= 8
x
3+x6= 2
z
1;z2;x2;x3;x4;x5;x6¸0(4)