Mathématiques: Algèbre

Optimisation linéaire
Polygone des contraintes

Définitions

Dans un problème d'optimisation, les inéquations du système représentent les contraintes.

Les droites des équations correspondantes à ces inéquations sont dites les droites frontières .

Le polygone des contraintes est formé par les droites frontières.

La droite frontière d'une inéquation au sens strict (< ou >) est représentée en pointillé.

La droite frontière d'une inéquation au sens large (≤ ou ≥) est représentée en trait plein.

Les solutions des équations du système donnent les coordonnées des sommets du polygone des contraintes.

Les solutions des inéquations du système donnent l'ensemble solution des toutes les inéquations.

Dans un graphique, l'ensemble des solutions des inéquations du système est appelé région solutions

Un polygone des contraintes est fermé ou borné lorsque la région qu'il délimite est bornée de toutes parts par des segments . Il est ouvert ou non-borné lorsque la région qu'il délimite n'est pas bornée sur tous les côtés.



Les points qui sont à l’intérieur du polygone des contraintes sont les points solutions de toutes les inéquations du système. L'intérieur du polygone des contraintes constitue la région solution.


Un sommet fait parti de la région-solution seulement si TOUTES les droites frontières qui le forment sont tracées par des traits pleins.

Exercice

Voici quelques renseignements à propos d'un polygone de contraintes:

• Le polygone des contraintes est borné et de forme triiangulaire.

• Le sommet A(9, 27) fait partie de la région-solution.

• Les sommets B(45, 15) et C(27, 9) ne font pas partie de la région solution.

Donner le système d'inéquations associé au polygone de contraintes.


Réponse:



Le sommet A(9, 27) est l'intersection de deux droites pleines. Il appartient à la région-solution.

Les sommets B(45, 15) et C(27,9) sont des intersections d'uune droite en trait plein et de deux droites en pointillés. Il n'appartient pas à la région-solution.

• Équation de la droite (AB)

y = a x + b

27 = 9 a + b
15 = 45 a + b

D'où: a = - 1/3 et b = 30 .

(AB): y = - (1/3) x + 30

• Équation de la droite (AC)

y = a x + b

27 = 9 a + b
9 = 27 a + b

D'où: a = - 1 et b = 36.

(AC): y = - x + 36

• Équation de la droite (CB)

y = a x + b

15 = 45 a + b
9 = 27 a + b

D'où: a = 1/3 et b = 0 .

(CB): y = (1/3) x

Nous avons les équatons des frontières. Pour trouver les inéquations correspondantes, on s'appuie sur le domaine des contraintes et on fait des tests avec ≥, ≤, < et > sur des points simples:

• (AB) Test (0,0) y ≤ - x/3 + 30 VRAI

• (AC) Test (0,0) y ≥ - x + 36 FAUX

• (BC) Test (21, 3) y > x/3 VRAI

Ainsi, le système d'inéquations s'ecrit:

y ≤ - x/3 + 30
y ≥ - x + 36
y > x/3