26
Recherche opérationnelle
Les implications de ce théorème sont les suivantes :
comme nous sommes dans
m en ce qui concerne les i et comme un point extrême est
tel que les i associés aux i strictement positifs sont indépendants, il en résulte que pour
un point extrême, le nombre de i strictement positifs est au plus égal à .
On en déduit que pour obtenir un point extrême, il suffirait a priori d'extraire des
vecteurs i vecteurs indépendants avec
et de résoudre le système d'équations:
b
P
x i
i
r
i
=
1
=
en espérant que les i trouvés soient positifs ou nuls.
Cependant, dans les cas où r < m ce système est en général impossible. On essaiera
toujours de se ramener au cas où r = m grâce au théorème suivant :
Théorème III : À un point extrême du domaine des solutions réalisables peut être
associé un ensemble de m vecteurs P i linéairement indépendants.
Nous remarquerons tout d'abord que, grâce à l'addition des variables d'écart
1
, le rang des
vecteurs P 1 , P 2 , P n+m est égal à m. En effet :
sont linéairement indépendants
Soit alors un point extrême
avec
m
r
. Les vecteurs P 1 , P 2 , P r sont linéairement indépendants, en vertu du
théorème II.
Si nous ne pouvons compléter ces vecteurs indépendants que par
r
r' autres vecteurs
indépendants P r+1 , P r+2 ,… P r’ avec
m
r'
c'est que les
'
r
m
n
autres vecteurs
s'expriment en fonction des r’ vecteurs P 1 , P 2 , P r , donc que le rang du système P 1 , P 2 ,
P n+m est
m
r'
et non m ce qui est contraire à la remarque faite plus haut. D'où le
théorème III.
1 Dans le cas où la forme standard
ne résulte pas de l'addition systématique de variables
d'écart (par exemple lorsque certaines contraintes sont des égalités) on supposera que le rang de
est . Les résultats dégagés seront alors valables pour ce cas.