régionnement du plan

Tracez une droite sur une feuille : les points se retrouvent d’un côté, de l’autre, ou sur la droite. Avec plusieurs droites ou courbes, le plan ressemble à une carte découpée en zones. Chaque point appartient à une zone selon une règle précise.

Pour des inéquations, chaque règle sélectionne généralement un demi-plan. La zone qui respecte toutes les règles est leur partie commune : c’est elle que l’on cherche ou dans laquelle on optimise une quantité.

Un régionnement du plan est une famille de régions qui couvre le plan et dont les intérieurs ne se chevauchent pas. Chaque région est caractérisée par une même propriété géométrique ou analytique. Une droite, une courbe ou plusieurs frontières peuvent produire ce découpage.

Dans un système d’inéquations linéaires à deux inconnues, les inconnues x et y repèrent un point du plan. Chaque inéquation détermine un demi-plan, frontière comprise lorsque le signe est ≤ ou ≥, et frontière exclue lorsque le signe est < ou >. L’ensemble des solutions est l’intersection de ces demi-plans. Lorsqu’il est non vide, cet ensemble est convexe : le segment joignant deux de ses points reste entièrement dans l’ensemble. Il peut être borné, non borné, réduit à un segment ou à un point.

Pour parler d’une partition au sens strict, il faut préciser à quelle région appartiennent les frontières : deux demi-plans fermés ont leur droite frontière en commun, tandis que deux demi-plans ouverts ne la contiennent pas. Cette convention ne change pas le tracé des zones, mais elle change l’appartenance des points situés sur les courbes.

Le régionnement repose sur quatre éléments. Le plan fournit tous les points possibles. Les frontières, ici les droites x + y = 6 et 2x + y = 8 ainsi que les axes, séparent des côtés. Les règles de côté indiquent quels demi-plans garder. Enfin, les régions regroupent les points qui donnent les mêmes réponses à ces règles.

Une frontière dépend de l’égalité associée à une inéquation ; le signe de l’inéquation détermine ensuite le côté retenu. La zone admissible dépend de toutes les règles à la fois, car elle est leur intersection. La couleur, l’épaisseur des traits et l’échelle du dessin aident à lire la figure, mais ne définissent pas la région. Ces données suffisent à construire l’ensemble des solutions et à en calculer les sommets.

On cherche des points repérés par les coordonnées x et y, puis on veut maximiser la quantité z égale à 3x + 2y. Les quatre contraintes sont réunies dans le système suivant.

1. Les deux premières contraintes gardent le quadrant où les coordonnées sont positives ou nulles.
2. La droite x + y = 6 coupe les axes en (6,0) et (0,6) ; on garde le côté contenant (0,0).
3. La droite 2x + y = 8 coupe les axes en (4,0) et (0,8) ; on garde encore le côté contenant (0,0).
4. Les deux droites se rencontrent lorsque x + y = 6 et 2x + y = 8. La soustraction donne x = 2, puis y = 4.

La zone commune est le quadrilatère de sommets (0,0), (4,0), (2,4) et (0,6). Aux quatre sommets, z vaut respectivement 0, 12, 14 et 12. Le maximum est donc 14, atteint en (2,4). Pour contrôler le calcul, ce point vérifie 2 + 4 = 6 et 2 × 2 + 4 = 8 : il appartient bien aux deux frontières actives.

Pour résoudre graphiquement deux inéquations, on trace chaque droite frontière, puis on teste un point qui n’est pas sur la droite, souvent l’origine. Son résultat indique quel demi-plan conserver. Si l’origine est sur la frontière, il faut choisir un autre point test.

Pour un système, on superpose les demi-plans et on garde uniquement leur intersection. Le calcul algébrique des points d’intersection est préférable à une lecture approximative du dessin lorsque les sommets doivent être exacts.

En programmation linéaire à deux variables, on évalue la fonction à optimiser aux sommets de la zone admissible lorsqu’elle est un polygone borné. Si la zone est non bornée, il faut aussi vérifier que la quantité cherchée possède réellement un maximum ou un minimum.

Un régionnement décrit l’ensemble des zones créées par des frontières et les règles qui les distinguent. Une zone admissible est seulement la région où toutes les contraintes d’un problème sont satisfaites. Dans l’exemple, les quatre droites régionnent le plan, tandis que le quadrilatère de sommets (0,0), (4,0), (2,4) et (0,6) est la zone admissible.

Une équation comme x + y = 6 décrit ici une droite. Une inéquation comme x + y ≤ 6 décrit l’un des demi-plans bordés par cette droite. Le point (0,0) satisfait l’inéquation, mais pas l’équation : ce test sépare immédiatement les deux objets.

Une intersection peut être vide. Par exemple, x ≥ 1 et x ≤ 0 ne laissent aucun point commun. Si les zones coloriées ne se recouvrent pas, il faut conclure que le système n’a pas de solution, et non chercher un sommet absent.

La zone peut être non bornée. Une figure ouverte dans une direction ne prouve ni l’existence ni l’absence d’un optimum : il faut étudier le sens de variation de la fonction à optimiser dans cette direction.

Une zone non vide n’est pas toujours un polygone avec une aire positive. Des contraintes peuvent la réduire à un segment ou à un seul point. Il faut alors conserver cet ensemble dégénéré et vérifier la fonction objectif sur les points qui restent.

Le tracé de la frontière encode son inclusion. Avec ≤ ou ≥, la droite appartient au demi-plan ; avec < ou >, elle en est exclue. Confondre ces cas donne une mauvaise réponse pour les points où l’égalité est atteinte.

Le glossaire Demi-plan précise l’objet associé à une inéquation linéaire et le rôle de sa droite frontière.

L’article La programmation linéaire prolonge le passage du système de contraintes à la recherche d’un optimum.