Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Autres notions rattachées à un polyèdre convexe fermé C de R n :
– Si x ∈ C, le cône tangent à C en x et le cône normal à C en x, c’est-à-dire
T (C, x) = {d ∈ R
n
| d = t(c − x) avec c ∈ C et t 0}
et
N (C, x) = {s ∈ R
n
| |s, c − x 0 pour tout c ∈ C}
respectivement, sont à leur tour des cônes convexes fermés polyédriques.
– Un point x de C est appelé point extrémal (ou sommet ) de C s’il n’y a pas
deux points distincts y et z de C tels que x = 1/2(y + z).
Autre manière équivalente de désigner un tel point : il est impossible d’avoir
x = αy + (1 − α) z avec y et z deux points distincts de C et α ∈ ]0, 1[ .
Un polyèdre convexe compact est l’enveloppe convexe de ses points extrémaux.
– Un hyperplan affine de R n , d’équation a, x = b, est appelé hyperplan
d’appui à C en x ∈ C lorsque
a, x = b et a, x b pour tout x ∈ C.
F ⊂ C est une face (exposée) de C s’il existe un hyperplan d’appui H à C tel
que F = C ∩ H. Si un tel hyperplan a pour équation a, x = b, on dira que F est
exposée par a.
Une face F de C est un polyèdre convexe fermé, de dimension comprise entre
0 et n − 1. Si dim F = 0 on retrouve la notion de point extrémal (ou sommet) de
C ; si dim F = 1 on dira que F est une arête de C ; si dim F = n − 1 on parlera
de F comme d’une facette de C.
Un polyèdre convexe fermé a un nombre fini de faces.
V.2. Optimisation à données affines
(Programmation linéaire)
V.2.1. Définitions et notations
– Un problème d’optimisation à données affines (ou programme linéaire) se
présente sous la forme suivante :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax b,
x 0
où c ∈ R n , b ∈ R m et A ∈ M m,n (R).
(5.13)
Minimiser c, x sous les contraintes Ax b et x 0 conduit au même
type de problème (en changeant c en −c). La présentation (5.13) est appelée
168
Autres notions rattachées à un polyèdre convexe fermé C de R n :
– Si x ∈ C, le cône tangent à C en x et le cône normal à C en x, c’est-à-dire
T (C, x) = {d ∈ R
n
| d = t(c − x) avec c ∈ C et t 0}
et
N (C, x) = {s ∈ R
n
| |s, c − x 0 pour tout c ∈ C}
respectivement, sont à leur tour des cônes convexes fermés polyédriques.
– Un point x de C est appelé point extrémal (ou sommet ) de C s’il n’y a pas
deux points distincts y et z de C tels que x = 1/2(y + z).
Autre manière équivalente de désigner un tel point : il est impossible d’avoir
x = αy + (1 − α) z avec y et z deux points distincts de C et α ∈ ]0, 1[ .
Un polyèdre convexe compact est l’enveloppe convexe de ses points extrémaux.
– Un hyperplan affine de R n , d’équation a, x = b, est appelé hyperplan
d’appui à C en x ∈ C lorsque
a, x = b et a, x b pour tout x ∈ C.
F ⊂ C est une face (exposée) de C s’il existe un hyperplan d’appui H à C tel
que F = C ∩ H. Si un tel hyperplan a pour équation a, x = b, on dira que F est
exposée par a.
Une face F de C est un polyèdre convexe fermé, de dimension comprise entre
0 et n − 1. Si dim F = 0 on retrouve la notion de point extrémal (ou sommet) de
C ; si dim F = 1 on dira que F est une arête de C ; si dim F = n − 1 on parlera
de F comme d’une facette de C.
Un polyèdre convexe fermé a un nombre fini de faces.
V.2. Optimisation à données affines
(Programmation linéaire)
V.2.1. Définitions et notations
– Un problème d’optimisation à données affines (ou programme linéaire) se
présente sous la forme suivante :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax b,
x 0
où c ∈ R n , b ∈ R m et A ∈ M m,n (R).
(5.13)
Minimiser c, x sous les contraintes Ax b et x 0 conduit au même
type de problème (en changeant c en −c). La présentation (5.13) est appelée
168