Solu tions des exer cices du cha pitre 8
541
© Dunod – Toute reproduction non autorisée est un délit.
où α est la matrice des colonnes hors- base, pour la base cou rante : la base ini tiale étant asso -
ciée au som met Ο (admis sible pour ce PL), on a : B 5 I, sinon pour connaître [α], il faut
résoudre le sys tème ci- dessus (si l’on connaît B
21
, la solu tion en est : α 5 B
2 1 # N).
Soit la fonc tion éco no mique Z 5 c # x 5 c B # x B 1 c N # x N ; rap pe lons que son expres sion en
fonc tion des variables hors base s’obtient en subs ti tuant aux variables de base (soit x B ) leur
expres sion en fonc tion des variables hors base (soit x N ) : A # x 5 b s’écrit B # x B 1 N # x B 5 b
d’où : x B 5 B
2 1 # b 1 B
2 1 # N # x N . Ainsi :
Z 5 c B # (B
2 1 # N # x N ) 1 c N # x N 5 c B # B
2 1 # N 1 (c N 2 c B # B
2 1 # N)x N
le vec teur des Δ j (pour x j hors base) n’est autre que :
D N 5 c N 2 c B # B
2 1 # N 5 c N 2 c B # α et D j 5 c j 2 a
i
c i # a ij ,
où la som ma tion est éten due à toutes les variables x i de la base.
Reve nons à notre exemple ; les variables d’écart consti tuent la base ini tiale ; puisque le
coef fi cient de cha cune dans Ζ est nul, il vient : c B 5 3 0, 0, 0, 0
(4) (5) (6) (7)
4 et, ainsi, D N 5 c N
ici, c’est- à-dire que D j 5 c j ( j 5 1, 2, 3, 4). Numé ri que ment : D N 5 3 5, 4, 3, 1
(1) (2) (3) (4)
4
d’où l’on déduit, d’après le pre mier cri tère de Dantzig, que la colonne A
1
(cf la variable x 1 )
doit entrer dans la base.
Cal cu lons alors les rap ports
b i
a i1
; on a :
b 5
a 51
5
12
1
5 12 ;
b 6
a 61
5
5
3
;
b 7
a 71
5
7
2
;
le plus petit posi tif d’entre eux est le second, ce qui, d’après le deuxième cri tère de Dantzig,
indique que la colonne A
6
(cf la variable x 6 ) doit sor tir de la base.
Cal cu lons les nou velles coor don nées du vec teur b , on a :
br 1 5 u 0 5
5
3
; br 5 5 b 5 2 u 0 # a 51 5 12 2
5
3
# 1 5
31
3
.
br 7 5 b 7 2 u 0 # a 71 5 7 2
5
3
# 2 5
11
3
.
On véri fie bien que :
D
1 1 1 1 1 0 0
3 2 3 1 0 1 0
2 1 1 4 0 0 1
(1) (2) (3) (4) (5) (6) (7)
T # F
5/3
0
0
0
31/3
0
11/3
V 5 D
12
5
7
T.
541
© Dunod – Toute reproduction non autorisée est un délit.
où α est la matrice des colonnes hors- base, pour la base cou rante : la base ini tiale étant asso -
ciée au som met Ο (admis sible pour ce PL), on a : B 5 I, sinon pour connaître [α], il faut
résoudre le sys tème ci- dessus (si l’on connaît B
21
, la solu tion en est : α 5 B
2 1 # N).
Soit la fonc tion éco no mique Z 5 c # x 5 c B # x B 1 c N # x N ; rap pe lons que son expres sion en
fonc tion des variables hors base s’obtient en subs ti tuant aux variables de base (soit x B ) leur
expres sion en fonc tion des variables hors base (soit x N ) : A # x 5 b s’écrit B # x B 1 N # x B 5 b
d’où : x B 5 B
2 1 # b 1 B
2 1 # N # x N . Ainsi :
Z 5 c B # (B
2 1 # N # x N ) 1 c N # x N 5 c B # B
2 1 # N 1 (c N 2 c B # B
2 1 # N)x N
le vec teur des Δ j (pour x j hors base) n’est autre que :
D N 5 c N 2 c B # B
2 1 # N 5 c N 2 c B # α et D j 5 c j 2 a
i
c i # a ij ,
où la som ma tion est éten due à toutes les variables x i de la base.
Reve nons à notre exemple ; les variables d’écart consti tuent la base ini tiale ; puisque le
coef fi cient de cha cune dans Ζ est nul, il vient : c B 5 3 0, 0, 0, 0
(4) (5) (6) (7)
4 et, ainsi, D N 5 c N
ici, c’est- à-dire que D j 5 c j ( j 5 1, 2, 3, 4). Numé ri que ment : D N 5 3 5, 4, 3, 1
(1) (2) (3) (4)
4
d’où l’on déduit, d’après le pre mier cri tère de Dantzig, que la colonne A
1
(cf la variable x 1 )
doit entrer dans la base.
Cal cu lons alors les rap ports
b i
a i1
; on a :
b 5
a 51
5
12
1
5 12 ;
b 6
a 61
5
5
3
;
b 7
a 71
5
7
2
;
le plus petit posi tif d’entre eux est le second, ce qui, d’après le deuxième cri tère de Dantzig,
indique que la colonne A
6
(cf la variable x 6 ) doit sor tir de la base.
Cal cu lons les nou velles coor don nées du vec teur b , on a :
br 1 5 u 0 5
5
3
; br 5 5 b 5 2 u 0 # a 51 5 12 2
5
3
# 1 5
31
3
.
br 7 5 b 7 2 u 0 # a 71 5 7 2
5
3
# 2 5
11
3
.
On véri fie bien que :
D
1 1 1 1 1 0 0
3 2 3 1 0 1 0
2 1 1 4 0 0 1
(1) (2) (3) (4) (5) (6) (7)
T # F
5/3
0
0
0
31/3
0
11/3
V 5 D
12
5
7
T.