Région réalisable
La région réalisable (également appelée ensemble des solutions réalisables ou ensemble admissible, en anglais Feasible region ou feasible set) est, en recherche opérationnelle, en optimisation et en modélisation mathématique, l'ensemble de toutes les solutions possibles (combinaisons de valeurs de variables) qui satisfont à toutes les contraintes d'un problème.
La région réalisable constitue le sous-espace dans lequel la recherche d'une solution optimale est effectuée. Toute solution située en dehors de cette région est considérée comme non réalisable (ou inadmissible).
Définition et formation
La région réalisable est formée par l'intersection des ensembles définis par chaque contrainte individuelle du problème. Les contraintes peuvent être représentées sous forme de :
- Inégalités : Elles établissent des limites supérieures ou inférieures pour les valeurs des variables ou leurs combinaisons (par exemple, « la consommation de la ressource A ne doit pas dépasser 100 unités », « la quantité de produits fabriqués doit être d'au moins 50 pièces »).
- Égalités : Elles exigent le respect strict d'une condition (par exemple, « le volume total des transports doit être égal à 1000 tonnes », « le solde des flux entrants et sortants est nul »).
- Conditions sur le signe des variables : Souvent, les variables doivent être non négatives, entières ou appartenir à un certain ensemble discret.
Un point (ou un vecteur de valeurs de variables) appartient à la région réalisable si et seulement s'il satisfait simultanément à toutes ces contraintes.
Interprétation géométrique
La région réalisable a souvent une interprétation géométrique claire, en particulier dans les problèmes avec un petit nombre de variables :
- Dans un espace bidimensionnel (2 variables) : Chaque contrainte linéaire sous forme d'inégalité définit un demi-plan. La région réalisable est l'intersection de ces demi-plans, formant un polygone convexe (potentiellement non borné ou vide).
- Dans un espace tridimensionnel (3 variables) : Chaque contrainte linéaire sous forme d'inégalité définit un demi-espace. La région réalisable est l'intersection de ces demi-espaces, formant un polyèdre convexe.
- Dans un espace multidimensionnel : La région réalisable, définie par des contraintes linéaires, est un polytope convexe.
Dans le cas de contraintes non linéaires, la région réalisable peut avoir une forme plus complexe et ne pas être convexe.
Rôle dans l'optimisation
La région réalisable joue un rôle fondamental en optimisation :
- Définition de l'espace de recherche : La solution optimale d'un problème (si elle existe) se trouve toujours à l'intérieur de la région réalisable ou sur sa frontière. Les algorithmes d'optimisation recherchent l'extremum de la fonction objectif précisément dans cette région.
- Vérification de l'existence de solutions : Si la région réalisable est un ensemble vide (c'est-à-dire que les contraintes sont contradictoires), alors le problème n'a pas de solutions réalisables, et par conséquent, pas de solution optimale.
- Influence sur la solution optimale : La forme et la taille de la région réalisable influencent directement la possibilité d'atteindre un extremum de la fonction objectif et la valeur de cet extremum.
Propriétés de la région réalisable (en programmation linéaire)
Dans les problèmes de programmation linéaire (PL), où toutes les contraintes et la fonction objectif sont linéaires, la région réalisable possède des propriétés importantes :
- Convexité : Si deux points appartiennent à la région réalisable, alors le segment de droite qui les relie appartient également entièrement à cette région. Cette propriété garantit que la solution optimale (si elle existe et est unique) se trouvera à l'un des sommets du polyèdre formant la région réalisable.
- Fermeture : La région réalisable inclut ses frontières (en raison des inégalités non strictes ≤, ≥ et des égalités).
La région réalisable peut être :
- Bornée : De dimensions finies.
- Non bornée : S'étendant à l'infini dans une ou plusieurs directions.
- Vide : Ne contenant aucun point.
Voir aussi
- Recherche opérationnelle
- Optimisation
- Modèle mathématique
- Contrainte
- Solution réalisable
- Solution optimale
- Fonction objectif
- Programmation linéaire
- Ensemble convexe
Bibliographie
- Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
- Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)