Fatimata Abdoulaye THIAM

Faty Mbacké Basse

Aminata BARRY
Aminata FALL
Niveau: M1 Géotechnique

Devoir recherche Opérationnelle

EXERCICE 3 :
a) Lorsque α = 1 et β = 4,
On a
Min Z = −x1 − x2 + x3 − x4
Sous contraintes
x1 − x3 + 2x4 = 4
x2 + 2x3 + x4 = 4
x1 , x2 , x3 , x4 ≥ 0

Montrons que la solution x1 = x2 = 4, x3 = x4 = 0 est optimale.

 Méthode du simplexe Tableaux.
Etape 1 :

x1 x2 x3 x4 e1 e2 Solution
Z -1 -1 1 -1 0 0 0
e1 1 0 -1 2 0 0 4
e2 0 1 2 1 0 0 4

Etape 2 : On remplace e1 par x1

x1 x2 x3 x4 e1 e2 Solution
Z 0 -1 0 1 0 0 4
x1 1 0 -1 2 0 0 4
e2 0 1 2 1 0 0 4
Etape 3 : On remplace e2 par x2
x1 x2 x3 x4 e1 e2 Solution
Z 0 0 2 2 0 0 8
x1 1 0 -1 2 0 0 4
x2 0 1 2 1 0 0 4

On x1=x2=4 et x3=x4=0
Z=8
b) Si β = 4, pour quelles valeurs de α cette solution demeure-t-elle optimale ?
Logiciel Excel Solveur
Après avoir mis les valeurs sur Excel solveur on obtiens :
Variable x1 X2 X3 X4

Profit/unit -1 1 -1
Optimal solution 0 2 0 2
Optimal solution
Value -4
RHS
contrainte 1 1 0 -1 2 < 4
contrainte 2 0 1 1 1 < 4

LHS RHS
contrainte 1 4 4
contrainte 2 4 4
Si on ne donne pas une valeur a α on obtient une solution optimale de –4

 Le Tableau de sensibilité 1:
 

 Le Tableau de sensibilité 2 :
  Le Tableau de sensibilité 3 :

D’après les rapports de sensibilité :

Les rapports de sensibilité indiquent que le coefficient α dans la fonction objective
peut varier entre 0 et 1 sans changer la solution optimale, cela signifie que tant que
α reste dans cette plage, la solution optimale trouvée restera la même. Si α dépasse
cette plage, la solution optimale pourrait changer, et on va résoudre à nouveau le
problème pour obtenir la nouvelle solution optimale.
 c) Lorsque α = 1 et β = 4,
On a
Min Z = − x1 − x2 + x3 − x4
Sous contraintes
x1 − x3 + 2x4 = 4
x2 + 2x3 + x4 = 4
x1 , x2 , x3 , x4 ≥ 0

d) Lorsque α = 1 et β = 4, formulons le dual du programme linéaire :

1 0 -1 2 B= 4 -1
A=
0 1 2 1 4 C= -1
1
-1

T = [y1 y2],

MaxW=λT b
s.C.
λ T A ≥ cT
λ≥0

1 0 -1 2
y1 y2 ≥ -1 -1 1 -1
* 0121
Max W= 4y1 + 4y2
S.C.
y1 ≥ -1
y2 ≥ -1
-y1 + 2y2 ≥ 1
2y1 + y2 ≥ -1

Exercice4 :
Produit : A, B, C
Vitamines=1, 2, 3, 4
aij=quantité de i contenue dans j
i=1, 2, 3, 4
j=A, B, C
Pj=prix au kg du produit j
di=besoin journalier en vitamine i
a) Quantités de produits A, B, C à utiliser
Soit : XA : quantité de A à produire en kg
XB : quantité de B à produire en kg
XC : quantité de C à produire en kg
PA : prix au kg du produit A
PB : prix au kg du produit B
PC : prix au kg du produit C
d1 : besoin journalier en vitamine 1
d2 : besoin journalier en vitamine 2
 d3 : besoin journalier en vitamine 3
d4 : besoin journalier en vitamine 4
 Objectif :
Minimisons le cout d’achat :
MinZ=PAXA + PBXB + PCXC
S.C

α1AXA + α1BXB + α1 C XC ˃ d1
α2AXA+ α2BXB + α2C XC ˃ d2
α3AXA + α3BXB+ α3C XC ˃ d3
α4AXA + α4BXB + α4C XC ˃ d4
XA, XB, XC ˃ 0
b) Le dual du problème
α1A + α1B + α1C d1 PA Y1

A= α2A + α2B + α2C d2 PB Y4

B=
C= λ=
= α3A + α3B + α3C d3 PC Y3
α4A + α4B + α4C d4 Y4
MaxW=λT b
s.C.
λ T A ˂ cT
λ≥0

Max W= d1Y1 + d2Y2 + d3Y3 + d4Y4

α1AY1 + α2AY2 + α3AY3 + α4AY4 ˂ PA
α1BY1 + α2BY2 + α3BY3 + α4BY4 ˂ PB
α1CY1 + α2CY2 + α3CY3 + α4CY4 ˂ PC
Y1, Y2, Y3, Y4 ˃ 0
  Interprétation en terme économique du dual :
 Variables duales Yi : Chaque Yi représente le cout marginal lié à une
