Généralités sur la programmation linéaire
43
Les coordonnées de
sont :
0
0
1
1
)
(1
1
)
(1
1
=
2
1
1
1
1
1
1
1
1
2
q
r
r
r
r
r
r
x
x
x
x
x
x
x
E


Pour
, on retrouve bien
Faisons croître de 0 à 1. On voit qu'il existe une valeur
qui annule au moins
une coordonnée de
en laissant les autres positives, sinon les
premières
coordonnées deviendraient infinies lorsque tend vers 1, ce qui est incompatible avec
l'hypothèse faite, à savoir que le domaine des solutions réalisables est borné.
Pour cette valeur
solution réalisable possède au plus
composantes non
nulles. On a bien mis sous la forme :
2
1
1
1
)
(1
=
E
E
x
avec
e
t appartenant à et ayant au plus
composantes non
nulles.
À présent, si
n'est pas un sommet, on le décompose de la même façon en
4
2
3
2
1
)
(1
=
E
E
E
appartenant à et ayant au plus
composantes non nulles. On a alors :
et comme
1
=
1
)
(1
1
2
1
2
1
2
1
4
2
1
3
2
1
)
(1
)
(1
=
E
E
E
x