Worldlex Wiki 
En optimisation mathématique et en informatique , une région admissible, un ensemble admissible ou un espace de solutions est l'ensemble de tous les points possibles (ensembles de valeurs des variables de choix) d'un problème d'optimisation qui satisfont les contraintes du problème , pouvant inclure des inégalités , des égalités et des contraintes d'intégrité . Il s'agit de l'ensemble initial des solutions candidates au problème, avant que cet ensemble ne soit restreint.
Par exemple, considérons le problème de minimisation de la fonction par rapport aux variables et sous les contraintes et . L'ensemble admissible est ici l'ensemble des paires ( x , y ) pour lesquelles la valeur de x est comprise entre 1 et 10, et la valeur de y entre 5 et 12. Cet ensemble admissible est distinct de la fonction objectif , qui énonce le critère à optimiser et qui, dans l'exemple ci-dessus, est .
Dans de nombreux problèmes, l'ensemble des solutions admissibles reflète la contrainte qu'une ou plusieurs variables doivent être non négatives. En programmation linéaire en nombres entiers , l'ensemble des solutions admissibles est l'ensemble des entiers (ou un sous-ensemble de celui-ci). En programmation linéaire , l'ensemble des solutions admissibles est un polytope convexe : une région de l'espace multidimensionnel dont les frontières sont formées par des hyperplans et dont les sommets sont des points cardinaux .
La satisfaction des contraintes est le processus de recherche d'un point dans la région admissible.
convexe admissible est un ensemble dans lequel un segment de droite reliant deux points admissibles quelconques ne passe que par d'autres points admissibles, et jamais par des points extérieurs à l'ensemble. Les ensembles convexes admissibles apparaissent dans de nombreux types de problèmes, notamment les problèmes de programmation linéaire, et ils présentent un intérêt particulier car, si le problème a une fonction objectif convexe à minimiser, il sera généralement plus facile à résoudre en présence d'un ensemble convexe admissible et tout optimum local sera également un optimum global .Aucun ensemble réalisable
Si les contraintes d'un problème d'optimisation sont contradictoires, aucun point ne satisfait toutes les contraintes et la région admissible est donc l' ensemble vide . Dans ce cas, le problème n'a pas de solution et est dit infaisable .
Ensembles réalisables bornés et non bornés
Les ensembles admissibles peuvent être bornés ou non bornés . Par exemple, l'ensemble admissible défini par les contraintes { x ≥ 0, y ≥ 0 } est non borné car, dans certaines directions, le déplacement est illimité tout en restant dans la région admissible. En revanche, l'ensemble admissible formé par les contraintes { x ≥ 0, y ≥ 0, x + 2y ≤ 4 } est borné car l'amplitude du déplacement dans chaque direction est limitée par les contraintes.
Dans les problèmes de programmation linéaire à n variables, une condition nécessaire mais insuffisante pour que l'ensemble réalisable soit borné est que le nombre de contraintes soit au moins n + 1 (comme illustré par l'exemple ci-dessus).
Si l'ensemble des solutions admissibles est non borné, il peut exister ou non un optimum, selon les spécificités de la fonction objectif. Par exemple, si la région admissible est définie par l'ensemble de contraintes { x ≥ 0, y ≥ 0 }, alors le problème de maximisation de x + y n'admet pas d'optimum puisque toute solution candidate peut être améliorée en augmentant x ou y ; en revanche, si le problème consiste à minimiser x + y , alors il existe un optimum (plus précisément en ( x , y ) = (0, 0)).
Solution candidate
En optimisation et dans d'autres branches des mathématiques , ainsi qu'en algorithmique de recherche (un domaine de l'informatique ), une solution candidate appartient à l' ensemble des solutions possibles dans la région admissible d'un problème donné. Une solution candidate n'est pas nécessairement une solution probable ou raisonnable au problème ; elle appartient simplement à l'ensemble des solutions qui satisfont toutes les contraintes , c'est-à-dire à l'ensemble des solutions admissibles . Les algorithmes de résolution de divers types de problèmes d'optimisation restreignent souvent l'ensemble des solutions candidates à un sous-ensemble des solutions admissibles, dont les points restent candidats tandis que les autres solutions admissibles sont exclues.
L'espace de toutes les solutions candidates, avant exclusion des points admissibles, est appelé région admissible, ensemble admissible, espace de recherche ou espace des solutions. Il s'agit de l'ensemble de toutes les solutions possibles qui satisfont aux contraintes du problème. La satisfaction des contraintes consiste à trouver un point dans l'ensemble admissible.
Algorithme génétique
Dans le cas de l' algorithme génétique , les solutions candidates sont les individus de la population qui évoluent grâce à l'algorithme.
Calcul
En calcul différentiel, on recherche une solution optimale à l'aide du test de la dérivée première : la dérivée première de la fonction à optimiser est annulée, et toutes les valeurs de la ou des variables de choix qui satisfont cette condition sont considérées comme des solutions candidates (tandis que celles qui ne la satisfont pas sont éliminées). Une solution candidate peut ne pas être une solution globale pour plusieurs raisons. Premièrement, elle peut correspondre à un minimum alors qu'on recherche un maximum (ou inversement). Deuxièmement, elle peut ne correspondre ni à un minimum ni à un maximum, mais plutôt à un point selle ou à un point d'inflexion , où se produit une pause temporaire dans la variation locale de la fonction. Ces solutions candidates peuvent être éliminées à l'aide du test de la dérivée seconde , dont la satisfaction est suffisante pour que la solution candidate soit au moins localement optimale. Troisièmement, une solution candidate peut être un optimum local sans être un optimum global .
En calculant les primitives des monômes de la forme , la solution candidate utilisant la formule de quadrature de Cavalieri serait . Cette solution candidate est en fait correcte sauf lorsque
Programmation linéaire
Dans la méthode du simplexe pour la résolution des problèmes de programmation linéaire , un sommet du polytope admissible est sélectionné comme solution candidate initiale et son optimalité est testée ; s’il est rejeté, un sommet adjacent est considéré comme solution candidate suivante. Ce processus se poursuit jusqu’à ce qu’une solution candidate optimale soit trouvée.
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index