augmentation d’une unité (g/kg) de vitamine i. En d’autres termes, Yi est le
prix d’ombre associé à la vitamine i.
 Objectif dual W : Maximiser la valeur totale des prix d’ombre correspondant
aux besoins en vitamines.
 Contraintes duales : les contraintes duales stipulent que la somme pondérée
des prix d’ombre des vitamines (pondérée par les coefficients aij) ne doit pas
dépasser le prix du produit j. En d’autres termes, le cout d’achat d’un kg de
produit j ne doit pas excéder ce que l’entreprise est prête à payer pour les
vitamines apportées par ce produit.

Exercice 5 :
Déterminons la production journalière de manière à maximiser le prix de vente
total.

 Variables de décision :

 xA : nombre de tonnes d'acier de type A produites par jour

 xB: nombre de tonnes d'acier de type B produites par jour
 xC: nombre de tonnes d'acier de type C produites par jour

 Fonction Objective :
Max Z=3xA+4xB+2xC

 Contraintes

Les contraintes sont liées à la disponibilité des matières premières :

 Contrainte sur le fer :

2 xA + xB +2 xC ≤30

 Contrainte sur la houille :

xA +3 xB +2 xC ≤60

Avec xA ; xB; xc >0

 Programmation linéaire :

Max Z=3xA + 4xB + 2xC

2 xA +1xB +2xC≤30

xA +3xB+2xC≤60

xA ; xB; xc >0

 Résolution du problème par la méthode de simplexe Tableau :

Max Z=3xA + 4xB + 2xC

2 xA +1xB +2Xc + e1 =30

xA +3xB+2xC + e2 = 60

xA ; xB; xc >0

xA xB xC e1 e2 Solution
Z -3 -4 -2 0 0 0
e1 2 1 2 1 0 30
e2 1 3 2 0 1 60

 On remplace e2 par XB en multipliant la ligne 3 par 1/3

xA xB xC e1 e2 Solution
Z -3 -4 -2 0 0 0
e1 2 1 2 1 0 30
XB 1/3 1 2/3 0 1/3 20

 On obtient :

xA xB xC e1 e2 Solution
Z -5/3 0 2/3 0 4/3 80
e1 5/3 0 4/3 1 -1/3 10
XB 1/3 1 2/3 0 1/3 20
  On remplace e1 par xA en multipliant la ligne 2 par 3/5

xA xB xC e1 e2 Solution
Z -5/3 0 2/3 0 4/3 80
e1 1 0 4/5 3/5 -1/5 6
XB 1/3 1 2/3 0 1/3 20

On obtient :

xA xB xC e1 e2 Solution
Z 0 0 2 1 1 90
XA 1 0 4 3 -1 6
XB 0 1 2/5 -1/5 2/5 18

Ainsi

xA =6

xB =18

xC =0

Z=90

 Résolution avec la méthode Excel solveur :

Variable xA xB xC

Profit/unit 3 4 2
Optimal solution 6 18 0
Optimal solution Value 90
RHS
contrainte 1 2 1 2 < 30
contrainte 2 1 3 2 < 60

LHS RHS
contrainte 1 30 30
contrainte 2 60 60
D’après Excel solveur on obtiens
xA =6
xB =18
xC =0
Et Max Z =90
En conclusion, la production journalière optimale est de 6 tonnes d'acier A, 18
tonnes d'acier B, et 0 tonnes d'acier C pour maximiser le prix total à 90 millions.

Exercice 6 :
Donnons un modèle permettant de déterminer les compositions des mélanges et les quantités à
produire pour maximiser la recette

 Variables de décision :

Soit :

X1A :la quantité du constituant 1 dans l’essence A

X2A :la quantité du constituant 2 dans l’essence A

X3A :la quantité du constituant 3 dans l’essence A

X1B :la quantité du constituant 1 dans l’essence B

X2B :la quantité du constituant 2 dans l’essence B

X3B :la quantité du constituant 3 dans l’essence B

 Fonction Objective :
Max Z =5.5(X1A+ X2A+ X3A) + 4.5(X1B+ X2B+ X3B)-3(X1A+ X1B)+6(X2A+ X2B)+4(X3A+ X3B)

 Contraintes :

X1A+ X1B< 3000

X2A+ X2B< 2000
X3A+ X3B< 4000
X1A
< 0.3
X1A+ X2A+ X3A
X2A
< 0.4
X1A+ X2A+ X3A
X3A
< 0.5
X1A+ X2A+ X3A
X1B
<0.5
X1B+ X2B+ X3B
X2B
<0.1
X1B+ X2B+ X3B

X1A; X2A; X3A;>0

X1B; X2B; X3B>0
On pose:
RA= X1A+ X2A+ X3A
RB= X1B+ X2B+ X3B
Ainsi on a :
Max Z =5.5 RA +4.5RB - 3(X1A+ X1B) +6(X2A+ X2B)+4(X3A+ X3B)
X1A+ X1B< 3000
X2A+ X2B< 2000
X3A+ X3B< 4000
X1A < 0.3RA
X2A < 0.4 RA
X3A < 0.5 RA
X1B < 0.5RB
X2B < 0.1RB
X1A; X2A; X3A >0
X1B; X2B; X3B >0