Chapitre 8 • La pro gram ma tion linéaire
316
i
j
e � 2
z � 0
s � 5
c i
c j
� j
1 000
1 125
1 500
6 750
500 500 ( * )
1
1
1
1
1
1
1
1
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
0
0
2
2
pivot
12
12
6
6
6
3
3
3
3
5
5
7
7
4
4
4
4
↑
�
�
�
� i
�ie
Dans la suite nous n’écri vons que rare ment la ligne c j (car il s’agit de don nées ini ­
tiales).
Cal cu lons main te nant les quo tients
b i
a ie
c’est­ à­dire
b i
a i2
puisque e est désor mais
connu : e 5 2 ; les valeurs de i sont : 4, 5, 6 et 7 et l’on a donc :
b 4
a 42 5
1 000
0
(1)
5 ` ;
b 5
a 52
5
500
1
;
b 6
a 62 5
1 500
0
5 ` ;
b 7
a 72 5
6 750
6
5 1 125 ;
on peut écrire ces résul tats sur une nou velle colonne
b i
a ie
(e, indice de la colonne
entrante), immé dia te ment à droite de b, le vec teur cou rant des seconds membres.
Pre nons le rap port le plus petit posi tif : c’est 500, qui cor res pond à l’indice i 5 5 ; ce
sera donc la 5
e
colonne (soit x 5 ) qui sor tira de la base ; l’indice de la variable sor tant
de la base est donc s 5 5.
Il faut main te nant appli quer les for mules de chan ge ment de coor don née (avec e 5 2
et s 5 5) :
z r 5 z 1
b 5
a 52
# D 2
br k 5 b k 2 a k2 #
b 5
a 52
ar kl 5 a kl 2 a k2 #
a 5l
a 52
(k 2 5)
a 5l 5
a 5l
a 52 et br 5 5
b 5
a 52 .
L’élé ment α se (ici a 52 ) qui joue un rôle fon da men tal a été appelé élé ment dis tin gué
ou pivot de la trans for ma tion. Rappelons que le pivot est nécessairement strictement
positif : ceci résulte du second critère de Dantzig.
(1) On ne s’inquiè tera pas du fait que l’on pose ici :
1 000
0
5 `, c’est une simple conven tion.