Linear optimization
Optimisation linéaire
Avec Solveur d'Excel MS Office
© The scientific sentence. 2010
|
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
|
|