2.2 Complexité des Problèmes
51
© Dunod – Toute reproduction non autorisée est un délit.
aussi fréquemment que ceux cités précédemment par le chercheur opérationnel font
aussi partie de la classe des problèmes NP-complets. Nous indiquons, tout au long
de cet ouvrage, le caractère NP-complet d’un problème à chaque fois qu’il a lieu.
Une longue liste de problèmes NP-complets pourra être consultée dans l’ouvrage de
Garey et Johnson cité dans la bibliographie.
2.2.3 Les problèmes d’optimisation NP-difficiles
Les problèmes d’optimisation sont définis de la manière suivante. Pour une donnée (instance) du problème, l’algorithme doit déterminer une structure particulière
répondant à un critère d’optimisation. Ainsi, dans la version optimisation du problème du plus court chemin (tout arc de A étant valué), la donnée est :
G 5 1 S, A2 un graphe, a et b deux sommets de G, v la fonction de valuation des arcs
et il est demandé de trouver un chemin d’origine a et d’extrémité b de valeur minimale.
Dans la version optimisation du problème du plus long chemin élémentaire, c’est un
chemin élémentaire reliant a et b de valeur maximale qui doit être trouvé. Pour le
problème de l’arbre couvrant de poids (ou coût) minimal, étudié plus loin dans cet
ouvrage, la structure à déterminer est un arbre couvrant, et le critère à optimiser est
le poids (coût) de cet arbre. Le plus souvent, en recherche opérationnelle, le critère
d’optimisation consistera à minimiser un coût ou à maximiser un gain.
Nous venons de voir au paragraphe précédent que le problème de décision du
plus long chemin élémentaire est NP-complet, donc de résolution difficile. La version optimisation de ce problème est donc au moins aussi difficile à résoudre. De
manière plus générale, à tout problème d’optimisation on peut associer un problème
de décision
1
; lorsque ce problème de décision est NP-complet, le problème d’optimisation sera qualifié de problème NP-difficile. La résolution exacte de problèmes
NP-difficiles ne pourra se faire qu’avec des procédures énumératives de type séparation et évaluation (recherches arborescentes) ou pour une certaine sous-classe de
problèmes en utilisant la programmation dynamique (deux paragraphes de ce précis
sont dédiée à ces techniques de résolution). Cette résolution menée jusqu’à obtention
de l’optimum ne pourra être effectuée en pratique que pour des problèmes de petite
taille.
Citons maintenant quelques types de problèmes classiques d’optimisation NPdifficiles rencontrés en recherche opérationnelle (le lecteur retrouvera les exemples
cités dans les différents chapitres de cet ouvrage) : le problème du voyageur de commerce et, plus généralement, les problèmes de tournées de véhicules, de nombreux
problèmes d’ordonnancement lorsque des contraintes de ressource sont nécessaires
pour l’exécution des tâches, les problèmes d’emploi du temps, la programmation
linéaire en nombres entiers (même dans le cas plus particulier du problème du sac
à dos qui comporte, pourtant, une seule contrainte). Par contre la programmation
linéaire en variables continues est un problème polynomial (même si l’algorithme du
1. Dans un problème de minimisation d’une fonction économique f, on se fixe une borne B (qui
sera l’une des données du problème de décision associé). La question du problème de décision
associé étant : « existe-t-il une solution de coût inférieur ou égal à B ? ».
51
© Dunod – Toute reproduction non autorisée est un délit.
aussi fréquemment que ceux cités précédemment par le chercheur opérationnel font
aussi partie de la classe des problèmes NP-complets. Nous indiquons, tout au long
de cet ouvrage, le caractère NP-complet d’un problème à chaque fois qu’il a lieu.
Une longue liste de problèmes NP-complets pourra être consultée dans l’ouvrage de
Garey et Johnson cité dans la bibliographie.
2.2.3 Les problèmes d’optimisation NP-difficiles
Les problèmes d’optimisation sont définis de la manière suivante. Pour une donnée (instance) du problème, l’algorithme doit déterminer une structure particulière
répondant à un critère d’optimisation. Ainsi, dans la version optimisation du problème du plus court chemin (tout arc de A étant valué), la donnée est :
G 5 1 S, A2 un graphe, a et b deux sommets de G, v la fonction de valuation des arcs
et il est demandé de trouver un chemin d’origine a et d’extrémité b de valeur minimale.
Dans la version optimisation du problème du plus long chemin élémentaire, c’est un
chemin élémentaire reliant a et b de valeur maximale qui doit être trouvé. Pour le
problème de l’arbre couvrant de poids (ou coût) minimal, étudié plus loin dans cet
ouvrage, la structure à déterminer est un arbre couvrant, et le critère à optimiser est
le poids (coût) de cet arbre. Le plus souvent, en recherche opérationnelle, le critère
d’optimisation consistera à minimiser un coût ou à maximiser un gain.
Nous venons de voir au paragraphe précédent que le problème de décision du
plus long chemin élémentaire est NP-complet, donc de résolution difficile. La version optimisation de ce problème est donc au moins aussi difficile à résoudre. De
manière plus générale, à tout problème d’optimisation on peut associer un problème
de décision
1
; lorsque ce problème de décision est NP-complet, le problème d’optimisation sera qualifié de problème NP-difficile. La résolution exacte de problèmes
NP-difficiles ne pourra se faire qu’avec des procédures énumératives de type séparation et évaluation (recherches arborescentes) ou pour une certaine sous-classe de
problèmes en utilisant la programmation dynamique (deux paragraphes de ce précis
sont dédiée à ces techniques de résolution). Cette résolution menée jusqu’à obtention
de l’optimum ne pourra être effectuée en pratique que pour des problèmes de petite
taille.
Citons maintenant quelques types de problèmes classiques d’optimisation NPdifficiles rencontrés en recherche opérationnelle (le lecteur retrouvera les exemples
cités dans les différents chapitres de cet ouvrage) : le problème du voyageur de commerce et, plus généralement, les problèmes de tournées de véhicules, de nombreux
problèmes d’ordonnancement lorsque des contraintes de ressource sont nécessaires
pour l’exécution des tâches, les problèmes d’emploi du temps, la programmation
linéaire en nombres entiers (même dans le cas plus particulier du problème du sac
à dos qui comporte, pourtant, une seule contrainte). Par contre la programmation
linéaire en variables continues est un problème polynomial (même si l’algorithme du
1. Dans un problème de minimisation d’une fonction économique f, on se fixe une borne B (qui
sera l’une des données du problème de décision associé). La question du problème de décision
associé étant : « existe-t-il une solution de coût inférieur ou égal à B ? ».