CHAPITRE 1 RECHERCHE OPERATIONNELLE
CORRECTION SERIE N°1
Exercice 1 : Problème d’alimentation 1
Formulation en un PL :
On peut résumer toutes les données du problème dans le tableau suivant
M N Quantités prescrites
A 0.1 0 0.4
B 0 0.1 0.6
C 0.1 0.2 2
D 0.2 0.1 1.7
Coût 10 4
Ce genre de tableau peut aider à mieux analyser le problème et ainsi formuler le programme
linéaire correspondant.
Les variables de décision sont
xM : la quantité d’aliments M à utiliser pour l’alimentation des deux bestiaux
xN : la quantité d’aliments N à utiliser pour l’alimentation des deux bestiaux
Les contraintes de non-négativité sont x 1≥0 , x 2 ≥0 .
Le choix de cette quantité est contraint à la présence dans l’alimentation du composant
A : 0 . 1 x 1 ≥0 . 4 ⇒ x 1≥4
B : 0 . 1 x 2 ≥0 .6 ⇒ x 2 ≥6
C : 0 . 1 x 1 +0 . 2 x 2 ≥2 ⇒ x 1 +2 x2 ≥20
D : 0 . 2 x 1 + 0. 1 x 2 ≥1 .7 ⇒ 2 x 1 + x 2 ≥17
La fonction objectif est une fonction coût : z=10 x 1 + 4 x 2 .
Le programme linéaire est un programme de minimisation :
Min 10 x 1 +4 x 2
s.c. x 1≥4
x 2 ≥6
x 1 + 2 x 2 ≥20
2 x 1 + x 2 ≥17
x 1 ≥0 , x 2≥0
Exercice 2 : Problème de mélange 2
Formulation en un PL :
La décision à prendre : Combien acheter de chaque alliage A, B, …, I ?
Les variables de décision sont :
1
Méthodes et modèles de la recherche opérationnelle, A. Kaufmann, pp 24-25
2
G. B. Dantzig applications et prolongements de la programmation linéaire pp :13-14
1
CHAPITRE 1 RECHERCHE OPERATIONNELLE
xi : la quantité d’alliage i, i= A, B, …, I, à acheter.
On vérifie bien que les variables de décision xi , i= A, B, …, I, sont positives :
x A≥0 , x B≥0 , x C ≥0 , x D≥0 , x E ≥0 , x F ≥0 , xG ≥0 , x H ≥0 , x I ≥0 .
Les contraintes relatives au problème sont :
Equation de la conservation de la matière :
x A≥0 , x B≥0 , x C ≥0 , x D≥0 , x E ≥0 , x F ≥0 , xG ≥0 , x H ≥0 , x I ≥0
Equation de la satisfaction des proportions en Plomb :
x A +0 . 3 x B+ 0. 5 x C + 0. 3 x D + 0. 3 x E +0 . 4 x F +0 . 2 x G +0 . 4 x H +0 . 3 x I =0. 3
Equation de la satisfaction des proportions en Zinc :
0 . 1 x A +0 . 3 x B + 0 .5 x C + 0 .3 x D + 0. 3 x E +0 . 4 x F +0 . 2 x G +0 . 4 x H + 0. 3 x I =0 . 3
Equation de la satisfaction des proportions en Etain :
0 . 8 x A + 0 .6 x B +0 . 1 x C +0 . 1 x D +0 . 4 x E +0 . 3 x F +0 . 5 xG + 0. 1 x H +0 .5 x I =0. 4
La fonction objectif dans cet exemple représente le coût d’achat des différents alliages A, B,
C, D, E, F, G, H et I. Donc l’expression de la fonction objectif est la suivante :
z=4 .1 x A + 4 .3 x B +5 . 8 xC +6 x D+ 7 .6 x E + 7 .5 x F + 7 .3 x G +6 . 9 x H + 7 .3 x I
Le programme linéaire qui modélise ce problème mélange s'écrit :
Min 4 .1 x A +4 . 3 x B +5 .8 x C +6 x D +7 . 6 x E+7 . 5 x F +7 . 3 x G+6 .9 x H +7 . 3 x I
s.c. x A +x B +x C + x D +x E +x F +x G +x H +x I =1
0. 1 x A+0 .1 x B +0 . 4 x C +0 .6 x D +0 .3 x E+0. 3 x F +0. 3 x G +0 .5 x H +0 . 2 x I =0 .3
0. 1 x A +0 .3 x B +0 . 5 x C +0 . 3 x D +0 .3 x E+0 . 4 x F +0. 2 xG +0. 4 x H +0 .3 x I=0. 3
0. 8 x A +0 . 6 x B+0 .1 x C +0. 1 x D +0 . 4 x E +0 .3 x F +0 .5 x G +0 .1 x H +0 . 5 x I =0 . 4
x A , x B , x C , x D , x E , x F xG , x H , x I ≥0
Exercice 3 : Sélection de Médias 3
Formulation en un PL :
Les variables de décision du problème sont
x1 : le nombre de spots publicitaires dans la télévision locale
x2 : le nombre de spots publicitaires dans la télévision par satellite
x3 : le nombre de spots publicitaires dans la radio
x4 : le nombre d’affiches publicitaires dans les journaux
Les contraintes de non-négativité sont vérifiées.
Les contraintes du problème sont :
Coût total de la compagne publicitaire : 1 2 40 x +75 x +30 x 3 +15 x 4 ≤800
Nombre de clients femmes potentiels par publicité :
300 x 1 +400 x 2 +200 x 3 +100 x 4 ≥2000
Contraintes de la télévision : 40 x 1 +75 x 2 ≤500 , x 1≥3 et x 2 ≥2
Contraintes sur le nombre de publicités dans la radio et dans les journaux
5≤x3 ≤10 et
5≤x 4 ≤10 .
La fonction objectif à maximiser représente le nombre de clients potentiels par publicité
z=400 x 1 +900 x 2 +500 x3 +200 x 4 .
3
Operations research principles and practice, pp17-18
2
CHAPITRE 1 RECHERCHE OPERATIONNELLE
Le programme linéaire résultant est :
Max 400 x 1 + 900 x2 +500 x3 +200 x 4
s.c. 40 x 1 +75 x 2 +30 x 3 +15 x 4 ≤800
30 x1 +40 x 2 +20 x 3 +10 x 4 ≥2000
40 x1 +75 x 2 ≤500
x1 ≥3
x2 ≥2
x3 ≥5
x3 ≤10
x4 ≥5
x4 ≤10
x 1 ≥0 , x 2 ≥0 , x 3 ≥0 , x 4 ≥0
