Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
où A ∈ M m,n (R) est la matrice dont les m lignes successives sont a 1 , . . . , a m , b
le vecteur de R m de coordonnées b 1 , . . . , b m , et l’ordre de R m « coordonnée par
coordonnée » (i.e., si x = (x 1 , . . . , x m ) et y = (y 1 , . . . , y m ) sont deux vecteurs de
R m , « x y » signifie « x i y i pour tout i = 1, . . . , m »).
Parmi les classes particulières de polyèdres convexes fermés signalons :
– Les sous-espaces affines de R n , que l’on peut décrire comme intersections
d’hyperplans affines fermés :
{x ∈ R n | |a i , x = b i pour tout i = 1, . . . , m}
(Ax = b sous forme condensée).
(5.3)
Lorsqu’un sous-espace affine est représenté comme en (5.3) avec des a i linéairement indépendants (i.e. A est surjective), ce sous-espace est de dimension
n − m.
– Les polyèdres convexes compacts (c’est-à-dire fermés bornés) de R n , appelés
aussi polytopes de R n quand ils sont d’intérieur non vide. Il y a deux manières
équivalentes de représenter un polyèdre convexe compact C de R n :
C = {x ∈ R
n
| Ax b} et C est borné,
ou bien
C = conv {v 1 , . . . , v k } ,
(5.4)
où v 1 , . . . , v k sont des vecteurs de R n .
– Les cônes convexes fermés polyédriques de R n ; ce sont les intersections d’un nombre fini de demi-espaces vectoriels fermés de R n
(b = 0 dans la description (5.2)) :
{x ∈ R n | |a i , x 0 pour i = 1, . . . , m}
(Ax 0 sous forme condensée).
(5.5)
Il y a deux manières équivalentes de représenter un cône convexe fermé polyédrique K de R n : comme en (5.5) , ou bien
K =
k
i=1
t i v i | t i 0 pour tout i = 1, . . . , k
,
(5.6)
où v 1 , . . . , v k sont des vecteurs de R n .
K, décrit en (5.6), est un cône convexe fermé (le caractère fermé de K fera
l’objet d’un exercice), auquel on se référera par la notation cône {v 1 , . . . , v k }
166
où A ∈ M m,n (R) est la matrice dont les m lignes successives sont a 1 , . . . , a m , b
le vecteur de R m de coordonnées b 1 , . . . , b m , et l’ordre de R m « coordonnée par
coordonnée » (i.e., si x = (x 1 , . . . , x m ) et y = (y 1 , . . . , y m ) sont deux vecteurs de
R m , « x y » signifie « x i y i pour tout i = 1, . . . , m »).
Parmi les classes particulières de polyèdres convexes fermés signalons :
– Les sous-espaces affines de R n , que l’on peut décrire comme intersections
d’hyperplans affines fermés :
{x ∈ R n | |a i , x = b i pour tout i = 1, . . . , m}
(Ax = b sous forme condensée).
(5.3)
Lorsqu’un sous-espace affine est représenté comme en (5.3) avec des a i linéairement indépendants (i.e. A est surjective), ce sous-espace est de dimension
n − m.
– Les polyèdres convexes compacts (c’est-à-dire fermés bornés) de R n , appelés
aussi polytopes de R n quand ils sont d’intérieur non vide. Il y a deux manières
équivalentes de représenter un polyèdre convexe compact C de R n :
C = {x ∈ R
n
| Ax b} et C est borné,
ou bien
C = conv {v 1 , . . . , v k } ,
(5.4)
où v 1 , . . . , v k sont des vecteurs de R n .
– Les cônes convexes fermés polyédriques de R n ; ce sont les intersections d’un nombre fini de demi-espaces vectoriels fermés de R n
(b = 0 dans la description (5.2)) :
{x ∈ R n | |a i , x 0 pour i = 1, . . . , m}
(Ax 0 sous forme condensée).
(5.5)
Il y a deux manières équivalentes de représenter un cône convexe fermé polyédrique K de R n : comme en (5.5) , ou bien
K =
k
i=1
t i v i | t i 0 pour tout i = 1, . . . , k
,
(5.6)
où v 1 , . . . , v k sont des vecteurs de R n .
K, décrit en (5.6), est un cône convexe fermé (le caractère fermé de K fera
l’objet d’un exercice), auquel on se référera par la notation cône {v 1 , . . . , v k }
166