34
Recherche opérationnelle
1.4.1. Utilisation de l'écriture matricielle dans la programmation linéaire
Soit un programme linéaire mis sous forme standard
b
Ax =
cx
Z
A
b
x
c
Supposons que nous disposions d'une solution de base du P.L., c'est-à-dire que nous
ayons trouvé
vecteurs indépendants de la matrice . Rappelons que la solution de
base est alors constituée par variables de base non nulles
2 (celles qui correspondent
aux vecteurs indépendants) les autres variables étant nulles (variables hors base).
Nous appellerons l'ensemble des indices des variables de base, l'ensemble des indices
des variables hors base. On peut écrire
I
I
x
x
x =
(après réordonnancement des variables)
sera le vecteur colonne des variables de base
le vecteur colonne des variables hors base
( vecteur colonne
valeur colonne
)
De même, on peut décomposer en
avec
matrice
et matrice
.
est la matrice extraite de en prenant les
vecteurs colonnes correspondant aux
variables de base. On sait que
est une matrice inversible, puisque les vecteurs
colonnes la composant sont indépendants.
sera appelée matrice de base;
qui correspond aux variables hors base, sera appelée
matrice hors base.
2 Sauf dégénérescences.