EPFL MATHÉMATIQUES DISCRÈTES

Institut de Mathématiques IN
J.-F. Hêche HIVER 2005/2006

CORRIGÉ DE LA SÉRIE D’EXERCICES 1

Problème 1

a) Forme canonique :

Maximiser z = 2x1 − x+2 + x−2

s.c. 1
3 x1 + x+2 − x−2 ≤ 2
− 13 x1 − x+2 + x−2 ≤ −2
−2x1 + 5x+
2 − 5x−
2 ≤ 7
x1 + x+2 − x−2 ≤ 4
x1 , x+
2 , x−
2 ≥ 0

avec x2 = x+ −
2 − x2 .
Forme standard :
Maximiser z = 2x1 − x+2 + x−2
s.c. 1
3 x1 + x+2 − x−2 = 2
+ −
−2x1 + 5x2 − 5x2 + x3 = 7
x1 + x2 − x−2 + x4 = 4
x1 , x+
2 , x−
2 , x3 , x4 ≥ 0

toujours avec x2 = x+ −
2 − x2 .
b) Forme canonique :

Maximiser z̄ = 3x1 − x3
1 −
s.c. −x1 + 2 x2 + 3x3 ≤ −2
−4x−2 + x3 ≤ 5
4x−2 − x3 ≤ −5
x1 , x−
2 , x3 ≥ 0

avec x2 = −x−
2 et z = −z̄.
Forme standard :
Maximiser z̄ = 3x1 − x3
1 −
s.c. x1 − 2 x2 − 3x3 − x4 = 2
−4x−2 + x3 = 5
x1 , x−
2 , x3 , x4 ≥ 0

toujours avec x2 = −x−

2 et z = −z̄.
c) Forme canonique :
Maximiser z̄ = −2x1 + 3x′2 − 9
s.c. 2x1 − x′2 ≤ 5
−2x1 + x′2 ≤ 1
x1 − 3x′2 ≤ 8
x1 , x′2 ≥ 0
avec x2 = x′2 − 3 et z = −z̄.

1
 Forme standard :
Maximiser z̄ = −2x1 + 3x′2 − 9
s.c. 2x1 − x′2 = 5
−x1 + 3x′2 − x3 = 10
x1 , x′2 , x3 ≥ 0

toujours avec x2 = x′2 − 3 et z = −z̄.

Problème 2
Soient les variables de décision :

x1 : nombre de litres d’essence de bergamote produits en une semaine avec

traitement des déchets,
x2 : nombre de litres d’essence de bergamote produits en une semaine sans
traitement des déchets.
On obtient le problème suivant :

Maximiser z = −0.4 · 5x1 − 15(0.4 · 0.2x1 + 0.4x2 ) + 110(x1 + x2 ) − 20(x1 + x2 )

s.c. 0.4x1 ≤ 8000
0.4 · 0.2x1 + 0.4x2 ≤ 2800
x1 , x2 ≥ 0
Après simplification et mise sous forme d’un programme linéaire :

Minimiser z = −86.8x1 − 84x2

s.c. 0.4x1 − 8000 ≤ 0
0.08x1 + 0.4x2 − 2800 ≤ 0
x1 , x2 ≥ 0

Problème 3
Le plan de production de l’entreprise doit préciser le ¡¡ volume ¿¿ des quatre opérations possibles :
1. presser des olives pour obtenir de l’huile A ;
2. presser des olives pour obtenir de l’huile B ;
3. raffiner de l’huile A ;
4. raffiner de l’huile B.
Associons à chacune de ces opérations une variable de décision :
x1 : nombre de tonnes d’olives pressées pour obtenir de l’huile A ;
x2 : nombre de tonnes d’olives pressées pour obtenir de l’huile B ;
x3 : nombre de litres d’huile A raffinés ;
x4 : nombre de litres d’huile B raffinés ;
La quantité totale (en litres) d’huile A vendue est 300x1 − x3 et ne doit pas dépasser 3000 litres.
La première contrainte est donc
300x1 − x3 ≤ 3000.
La quantité totale (en litres) d’huile B vendue est 200x2 + 0.6x3 − x4 et ne doit pas dépasser
3000 litres. La deuxième contrainte est donc

200x2 + 0.6x3 − x4 ≤ 3000.

2
La quantité totale (en litres) d’huile C vendue est 0.3x3 + 0.8x4 et ne doit pas dépasser 2000
litres. La troisième contrainte est donc

0.3x3 + 0.8x4 ≤ 2000.

Il n’est pas possible de raffiner plus d’huile A qu’il n’en a été pressée. Le plan de production
doit donc vérifier
x3 ≤ 300x1 .
De même, la quantité d’huile B raffinée doit satisfaire

x4 ≤ 200x2 + 0.6x3 .

Finalement, les variables de décision ne peuvent pas prendre des valeurs négatives et doivent
satisfaire
x1 , x2 , x3 , x4 ≥ 0.
Les coûts d’achat et de transformation sont

1000(x1 + x2 ) + 0.5x3 + 0.3x4

et le chiffre d’affaires mensuel est

4(300x1 − x3 ) + 6(200x2 + 0.6x3 − x4 ) + 10(0.3x3 + 0.8x4 ).

Le profit mensuel de l’entreprise est donc

z = 4(300x1 − x3 ) + 6(200x2 + 0.6x3 − x4 ) + 10(0.3x3 + 0.8x4 )

 
− 1000(x1 + x2 ) + 0.5x3 + 0.3x4
= 200x1 + 200x2 + 2.1x3 + 1.7x4 .

En résumé, le programme linéaire que doit résoudre l’entreprise est

