28
Recherche opérationnelle
.
=
1
=
b
x
a j
j
i
n
i
On trouvera une illustration de ces points dans l'exemple des carmions exposé
précédemment, où
. On a en effet déjà remarqué qu'un sommet du
polygone convexe, donc un point extrême du domaine des solutions réalisables, est
donné par l'intersection de deux droites (soit du type
), soit du type
0
=
2
1
bx
ax
Par ailleurs, si on ajoute les variables d'écart x 3 , x 4 , x 5 avec
200
=
350
=
2
450
=
3
5
2
1
4
2
1
3
2
1
x
x
x
x
x
x
x
x
x
0
,
,
,
,
5
4
3
2
1
x
x
x
x
x
On voit que chaque point extrême du domaine des solutions réalisables est caractérisé
par variables positives sur les et les deux autres nulles, ce qui correspond bien aux
solutions de base définies plus haut. Par exemple :
.
Revenons maintenant à l'exposé général pour souligner l'importance des points extrêmes
du domaine D.
1.3.5. Solutions réalisables et solutions de base
Théorème IV: Si le domaine D des solutions réalisables est borné, toute solution
réalisable x peut se mettre sous la forme d'une combinaison linéaire convexe des
solutions de base
La démonstration de ce théorème étant assez longue, nous renvoyons le lecteur intéressé
à une annexe placée à la fin de ce chapitre, où les principes du raisonnement lui seront
exposés. On peut par ailleurs proposer une justification intuitive du résultat en prenant
un polygone convexe de R
2 :