Généralités sur la programmation linéaire
35
De la même façon on peut écrire :
)
avec vecteur ligne
et
vecteur ligne
Dans ces conditions, le programme linéaire (1) s'écrit :
(2)
0
, I
I x
x
Comme est irréversible, la première équation donne :
ou
(3)
Cette écriture est absolument générale : elle ne préjuge en rien des valeurs des
composantes de
et : c'est une simple transformation des équations du programme
(1).
Pour la solution de base correspondant à l'ensemble d'indices , les valeurs des variables
du PL sont données par :
et
Sur la formule (3), on constate le fait suivant, très important :
lorsque l'on dispose d'une base, les variables de base s'expriment linéairement en
fonction des variables hors base.
Posons :
et :
est un vecteur colonne
et une matrice
Pour tout
la formule (3) donne :
(4)
=
j
ij
I
j
i
i
x
t
t
x
pour
Remarque essentielle :
est positif, puisque valeur d'une variable de base d'une
solution de base.
Par ailleurs, on a, d'après (2) :
combinons cette formule avec (3).
Il vient