LP : Solutions et domaine réalisables

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 :

programmation linéaire domaine de définition domaine réalisable

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

programmation linéaire domaine de définition domaine réalisable

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 :

programmation linéaire domaine de définition domaine réalisable

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é.

programmation linéaire domaine de définition domaine réalisable
Partager
fr_FRFR
%d blogueurs aiment cette page :