Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Une base est un ensemble J ⊂ {1, . . . , n} d’indices de colonnes de A telle que
la sous-matrice A J constituée des colonnes de A d’indices j ∈ J soit inversible ;
A J est la matrice de base associée à J .
Un élément (ou point) de base correspondant à la base J est un vecteur x =
(x 1 , . . . , x n ) de R n tel que
x j = 0 si j /
∈ J, x j est pris dans x J :=
A
J
−1 b sinon.
Cet x a donc des composantes « hors-base » qui sont nulles, et des composantes
« de base » qui sont celles de x J .
Une base J est dite admissible lorsque l’élément de base x correspondant est
dans l’ensemble-contrainte décrit en (5.16), c’est-à-dire lorsque (x J ) j 0 pour
tout j ∈ J (les autres composantes, celles hors-base, étant nulles).
Si (5.16) est la représentation d’un ensemble-contrainte d’un programme linéaire, une base admissible J est appelée optimale lorsque l’élément de base correspondant est solution du programme linéaire considéré.
À partir d’une base J , on construit l’élément de base correspondant en complétant par des 0 l’élément x J ; si l’un des x j , j ∈ J , est nul, il y a une certaine
ambiguïté à reconnaître la base J ; on dira que l’élément de base est dégénéré si
précisément l’une des composantes de base est nulle.
Le résultat qui suit établit un lien fort entre la géométrie d’un polyèdre convexe
fermé et sa représentation sous la forme standard (5.16) .
Th´ eor` eme. Soit C décrit comme en (5.16) . Alors les points extrémaux (ou sommets) de C sont exactement les éléments de base admissibles.
V.2.2. Résultats fondamentaux d’existence
Th´ eor` eme. Si la forme linéaire x −→ →c, x est majorée sur le polyèdre convexe
fermé C = ∅, alors elle y atteint sa borne supérieure.
Ceci est un résultat d’existence particulier au « monde linéaire » : le seul fait
pour c, ·· d’être majorée sur C entraîne l’existence de x maximisant c, ·· sur C.
Sa démonstration fera l’objet d’un exercice.
Th´ eor` eme. – Si l’ensemble-contrainte d’un programme linéaire est un polyèdre
convexe fermé non vide décrit comme en (5.16), alors il existe des éléments de
base admissibles (i.e. il existe des éléments de base correspondant à des bases
admissibles).
– Si l’ensemble-contrainte d’un programme linéaire est décrit comme en (5.16)
et si ce programme linéaire a des solutions, alors il existe des éléments de base
optimaux (i.e. il existe des éléments de base correspondant à des bases optimales).
170
Une base est un ensemble J ⊂ {1, . . . , n} d’indices de colonnes de A telle que
la sous-matrice A J constituée des colonnes de A d’indices j ∈ J soit inversible ;
A J est la matrice de base associée à J .
Un élément (ou point) de base correspondant à la base J est un vecteur x =
(x 1 , . . . , x n ) de R n tel que
x j = 0 si j /
∈ J, x j est pris dans x J :=
A
J
−1 b sinon.
Cet x a donc des composantes « hors-base » qui sont nulles, et des composantes
« de base » qui sont celles de x J .
Une base J est dite admissible lorsque l’élément de base x correspondant est
dans l’ensemble-contrainte décrit en (5.16), c’est-à-dire lorsque (x J ) j 0 pour
tout j ∈ J (les autres composantes, celles hors-base, étant nulles).
Si (5.16) est la représentation d’un ensemble-contrainte d’un programme linéaire, une base admissible J est appelée optimale lorsque l’élément de base correspondant est solution du programme linéaire considéré.
À partir d’une base J , on construit l’élément de base correspondant en complétant par des 0 l’élément x J ; si l’un des x j , j ∈ J , est nul, il y a une certaine
ambiguïté à reconnaître la base J ; on dira que l’élément de base est dégénéré si
précisément l’une des composantes de base est nulle.
Le résultat qui suit établit un lien fort entre la géométrie d’un polyèdre convexe
fermé et sa représentation sous la forme standard (5.16) .
Th´ eor` eme. Soit C décrit comme en (5.16) . Alors les points extrémaux (ou sommets) de C sont exactement les éléments de base admissibles.
V.2.2. Résultats fondamentaux d’existence
Th´ eor` eme. Si la forme linéaire x −→ →c, x est majorée sur le polyèdre convexe
fermé C = ∅, alors elle y atteint sa borne supérieure.
Ceci est un résultat d’existence particulier au « monde linéaire » : le seul fait
pour c, ·· d’être majorée sur C entraîne l’existence de x maximisant c, ·· sur C.
Sa démonstration fera l’objet d’un exercice.
Th´ eor` eme. – Si l’ensemble-contrainte d’un programme linéaire est un polyèdre
convexe fermé non vide décrit comme en (5.16), alors il existe des éléments de
base admissibles (i.e. il existe des éléments de base correspondant à des bases
admissibles).
– Si l’ensemble-contrainte d’un programme linéaire est décrit comme en (5.16)
et si ce programme linéaire a des solutions, alors il existe des éléments de base
optimaux (i.e. il existe des éléments de base correspondant à des bases optimales).
170