Le problème d'affectation quadratique est l'un des problèmes fondamentaux d'optimisation combinatoire dans le domaine de l'optimisation ou de la recherche opérationnelle en mathématiques ; il appartient à la catégorie des problèmes de l'emplacement d'installation. Il a été initialement proposé par Tjalling Koopmans et Martin J. Beckmann.
Ce problème modélise la situation suivante, tirée de la vie réelle :
Soit un ensemble de n installations et un ensemble de n emplacements. Pour chaque paire d'emplacements, une distance est spécifiée, et pour chaque paire d'installations, un poids ou un flux est spécifié (par exemple, la quantité de marchandises transportées entre les deux installations). Le problème consiste à affecter toutes les installations à des emplacements différents, dans le but de minimiser la somme des distances multipliées par les flux correspondants.
L'énoncé du problème ressemble à celui du problème d'affectation, sauf que la fonction objectif est exprimée en termes d'inégalités quadratiques, d'où son nom.
Définition mathématique formelle La définition formelle du problème d'affectation quadratique est la suivante:
Étant donné un entier positif et coefficients de coût , déterminez la matrice qui minimise la fonction objectif.
compte tenu des contraintes
Formulation de Koopmans-Beckmann Le problème d'affectation quadratique a été initialement défini par Tjalling Koopmans et Martin J. Beckmann sous la forme suivante.
Étant donné deux matrices carrées D et T, trouvez la matrice de permutation X qui minimise le produit scalaire double de T avec X. . Autrement dit, étant donné D et T, trouvez afin de
En utilisant la terminologie ci-dessus, la matrice D répertorie les distances ( indique la distance de l'emplacement i à l'emplacement j) et T les flux ( indique la quantité de marchandises à transporter de l'installation i à l'installation j). La matrice de permutation X représente une affectation des installations aux emplacements ( vaut 1 uniquement si l'installation i est située à l'emplacement j).
Intuitivement, la fonction objectif favorise le regroupement des installations entre lesquelles les flux sont importants.
Complexité computationnelle Ce problème est NP-difficile ; il n’existe donc aucun algorithme connu permettant de le résoudre en temps polynomial, et même des instances de petite taille peuvent nécessiter un temps de calcul important. Il a également été démontré que ce problème ne dispose d’aucun algorithme d’approximation fonctionnant en temps polynomial pour un facteur (constant) quelconque, à moins que P = NP. Le problème du voyageur de commerce peut être considéré comme un cas particulier du problème d'affectation quadratique si l’on suppose que les flux relient toutes les installations uniquement le long d’un seul anneau, que tous les flux ont la même valeur non nulle (constante) et que toutes les distances sont égales aux distances respectives de l’instance du problème du voyageur de commerce. D'autres problèmes d’optimisation combinatoire classiques peuvent être décrits sous cette forme.
Applications Outre sa formulation initiale relative à l'implantation d'usines, le problème d'affectation quadratique est un modèle mathématique permettant de résoudre le problème du placement de composants électroniques interconnectés sur un circuit imprimé ou une puce électronique, qui s'inscrit dans la phase de placement-routage de la conception assistée par ordinateur dans l'industrie électronique.
Le problème d'affectation quadratique a également été utilisé pour modéliser le coût de la disposition des caractères sur un clavier. Dans ce cas, les emplacements correspondent aux touches du clavier et leurs distances par paires correspondent au temps nécessaire pour appuyer sur une paire de touches donnée. Les éléments sont les caractères et leurs poids sont proportionnels à la fréquence d'apparition de la paire de caractères donnée dans un corpus de textes. Ce type de modèle a été utilisé lors de la conception de la norme relative au clavier AZERTY (NF Z71-300).
Articles connexes Problème d'affectation des goulots d'étranglement de type quadratique
Références
Bibliographie A2.5: ND43, pg.218.
Catégorie:Recherche opérationnelle Catégorie:Problème NP-difficile