Universit Saad Dahlab de Blida, Facult des sciences

Dpartement de mathmatiques,
3 ime Anne Licence LMD

Blida, le 30 Juin 2010

Epreuve de Rattrapage
Module : Programmation linaire

Exercice 1.
Une verrerie produit des verres caf, des verres th et des verres eau.
Les prix de vente, les quantits requises de verre ainsi que les temps de faonnage et
d'emballage sont diffrents pour chacun des produits et sont donns dans le tableau suivant :

Verres Verres th Verres eau

caf
Temps de faonnage ( min ) 4 2 12
Temps d'emballage ( min ) 2 1 4
Quantit de verre ( kg ) 0.1 0.15 0.1
Prix de vente ( DA ) 8 6 15

Pour la semaine venir, l'entreprise dispose de 3000 minutes pour le faonnage, de 1200
minutes pour l'emballage et de 100 kilogrammes de verre.
a. Formuler un programme linaire aidant l'entreprise dterminer une production
maximisant son chiffre d'affaires.
b. Donner le programme dual du problme.
c. Rsoudre le problme primal.
d. Donner la solution optimale du programme dual.
e. Si l'entreprise pouvait amliorer le faonnage ou l'emballage de ces produits, ce qui
reviendrai disposer de plus de temps pour l'une ou l'autre de ces deux activits, quelle
tape de la production lui conseillerez-vous de modifier en premier ?

1
Exercice 2. Soit le problme linaire P suivant :
max. Z = C. X
(P) A.X=b
X 0.
a) Montrer que la fonction objective du problme (P) dfinie sur le polydre
K = { X , X 0 / A . X = b } atteint son maximum en un point extrme de K.
b) Si la fonction objective prend sa valeur maximale au plus dun point extrme alors toutes
combinaisons linaire convexe de ces points donne la mme valeur la fonction objective.
c) Un point x de K est un point extrme si et seulement si x est une solution de base
ralisable du problme A.X = b.
d) En dduire si K alors il admet au moins un point extrme.

Exercice 3.
En appliquant la mthode du grand M, montrer que le problme linaire suivant n'a pas de
solutions.
MinZ = -2 x1 - 3 x2 + x3
- 4 x1 - 5 x2 - 2 x3 5
- x1 + 6 x2 + x3 10
x1 0 ; x2 0; x3 0

2
 Correction des exercices proposs le 30 Juin 2010
Dans la cadre de l'preuve de Rattrapage du Module de la Programmation linaire
De la 3 ime Anne Licence LMD
Par Dr. DERBALA Ali.

Solution 1.
a. Dfinissons les variables de dcision par :
X1 : le nombre de verres caf produits pendant la semaine venir ;
X2 : le nombre de verres th produits pendant la semaine venir ;
X3 : le nombre de verres eau produits pendant la semaine venir ;
Le plan de production maximisant le chiffre d'affaires est solution du programme linaire :

Max z = 8 X1 + 6 X2 + 15 X3
4 X1 + 2 X2 + 12 X3 3000
2 X1 + X2 + 4 X3 1200
0,1 X1 + 0,15 X2 + 0,1 X3 100
X1 0, X2 0 et X3 0
b. Le problme dual du programme prcdent est :
Min w = 3000 y1 + 1200 y2 + 100 y3
4 y1 + 2 y2 + 0,1 y3 8
2 y1 + y2 + 0,15 y3 6
12 y1 + 4 y2 + 0,1 y3 15
y1 0, y2 0 et y3 0

c. Le but est d'obtenir une base optimale forme de ( X1 , X2, X3 ). En dressant les tableaux du
simplexe on obtiendra : si on choisit de faire entrer X1 , il est optimal de faire sortirX5.
V.B 1 X1 X2 X3 X4 X5 X6 Cot
X4 3000 4 2 12 1 0 0 750
X5 1200 2 1 4 0 1 0 600
X6 100 1/10 3/20 1/10 0 0 1 1000
Z 0 -8 -6 -15 0 0 0

