8.4 Aspect matriciel
325
© Dunod – Toute reproduction non autorisée est un délit.
• si une contrainte i com porte un second membre néga tif : b i , 0, on mul ti plie par
21 chaque membre de cette contrainte ;
• si cer taines contraintes sont ini tia le ment en inéga lité, on peut les rame ner à des
éga li tés par intro duc tion de nou velles variables, nom mées « variables d’écart » .
Ainsi 3x 1 1 4x 2 < 5 équi vaut à : 3x 1 1 4x 2 1 x e 5 5 et x e > 0.
De même, 2x 1 1 7x 2 > 11 équi vaut à : 2x 1 1 7x 2 2 x r
e 5 11 et x r
e > 0.
Donc, dans le cas de contraintes a a ij x j < b i , on ajoute une variable d’écart, tan
dis que dans le cas inverse : a a ij x j > b i , on retranche une variable d’écart (après
avoir rendu b i positif, si nécessaire). Obser vons que ces variables d’écart, tout comme
les variables « prin ci pales » (c’est àdire les variables d’ori gine, intro duites pour for
mu ler le pro blème) sont toutes posi tives ou nulles. Ainsi, lors de la réso lu tion, on ne
fera pas de dis tinction entre les variables d’écart et les variables prin ci pales.
Nous ferons les deux hypo thèses sui vantes sur la forme stan dard FS :
1) le nombre de lignes de A (contraintes expli cites) est infé rieur au nombre de
colonnes de A (qui est égal au nombre de variables) : m , n.
Remar quons que, si les contraintes expli cites du PL étaient ini tia le ment des inéga li
tés, on intro duit une variable d’écart dans cha cune, soit en tout m variables d’écart.
Alors le nombre total de variables devient nécessairement supé rieur à m. Cette hypo
thèse est donc, en pra tique, peu limi ta tive.
2) Nous sup po se rons que l’on peut extraire de A, m colonnes dif fé rentes qui,
regrou pées dans une matrice car rée B, sont telles que le déter mi nant de B n’est pas
nul (ce qui équi vaut à dire que les m vecteurs colonnes ainsi extraits, sont indé pen
dants ; on dit alors que le « rang » de la matrice A est égal à m).
Remar quons à nou veau que si les contraintes expli cites du PL étaient ini tia le ment
des inéga li tés, les m colonnes de A asso ciées aux variables d’écart forment la matrice
m 3 m :
•
61 0
0
c 0
0 61 0
c 0
0 0 61 c 0
(
(
c f
(
0 0
0
c 61
µ
Cette matrice dia go nale a pour déter mi nant le pro duit des élé ments dia go naux, qui
vaut donc 11 ou 21 : il est donc non nul.
À nou veau, cette hypo thèse est, en pra tique, peu res tric tive.
Dans ces condi tions, le sys tème linéaire A # x 5 b de m équa tions à n inconnues
admet au moins une solu tion (et, en géné ral, une infi nité). C’est un sys tème « sous
déter miné » com por tant plus d’inconnues que d’équa tions. Notons que si l’on
connaît deux solu tions dif fé rentes xr et xs de ce sys tème, alors tout x de la forme
x 5 l # xr 1 (1 2 l) # xs, où 0 < l < 1, est aussi une solu tion du sys tème ; x est
nommé : “com bi nai son linéaire convexe” de xr et de xs.
325
© Dunod – Toute reproduction non autorisée est un délit.
• si une contrainte i com porte un second membre néga tif : b i , 0, on mul ti plie par
21 chaque membre de cette contrainte ;
• si cer taines contraintes sont ini tia le ment en inéga lité, on peut les rame ner à des
éga li tés par intro duc tion de nou velles variables, nom mées « variables d’écart » .
Ainsi 3x 1 1 4x 2 < 5 équi vaut à : 3x 1 1 4x 2 1 x e 5 5 et x e > 0.
De même, 2x 1 1 7x 2 > 11 équi vaut à : 2x 1 1 7x 2 2 x r
e 5 11 et x r
e > 0.
Donc, dans le cas de contraintes a a ij x j < b i , on ajoute une variable d’écart, tan
dis que dans le cas inverse : a a ij x j > b i , on retranche une variable d’écart (après
avoir rendu b i positif, si nécessaire). Obser vons que ces variables d’écart, tout comme
les variables « prin ci pales » (c’est àdire les variables d’ori gine, intro duites pour for
mu ler le pro blème) sont toutes posi tives ou nulles. Ainsi, lors de la réso lu tion, on ne
fera pas de dis tinction entre les variables d’écart et les variables prin ci pales.
Nous ferons les deux hypo thèses sui vantes sur la forme stan dard FS :
1) le nombre de lignes de A (contraintes expli cites) est infé rieur au nombre de
colonnes de A (qui est égal au nombre de variables) : m , n.
Remar quons que, si les contraintes expli cites du PL étaient ini tia le ment des inéga li
tés, on intro duit une variable d’écart dans cha cune, soit en tout m variables d’écart.
Alors le nombre total de variables devient nécessairement supé rieur à m. Cette hypo
thèse est donc, en pra tique, peu limi ta tive.
2) Nous sup po se rons que l’on peut extraire de A, m colonnes dif fé rentes qui,
regrou pées dans une matrice car rée B, sont telles que le déter mi nant de B n’est pas
nul (ce qui équi vaut à dire que les m vecteurs colonnes ainsi extraits, sont indé pen
dants ; on dit alors que le « rang » de la matrice A est égal à m).
Remar quons à nou veau que si les contraintes expli cites du PL étaient ini tia le ment
des inéga li tés, les m colonnes de A asso ciées aux variables d’écart forment la matrice
m 3 m :
•
61 0
0
c 0
0 61 0
c 0
0 0 61 c 0
(
(
c f
(
0 0
0
c 61
µ
Cette matrice dia go nale a pour déter mi nant le pro duit des élé ments dia go naux, qui
vaut donc 11 ou 21 : il est donc non nul.
À nou veau, cette hypo thèse est, en pra tique, peu res tric tive.
Dans ces condi tions, le sys tème linéaire A # x 5 b de m équa tions à n inconnues
admet au moins une solu tion (et, en géné ral, une infi nité). C’est un sys tème « sous
déter miné » com por tant plus d’inconnues que d’équa tions. Notons que si l’on
connaît deux solu tions dif fé rentes xr et xs de ce sys tème, alors tout x de la forme
x 5 l # xr 1 (1 2 l) # xs, où 0 < l < 1, est aussi une solu tion du sys tème ; x est
nommé : “com bi nai son linéaire convexe” de xr et de xs.