8.3 Dégé né res cences
321
© Dunod – Toute reproduction non autorisée est un délit.
NB : si lors de la seconde itération on avait fait entrer en base x 3 au lieu de x 1 , on
serait parvenu à l’optimum en 3 itérations : une de moins.
Connais sant désor mais l’algo rithme du sim plexe et son implémentation sous
forme de la méthode des tableaux, nous sommes en mesure de pré sen ter des cas par
ti cu liers (ou dégé né res cences) qui s’illus trent aisé ment gra phi que ment.
8.3 dégé né res cences
8.3.1 Dégé né res cence de pre mière espèce
Pour cer tains pro grammes linéaires, l’opti mum peut être réa lisé en plu sieurs points
de la fron tière du domaine admis sible : tous les points d’une arête ou d’une facette
(ou...) sont alors opti maux.
Ainsi soit le pro gramme :
3max4 z 5 6x 1 1 4x 2
sous les contraintes :
d
23x 1 1 2x 2 < 4
3x 1 1 2x 2 < 16
x 1
< 3
x 1 , x 2 > 0
soit d
23x 1 1 2x 2 1 x 1
5 4
3x 1 1 2x 2 1
1 x 2
5 16
x 1
1 x 3 5 3
x 1 , x 2 , x 1 , x 2 , x 3 > 0
Les tableaux suc ces sifs condui sant à la solu tion se pré sentent de la manière sui vante :
(les suivre en parallèle avec la figure 8.8) :
j
j
0
0 0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
3
3
6
3
3
3
3
z
z 18
i
b
c i
i
c i
1
1
1
1
1
1
2
6 4
4
4
16
7
13
6
↑
s
↑
s
↑
e
↑
e
2
Sommet
O
Sommet
D
(0)
(1)
3
1 2
3
1 2
1
2
3
1
1
1
1
1
1
2
2
2
2
j 0 0
0
0
0
0
0 0 0
0
0
0
2
1
3
3
z 32
i
c i
1
1
1
1
1
1
1
6
2
2
2
2
2
6
6
4
7
↑
s
↑
e
(2)
3
1
2
1
j
0
0
0
0
0
0
0 0
0
5
0
0 2
z 32
i
c i
1
1
1
1
1
2
2
6
4
(3)
1 2
3
2
1
3
1
4
3
4
1
6
1
6
1
6
1
6
Sommet
C
Sommet
B
321
© Dunod – Toute reproduction non autorisée est un délit.
NB : si lors de la seconde itération on avait fait entrer en base x 3 au lieu de x 1 , on
serait parvenu à l’optimum en 3 itérations : une de moins.
Connais sant désor mais l’algo rithme du sim plexe et son implémentation sous
forme de la méthode des tableaux, nous sommes en mesure de pré sen ter des cas par
ti cu liers (ou dégé né res cences) qui s’illus trent aisé ment gra phi que ment.
8.3 dégé né res cences
8.3.1 Dégé né res cence de pre mière espèce
Pour cer tains pro grammes linéaires, l’opti mum peut être réa lisé en plu sieurs points
de la fron tière du domaine admis sible : tous les points d’une arête ou d’une facette
(ou...) sont alors opti maux.
Ainsi soit le pro gramme :
3max4 z 5 6x 1 1 4x 2
sous les contraintes :
d
23x 1 1 2x 2 < 4
3x 1 1 2x 2 < 16
x 1
< 3
x 1 , x 2 > 0
soit d
23x 1 1 2x 2 1 x 1
5 4
3x 1 1 2x 2 1
1 x 2
5 16
x 1
1 x 3 5 3
x 1 , x 2 , x 1 , x 2 , x 3 > 0
Les tableaux suc ces sifs condui sant à la solu tion se pré sentent de la manière sui vante :
(les suivre en parallèle avec la figure 8.8) :
j
j
0
0 0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
3
3
6
3
3
3
3
z
z 18
i
b
c i
i
c i
1
1
1
1
1
1
2
6 4
4
4
16
7
13
6
↑
s
↑
s
↑
e
↑
e
2
Sommet
O
Sommet
D
(0)
(1)
3
1 2
3
1 2
1
2
3
1
1
1
1
1
1
2
2
2
2
j 0 0
0
0
0
0
0 0 0
0
0
0
2
1
3
3
z 32
i
c i
1
1
1
1
1
1
1
6
2
2
2
2
2
6
6
4
7
↑
s
↑
e
(2)
3
1
2
1
j
0
0
0
0
0
0
0 0
0
5
0
0 2
z 32
i
c i
1
1
1
1
1
2
2
6
4
(3)
1 2
3
2
1
3
1
4
3
4
1
6
1
6
1
6
1
6
Sommet
C
Sommet
B