V
POLYÈDRES CONVEXES FERMÉS.
OPTIMISATION À DONNÉES AFFINES
(PROGRAMMATION LINÉAIRE)
Rappels
·, ·· dénote le produit scalaire usuel dans R n ; les formes linéaires sur R n sont
du type x ∈ R n −→ →c, x, où c ∈ R n .
Les hyperplans affines de R n peuvent être décrits de la manière suivante :
{x ∈ R
n
| |a i , x = b i } ,
(5.1)
où a i est un vecteur non nul de R n et b i un réel. Les demi-espaces affines fermés de
R n peuvent être décrits d’une manière similaire à (5.1), une inégalité (a i , x b i )
se substituant à l’égalité a i , x = b i .
Naturellement, un hyperplan affine (d’équation a i , x = b i ) peut être vu
comme l’intersection des deux demi-espaces fermés (d’équation a i , x b i et
−a i , x −b i respectivement).
V.1. Polyèdres convexes fermés
D´ efinition. Un polyèdre convexe fermé de R n est l’intersection d’un nombre fini
de demi-espaces affines fermés de R n .
Le polyèdre convexe fermé C, intersection des m demi-espaces affines fermés
d’équation a i , x b i , est décrit d’une manière condensée sous la forme
Ax b,
(5.2)