Corrigés Travaux dirigés de recherche opérationnelle

Optimisation classique et Programmation Linéaire

Exercice2
Comme q=q 1+ q2 la fonction de coût devient :

C=50+ 40 q
¿ 50+ 40 ( q1 +q 2 )

¿ 50+ 40 q1 +40 q 2
Le revenu total R s’obtient en multipliant le prix par la quantité sur chaque marché :
R=p 1 q 1+ p 2 q 2

¿ ( 60 −2 q 1 ) q1 + ( 80 − 4 ) q 2
2 2
¿ 60 q 1 −2 q 1+ 80 q2 − 4 q2
On obtient le bénéfice B en calculant la différence entre le revenu et le coût :
B=R −C
2 2
20 q 1 −2 q 1+ 80 q2 − 4 q2 −50
Annulons les premières dérivées partielles :
dB
=− 4 q 1+20=0 , alors q 1=5
d q1

dB
=−8 q 1 +40=0 , alors q 2=5
d q2
Il reste à vérifier que le point candidat (q1; q2) = (5; 5) est un maximum ; pour cela, calculons les deuxièmes
dérivées partielles :
2
d B
2
=− 4
d q1
2
d B
2
=− 8
d q2
2
d B
=0
d q1 d q2
La matrice hessienne est donc :

(−04 0
−8 )
Par conséquent :
∆ 1=− 4< 0
 ∆ 2=32>0
il s’agit d’un maximum. Le bénéfice maximum réalisé est égal à :
et le bénéfice maximal est égal à 100
quant aux prix ils s’élèvent à

p1=60 − 2 ( 5 )=50

p2=80 − 4 ( 5 )=60
Optimisation classique avec contraintes

Exercice 5
Calculons le nombre d'appareils que doit produire la firme dans chaque usine afin de minimiser le cout total
de production y compris le cout de transport. Le cout total est égal a:

CT =( CT 1 −4 q1 ) + ( CT 2 − 2 q2 )
2 2
¿ 0 , 03 q 1+ 0 ,02 q 2+10 q1 +12 q2 +350
s 'agit donc de minimiser cette fonction, et cela sous la contrainte de livrer 100 appareils au total, c'est-d-dire
q 1+ q2=100 . La fonction auxiliaire devient par consequent :
2 2
F ( q1 , q2 , α ) =0 , 03 q1 +0 , 02 q2 +10 q 1+12 q 2+ 350− α ( q1 +q 2 −100 )

Comme précédemment, on cherche les dérivées partielles de premier ordre:

dF
=0 , 06 q 1+10 − α
d q1

dF
=0 , 04 q 2+ 12− α
d q2

dF
=q 1+ q2 −100
dα
Pour trouver le point critique, on les annule:
0 , 06 q 1+10 − α =0

0 , 04 q 2 +12− α =0

q 1+ q2 −100=0

et en résolvant pour q 1 et q 2, on trouve: q 1 = 60 et q 2 = 40 faut encore verifier que, pour ces valeurs, il s ^agit
bien d’un minimum:
2
d F
2
=0 , 06
d q1
2
d F
2
=0 , 04
d q2
 2
d F
=0
d q1 d q2
∗
α =0.06 −0.04 −0=0.0024 .
2 2
d F d F
∗
Comme α , 2 et 2 ont positifs, il s’agit bien d’un minimum,
d q1 d q2
Par conséquent, quand la firme livre 60 appareils de sa première usine et 40 de sa deuxième usine, le coût total
est minimal sous la contrainte d’une livraison de 100 appareils.

Programmation Linéaire et Méthode du Simplexe

Exercice 1
Soient x1, x2 et x3 le nombre de kilo de chaque mélange.

X1 X2 X3 bi
Cacahuètes 1 2/3 1/ 450
4
Noix 1/3 3/ 300
4
π 25 40 50
Max Z =25 X 1+ 40 X 2+50 X 3 Max Z=25 X 1+ 40 X 2+50 X 3+0 S 1+0 S 2

