22
Recherche opérationnelle
Nous travaillerons donc dans l'espace
Toute solution réalisable du programme est un vecteur
satisfaisant aux
contraintes (1).
1.3.2. Convexité du domaine des solutions réalisables
Théorème I : L'ensemble des solutions réalisables du P.L (programme linéaire) est
convexe.
En effet soient deux solutions réalisables
, on a :
≥ 0 et
≥ 0
et
prenons alors un point
avec
On a :
1)
2)
+
Donc
est solution réalisable, ce qui assure la convexité du domaine des solutions
réalisables.
Remarque importante : de même, si l'on se place dans
et si l'on se limite aux
variables principales, (ensemble des x tels que
) est également convexe.
Nous allons maintenant essayer de caractériser les points extrêmes du domaine des
solutions réalisables.
1.3.3. Points extrême du domaine convexe des solutions réalisables
Pour démontrer le théorème suivant, nous allons écrire les équations du programme
linéaire dans le langage vectoriel.
Soit les vecteurs P 1 , P 2 , P n+m de
formés par les colonnes de la matrice .
=
=
etc..
Le programme II peut s'écrire :
b
P
x j
j
m
n
j
=
1
=