Chapitre 8 • La pro gram ma tion linéaire
332
Rap pe lons que le pro gramme linéaire (après intro duc tion des variables d’écart)
s’écrit : A # x 5 b , x > 0 , max z 5 c # x. Avec la base, de matrice B, il vient :
B # x B 1 N # x N 5 b et z 5 c B # x B 1 c N # x N .
Sup po sons que l’on connaisse B
21
, il vient l’expres sion cherc hée (cf 8.4.2) :
b
x B 5 B
21 # b 2 B
21 # N # x N
z 5 c B # B
21 # b 1 (c N 2 c B # B
21 # N)x N 5 z
,
B 1 D N # x N
à par tir de laquelle on peut démar rer la réso lu tion. Le tableau asso cié s’écrit (sous
forme matricielle) :
b
I # x B 1 B
2 1 # N # x N 5 B
2 1 # b (le second membre est b 5 B
2 1 # b)
0 # x B 1 D N # x N
5 z 2 z
,
B
( z
,
B 5 c B # B
2 1 # b)
Remar quons que, pour obte nir les expres sions ci- dessus, il suf fit de connaître B
21 # N
et B
21 # b (et donc, pas néces sai re ment, B
21
expli ci te ment).
Voici un exemple de ce cas ; soit le PL ci­ dessous :
e
x 1 1 x 2 2 x 3 1 x 4
5
1
2x 1
1 4x 3 1 2x 4 1 x 5 5
7
x 1 1 6x 2 1 x 3
1 2x 5 5
19
x 1
,
x 2
,
x 3
,
x 4
,
x 5 >
0
x 1 1 3x 2 1 5x 3 1 x 4 1 4x 5 5 z 3MAX 4
Soit la « solu tion » : x 1 5 0, x 2 5 2, x 3 5 1, x 4 5 0 et x 5 5 3. Le lec teur véri fira
aisé ment qu’il s’agit bien d’une solu tion admis sible. Exa mi nons s’il s’agit d’une solu ­
tion de base ; elle com porte bien m 5 3 variables posi tives : x 2 , x 3 et x 5 (une solu tion
qui com por te rait plus de m variables posi tives ne sau rait être de base). La matrice Β
asso ciée est for mée des colonnes A
2
, A
3
et A
5
de la matrice A : B 5 C
1 21 0
0 4 1
6 1 2
S ;
on véri fie que Β est régu lière, puisque dét B 5 I. Le cal cul de B
21
four nit :
B
2 1 5 C
7
2 21
6
2 21
224 27 4
S. Nous invitons le lecteur à vérifier que B
–1
· B = I.
Le sys tème des contraintes expli cites : B # x B 1 N # x N 5 b s’écrit :
C
1 21 0
0 4 1
6 1 2
S # C
x 2
x 3
x 5
S 1 C
1 1
2 2
1 0
S # B
x 1
x 4
R 5 C
1
7
19
S.
Le pro duit à gauche par B
21
four nit : I # x B 1 B
21 # N # x N 5 B
21 # b, soit :