{ {
2 1 2 1
X 1+ X 2+ X 3 ≤ 450 X 1+ X 2+ X 3+ S 1=450
3 4 ⟹ 3 4
SC 1 3 SC 1 3
X 2+ X 3 ≤300 X 2+ X 3+ S 2=300
3 4 3 4
X1, X 2, X3≥0 X 1 , X 2, X 3 , S 1, S 2≥ 0

Le tableau du simplexe est le suivant :

X1 X2 X3 S1 S2 bi Di=bi/aij
S1 1 2/3 1/ 1 0 450 1800 L1
4
S2 0 1/3 3/ 0 1 300 400 L2
4
Z-cX -25 -40 -50 0 0 0 L3
S1 1 5/9 0 1 - 1/3 350 350 L’1=L1-1/4L’2
X3 0 4/9 1 0 1 1/3 400 +∞ L’2=4/3L2
Z-cX -25 -160/9 0 0 200/3 20000 L’3=L3+50L’2

X1 1 5/9 0 1 - 1/3 350 630 L’’1=L’1

X3 0 4/9 1 0 4/3 400 900 L’’2=L’2
Z-cX 0 -35/9 0 25 175/3 28750 L’’3=L’3+25L’’1
X2 9/5 1 0 9/5 -3/5 630 L1=9/5L1
X3 -4/5 0 1 -4/5 8/5 120 L2=L2-*4/9L1
Z-cX 7 0 0 32 56 31200 L3=L3+35/9L1

S= { ^
X 2=630 , ^ X 1= S^ 1 =S^ 2=0 , Z^ =31200 }
X 3=120 , ^
Exercice 2
1. Résoudre graphiquement le programme linéaire :

a) Attention assurez vous que la fonction objectif est maximisée

Maximiser z=2 x1 +3 x 2
sous contrainte x 1+ 3 x 2 ≤6
2 x1 + x 2 ≤ 4
x1 , x2 ≥ 0

Représenter graphiquement les droites, (D1): x 1+ 3 x 2=6 et (D2): 2 x1 + x 2=4.

Identifier la zone solution, celle qui vérifie les deux contraintes (c’est la zone contenant les hachures,
celle entre les deux droites et les deux axes).
Déterminer les coordonnées des points candidats : O(0, 0) ; A(0, 2); B(6/5 ; 8/5) ; C(2, 0).
Z(O)=0 ; Z(A)=6 ; Z(B)=7,2 ; Z(C)=4. Le maximum est atteint au point B.
S= { ^x 1=6/ 5 ; ^x 2=8/ 5 ; ^z =7 , 2 }

(x1=x et x2=y)

b)Attention assurez vous que la fonction objectif est minimisée

M inim iser z=3 x 1 +4 x 2
souscontrainte x 1+ 2 x 2 ≥8
3 x 1+3 x 2 ≥ 15
x1 , x2 ≥ 0
Représenter graphiquement les droites, (D1): 1 x 2=8 et (D2): 3 x 1+ x 2=15 .
x + 2

Identifier la zone solution, celle qui vérifie les deux contraintes (c’est la zone contenant les hachures,
celle au-dessus des deux droites et des deux axes).
Déterminer les coordonnées des points candidats : A(0, 5); B(2 ; 3) ; C(8, 0).
Z(A)=20 ; Z(B)=18 ; Z(C)=24. Le minimum est atteint au point B.
S= { ^x 1=2; x^ 2=3 ; ^z =18 }
2. Résoudre par le simplexe les programmes linéaires :
a) Attention assurez vous que la fonction objectif est minimisée
MinC=36 X 1+ 40 X 2+28 X 3 Min C=36 X 1+40 X 2+28 X 3+0 t 1+ 0 t 2

{ {
6 X 1+ 5 X 2+ 2 X 3 5 ⟹ 6 X 1+ 5 X 2+ 2 X 3 −t 1=5
SC 2 X 1+ 5 X 2+ 4 X 3 ≥ 3 SC 2 X 1+5 X 2+4 X 3 − t 2=3
X1, X 2, X3≥0 X 1 , X 2 , X 3 , t 1 , t 2 ≥0

La fonction objectif est réécrite sous forme MinC −36 X 1 − 40 X 2 −28 X 3 − 0 t 1− 0 t 2=0

X1 X2 X3 t1 t2 bi Di=bi/
aij

X1 6 5 2 -1 0 5 L1
X2 2 5 4 0 -1 3 L2
Z-cX -36 -40 -28 0 0 0 L3

X1 1 5/6 1/3 - 1/6 0 5/6 L1=1/6L1

X2 3
0 3 1/3 1/3 1/3 -1 1 1/3 L2=L2-2L1
Z-cX 0 -10 -16 -6 0 30 L3=L3+36L1

X1 1 0 -0,5 -0,25 0,25 0,5 L1=L1-5/6L2

X2 0 1 1 0,1 -0,3 0,4 L2=10/3L2
Z-cX 0 0 -6 -5 -3 34 L3=L3+10L2

S= { ^
X 1=0 ,5 , ^ X 3 =t^ 1= t^ 2=0 , Z^ =34 }
X 2 =0 , 4 , ^

b) Le même raisonnement peut être appliqué au b)

