Généralités sur la programmation linéaire
23
et la maximisation de la fonction suivante :
j
j
m
n
j
x
c
z
1
=
=
Théorème II : Si l'on trouve vecteurs Pi linéairement indépendants
que l'on
désignera, après renumérotation, par 1 2
K
valeurs positives 1 2
k avec
1 1
2 2
k k
alors le point :
=
est un point extrême du domaine des solutions réalisables.
Réciproquement, un point extrême de ce domaine, de coordonnées
est tel que les vecteurs P i associés aux x i strictement positifs sont indépendants.
Démontrons la première partie du théorème : Soit en effet
avec k ≤ m,
P 1 , P 2 …P k indépendants et :
Le point =
est solution réalisable du P.L. Supposons que
ne soit pas un point
extrême du domaine des solutions réalisables, que nous appellerons D. C'est que l'on
peut trouver deux points x
1 et x
2 (solutions réalisables) tels que :
avec
Ce qui impose d'abord que les n+m-k dernières composantes de x
1 et x
2 soient nulles.
2
1
)
(1
=
x
x
x
1
<
<
0