Chapitre 8 • La pro gram ma tion linéaire
330
Dans le pro blème de l’ate lier (3 pro duits, 45 h/semaine), on a :
c 5 [4,12, 3, 0, 0, 0, 0] et x
T 5 3x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 4
T
. On peut aussi sépa
rer, dans le vec teur c, les coef fi cients asso ciés aux variables de base qui forment le
sous vecteur ligne 1 3 m noté c B , des autres coef fi cients qui, eux, sont asso ciés aux
variables hors base et forment le sous vecteur colonne 1 3 (n 2 m), notés c N.
Ainsi z 5 c # x 5 (c B , c N ) # a
x B
x N
b 5 c B # x B 1 c N # x N .
Pour expri mer z seule ment en fonc tion des variables hors- base, il suf fit de tirer
l’expres sion de x B à par tir du sys tème : B # x B 1 N # x N 5 b. En mul ti pliant à gauche
par B
21
chaque membre, il vient :
B
2 1 # B # x B 1 B
2 1 # N # x N 5 B
2 1 # b, d où x B 5 B
2 1 # b 2 B
2 1 # N # x N ,
qui est la forme matricielle de l’expres sion des variables de base en fonc tion des
variables hors base.
Subs ti tuons alors à x B cette expres sion dans la rela tion z 5 c B # x B 1 c N # x N .
Il vient : z 5 c B # (B
21 # b 2 B
21 # N # x N ) 1 c N # x N , soit :
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 .
La valeur numé rique z
,
B de la fonc tion éco no mique pour la solu tion de base x B
s’obtient en fai sant x N 5 0 ; elle est donc : z
,
B 5 c B # B
2 1 # b.
Puisque z est désor mais exprimé seule ment en fonc tion des variables hors base, le
coef fi cient de toute variable hors- base x j , dans cette der nière expres sion de z, n’est
autre que le coef fi cient noté plus haut Δ j . Ainsi le vec teur 1 3 (n 2 m) des Δ j , noté
D N , est :
D N 5 c N 2 c B # B
21 # N
soit, com po sante par com po sante : D j 5 c j 2 c B # (B
21 # N)
j
où y
j 5 (B
21 # N)
j
est
la colonne asso ciée à la variable hors base x j , dans la matrice B
21 # N (dans la méthode
des tableaux, c’est la colonne asso ciée à la variable hors base x j ). On a donc :
D j 5 c j 2 a
i
c i # a ij ,
où la som ma tion est faite pour tous les indices i des m variables de base, et a ij est
l’élé ment i du vecteur colonne y
j 5 (B
21 # N)
j
du tableau cou rant.
8.5 démar rage de L ’ aLgo rithme du sim pLexe :
pro bLème de La base ini tiaLe
8.5.1 Cas « favo rable »
Plaçons nous dans le cas où toutes les m contraintes d’un pro gramme linéaire sont ini
tia le ment sous forme d’in équa tions, com por tant p variables prin ci pales, du type :
a
p
j51
a ij # x j < b i où b i est posi tif ou nul (i 5 1, 2, c , m).
’
330
Dans le pro blème de l’ate lier (3 pro duits, 45 h/semaine), on a :
c 5 [4,12, 3, 0, 0, 0, 0] et x
T 5 3x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 4
T
. On peut aussi sépa
rer, dans le vec teur c, les coef fi cients asso ciés aux variables de base qui forment le
sous vecteur ligne 1 3 m noté c B , des autres coef fi cients qui, eux, sont asso ciés aux
variables hors base et forment le sous vecteur colonne 1 3 (n 2 m), notés c N.
Ainsi z 5 c # x 5 (c B , c N ) # a
x B
x N
b 5 c B # x B 1 c N # x N .
Pour expri mer z seule ment en fonc tion des variables hors- base, il suf fit de tirer
l’expres sion de x B à par tir du sys tème : B # x B 1 N # x N 5 b. En mul ti pliant à gauche
par B
21
chaque membre, il vient :
B
2 1 # B # x B 1 B
2 1 # N # x N 5 B
2 1 # b, d où x B 5 B
2 1 # b 2 B
2 1 # N # x N ,
qui est la forme matricielle de l’expres sion des variables de base en fonc tion des
variables hors base.
Subs ti tuons alors à x B cette expres sion dans la rela tion z 5 c B # x B 1 c N # x N .
Il vient : z 5 c B # (B
21 # b 2 B
21 # N # x N ) 1 c N # x N , soit :
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 .
La valeur numé rique z
,
B de la fonc tion éco no mique pour la solu tion de base x B
s’obtient en fai sant x N 5 0 ; elle est donc : z
,
B 5 c B # B
2 1 # b.
Puisque z est désor mais exprimé seule ment en fonc tion des variables hors base, le
coef fi cient de toute variable hors- base x j , dans cette der nière expres sion de z, n’est
autre que le coef fi cient noté plus haut Δ j . Ainsi le vec teur 1 3 (n 2 m) des Δ j , noté
D N , est :
D N 5 c N 2 c B # B
21 # N
soit, com po sante par com po sante : D j 5 c j 2 c B # (B
21 # N)
j
où y
j 5 (B
21 # N)
j
est
la colonne asso ciée à la variable hors base x j , dans la matrice B
21 # N (dans la méthode
des tableaux, c’est la colonne asso ciée à la variable hors base x j ). On a donc :
D j 5 c j 2 a
i
c i # a ij ,
où la som ma tion est faite pour tous les indices i des m variables de base, et a ij est
l’élé ment i du vecteur colonne y
j 5 (B
21 # N)
j
du tableau cou rant.
8.5 démar rage de L ’ aLgo rithme du sim pLexe :
pro bLème de La base ini tiaLe
8.5.1 Cas « favo rable »
Plaçons nous dans le cas où toutes les m contraintes d’un pro gramme linéaire sont ini
tia le ment sous forme d’in équa tions, com por tant p variables prin ci pales, du type :
a
p
j51
a ij # x j < b i où b i est posi tif ou nul (i 5 1, 2, c , m).
’