Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction: Ce problème du voyageur de commerce est un problème de recherche

Introduction: Ce problème du voyageur de commerce est un problème de recherche opérationnelle et n’est pas sans rappeler les cycles hamiltoniens. En effet, le nom donné à ce problème du voyageur de commerce a pour origine le fait qu’un circuit hamiltonien est celui que suivrait un voyageur de commerce partant d’une ville pour traverser une seule et unique fois n autres villes et revenir à son point de départ et ce à cause de son travail. Son objectif est rationnellement d’effectuer ces trajets, ce circuit en un temps minimal, une distance minimale ou un coût minimal. Pour parvenir à ses fins, le voyageur commercial peut bien sûr effectuer des essais successifs différents en notant à chaque essai, le temps nécessaire, le coût et la distance. Il pourra certainement trouver la solution mais cela pourra lui prendre d’autant plus de temps que le nombre de villes à traverser est lui aussi grand. Cette façon de procéder devient donc vite irréalisable. Mais avant de poursuivre sur le problème, on abordera dans un premier temps les origines du problème avec Sir William Rowan Hamilton. Ensuite par poser le problème et la problématique sous jacente puis on énoncera des méthodes de résolution. Et pour finir, on va donner des exemples qui appliquent une de ces méthodes de résolution sur quelques exemples ou exercices. i. Les origines du problème du voyageur de commerce ii. Le problème du voyageur de commerce iii. Méthodes de résolution iv. Exemples de résolution du problème du voyageur de commerce 1 a. Les origines du problème du voyageur de commerce C’est en 1859 que la notion de cycle hamiltonien est apparue et ce à la suite du lancement par l’illustre mathématicien Sir William Rowan Hamilton d’un casse tête, celui du voyage fermé autour du monde, principalement composé d’un dodécaèdre régulier en bois. C’est l’un des soldes de Platon, un polyèdre dont les 12 faces sont des pentagones réguliers et dont 3 arêtes de ces pentagones se rencontrent à chacun des sommets. Dans son casse tête, Hamilton a donné à chacun des 20 sommets du dodécaèdre le nom d’une grande ville du monde : Bruxelles, Francfort, Delhi etc. ce qui n’est pas sans faire penser au tour du monde en 80 jours écris par Jules Verne en 1873. L’objectif était alors de passer une seule et unique fois dans chaque ville et ce en n’utilisant que les arêtes du dodécaèdre mais en partant d’une ville pour au final y revenir. Cela revient donc à chercher un cycle Hamiltonien dans la figure car le dodécaèdre étant assez difficilement manipulable, Sir Hamilton la remplacer par un graphe planaire isomorphe. En effet, la difficulté de manipulation venait du fait que pour noter les passages, on pouvait planter un clou sur chaque sommet et faire passer une ficelle. Rien ne peut amener la preuve du succès de ce dodécaèdre auprès du public mais les mathématiciens ont immortalisés son souvenir en définissant un cycle hamiltonien comme étant un cycle élémentaire qui passe une fois et une seule par chacun des sommets d’un graphe (généralement, il ne passe pas par toutes les arêtes, il n’en emprunte que deux à chaque sommet). Et c’est donc de ce problème que le problème du voyageur de commerce est tiré. Définissons ce que sont les circuits et cycles hamiltoniens. Soit G = [X, U] un graphe connexe d’ordre N On appelle chemin hamiltonien (chaîne hamiltonienne) un chemin (une chaîne) passant une fois, et une seule fois seulement, par chacun des sommets de G. Un chemin hamiltonien (une chaîne hamiltonienne) est donc élémentaire et de longueur N-1. Un circuit hamiltonien ( un cycle hamiltonien) est un circuit ( un cycle) qui passe une fois, et une seule fois seulement, par chacun des sommets de G. Un cycle hamiltonien est donc un cycle élémentaire de longueur N. On dit qu’un graphe G est hamiltonien s’il contient un cycle hamiltonien ( cas non orienté) ou un circuit hamiltonien ( cas orienté). 2. Le problème du voyageur de commerce Le problème du voyageur de commerce ou problème de circuits hamiltoniens ( cycle hamiltonien) de longueur minimale se rencontre dans de très nombreux et dans des domaines variés : ramassage scolaire, ordonnancement de production, câblage de circuits, synthèse de 2 circuits logiques séquentiels etc. mais il peut également être étendu au cas multiple où plusieurs voyageurs de commerce doivent couvrir une certaine zone. Toutefois, dans le cas d’un seul voyageur de commerce, il faut faire la distinction entre deux cas de figure, le cas non orienté et le cas orienté lequel peut d’ailleurs se ramener à un problème non orienté. Le cas orienté est caractérisé par le fait que les arcs séparant des sommets vont représenter des contraintes d’antériorités c’est à dire que le début d’exécution d’une tache j ne pourra se faire après une certaine durée suivant le début d’exécution d’une tache i de sorte que par exemple. La tache j ne pourra débuter après que i soit exécutée. Dans le problème du voyageur de commerce, on a donc un graphe connexe G = [X,U] dans lequel chaque arc u= (i,j) est muni d’une longueur L(i,j) et ce graphe est d’ordre N. X est l’ensemble des sommets. U est l’ensemble des arcs. Dès lors que l’on a un problème à résoudre et que l’on a un graphe associé, pour pouvoir trouver le chemin de longueur minimal passant par tous les sommets c’est à dire une chaîne hamiltonienne, il faut que des conditions nécessaires et suffisantes soient validées afin que la résolution puisse être mise en œuvre. Mais il n’existe pas de conditions nécessaires et suffisantes mais seulement des conditions nécessaires et des conditions suffisantes. - Voyons tout d’abord les conditions nécessaires (CN). Une CN pour qu’un graphe G=X, U non orienté soit hamiltonien est que ce graphe soit 2-connexe c’est à dire que dans le graphe, on peut trouver deux chaînes allants de n’importe quel sommet à n’importe quel autre. Ceci est évident mais cette condition n’est pas suffisante. C’est une CN car s’il n’y avait qu’une seule chaîne, le chemin minimal se réduirait à cette chaîne et cette solution serait non seulement évidente mais inévitable et de plus il n’y aurait plus de critère de minimisation. A B C D E C’est un graphe 2-connexe mais il ne contient pas de cycle hamiltonien car en effet, on ne peut passer chaque sommet une seule et unique fois en partant d’un point pour y revenir. On est obligé de passer 2 fois par 2 sommets. Une autre condition nécessaire pour qu’un plus court chemin existe est que le graphe associé au problème ne comporte pas de longueur d’arc négative. 3 Et dans le cas du problème du voyageur de commerce, il faut que le graphe associé au problème soit complet c’est à dire que tous les couples de sommet sont reliés au moins par un arc donc si (i,j) n’existe pas alors (j,i) existe. Il existe d’autres CN mais ne connaissant pas de conditions nécessaires et suffisantes voyons plutôt des conditions suffisantes CS. CS dans le cas non orienté : Proposition 1 : le graphe complet d’ordre N, KN est hamiltonien. Si le graphe est complet alors tous les couples de sommets sont reliés au moins par un arc et s’il est d’ordre N alors il y a N arcs donc il est forcement hamiltonien. Soit G=[X,U] un graphe non orienté d’ordre N et supposons qu’il existe deux sommets s et t non reliés par un arc tel que : dG(s) + dG(t)  N Soit G +(s,t) la notation pour le graphe obtenue en rajoutant l’arc (s,t) à G Proposition 2 : si G +(s,t) est hamiltonien, G est lui même hamiltonien. On dit alors que la propriété P : « être hamiltonien » est stable par la transformation G→ G +(s,t) Soit G un graphe simple d’ordre N et k un nombre entier 1 k N. On considère la procédure récursive qui suit : à partir de G on ajoute progressivement des arêtes joignant des sommets non adjacents dont la somme des degrés est supérieure ou égale à k. Ce graphe ainsi obtenue qui contient le graphe G sera appelé la k-fermeture de G et sera noté [G]N Théorème (Bondy, Chvatal 1976) : pour que G soit hamiltonien, il faut et il suffit que [G]N soit hamiltonien. Théorème (Erdös- Chvatal 1972) : soit G un graphe h-connexe ( h  2). Si le nombre de stabilité (G) vérifie : (G)  h, alors G est hamiltonien. Lemme : si G est h-connexe et si A={a1,…,ah} X est un ensemble de h sommets distincts ; pour tout sommet x  X-A, il existe h chaînes élémentaires joignant x à chacun des ai et ayant x comme seul sommet commun. Corollaire : si ([G]N)  h([G]N), alors G est hamiltonien. Voyons maintenant le cas orienté. Théorème (Meyniel 1973) : soit G = [X,U] un graphe fortement connexe sans boucle d’ordre N tel que : (i,j)  U et (j,i) U  dG(i) + dG(j)  2N-1 uploads/Voyage/ 5385-cd-882-f-827.pdf