Maximiser z = 200x1 + 200x2 + 2.1x3 + 1.7x4
s.c. 300x1 − x3 ≤ 3000
200x2 + 0.6x3 − x4 ≤ 3000
0.3x3 + 0.8x4 ≤ 2000
−300x1 + x3 ≤ 0
−200x2 − 0.6x3 + x4 ≤ 0
x1 , x2 , x3 , x4 ≥ 0

Problème 4

a) Introduisons une nouvelle variable, t ∈ R, telle que

t ≥ 2x1 + 3x2 et
t ≥ x1 − 2x2 + 4x3 .

Le programme linéaire s’écrit alors

Minimiser z = t
s.c. −2x1 + x3 = 12
x1 + 2x2 ≤ 5
2x1 + 3x2 − t ≤ 0
x1 − 2x2 + 4x3 − t ≤ 0
x1 , x2 , x3 ≥ 0
t ∈ R

3
 En posant t = t+ − t− avec t+ , t− ≥ 0, et en utilisant le fait que a = b si et seulement si
a ≥ b et a ≤ b, le programme linéaire considéré prend la forme canonique suivante :

Maximiser z̄ = t− − t+
s.c. −2x1 + x3 ≤ 12
2x1 − x3 ≤ −12
x1 + 2x2 ≤ 5
2x1 + 3x2 − t+ + t− ≤ 0
x1 − 2x2 + 4x3 − t+ + t− ≤ 0
x1 , x2 , x3 , t+ , t− ≥ 0

avec z = −z̄.

Remarque. L’introduction des variables t+ et t− n’est en fait pas nécessaire dans ce problème.
En effet, puisque t ≥ 2x1 +3x2 et que x1 , x2 ≥ 0, la variable t est nécessairement non négative.
b) Rappelons tout d’abord que minimiser |x| est équivalent au problème suivant :

Minimiser |x| = Minimiser t

s.c. t ≥ x
t ≥ −x
t ≥ 0.

La contrainte x1 − 4x2 + x3 = 5 peut être remplacée par les deux contraintes x1 − 4x2 + x3 ≤ 5
et −x1 + 4x2 − x3 ≤ −5. Le programme linéaire sous forme canonique s’écrit donc :

Maximiser z̄ = −t1 − t2
s.c. x1 − 4x2 + x3 ≤ 5
−x1 + 4x2 − x3 ≤ −5
5x2 − 3x3 ≤ 6
x1 − 2x3 − t1 ≤ 0
−x1 + 2x3 − t1 ≤ 0
−x1 + 3x2 + x3 − t2 ≤ 0
x1 − 3x2 − x3 − t2 ≤ 0
x1 , x2 , x3 , t1 , t2 ≥ 0

avec z = −z̄.

c) Le problème est équivalent au programme linéaire suivant :

Minimiser z = t1 + t2
s.c. x1 + x2 ≤ 1
−x1 + x2 ≤ 1
−x1 + x2 + x3 ≤ 7
x1 − x2 − 2x3 ≤ 7
x1 − 10 ≤ t1
−x1 + 10 ≤ t1
2x2 − 4 ≤ t2
3x1 − 4x3 ≤ t2
−3x1 + 4x3 ≤ t2
x1 , x2 , x3 , t1 ≥ 0
t2 ∈ R

4
 La forme canonique est donnée par :

Maximiser z̄ = −t1 − t+ −
2 + t2
s.c. x1 + x2 ≤ 1
−x1 + x2 ≤ 1
−x1 + x2 + x3 ≤ 7
x1 − x2 − 2x3 ≤ 7
x1 − t1 ≤ 10
−x1 − t1 ≤ −10
2x2 − t+
2 + t−2 ≤ 4
3x1 − 4x3 − t2 + t−
+
2 ≤ 0
−3x1 + 4x3 − t+
2 + t −
2 ≤ 0
x1 , x2 , x3 , t1 , t2 , t−
+
2 ≥ 0

avec z = −z̄.

Problème 5
Les droites de visée sont données par :

A: x = 3,
B: y = 5/12x + 3/2,
C: y = 3,
D: y = −3/4x + 9/2.

On cherche la position (x, y) du voilier minimisant la somme des erreurs de visée. Ces erreurs
sont données par :

A: e1 = |3 − x|,
|5/12(6 − x) − (4 − y)| 12 · |(5/12)(6 − x) − (4 − y)|
B: e2 = p = ,
(25/144 + 1) 13
C: e3 = |3 − y|,
| − 3/4(6 − x) + y| 4 · |(−3/4)(6 − x) + y|
D: e4 = p = .
(9/16 + 1) 5

Le problème peut être formulé de la manière suivante :

Minimiser z = e1 + e2 + e3 + e4
s.c. e1 = |3 − x|
12·|(5/12)(6−x)−(4−y)|
e2 = 13
e3 = |3 − y|
4·|(−3/4)(6−x)+y|
e4 = 5
e1 , e2 , e3 , e4 , x , y ≥ 0

Remarque. Les variables x et y sont a priori libres mais une esquisse du problème montre que
la solution se trouve dans le premier quadrant. Nous avons donc préféré simplifier la formulation
en imposant x, y ≥ 0.

5
Le PL correspondant à la formulation ci-dessus est donné par :

Minimiser z = e1 + e2 + e3 + e4
s.c. −x − e1 ≤ −3
x − e1 ≤ 3
−5/12x + y − 13/12e2 ≤ 3/2
5/12x − y − 13/12e2 ≤ −3/2
− y − e3 ≤ −3
y − e3 ≤ 3
3/4x + y − 5/4e4 ≤ 9/2
−3/4x − y − 5/4e4 ≤ −9/2
x , y , e1 , e2 , e3 , e4 ≥ 0

6 novembre 2005 – JFH