Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
J = {1, 2, 5} x = (3, 2, 0, 0, 1)
admissible
J = {2, 3, 4} x = (0, 3, 5, 1, 0)
admissible
J = {2, 3, 5} x =
0,
7
2 ,
9
2 , 0, −
1
2
non admissible
J = {3, 4, 5} x = (0, 0, 8, 7, 3)
admissible
J = {1, 3, 5} x = (7, 0, −6, 0, 3)
non admissible
J = {1, 4, 5} x = (4, 0, 0, 3, 3)
admissible
J = {2, 4, 5} x = (0, 8, 0, −9, −5)
non admissible
J = {1, 3, 4} n’est pas une base.
* Exercice V.2. Soit Λ n le simplexe-unité de R n , c’est-à-dire
Λ n :=
x =(x 1 , . . . , x n ) ∈ R
n
|
n
i=1
x i = 1, x i 0 pour tout i = 1, . . . , n
.
Déterminer tous les points extrémaux de Λ n de la manière suivante :
– décrire Λ n sous la forme
Ax = b
x 0
, avec A ∈ M m,n (R) de rang m et
b ∈ R m ;
– faire ensuite la liste des éléments de base admissibles.
Solution : Λ n peut être décrit sous la forme
Ax = b
x 0
, avec
A = [1.......1] ∈ M 1,n (R) (de rang 1) et b = 1. Il s’ensuit la liste des bases et
des éléments de base :
Bases
Éléments de base associés
Statut
{i} , 1 i n e i = (0, . . . , 0, 1, 0, . . . , 0) , 1 i n
Tous
éléments de la base canonique de R n admissibles.
e 1 , . . . , e n sont les (seuls) points extrémaux de Λ n .
Commentaire : On peut, bien entendu, démontrer directement les résultats suivants :
– Λ n = conv{e 1 , . . . , e n } (il suffit d’écrire x = (x 1 , . . . , x n ) ∈ Λ n comme
n
i=1
x i e i ).
– Tout e i est un point extrémal de Λ n .
176