Chapitre 8 • La pro gram ma tion linéaire
326
Base
Par défi ni tion, une « base » d’un PL est un ensemble de m vecteurs­ colonne indé pen ­
dants, extraits de A. Ainsi si l’on découpe A en colonne :
A  A 1
A
2
A
3
A
n
. . .
et que l’on ait extrait de A les m colonnes d’indices j 1 , j 2 , c , j m , à la base B est asso ­
ciée une matrice car rée m 3 m, de déter mi nant non nul :
A
j 1
A
j 2
A
jm
B 
. . .
x B 5 D
x j 1
x j 2
(
x j m
T
Les « variables de base » sont les variables x j1 , x j2 , c , x jm asso ciées aux colonnes
consti tuant la base ; on note x B le vec teur colonne des m variables de base. Les
n 2 m autres variables sont dites « variables hors base » et l’on note x N leur
vecteur­ colonne.
Réécri ture du pro gramme linéaire asso ciée à une base B
Par per mu ta tion des colonnes de A, on place en tête (calées à gauche) les colonnes
de base qui forment la sous­matrice B, puis on place, immé dia te ment à droite de
celles­ ci, les colonnes hors base (qui forment la sous­ matrice N ). On per mute dans
le même ordre les variables ; ainsi A 5 (B, N)
et x 5 a
x B
x N
b :
A 
B
N
A j 1 A
j 2
A
jm
. . .
. . .


Alors le sys tème des contraintes expli cites A # x 5 b, cal culé par blocs, devient :
(B, N) # a
x B
x N
b 5 b, soit B # x B 1 N # x N 5 b.
Don nons un exemple de cette réécri ture (avec m 5 2 contraintes) :
e
2x 1 1 3x 2 2 x 3 1 x 4 1 3x 5 5 12
7x 1 2 x 2 1 2x 3 1 5x 4 1 x 5 5 6