Généralités sur la programmation linéaire
25
Parmi les x i , un certain nombre sont positifs, les autres nuls. Supposons qu'il y en ait
positifs. Après renumérotation, on peut écrire :
b
P
x i
i
r
i
=
1
=
Supposons que les i
soient linéairement dépendants, alors, il existe des
non tous nuls tels que :
0
=
1
=
i
i
r
i
P
soit alors un nombre µ arbitraire; on a :
b
P
P
x
i
i
r
i
i
i
r
i
=
1
=
1
=
et
b
P
P
x
i
i
r
i
i
i
r
i
=
1
=
1
=
Considérons les deux points :
=
et
Les 1 2 r étant toujours positifs, on peut toujours choisir µ de telle façon que
i
i
x
et
i
i
x
restent positifs pour tout i, donc que
1
2 soient des solutions
réalisables. Mais, on a bien évidemment :
2
1
2
1
2
1
=
x
x
x
ce qui contredit l'hypothèse que est point extrême.
En conséquence, les i
sont linéairement indépendants. Le théorème II est
alors complètement démontré.