Problème d'optimisation - Optimization problem
En mathématiques , en informatique et en économie , un problème d'optimisation est le problème de trouver la meilleure solution parmi toutes les solutions possibles .
Les problèmes d'optimisation peuvent être divisés en deux catégories, selon que les variables sont continues ou discrètes :
- Un problème d'optimisation avec des variables discrètes est connu sous le nom d' optimisation discrète , dans laquelle un objet tel qu'un entier , une permutation ou un graphique doit être trouvé à partir d'un ensemble dénombrable .
- Un problème avec des variables continues est connu comme une optimisation continue , dans laquelle une valeur optimale d'une fonction continue doit être trouvée. Ils peuvent inclure des problèmes contraints et des problèmes multimodaux.
Problème d'optimisation continue
La forme standard d'un problème d'optimisation continue est
où
- f : ℝ n → ℝ est la fonction objectif à minimiser sur le vecteur n -variable x ,
- g i ( x ) ≤ 0 sont appelées contraintes d' inégalité
- h j ( x ) = 0 sont appelés contraintes d'égalité , et
- m ≥ 0 et p ≥ 0 .
Si m = p = 0 , le problème est un problème d'optimisation sans contrainte. Par convention, le formulaire standard définit un problème de minimisation . Un problème de maximisation peut être traité en annulant la fonction objectif.
Problème d'optimisation combinatoire
Formellement, un problème d' optimisation combinatoire A est un quadruple ( I , f , m , g ) , où
- I est un ensemble d'instances;
- étant donné une instance x ∈ I , f ( x ) est l'ensemble des solutions réalisables;
- étant donné une instance x et une solution réalisable y de x , m ( x , y ) désigne la mesure de y , qui est généralement un réel positif .
- g est la fonction de but, et est soit min, soit max .
Le but est alors de trouver pour une instance x une solution optimale , c'est-à-dire une solution réalisable y avec
Pour chaque problème d'optimisation combinatoire, il existe un problème de décision correspondant qui demande s'il existe une solution réalisable pour une mesure particulière m 0 . Par exemple, s'il y a un graphe G qui contient les sommets u et v , un problème d'optimisation pourrait être "trouver un chemin de u vers v qui utilise le moins d'arêtes". Ce problème pourrait avoir une réponse de, disons, 4. Un problème de décision correspondant serait "y a-t-il un chemin de u à v qui utilise 10 arêtes ou moins?" Ce problème peut être résolu par un simple «oui» ou «non».
Dans le domaine des algorithmes d'approximation , les algorithmes sont conçus pour trouver des solutions quasi optimales à des problèmes difficiles. La version de décision habituelle est alors une définition inadéquate du problème puisqu'elle ne spécifie que des solutions acceptables. Même si nous pourrions introduire des problèmes de décision appropriés, le problème est plus naturellement caractérisé comme un problème d'optimisation.
Voir également
- Problème de comptage (complexité)
- Optimisation de la conception
- Problème de fonction
- Problème de gants
- Recherche opérationnelle
- Satisfaisant : il n'est pas nécessaire de trouver l'optimum, juste une solution «assez bonne».
- Problème de recherche
- Programmation semi-infinie
Références
Liens externes
- "Comment la formation du trafic optimise la bande passante du réseau" . IPC . 12 juillet 2016 . Récupéré le 13 février 2017 .