40
Recherche opérationnelle
ANNEXE
Principes de la démonstration du théorème IV :
Si le domaine
des solutions réalisables est borné, toute solution réalisable peut se
mettre sous la forme d'une combinaison linéaire convexe des solutions de base
.
,
,
2
1
p
x
x
x
Remarquons tout d'abord qu'on peut effectivement parler des solutions de base (ou
points extrêmes)
puisque l'on a montré que ces solutions de base étaient en
nombre fini.
Il s'agit de montrer que toute solution réalisable du P.L peut se mettre sous la forme
avec
et
=1
Donnons les grandes lignes de la démonstration.
Soit donc une solution réalisable . Numérotons
les composantes strictement
positives de , les
autres étant nulles. On a alors, avec les notations
précédentes,
Si les vecteurs
sont linéairement indépendants, est un point extrême de .
Supposons qu'il n'en soit pas ainsi. Nous allons mettre sous la forme :
2
1
)
(1
=
E
E
x
où
et où
sont deux solutions réalisables ayant au plus
composantes non nulles.
Pour ce faire, nous supposerons que le rang du système de vecteurs
est
que
sont linéairement indépendants, après renumérotation
éventuelle. On a :
(1)
pour choisir , opérons de la façon suivante :
(1) peut toujours s'écrire, étant un nombre quelconque :
(2)
Or, comme
sont indépendants et que le rang du système
est , on
peut exprimer
d'une façon unique en fonction de
soit