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 5

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
En appliquant la règle de Bland, on trouve les pivots suivants.

x1 x2 x3 x4 x5 x6 z q.c.
1 4 1 0 3 0 0 5 5
0 -2 2 1 5 0 0 4 2 ←
T1 =
0 7 2/3 0 8 1 0 2 3
0 10 -5 0 3 0 1 23
↑

Le tableau T2 est admissible et non borné. On arrête donc l’optimisation, i.e. il n’existe pas de
prochain pivot.

x1 x2 x3 x4 x5 x6 z q.c.
4 7 0 0 1 4 0 4 4/7
2 8 0 1 0 3 0 0 0
T3 =
-2 9 1 0 0 2 0 0 0 ←
5 -2 0 0 0 -5 1 3
↑

x1 x2 x3 x4 x5 x6 z q.c.
5 0 0 1 4 1 0 1 1
-3 0 1 -7 5 0 0 14 -
T4 =
2 1 0 8 2 0 0 8 1 ←
8 0 1 -3 -2 0 1 -4
↑

Le tableau T5 est optimal.

x1 x2 x3 x4 x5 x6 z q.c.
3 3 1 0 4 0 0 0 0 ←
2 2 0 0 3 1 0 1 2
T6 =
0 5 0 1 2 0 0 4 -
-8 4 0 0 -1 0 1 2
↑

1
Problème 2

a)
Min w = −y1 − y2
s.c. y1 − 2y2 = 0
y1 + y2 ≤ 7
2y1 + y2 ≥ 2
y1 ∈ R
y2 ≥ 0
b)
Max w = −5y1
s.c. −y1 + y2 ≤ 4
2y1 + y2 = 2
y1 , y 2 ≥ 0
c)
Min w = 4y1 + 2y2
s.c. y1 = 3
−y1 + 2y2 ≥ −5
y1 + y 2 ≥ 0
y1 ≥ 0
y2 ∈ R
d)
Max w = 5y1 + 12y2 + 6y3
s.c. 2y1 + y3 = 3
−y1 + 3y2 ≤ 0
2y1 + 4y2 ≤ −1
y1 ≥ 0
y2 ∈ R
y3 ≤ 0
e)
Min w = 8y1 + 6y2 − 3y3
s.c. −y1 + 2y2 ≥ 0
4y1 ≥ 5
2y1 + y2 + y3 = 1
y1 ≥ 0
y2 ∈ R
y3 ≤ 0

Problème 3

a) Le plan de production maximisant le chiffre d’affaires est solution du programme linéaire :

Maximiser z = 8x1 + 6x2 + 15x3

s.c. 4x1 + 2x2 + 12x3 ≤ 3000
2x1 + x2 + 4x3 ≤ 1200
1 3 1
10 x1 + 20 x2 + 10 x3 ≤ 100
x1 , x2 , x3 ≥ 0

2
 b) Le problème dual est :

Miminiser w = 3000y1 + 1200y2 + 100y3

1
s.c. 4y1 + 2y2 + 10 y3 ≥ 8
3
2y1 + y2 + 20 y3 ≥ 6
1
12y1 + 4y2 + 10 y3 ≥ 15
y1 , y2 , y3 ≥ 0
c) Le plan de production optimale est donné par :
x∗1 = 25,x∗2 = 550,x∗3 = 150,(x∗4 = x∗5 = x∗6 = 0),z ∗ = 5750.
La solution optimale duale se lit dans la dernière ligne de T opt :
y1∗ = 1/4,y2∗ = 5/2,y3∗ = 20,(y4∗ = y5∗ = y6∗ = 0),w∗ = 5750.

d) Le coût marginal associé à la première ressource (le temps de façonnage) est y 1∗ = 1/4
et celui associé à la deuxième ressource (le temps d’emballage) est y 2∗ = 5/2. Il est donc
préférable d’essayer d’augmenter en premier le temps d’emballage car, pour une augmen-
tation égale, l’impact sur le chiffre d’affaires sera plus important.

Problème 4
Le problème dual est :
Minimiser z = 2y1 − 3y2
s.c. y 1 − y2 ≥ 3
−y1 + y2 ≥ −2
y1 , y2 ≥ 0
Les contraintes du primal s’écrivent aussi :
x1 − x 2 ≤ 2
x1 − x 2 ≥ 3
et le problème n’a pas de solutions admissibles.
De même, les contraintes du dual s’écrivent :
y1 − y 2 ≥ 3
y1 − y 2 ≤ 2
et ce problème est, lui aussi, sans solution admissible.

Problème 5
La droite passant par P et perpendiculaire à l’hyperplan a i x = bi est donnée par
ai
y+λ , λ ∈ R.
kai k
ai est un vecteur perpendiculaire à l’hyperplan d’équation a i x = bi et est dirigé vers l’extérieur
du domaine P . La distance di entre y et cet hyperplan est donnée par l’équation
 
ai
bi = a i x = a i y + d i .
kai k
b −a y
La distance di vaut donc ika ik . Si y ∈ P , cette valeur est positive. On peut donc formuler le
i
problème de la manière suivante :
Max z = min{d1 , . . . ,dm }
b −a y
s.c. di = ika ik i = 1, . . . ,m
i
ai y ≤ b i i = 1, . . . ,m

3
Ce problème est équivalent à :

Max z = t
b −a y
s.c. t ≤ ika ik i = 1, . . . ,m
i
ai y ≤ b i i = 1, . . . ,m

25 novembre 2003 – JFH/sp