38
Recherche opérationnelle
Cela devient parfaitement évident si l'on prend soin de prendre pour contraintes du
programme linéaire les équations (7) sous la forme :
(7)
=
I
i
t
x
t
x
i
j
ij
I
j
i
Ces équations, encore une fois, sont absolument équivalentes aux équations initiales du
programme (1). Alors, la matrice de base initiale (les
de base, avec
) est la
matrice unité
1 0 . . . 0
0 1 . . . 0
0 0 1 . . 0
0 0
1
0
0 . . . 1 0
0 0 0 0 0 1
Si l'on fait sortir la variable
de la base et si on fait entrer dans le base avec
,
on obtient la nouvelle matrice de base :
1 0 .
. 0
0 1 . .
. 0
0 0 1 .
. 0
0 0
0
0 . . .
1 0
0 0 0
0 1
c'est-à-dire la matrice unité où l'on remplace la colonne par la colonne :
Comme
, le déterminant de cette nouvelle matrice n'est pas nul. On a
donc bien une nouvelle matrice de base inversible.
Ce qu'il faut remarquer à présent, c'est que l'intérêt de cette opération provient du fait
que l'on a choisi pour variable
entrant dans la base une variable hors base telle que