EPFL MATHÉMATIQUES DISCRÈTES
Institut de Mathématiques MA/IN
J.-F. Hêche HIVER 2003/2004
CORRIGÉ DE LA SÉRIE D’EXERCICES 1
Les énoncés des séries et leurs corrigés ainsi que les copies des présentations sont disponibles
sur le site du cours : [Link]
Problème 1
a) L’ensemble des solutions du système d’inéquations est donné par la région grisée ci-dessous :
x2
10
8
(4)
6
(3)
(1)
4
2
(2)
x1
−2 2 4 6 8 10 12
−2
b) Étudions la variation du domaine des solutions en fonction du membre de droite de
l’inéquation (1) noté b1 .
Si b1 ≥ 24, l’inéquation (1) est inutile : Si b1 < −25, il n’y a pas de solutions :
x2 x2
10 10
4x − 5y = −25
8 8
(4) (4)
6 6
(3) (3)
4 4
2 2 (2)
(2)
x1 x1
−2 2 4 6 8 10 12 −2 2 4 6 8 10 12
−2 −2
4x − 5y = 24
Problème 2
a) La zone grisée du graphique ci-dessous représente le domaine admissible des solutions du
programme linéaire. Il est non borné.
1
18 x2
16 c
14 z=8
12
10
8 b
6
4
2 a
x1
−2 2 4 6 8 10 12 14
−2
En faisant varier la ligne de niveau de z, on trouve que la valeur optimale de la fonction
objectif vaut 8, avec x1 = 0 et x2 = 2 (point extrême a).
b) Étudions la variation de z en fonction du coefficient de la variable x 1 dans la fonction
objectif noté c1 .
−∞ ≤ c1 ≤ −20 L’optimum est en a pour une valeur de la fonction objectif
z ∗ = 8, avec x∗1 = 0 et x∗2 = 2.
−20 ≤ c1 ≤ −4 L’optimum est en b pour une valeur de la fonction objectif
z ∗ = 45 c1 + 33, avec x∗1 = 1.25 et x∗2 = 8.25.
−4 ≤ c1 ≤ − 38 L’optimum est en c pour une valeur de la fonction objectif
z ∗ = 9c1 + 64, avec x∗1 = 9 et x∗2 = 16.
− 38 ≤ c1 ≤ ∞ Le problème n’admet plus d’optimum fini.
z∗
50
(−2.6̄,40) 40
(−4,28) 30
20
10
(−20,8)
c1
−20 −10
Nous obtenons une fonction convexe, linéaire par morceaux.
Remarque. Pour trouver les points de ((cassure)) de cette fonction il suffit de déterminer
les valeurs de c1 pour lesquelles la fonction z a la même pente qu’une des contraintes.
2
Problème 3
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
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 z = 340 frs en fabriquant x 1 = 22 radios A et x2 = 1
radio B, car elle vend toute sa production.
3
Problème 4
a) L’ensemble des combinaisons linéaires de deux vecteurs linéairement indépendants dans le
plan est R2 :
S = {x ∈ R2 | x = λ1 a + λ2 b, λ1 ,λ2 ∈ R}.
b) L’ensemble des combinaisons coniques de deux vecteurs linéairement indépendants dans
le plan est le cône engendré par ces deux vecteurs :
S = {x ∈ R2 | x = λ1 a + λ2 b, λ1 ,λ2 ≥ 0, λ1 ,λ2 ∈ R}
14
12
10
8
6
4
2
2 4 6 8 10 12 14
c) L’ensemble des combinaisons affines de deux vecteurs linéairement indépendants dans le
plan est la droite qui passe par les extrémités de ces deux vecteurs :
S = {x ∈ R2 | x = λ1 a + λ2 b, λ1 + λ2 = 1, λ1 ,λ2 ∈ R}.
8
6
4
2
2 4 6 8
d) L’ensemble des combinaisons convexes de deux vecteurs linéairement indépendants dans
le plan est le segment compris entre les extrémités de ces deux vecteurs :
S = {x ∈ R2 | x = λ1 a + λ2 b, λ1 + λ2 = 1, λ1 ,λ2 ≥ 0, λ1 ,λ2 ∈ R}.
8
6
4
2
2 4 6 8
4
Relations entre les différentes combinaisons :
Combinaison linéaire
de x1 , . . . ,xn
X
λ i xi P
λi ≥ 0, ∀i i i λi = 1
avec λi ∈ R, ∀i
Combinaison conique Combinaison affine
de x1 , . . . ,xn de x1 , . . . ,xn
X X
λ i xi λ i xi
i i
avec λi ∈ R, ∀i avecP
λi ∈ R, ∀i
et λi ≥ 0, ∀i et i λi = 1
Combinaison convexe P
λi ≥ 0, ∀i, de x1 , . . . ,xn i λi = 1,
P
i λi = 1 X λi ≥ 0, ∀i
λ i xi
i
P avec λi ∈ R, ∀i,
i λi = 1 et λi ≥ 0, ∀i
Problème 5
a) La distance δ entre le plan a1 x1 + a2 x2 + a3 x3 = b et le point p est donnée par
|b − a1 p1 − a2 p2 − a3 p3 | |5 − 4 · 1 − 2 · 3 − 3 · 6| 23
δ= p = √ =√ .
2 2
a1 + a2 + a32 16 + 4 + 9 29
b) La distance δ entre l’hyperplan ax = b et p (p, a, x ∈ R n ) est donnée par
|b − ap|
δ= .
||a||
c) Le vecteur a est le vecteur normal à l’hyperplan orienté vers l’extérieur du demi-espace
ax ≤ b. La variable d’écart s représente donc la ((distance signée)) entre le point p et
l’hyperplan ax = b à un facteur près, d’où son nom.
b − ap
La ((distance signée)) exacte entre le point p et l’hyperplan ax = b est . Cette
||a||
distance est positive ou nulle si le point p se trouve dans le demi-espace ax ≤ b et négative
sinon.
22 octobre 2003 – JFH/sp
