Chapitre 8 • La pro gram ma tion linéaire
322
N.B. Lors de chaque itération (pas), on a
cerclé le pivot.
Sur le troi sième tableau, on constate que
D 3 5 0, alors que la colonne 3 est hors base.
Bien qu’on ait atteint la valeur opti male
de la fonc tion éco no mique, si l’on consi dère
que D 3 est le plus grand des Δ j non négatifs
cor res pon dant aux variables hors base (troi
sième tableau), on peut faire entrer la variable
x 3 dans la base, d’où sort la variable x 1 , et
l’on a alors D 1 5 0 (qua trième tableau).
Ce fait tra duit que la fonc tion éco no
mique z 5 6x 1 1 4x 2 est paral lèle à l’hyper
plan (ici, la droite) limi tant le demi plan
déter miné par la contrainte 3x 1 1 2x 2 < 16 ;
les som mets Β et C sont tous deux opti maux.
L’enve loppe convexe de ces som mets, c’estàdire le seg ment BC, est telle que cha cun de ses points donne à z la valeur opti male
32. C’est le cas dit de « dégé né res cence de pre mière espèce ».
8.3.2 Dégé né res cence de deuxième espèce
Pour cer tains pro grammes linéaires, une (ou plu sieurs) variable(s) de la base opti
male peut être nulle. Voici un exemple détaillé : ajou tons au pro gramme pré cé dent
la contrainte :
x 1 1 4x 2 < 22 soit x 1 1 4x 2 1 x 4 5 22
et pre nons comme fonc tion éco no mique :
3max4 z 5 x 1 1 x 2 (au lieu de 3max4 z 5 6x 1 1 4x 2 )
Il en résulte la figure 8.9. Trai tons néan moins le pro gramme par la méthode des
tableaux. On obtient les résul tats sui vants, ayant choisi arbi trai re ment, au deuxième
tableau, de faire sor tir la variable x 4 de la base (on avait le choix entre x 2 et x 4 ).
0
0
0
0
0
0
0 0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
Sommet
O
Sommet
A
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
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
0
0
3
3
z 0
z 2
3
2
1
1/ 2
5/ 2
3/ 2
1/ 2
i
i
c i
ci
1
1
1
1
12
14
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2 *
0 *
2 *
2
2
2
2
22
16
6
4
4
7
↑
s
↑
s
↑
s
↑
e
↑
e
1
1
1
2
2
2
2
3
3
3
3
3
3
4
i
ci
1
1
1
1
1
1
2
2
2
5
1
1
2
3
3
4
4
4
4
i
j
j
j
j
c i
1
1
1
1
14
1
5
5
1
1
1
1 1
1
1
1
2
2
7/ 2
2
1
2
2
3
3
4
7
2
7
1
7
2
7
1
7
6
7
i
i
i/ ie
i
i
i/ ie
3
14
2
5
2
5
1
5
7
5
1
5
6
5
1
10
3
10
négatif
Figure 8.8
322
N.B. Lors de chaque itération (pas), on a
cerclé le pivot.
Sur le troi sième tableau, on constate que
D 3 5 0, alors que la colonne 3 est hors base.
Bien qu’on ait atteint la valeur opti male
de la fonc tion éco no mique, si l’on consi dère
que D 3 est le plus grand des Δ j non négatifs
cor res pon dant aux variables hors base (troi
sième tableau), on peut faire entrer la variable
x 3 dans la base, d’où sort la variable x 1 , et
l’on a alors D 1 5 0 (qua trième tableau).
Ce fait tra duit que la fonc tion éco no
mique z 5 6x 1 1 4x 2 est paral lèle à l’hyper
plan (ici, la droite) limi tant le demi plan
déter miné par la contrainte 3x 1 1 2x 2 < 16 ;
les som mets Β et C sont tous deux opti maux.
L’enve loppe convexe de ces som mets, c’estàdire le seg ment BC, est telle que cha cun de ses points donne à z la valeur opti male
32. C’est le cas dit de « dégé né res cence de pre mière espèce ».
8.3.2 Dégé né res cence de deuxième espèce
Pour cer tains pro grammes linéaires, une (ou plu sieurs) variable(s) de la base opti
male peut être nulle. Voici un exemple détaillé : ajou tons au pro gramme pré cé dent
la contrainte :
x 1 1 4x 2 < 22 soit x 1 1 4x 2 1 x 4 5 22
et pre nons comme fonc tion éco no mique :
3max4 z 5 x 1 1 x 2 (au lieu de 3max4 z 5 6x 1 1 4x 2 )
Il en résulte la figure 8.9. Trai tons néan moins le pro gramme par la méthode des
tableaux. On obtient les résul tats sui vants, ayant choisi arbi trai re ment, au deuxième
tableau, de faire sor tir la variable x 4 de la base (on avait le choix entre x 2 et x 4 ).
0
0
0
0
0
0
0 0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
Sommet
O
Sommet
A
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
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
0
0
3
3
z 0
z 2
3
2
1
1/ 2
5/ 2
3/ 2
1/ 2
i
i
c i
ci
1
1
1
1
12
14
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2 *
0 *
2 *
2
2
2
2
22
16
6
4
4
7
↑
s
↑
s
↑
s
↑
e
↑
e
1
1
1
2
2
2
2
3
3
3
3
3
3
4
i
ci
1
1
1
1
1
1
2
2
2
5
1
1
2
3
3
4
4
4
4
i
j
j
j
j
c i
1
1
1
1
14
1
5
5
1
1
1
1 1
1
1
1
2
2
7/ 2
2
1
2
2
3
3
4
7
2
7
1
7
2
7
1
7
6
7
i
i
i/ ie
i
i
i/ ie
3
14
2
5
2
5
1
5
7
5
1
5
6
5
1
10
3
10
négatif
Figure 8.8