Domaine réalisable
Une solution d’un problème linéaire est dit Réalisable si toutes les contraintes sont satisfaites. Le domaine réalisable contient toutes les solutions réalisables du problème. La solution optimal est la/les « meilleure(s) » des solutions réalisables.
Pour savoir si une solution est réalisable, il suffit de tester si toutes les contraintes sont satisfaites, cela peut se faire à la main ou sous forme matricielle.
A la main :
Vérifions si la solution (3, 1) est réalisable.
La première équation donne 3*1/3 + 1 = 2, la contrainte est satisfaite.
La deuxième inéquation donne -2*3 + 5*1 = -1 ≤ 7, la contrainte est satisfaite.
La troisième inéquation donne 3 + 1 = 4 ≤ 4, la contrainte est satisfaite, on dit qu’elle est saturée.
Les deux contraintes de type sont satisfaites.
La solution est réalisable. La valeur de la fonction objectif est z = 3 – 1 = 2.
D’un point de vue matriciel : il faut multiplier la matrice du programme linéaire par le vecteur de solution et comparer le résultat aux membres à droite du programme linéaire
Domaine réalisable (ou domaine de définition)
Chaque contrainte peut être assimilé à une équation partageant le plan en deux. Par exemple l’équation ai*x1 + bi*x2 = ci partage le plan en deux demi-plans P1 et P2 d’équation :
La contrainte inférieur ou égale déterminera un demi-plan, la contrainte supérieur ou égale déterminera l’autre demi-plan. Pour savoir dans quel demi-plan se situe les solutions réalisables pour la contraintes, il suffit de tester un exemple simple et de déterminer si elle est réalisable ou non.
Par exemple pour la contrainte : x1 + x2 ≤ 4, la solution (0,0) est réalisable, donc l’origine est dans le demi-plan réalisable.
L’intersection de tous les demi-plans réalisables constitue le domaine réalisable. Ce dernier peut être borné ou non borné.