c) ne pas faire le c) vous n’obtiendrez pas de solution réalisable
 Max π =2 X 1+ 5 X 2+ 3 X 3 Max π=2 X 1+5 X 2+3 X 3+0 S 1+0 t 2+0 t 3

{ { {
X 1+2 X 2− X 3≤ 7 X 1+2 X 2 − X 3 ≤ 7 X 1+2 X 2− X 3+ S 1=7
− X 1+ X 2 −2 X 3 ≤− 5 ⟹ X 1 − X 2+2 X 3 ≥ 5 X 1 − X 2+ 2 X 3 −t 2=5
SC X 1+ 4 X 2+3 X 3 ≥1 SC X 1+ 4 X 2+3 X 3 ≥ 1 ⟹ SC X 1+ 4 X 2+3 X 3 −t 3=1
2 X 1− X 2+ 4 X 3=6 2 X 1 − X 2+ 4 X 3=6 2 X 1 − X 2+ 4 X 3=6
X 1 , X 2 , X 3 ≥0 X 1, X 2,X 3≥0 X 1 , X 2 , X 3 , S∧1 ,t 2, t 3 ≥ 0

La fonction objectif est réécrite sous forme Max π − 2 X 1 −5 X 2 −3 X 3 −0 S 1− 0 t 2 −0 t 3=0

X1 X2 X3 S1 t2 t3 bi Di=bi/aij

S1 1 2 -1 1 0 0 7 L1
X1 1 -1 2 0 -1 0 5 L2
X2 1 4 3 0 0 -1 1 L3
X3 2 -1 4 0 0 0 6 L4
Z-cX -2 -5 -3 0 0 0 0 L5

Le dual
Exercice 1
Soit le primal du problème de programmation linéaire suivant :
Max π =14 X 1+12 X 2+18 X 3

{
2 X 1+ X 2+ X 3 ≤ 2
SC X 1+ X 2+3 X 3 ≤ 4
X 1, X2, X 3≥0

1. Le dual est
Min π =2Y 1+ 4 Y 2

{
2 Y 1+ Y 2 ≥ 14
SC Y 1+Y 2≥ 12
Y 1+3 Y 3≥ 18
Y 1, Y 2 ≥0
Le dual peut être résolu graphiquement ou par la méthode du simplexe
2. Résoudre graphiquement le dual
Représenter graphiquement les droites, (D1): 2Y1+Y2=14 ; (D2): Y1+Y2=12 ; (D3): Y1+3Y2=18
Identifier la zone solution, celle qui vérifie les trois contraintes (c’est la zone contenant les hachures,
celle au-dessus des trois droites et des deux axes).
Déterminer les coordonnées des points candidats : A(0, 14); B(2 , 10) ; C(9, 3) ; D(18, 0).
π(A)=56 ; π(B)=44 ; π(C)=30 ; π(D)=36. Le minimum est atteint au point C.

S= {Y^ 1=9 ; Y^ 2=3; π^ =30 }

3. Utiliser les solutions du dual pour trouver la valeur optimale de :
3.1. Le primal de la fonction objectif
3.2. Le primal des variables de décision
Si on ajoute les variable supplémentaires au dual on obtient:
Min π =2Y 1+ 4 Y 2 Min π =2 Y 1+ 4 Y 2+0 t 1+0 t 2+0 t 3

{ {
2 Y 1+ Y 2 ≥ 14 2Y 1+Y 2− t 1=14
⟹
SC Y 1+Y 2≥ 12 SC Y 1+Y 2 −t 2=12
Y 1+3 Y 3≥ 18 Y 1+3 Y 3 −t 3=18
Y 1, Y 2 ≥0 Y 1 ,Y 2 , t 1 ,t 2 ,t 3 ≥ 0

S= {Y^ 1=9 ; Y^ 2=3; t^ 1=− 7 ; t^ 2=t^ 3=0 ; π^ =30 }

Les propriétés du dual permettent de répondre aux questions 3.1 et 3.2 à l’aide du tableau de
correspondance ci-dessous:
Primal Dual
X1=0 t1=-7
X2= t2=0
X3= t3=0
S1=0 Y1=9
S2=0 Y2=3
π=30
Il suffit alors de résoudre le système des contraintes du primal en considérant X1=0 comme suit:

{XX2+3 X 3=4 { X 2=1

2+ X 3=2 ⇒ X 1=1

D’ou le tableau final

Primal Dual
X1=0 t1=-7
X2=1 t2=0
X3=1 t3=0
 S1=0 Y1=9
S2=0 Y2=3
π=30

Exercice 2
Appliquez le même raisonnement utilisé à l’exercice précédent