44
Recherche opérationnelle
est combinaison linéaire convexe de
solutions réalisables.
On poursuit le processus ainsi entamé, en décomposant tout point obtenu qui n'est pas
un sommet. À chaque étape de la décomposition,
s'exprime sous la forme d'une
combinaison linéaire convexe des . Cela se démontre facilement par récurrence.
À chaque décomposition, on augmente le nombre de composantes nulles des solutions
, on diminue le nombre de leurs composantes non nulles, donc le nombre de vecteurs
intervenant dans la solution par :
b
P
x
P
x
P
x
k
k
=
2
2
1
1
0
>
, 2
1
k
x
x
x
En conséquence, on aboutit obligatoirement à des systèmes de vecteurs indépendants
pour chaque , et donc à des
qui ne soient que des points extrêmes, ou des solutions
de base. C'est ainsi que l'on peut démontrer le théorème IV.