3
Si on fait rentrer X1 dans la base, si X4 sortira, a nous cotera 750, de mme pour X5 , elle
nous cotera 600 et X6 nous cotera 1000. A moindre cot, Il est optimal de faire sortir X5.

V.B 1 X1 X2 X3 X4 X5 X6 Cot
X4 600 0 0 4 1 -2 0
X1 600 1 1/2 2 0 1/2 0 1200
X6 40 0 1/10 - 1/10 0 -1/20 1 400
Z 4800 0 -2 1 0 4 0

Si on fait rentrer X2 dans la base, il est optimal de faire sortir X6.

V.B 1 X1 X2 X3 X4 X5 X6 Cot
X4 600 0 0 4 1 -2 0 150
X1 400 1 0 5/2 0 3/4 -5 160
X2 400 0 1 -1 0 -1/2 10 -
Z 5600 0 0 -1 0 3 20

Si on fait rentrer X3 dans la base, il est optimal de faire sortir X4.

V.B 1 X1 X2 X3 X4 X5 X6 Cot
X3 150 0 0 1 1/4 -1/2 0 -
X1 25 1 0 0 -5/8 2 -5 -
X2 550 0 1 0 1/4 -1 10 -
Z 5750 0 0 0 1/4 5/2 20

Ce tableau final est optimal.

La solution est : X1* = 25 verres caf, X2 * = 550 verres th
et X3* = 150 verres eau pour un chiffre d'affaires de Z* = 5750 DA.

d. La solution optimale duale se lit du tableau optimal :

y1* = 1/4, y2 * = 5/2 et y3* = 20, w* = 5750 DA.

