Problème d'optimisation

mathématiques , en ingénierie , en informatique et en économie , un problème d'optimisation est le problème qui consiste à 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 lequel un objet tel qu'un entier , une permutation ou un graphe doit être trouvé à partir d'un ensemble dénombrable .
Un problème à variables continues est appelé optimisation continue ; il s’agit de trouver la valeur optimale d’une fonction continue . Ce type de problème peut inclure des problèmes avec contraintes et des problèmes multimodaux.

forme standard d'un problème d'optimisation continue est

où ℝ n \to ℝ est la fonction objectif à minimiser sur levecteur contraintes d'inégalité inversant le sens de la fonction objectif.

Problème d'optimisation combinatoire

d'optimisation combinatoire

ensemble d'instances ; étant donné une instance mesure de réel positif . min soit max . L'objectif est alors de trouver, pour une instance À chaque problème d'optimisation combinatoire correspond un problème de décision qui cherche à déterminer s'il existe une solution réalisable pour une mesure particulière graphe algorithmes d'approximation , ces algorithmes sont conçus pour trouver des solutions quasi optimales à des problèmes difficiles. La formulation décisionnelle classique du problème s'avère alors inadéquate, car elle ne spécifie que des solutions acceptables. Bien qu'il soit possible d'introduire des problèmes de décision appropriés, le problème se caractérise plus naturellement comme un problème d'optimisation.