EPFL RECHERCHE OPÉRATIONNELLE
Institut de Mathématiques GC
Prof. M. Bierlaire ÉTÉ 2006
CORRIGÉ DE LA SÉRIE D’EXERCICES 2
Problème 1
a) Dans le graphe ci-dessous, la zone grisée représente le domaine des solutions admissibles.
x2
(2) (1)
5
z=9
4
c
d
2
b z=0
(3) x1
a e
−1 1 2 3 4 5 6
−1
b) Les points extrêmes du domaine admissible sont :
a = (0,0), b = (0,2), c = (1.5,3.5), d = (3,2) et e = (4,0).
c) On a représenté deux lignes de niveau de la fonction objectif z : z = 0 et z = 9. En
translatant la ligne de niveau de la fonction objectif correspondant à z = 0 le plus loin
possible dans la direction opposée au gradient (on minimise) tout en restant admissible,
on constate que le point extrême que l’on atteint est c. Il correspond donc à l’optimum.
La valeur optimale du problème est z ∗ = −9 et la solution optimale correspondante est
x∗1 = 1.5 et x∗2 = 3.5.
1
d) Le programme linéaire sous forme canonique :
Minimiser z = x1 − 3x2
s.c. −x1 + x2 ≤ 2
2x1 + x2 ≤ 8
x1 + x2 ≤ 5
x1 , x2 ≥ 0
Mettons-le sous forme standard :
Minimiser z = x1 − 3x2
s.c. −x1 + x2 + x3 = 2
2x1 + x2 + x4 = 8
x1 + x2 + x5 = 5
x1 , x2 , x3 , x4 , x5 ≥ 0
Problème 2
a) Posons x1 le nombre de radios de type A et x2 le nombre de radios de type B produites
chaque semaine.
Comme Pierre consacre 1 h par radio de type A et 2 h par radio de type B et que son
nombre total d’heures hebdomadaires de travail ne doit pas dépasser 24, la contrainte le
concernant est exprimée par :
x1 + 2x2 ≤ 24.
Comme Paul consacre 2 h par radio de type A et 1 h par radio de type B et que son
nombre total d’heures hebdomadaires de travail ne doit pas dépasser 45, la contrainte le
concernant est exprimée par :
2x1 + x2 ≤ 45.
Comme Jean consacre 1 h par radio de type A et 3 h par radio de type B et que son
nombre total d’heures hebdomadaires de travail ne doit pas dépasser 30, la contrainte le
concernant est exprimée par :
x1 + 3x2 ≤ 30.
Chaque radio de type A produite rapportant 15 frs et chaque radio de type B produite
rapportant 10 frs, on a la fonction objectif z à maximiser suivante :
z = 15x1 + 10x2 .
Le programme linéaire maximisant le chiffre d’affaires hebdomadaire de RadioIn est donc
donné par :
Max z = 15x1 + 10x2
s.c. x1 + 2x2 ≤ 24 (1)
2x1 + x2 ≤ 45 (2)
x1 + 3x2 ≤ 30 (3)
x1 , x2 ≥ 0
2
b) En faisant varier la ligne de niveau de z, on trouve l’optimum suivant :
x2
z = −340
(1)
10
(3)
x1
10 20 30
(2)
La fabrique RadionIn gagne donc 340 frs en fabriquant x 1 = 22 radios A et x2 = 1 radio
B, car elle vend toute sa production.
c) Le programme linéaire sous forme canonique s’énonce de la façon suivante :
Min z = −15x1 − 10x2
s.c. x1 + 2x2 ≤ 24
2x1 + x2 ≤ 45
x1 + 3x2 ≤ 30
x1 , x2 ≥ 0
Mettons-le à présent sous forme standard :
Min z = −15x1 − 10x2
s.c. x1 + 2x2 + x3 = 24
2x1 + x2 + x4 = 45
x1 + 3x2 + x5 = 30
x1 , x2 , x3 , x4 , x5 ≥ 0
Problème 3
a) Le domaine des solutions admissibles est :
5
x − y = −2
4
2 optimum
D
1
0
0 1 2 3 4 5
x+y =5
z=6 2x + y = 8
3
Les points extrêmes de D sont :
3
0 0 2 3 4
, , 7 , ,
0 2 2 2 0
b) On détermine la solution optimale graphiquement, en représentant les lignes de niveau de
z. L’optimum est atteint en (3,2) et a une valeur égale à -13.
c) Le programme linéaire sous forme canonique s’écrit de la façon suivante :
Minimiser z = −3x − 2y
s.c. −x + y ≤ 2
2x + y ≤ 8
x + y ≤ 5
x ≥ 0
y ≥ 0
Mettons-le sous forme standard :
Minimiser z = −3x − 2y
s.c. −x + y + a = 2
2x + y + b = 8
x + y + c = 5
x , y , a , b , c ≥ 0
Problème 4
a) Définissons les variables de décision :
x1 : nombre de panneaux de type I produits chaque jour ;
x2 : nombre de panneaux de type II produits chaque jour.
La fonction objectif à maximiser est le chiffre d’affaires de l’entreprise, il est donné par :
z = 800x1 + 300x2 .
La contrainte décrivant la capacité de production journalière est :
2x1 + x2 ≤ 400.
À cette contrainte vient s’ajouter les limitations du marché et la non-négativité des quantités
produites :
0 ≤ x1 ≤ 150
0 ≤ x2 ≤ 200.
Le programme linéaire recherché est donc :
Max z = 800x1 + 300x2
s.c. 2x1 + x2 ≤ 400
x1 ≤ 150
x2 ≤ 200
x1 , x 2 ≥ 0
b) La solution optimale (voir figure 1) est de produire chaque jour :
x1 = 150 panneaux de type I
x2 = 100 panneaux de type II pour un chiffre d’affaires de
z = 150’000 Frs.
4
x2
z = 150'000
région solution optimale
100 admissible
100 x1
Fig. 1 – Résolution graphique du problème des cellules photoélectriques.
c) Il suffit de transformer le problème linéaire de maximisation sous a) en un problème de
minimisation pour obtenir la formulation canonique :
Min z = −800x1 − 300x2
s.c. 2x1 + x2 ≤ 400
x1 ≤ 150
x2 ≤ 200
x1 , x 2 ≥ 0
Mettons-le sous forme standard :
Min z = −800x1 − 300x2
s.c. 2x1 + x2 + x3 = 400
x1 + x4 = 150
x2 + x5 = 200
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0
5 avril 2006 – mbi/mt/mts
