V.3. La dualité en programmation linéaire
Les deux matrices distinctes M 0 :=
1 0
0 1
et M 1 :=
0 1
1 0
sont donc les
extrémités du segment de droite B 2 (ou encore les points extrémaux de B 2 ).
Commentaire : Les matrices [a ij ] ∈ M n (R) vérifiant
a ij 0,
i
a ij = 1,
j
a ij = 1 pour tout (i, j)
sont appelées bistochastiques. L’ensemble B n de toutes les matrices bistochastiques
de taille n est un convexe compact de M n (R) dont les points extrémaux sont les
matrices de permutation (une matrice de permutation est une matrice dont chaque
ligne et chaque colonne ne contiennent qu’un seul terme non nul, lequel vaut 1).
Ainsi, si Π n désigne l’ensemble des n! matrices de permutation,
Π n = extr B n et B n = conv Π n .
Ce résultat, dû à G. Birkhoff (1946), est illustré pour n = 2 dans l’exercice.
Le plus petit sous-espace affine contenant B n (i.e. le sous-espace affine engendré par B n ) est de dimension (n − 1)
2 , une droite affine dans le cas de l’exercice.
* Exercice V.12. On considère le cône convexe K de R n engendré par les vecteurs a 1 , . . . , a m , c’est-à-dire K :=
m
i=1
t i a i | t i 0 pour tout i = 1, . . . , m
.
Montrer que K est nécessairement fermé.
Solution : 1 er cas : a 1 , . . . , a m sont linéairement indépendants.
On pose H := vect {a 1 , . . . , a m } ; H est un sous-espace vectoriel fermé
dont {a 1 , . . . , a m } constitue une base. Soit {x k } une suite d’éléments de K
ayant pour limite x.
Puisque x k =
m
i=1
t k
i a i avec t k
i 0 pour tout i, k, et que x k → x dans H,
nous avons :
t
k
i → t i pour tout i; x =
m
i=1
t i a i .
Donc t i 0 pour tout i, et x ∈ K en fait.
2 e cas : a 1 , . . . , a m sont linéairement dépendants.
189
Les deux matrices distinctes M 0 :=
1 0
0 1
et M 1 :=
0 1
1 0
sont donc les
extrémités du segment de droite B 2 (ou encore les points extrémaux de B 2 ).
Commentaire : Les matrices [a ij ] ∈ M n (R) vérifiant
a ij 0,
i
a ij = 1,
j
a ij = 1 pour tout (i, j)
sont appelées bistochastiques. L’ensemble B n de toutes les matrices bistochastiques
de taille n est un convexe compact de M n (R) dont les points extrémaux sont les
matrices de permutation (une matrice de permutation est une matrice dont chaque
ligne et chaque colonne ne contiennent qu’un seul terme non nul, lequel vaut 1).
Ainsi, si Π n désigne l’ensemble des n! matrices de permutation,
Π n = extr B n et B n = conv Π n .
Ce résultat, dû à G. Birkhoff (1946), est illustré pour n = 2 dans l’exercice.
Le plus petit sous-espace affine contenant B n (i.e. le sous-espace affine engendré par B n ) est de dimension (n − 1)
2 , une droite affine dans le cas de l’exercice.
* Exercice V.12. On considère le cône convexe K de R n engendré par les vecteurs a 1 , . . . , a m , c’est-à-dire K :=
m
i=1
t i a i | t i 0 pour tout i = 1, . . . , m
.
Montrer que K est nécessairement fermé.
Solution : 1 er cas : a 1 , . . . , a m sont linéairement indépendants.
On pose H := vect {a 1 , . . . , a m } ; H est un sous-espace vectoriel fermé
dont {a 1 , . . . , a m } constitue une base. Soit {x k } une suite d’éléments de K
ayant pour limite x.
Puisque x k =
m
i=1
t k
i a i avec t k
i 0 pour tout i, k, et que x k → x dans H,
nous avons :
t
k
i → t i pour tout i; x =
m
i=1
t i a i .
Donc t i 0 pour tout i, et x ∈ K en fait.
2 e cas : a 1 , . . . , a m sont linéairement dépendants.
189