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 :

Problème d'optimisation continue

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

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

Références

Liens externes