4
e. Le cot marginal associ la premire ressource ( le temps de faonnage ) est
y1* = 1/4 et celui associ la deuxime ressource ( le temps d'emballage ) est y2 * = 5/2. Il est
donc prfrable d'essayer d'augmenter en premier lieu le temps d'emballage car, pour une
augmentation gale, l'impact sur le chiffre d'affaire sera plus important.

Solution 2 . voir cours donns par Dr. DERBALA Ali

http://www.univ-blida.dz/fac_sciences/mathematique/ali_derbala.html

max Z = cx (1)

a. soit un PL sous forme standard ( P) Ax = d (2)
x0 (3)

Soient x1 , , x p les points extrmes de IK et x0 une solution optimale de (1)-(3).

Supposons le contraire, que x0 n'est pas un point extrme de IK.

p
Alors x0 = i x i et o
i =1
p p
Z(x0)= Z( i x i ) = i Z( x i ) (4)
i =1 i =1

Dterminons la valeur maximale que prend la fonction objectif Z aux points extrmes,
max Z ( x i ) = Z ( x r ) .
i{1,..., p}

Remplaons dans (4) chaque Z( x i ) par Z( x r ) .

p p p
D'o Z ( x 0 ) = Z ( i x i ) = i Z ( x i ) Z ( x r ) i Z ( x r )
i =1 i =1 i =1

Ou Z ( x r ) Z ( x 0 ). Ce qui implique que x0 n'est pas une solution optimale.

D'o x0 est un sommet de IK.

b. Soient x1 ,..., x p les points extrmes de IK et Z( x1 ) = ... = Z( x p ) = , la valeur minimale

p p
(resp. maximale). Soit x = i x i et o i = 1, avec i 0
i =1 i =1
p p
Z( x ) = Z( i x i ) = i = = Z( x i )
i =1 i =1

5
c. Soit x =(x1,...,xm,0,0,...,0) une solution de base ralisable. Montrons que

x est un point extrme. Raisonnons par absurde.

Supposons qu'il existent y et z deux sommets de IK tel que :

x = y + ( 1 - ) z ; 0 1.

Du fait que x 0 et 0 1, les " n - m " dernires composantes de y et z sont nulles.

y = (y1, y2, , ym, 0, , 0); et z = y = (z1, z2, , zm, 0, , 0)
Du fait que y et z sont des solutions ralisables alors
y1.a1+ y2.a2 + + ym.am = b, et z1.a1+ z2.a2 + + zm.am = b
D'o (y1- z1) a1+ ( y2 - z2) a2 + + (ym- zm) am = 0
(ai)i = 1,,m sont L.I forment une base.
Il en dcoulera y1- z1 = y2 - z2 = . = ym- zm = 0
y1 = z1 ; y2 = z2 ; . ; ym = zm. et donc x = y = z .

soit x est un point extrme, montrons qu'il est une solution de base ralisable de IK. x =
(x1, , xm, 0, , 0) est une solution de IK.
m
x = x i a i = b . Si a1, a2, , am sont L.I alors x est de base.
i =1

Si a1, a2, , am sont linairements dpendants, alors ils existent des scalaires yi non tous nuls
m m
tel que y i a i = 0 (1) . Mais x i a i = b (2)
i =1 i =1
m m m m
Pour > 0, x i a i + y i a i = b et x i a i y i a i = b
i =1 i =1 i =1 i =1

Nous avons trouv deux solutions (pas ncessairement ralisables)

y = (x1+ y1, , xm + ym, 0, , 0) et z = (x1- y1, , xm- ym, 0, , 0)

Comme xi > 0, on peut choisir tel que y et z soient des solutions ralisables.
Mais x = 1/2 y + 1/2 z . Absurde car x ne sera pas un sommet.

d. si le polydre de ralisabilit IK est non vide, alors il contient au moins une solution
ralisable partir de laquelle on peut construire une solution de base ralisable et donc il
contient au moins un point extrme.

6
Solution 3 . MinZ = -2 x1 - 3 x2 + x3
- 4 x1 - 5 x2 - 2 x3 5 2
- x1 + 6 x2 + x3 10
x1 0 ; x2 0; x3 0

MinZ = -2 x1 - 3 x2 + x3
- 4 x1 - 5 x2 - 2 x3 - x4 = 5
- x1 + 6 x2 + x3 - x5 = 10
xi 0 ; i = 1,,5.
MinZ = -2 x1 - 3 x2 + x3
4 x1 + 5 x2 + 2 x3 + x4 =- 5
x1 - 6 x 2 - x3 + x5 = -10
xi 0 ; i = 1,,5.
J1 = {3} et J2 = {1, 2}. On rajoute l'quation artificielle : x1 + x2 + x6 = M. o M est un
nombre positif aussi grand que l'on veut. Calculons min { cj, j J2 } = { -2, -3 } = c2
Le problme augment devient : MinZ = -2 x1 - 3 ( M - x1 - x6) + x3
4 x1 + 5 ( M - x1 - x6) + 2 x3 + x4 =- 5
x1 - 6 ( M - x1 - x6) - x3 + x5 = -10
x1 + x2 + x6 = M.
xi 0 ; i = 1,,5.

MinZ = x1 + x3 + 3 x6 - 3M
- x1 + 2 x 3 + x4 - 5 x6 = - 5M-5
7 x1 - x3 + x5 + 6 x6 = 6M-10
x1 + x2 + x6 = M.
xi 0 ; i = 1,,5.
CB xB di x1 x2 x3 x4 x5 x6
0 x4 -5M-5 -1 0 2 1 0 -5
0 x5 6M-10 7 0 -1 0 1 6
0 x2 M 1 1 0 0 0 1

Zj - cj - 3M -1 0 -1 0 0 -3

7
X4 = - 5M - 5 < 0, a4 sort de la base.
Calculons min {Zj - cj / a4j < 0 } = {-1/-1, -3/-5} = 3/5; a6 rentre dans la base.

CB xB di x1 x2 x3 x4 x5 X6
3 x6 M+1 1/5 0 -2/5 -1/5 0 1
0 x5 -16 29/5 0 7/5 6/5 1 0
0 x2 -1 4/5 1 2/5 1/5 0 0

Zj - cj 3 -2/5 0 -11/5 -3/5 0 0

X5 = - 16 < 0, a5 sort de la base. Tous les a5j 0, j = 1, 3, 4.

Le problme augment n'a pas de solutions optimales finies.
D'o le problme initial n'a pas de solutions finies.