Programmation linéaire : le polygone des contraintes

Extrait de la leçon

3. Le polygone des contraintes et ses sommets

L'ensemble des points $M (x; y)$ dont les coordonnées vérifient toutes les inéquations d'un système est l'intersection de plusieurs demi-plans. On l'appelle le domaine des solutions (ou domaine réalisable). Lorsque ce domaine est limité de tous les côtés, c'est un polygone : le polygone des contraintes. Ses côtés sont portés par les droites frontières. Ses sommets sont des points d'intersection de deux droites frontières qui vérifient toutes les contraintes. Méthode pour trouver les sommets :

Écrire l'équation de chaque droite frontière (on remplace le signe d'inégalité par $=$ ).
Pour chaque paire de droites, résoudre le système de deux équations (par substitution ou par combinaison, comme au chapitre précédent). Deux droites parallèles n'ont pas de point commun.
Garder seulement les points qui vérifient toutes les inéquations du système. Les autres points sont hors du domaine : on les rejette.
Décrire le domaine en citant les sommets dans l'ordre où on les rencontre en faisant le tour du polygone, et en précisant sur quelle droite se trouve chaque côté.

Exemple. Déterminer le polygone des contraintes de Mme Mengue : $x \geq 0$ ; $y \geq 0$ ; $3 x + 2 y \leq 24$ ; $x + y \leq 10$ .

Solution. Droites frontières : $D_{1} : x = 0$ ; $D_{2} : y = 0$ ; $D_{3} : 3 x + 2 y = 24$ ; $D_{4} : x + y = 10$ . Intersections deux à deux :

$D_{1}$ et $D_{2}$ : $O (0; 0)$ . Il vérifie tout ( $0 \leq 24$ et $0 \leq 10$ ) : gardé.
$D_{1}$ et $D_{3}$ : $x = 0$ donne $2 y = 24$ , $y = 12$ , point $(0; 12)$ . Or $0 + 12 = 12 > 10$ : rejeté.
$D_{1}$ et $D_{4}$ : $x = 0$ donne $y = 10$ , point $(0; 10)$ . $3 \times 0 + 2 \times 10 = 20 \leq 24$ : gardé.
$D_{2}$ et $D_{3}$ : $y = 0$ donne $3 x = 24$ , $x = 8$ , point $(8; 0)$ . $8 + 0 = 8 \leq 10$ : gardé.
$D_{2}$ et $D_{4}$ : $y = 0$ donne $x = 10$ , point $(10; 0)$ . $3 \times 10 = 30 > 24$ : rejeté.
$D_{3}$ et $D_{4}$ : de $x + y = 10$ on tire $y = 10 - x$ . Alors $3 x + 2 (10 - x) = 24$ , soit $x + 20 = 24$ , donc $x = 4$ et $y = 6$ . Point $(4; 6)$ , avec $x \geq 0$ et $y \geq 0$ : gardé.

Conclusion : le polygone des contraintes est le quadrilatère $O A B C$ avec $O (0; 0)$ , $A (8; 0)$ , $B (4; 6)$ et $C (0; 10)$ . Le côté $[O A]$ est sur l'axe des abscisses, $[A B]$ sur $D_{3}$ , $[B C]$ sur $D_{4}$ et $[C O]$ sur l'axe des ordonnées.

x + y ≤ 10, x + 3y ≤ 18, 2x + y ≤ 16, x ≥ 0, y ≥ 0 : le domaine réalisable est le polygone OABCD ; ses sommets sont les intersections des droites frontières.

À retenir

Le domaine des solutions est l'ensemble des points qui vérifient toutes les contraintes à la fois.
Un sommet est l'intersection de deux droites frontières qui vérifie toutes les contraintes.
Un point d'intersection qui ne vérifie pas une seule contrainte n'est pas un sommet : on le rejette.
On décrit le polygone par ses sommets, cités dans l'ordre du contour.

Envie de découvrir les autres exercices de ta classe ?

« Programmation linéaire » fait partie des chapitres gratuits : il s'ouvre dès que tu crées ton compte élève. Avec un compte élève, les 3 premiers chapitres de chaque matière sont gratuits, et l'essai de 7 jours ouvre tout le reste, sans paiement.

Programme gabonais, de la 6e à la Terminale, par classe et par série.

Essai gratuit de 7 jours : aucun paiement demandé.

Espace parent inclus pour suivre la progression.

D'autres exemples