30
Recherche opérationnelle
La restriction portant sur le caractère borné du domaine des solutions réalisables est
fondamentale pour le théorème IV, comme on pourrait le voir en lisant l'annexe
Pour la suite de l'exposé, nous considèrerons toujours des domaines D bornés : cette
hypothèse n'est pas gênante en recherche opérationnelle, où l'on est censé manier des
grandeurs économiques; elle le serait sans doute davantage pour un exposé
mathématique.
Le domaine D des solutions réalisables d'un P.L. porte, lorsqu'il est borné, le nom
particulier de polyèdre convexe. Nous utiliserons ce terme dorénavant. Les points
extrêmes, en nombre fini, seront les sommets du polyèdre.
1.3.6. Fonction économique et sommets du polyèdre convexe
L'analyse que l'on vient de faire sur les points extrêmes (ou sommets) du domaine des
solutions réalisables et la relation existant entre n'importe quelle solution réalisable et ses
points extrêmes trouve sa pleine justification dans le théorème suivant :
Théorème V : La fonction économique est maximale en au moins un des sommets du
polyèdre convexe; si elle est maximale en plus d'un sommet, elle est maximale en toute
combinaison linéaire de ces sommets.
Soit
les sommets du polyèdre convexe et soit un point quelconque du
polyèdre convexe ( solution réalisable); supposons que ne soit pas un sommet.
D'après le théorème IV, peut s'écrire sous la forme d'une combinaison linéaire convexe
de
i
i
p
i
x
x
1
=
=
avec
Appelons
)
(x
Z
la valeur de la fonction économique pour une solution réalisable .
Soit un sommet
tel que
pour tout
alors
)
(
)
(
1
=
k
i
p
i
x
Z
x
Z
)
(
)
(
k
x
Z
x
Z