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