FACULTE DES SCIENCES DE TUNIS 24/06/2010
Dépt. des Sciences de l’Informatique
EXAMEN
Session De Rattrapage
Section : INFO3
Matière : Programmation Linéaire
Durée : 2 Heures
Documents Non Autorisés
----------------------------------------------------------------------------------------------------------------
Le barème est à titre indicatif
Exercice 1 (6 Pts)
Donner un exemple numérique d’un programme linéaire (P) dans chacun des cas suivants :
(Dans chacun des cas, (P) contiendra deux variables et deux contraintes. Chaque réponse doit être
justifiée)
1) (P) admet plusieurs solutions réalisables, mais aucune solution optimale. (1pt)
2) (P) admet plusieurs solutions optimales. (1pt)
3) (P) et son dual admettent chacun plusieurs solutions optimales. (2pts)
4) Ni (P) ni son dual n’admet de solution réalisable. (2pts)
Problème (14 Pts)
Soit le programme linéaire suivant :
(P)
1) Enoncer correctement le théorème des écarts complémentaire. (2.5 pts)
2) Ecrire le dual (D) de (P) (On appellera Y1, Y2 les variables de (D)). (1 pt)
3) Montrer que Y1 = 7 ; Y2 = 4 est solution optimale de (D).
Cette solution est-elle de base ? Est-elle unique ? Justifier la réponse. (3 pts)
4) Donner alors l’ensemble des solutions optimales de (D). (2 pts)
5) En déduire les bases optimales de (DS) où (DS) est le programme linéaire (D) écrit sous forme
standard (on appellera Y3 , Y4, Y5, Y6 et Y7 les variables d’écart associées à la 1ère, 2ème, 3ème 4ème et 5ème
contraintes de (D)). (2 pts)
6) Les coefficients du second membre de (P) sont supposés α et β respectivement au lieu de 2 et 1. Etablir
une relation entre α et β pour que la solution de (D) : Y1= 6 et Y2 = 6 reste optimale. (3.5pts)
FACULTE DES SCIENCES DE TUNIS 24/06/2010
Dépt. des Sciences de l’Informatique
Correction de l’Examen IF3
du 24/06/2010 ( Session Rattrapage)
Problème :
1) Théorème des écarts complémentaire (voir cours).
2)
(D)
3) -14 + 4 = -10 < 4 ==> X1 = 0
-7 + 8 = 1 < 14 ==> X2 = 0
7 + 8 = 15 < 18 ==> X3 = 0
14 + 4 = 18 = 18
7 - 8 = -1 < 4 ==> X5 = 0
Y1 > 0 ==> 2X4 = 2
Y2 > 0 ==> X4 = 1
Cette solution n’est pas de base car elle ne vérifie qu’une seule contrainte avec égalité.
Elle n’est pas unique.
4) L’ensemble des solutions optimales :
Sop = {( Y1, Y2) € R2 / avec 6 ≤ Y1 ≤ 8}
5) Les bases optimales sont pour lesquelles :
Y1 = 6 ==> Y2 = 6
et Y1 = 8 ==> Y2 = 2.
1er cas: Y1 = 6 ; Y2 = 6
-12 + 6 = -6 < 4 ==> Y3 = 10
-6 + 12 = 6 < 14 ==> Y4 = 8
6 +12 = 18 = 18 ==> Y5 = 0
12 + 6 = 18 = 18 ==> Y6 = 0
6 - 12 = -6 < 4 ==> Y7 = 10
La base optimale correspondante est J1= {1, 2, 3, 4, 7}
2ème cas : Y1 = 8 ; Y2 = 2
-16 + 2 = -14 < 4 ==> Y3 = 18
-8+ 4 = - 4 < 14 ==> Y4 = 18
8+ 4 = 12 < 18 ==> Y5 = 6
16 + 2 = 18 = 18 ==> Y6 = 0
8– 4 = 4= 4 ==> Y7 = 0
La base optimale correspondante est J2 = {1, 2, 3, 4, 5}
6) Y1 = 6, Y2 = 6 ==> J1 = {1, 2, 3, 4, 7}
πAJ = CJ ==> =>
C5 = 0 – (0, 0, , 0) = ≤0
C6 = 0 – (0, 0, , 0) = ≤0
=> α + β = 3 => β = 3 – α
=> =>
S(α, β) = {(α, β) € R2/ α + β = 3 avec 1 ≤ α ≤ 2}
