Chapitre 8 • La pro gram ma tion linéaire
324
8.4 aspect matricieL
8.4.1 Forme stan dard
La « forme stan dard » (F.S.) d’un pro gramme linéaire (PL) pour la réso lu tion par
algo rithme du sim plexe est la sui vante : toutes les contraintes expli cites sont des
équa tions dont les seconds membres sont des nombres posi tifs ou nuls ; toutes les
variables sont posi tives ou nulles ; la fonc tion éco no mique z est à maxi mi ser :
x j > 0 pour j 5 1, 2, c , n ; max z 5 a
n
j51
c j x j f
F.S. e a
n
j51
a ij x j 5 b i (où b i > 0) pour i 5 1, 2, c , m ;
Notons A 5 3a ij 4 la matrice m 3 n des coef fi cients des pre miers membres des
contraintes expli cites ; b, le vecteur colonne m 3 1 des seconds membres de ces
contraintes ; c, le vecteur ligne 1 3 n des coef fi cients de la fonc tion éco no mique ;
x, le vecteur colonne n 3 1 des variables du PL. La forme stan dard s’écrit alors
matriciellement :
F.S. U A # x 5 b (où b > 0) ; x > 0 ; max z 5 c # x V.
On remar quera que le résultat du pro duit c # x est une matrice de dimen sions 1 3 1,
donc com por tant un élé ment unique, égal à z.
En dési gnant par A
j
la j
ième
colonne de la matrice A ( j 5 1, 2, c , n), le sys tème
des contraintes expli cites peut s’écrire sous forme d’une com bi nai son linéaire des
vecteurs colonne extraits de A : x 1 # A
1 1 x 2 # A
2 1 c 1 x n # A
n 5 b.
Indi quons main te nant com ment rame ner tout PL à la forme stan dard :
• si l’objec tif du PL est de minimi ser z, on le rem place par maxi mi ser z r, où z r 5 2z ;
• si le signe d’une variable n’est pas connu à l’avance : par exemple pour x j > 2273,
on pose x r
j 5 x j 1 273 et l’on aura : x r
j > 0. Mais si l’on ne connaît pas de borne
infé rieure pour x j (comme ci dessus), on peut poser x j 5 x r
j 2 xs j avec x r
j et xs j posi
tifs ou nuls. En effet tout nombre réel x j peut être repré senté comme la dif fé rence de
deux nombres posi tifs ou nuls ;
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
z � 7
1
1
1
1
2
1
2
3
3
4
4
i
c i
1
1
1
1
1
2
2
5
1/ 4
1/ 4
1/ 6 1/ 6
1/ 6
1/ 6
5/ 6
7/ 6
5/ 12
1/ 12
� i
�
�
�
�
�
�
Cas où, au deuxième tableau, on fait sor tir x 2 au lieu de x 4 : D 1 , et D 2 sont
néga tifs, mais x 4 5 0.
F.S. c
s
324
8.4 aspect matricieL
8.4.1 Forme stan dard
La « forme stan dard » (F.S.) d’un pro gramme linéaire (PL) pour la réso lu tion par
algo rithme du sim plexe est la sui vante : toutes les contraintes expli cites sont des
équa tions dont les seconds membres sont des nombres posi tifs ou nuls ; toutes les
variables sont posi tives ou nulles ; la fonc tion éco no mique z est à maxi mi ser :
x j > 0 pour j 5 1, 2, c , n ; max z 5 a
n
j51
c j x j f
F.S. e a
n
j51
a ij x j 5 b i (où b i > 0) pour i 5 1, 2, c , m ;
Notons A 5 3a ij 4 la matrice m 3 n des coef fi cients des pre miers membres des
contraintes expli cites ; b, le vecteur colonne m 3 1 des seconds membres de ces
contraintes ; c, le vecteur ligne 1 3 n des coef fi cients de la fonc tion éco no mique ;
x, le vecteur colonne n 3 1 des variables du PL. La forme stan dard s’écrit alors
matriciellement :
F.S. U A # x 5 b (où b > 0) ; x > 0 ; max z 5 c # x V.
On remar quera que le résultat du pro duit c # x est une matrice de dimen sions 1 3 1,
donc com por tant un élé ment unique, égal à z.
En dési gnant par A
j
la j
ième
colonne de la matrice A ( j 5 1, 2, c , n), le sys tème
des contraintes expli cites peut s’écrire sous forme d’une com bi nai son linéaire des
vecteurs colonne extraits de A : x 1 # A
1 1 x 2 # A
2 1 c 1 x n # A
n 5 b.
Indi quons main te nant com ment rame ner tout PL à la forme stan dard :
• si l’objec tif du PL est de minimi ser z, on le rem place par maxi mi ser z r, où z r 5 2z ;
• si le signe d’une variable n’est pas connu à l’avance : par exemple pour x j > 2273,
on pose x r
j 5 x j 1 273 et l’on aura : x r
j > 0. Mais si l’on ne connaît pas de borne
infé rieure pour x j (comme ci dessus), on peut poser x j 5 x r
j 2 xs j avec x r
j et xs j posi
tifs ou nuls. En effet tout nombre réel x j peut être repré senté comme la dif fé rence de
deux nombres posi tifs ou nuls ;
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
z � 7
1
1
1
1
2
1
2
3
3
4
4
i
c i
1
1
1
1
1
2
2
5
1/ 4
1/ 4
1/ 6 1/ 6
1/ 6
1/ 6
5/ 6
7/ 6
5/ 12
1/ 12
� i
�
�
�
�
�
�
Cas où, au deuxième tableau, on fait sor tir x 2 au lieu de x 4 : D 1 , et D 2 sont
néga tifs, mais x 4 5 0.
F.S. c
s