[PDF] chapitre 2 exemple de problèmes doptimisation combinatoire

CHAPITRE2EXEMPLE DE PROBLÈMES D"OPTIMISATIONCOMBINATOIRESommaire1 Démarche en Optimisation Combinatoire. . . . . . . . . . . .71.1 Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71.2 Démarches. . . . . . . . . . . . . . . . . . . . . . . . . . . . .72 Exemples classiques de problèmes combinatoires. . . . . . .102.1 Le problème du sac-à-dos (knapsack). . . . . . . . . . . . . . .102.2 Problème de voyageur de commerce (TSP : Travelling SalesmanProblem). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122.3 Problème d"ordonnancement de tâches. . . . . . . . . . . . . .152.4 Problème du plus court chemin. . . . . . . . . . . . . . . . . .172.5 Problème de l"Arbre couvrant de poids minimum. . . . . . . .17IntroductionLaCombinatoireen mathématique est une branche dont le but est de dénombrer lesdispositions que l"on peut former à l"aide des éléments d"un ensemble fini .La définition de l"optimisation combinatoire est liée directement par l"espace de recherchedu problème . Le but de la résolution d"un tel problème est de chercher l"élément optimalà partir d"un ensemble fini dénombrable. Cet objet peut être unnombre entier, unsous-ensemble, ou unestructure de graphe.6Dr. Nada KHERICI

CHAPITRE 2. EXEMPLE DE PROBLÈMES D"OPTIMISATION COMBINATOIRECe chapitre présente d"abord la démarche de l"optimisation combinatoire (Sivazlian,2009). Ensuite, quelques exemples classiques de l"optimisation combinatoire seront ex-pliqués(Belhoul,2014), (Ouaarab,2015), (Lobjois,1999), (Korteet al.,2010), (Laribi,2018), (Verfaillie,2008).1Démarche en Optimisation Combinatoire1.1ExempleC"est la fin de l"année! Les étudiants doivent se préparer pour passer leurs examens. Omarpassera 3 modules et ne possède que 100 heures pour la révision. Il révise pendanttiheuresle modulei(i= 1,2,3). On suppose que la notenidu moduleidépend uniquement dutempstipassé à réviser. Supposons que :n1= 2.t1, n2= 2.t2-4, n3= 3/2.t3Omar veut optimiser sa tâche et avoir la moyenne maximale en respectant la contraintede temps. Les variables de décisionsxipour ce problème représentent les temps derévision (ti), estimés en minutes, attribués à chaque module . Le problème revient àtrouverx= (x1,x2,x3)qui donne le maximum de moyennef(x) = (2.x1+ 2.x2-4 +3/2.x3)/3oùx= (x1,x2,x3)?X={x1,x2,x3?N,:x1+x2+x36100?60;}.Le problème est alors noté comme suit :maxx?Xf(x).1.2DémarchesL"optimisation suit les mêmes démarches de travail de la Recherche Opérationnelle .La figure2.1résume les différentes étapes pour résoudre un problème d"optimisationcombinatoire.Figure 2.1- Démarche de résolution d"un problème d"optimisationOptimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/20217Dr. Nada KHERICI

2. EXEMPLES CLASSIQUES DE PROBLÈMES COMBINATOIRES1.2.4ImplémentationUne fois la solution établie (via une méthode de résolution) est validée, l"implémentationdu système peut être concrétisée.2Exemples classiques de problèmes combinatoiresOn qualifie un problème decombinatoires, un problème dont la résolution confronte unnombre de combinaisons énorme à explorer . Ces dernières ne sont pas toutes acceptéessauf celles répondant aux exigences du problème lui même.2.1Le problème du sac-à-dos (knapsack)2.1.1IntroductionSupposant que nous prévoyons une journée à la plage. Nous devons alors remplir nos sacsà dos avec des éléments nécessaires pour le voyage. Vu que la capacité du sac à dos estlimitée (un poids ou un volume maximum), on doit faire une décision pour pouvoir leremplir.Figure 2.2- Problème sac-à-dosChaque type d"élément est caractérisé par un poids (ou un volume) et une valeur (niveaud"importance).2.1.2FormalismeOn dispose d"un sac-à-dos dont le contenu ne peut pas excéder une capacitéc. Considéronsun ensemble denobjets, numérotés par l"indiceide1àn, possédant chacun un poidswi(weight en anglais) et une valeurpi(profit en anglais).Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/202110Dr. Nada KHERICI

2. EXEMPLES CLASSIQUES DE PROBLÈMES COMBINATOIRES2.2.4Instance Problème de voyage de commerce symétriqueOn peut utiliser un programme linéaire binaire ou entier pour modéliser le problème devoyageur de commerce symétrique. La modélisation binaire se présente comme suit :1.Variables de décision :Les variables sont définies sur l"ensemble{0,1}: La va-riablexijcorrespond à la présence de l"arcijdans le cycle hamiltonien du voyageur.On notexij= 1si le voyageur prend le chemin existant entre les villesietj, sinonxij= 0.2.Contraintes :Le problème de voyageur de commerce est limité par plusieurscontraintes :(a)Contrainte d"intégrité :xij? {0,1}.(b)Le voyageur doit entrer une seule fois dans une ville :?ni=1xij= 1.(c)Le voyageur doit sortir une seule fois d"une ville :?nj=1xij= 1.3.Critère :La fonction objectif du problème de voyageur de commerce se définitcomme la minimisation de la longueur du chemin :f(x) =n?i=1n?j=1cij.xij(2.3)oùcijest la distance entre les villesietj.Résoudre le problème de voyageur de commerce revient à trouver la matrice solutionx=(((((x11...x1n.........xn1...xnn)))))quiminimisela fonction objectif définie par l"équation2.3.Mathématiquement, un problème de sac à dos est représenté comme suit :Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/202114Dr. Nada KHERICI

CHAPITRE 2. EXEMPLE DE PROBLÈMES D"OPTIMISATION COMBINATOIRESoientnnombre de villes,cij?N?distance entre les villesietj,x=(((((x11... x1n.........xn1... xnn)))))Minimiserf(x) =n?i=1n?j=1cij.xijs.c.xi? {0,1}, i? {1,..,n}n?i=1xij= 1j= 1,..,nn?j=1xij= 1i= 1,..,n2.3Problème d"ordonnancement de tâchesLa production dans un atelier est la création d"un produit à travers l"utilisation et la trans-formation des ressources. Pour le bon fonctionnement de ce système, certains nombres deprocessus sont implémentés prenant en compte le temps et le coût de production.En général, le problème d"ordonnancement est relatif aux points suivants :-Un ensemble de tâches ou jobs à effectuer.-Un ensemble de ressources ou machines à utiliser par ces jobs.-Un programme à identifier, pour allouer les ressources aux taches.Les problèmes d"ordonnancement sont des problèmes d"optimisation définis en terme de :tâches et ressources.2.3.1FormalismeUne tâche(un job)iest une unité élémentaire du travail à effectuer qui commence dansune dateti(start time) et se termine dans une dateci(completion time). Elle utilise lesressources pendant un tempspi=ci-ti(processing time). Un job peut être interrompu,c"est-à-dire il est composé de plusieurs opérations. Dans le cas où le job ne peut pas êtreinterrompu, il est vu comme une seule tâche à effectuer.Uneressourceest tout ce qu"on utilise pour effectuer un job. Les ressources sont limitéesen temps et en quantités. Elles peuvent être des machines, ouvriers, équipements, etc.Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/202115Dr. Nada KHERICI

2. EXEMPLES CLASSIQUES DE PROBLÈMES COMBINATOIRESSoitJ={1,..,n}un ensemble denjobs etM={1,..,m}un ensemble de machines.Chaque jobj?Jest composé au plus demopérations ordonnéesOj1,..,Ojm. Chaqueopération doit être effectuée sur une machinek?Mspécifique durant un temps spéci-fique. Chaque job doit passer par chaque machine une et une seule fois, et chaque machinepeut exécuter seulement un job (ou une opération) à la fois sans interruption.Unordreest une allocation des opérations aux intervalles de temps sur toutes les ma-chines. Un problème d"ordonnancement de tâches consiste à trouver un ordre réalisablequi minimiseCmaxle temps nécessaire pour compléter tous les jobs.Une représentation possible du problème d"ordonnancement de tâches est le diagrammede Gantt. On associe à chaque opération une barre horizontale avec une longueur pro-portionnelle au temps de l"opération (Figure2.5).MMM(a) Flow ShopMMM(b) Job ShopFigure 2.5- Représentation de Gantt d"un ordonnancement de 3 tâches sur 3 machines,cas du Flow shop et Job shop.2.3.2InstancesIl existe plusieurs instances pour le problème d"ordonnancement selon le nombres demachines et la nature des jobs. On trouve les ordonnancements sur une machine uniqueou sur des machines parallèles. Il existent aussi les ordonnancements linéaire ou multiples.-Machine Unique :L"ensemble des tâches à réaliser est fait par une seule machine.On cherche l"ordre des tâches sur cette machine.-Machines parallèles :L"ensemble des tâches à réaliser est fait par des machinesidentiques. Les tâches ne sont pas toutes exécutées sur les mêmes machines.-Ateliers à cheminement unique (Flow Shop) :C"est-à-dire, le processus defabrication est linéaire (Figure2.5a). Les jobs sont découpés en tâches qui doivents"exécuter sur toutes les machines.Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/202116Dr. Nada KHERICI

CHAPITRE 2. EXEMPLE DE PROBLÈMES D"OPTIMISATION COMBINATOIRE-Ateliers à cheminements multiples (Job Shop) :Le processus de fabrica-tion n"est pas linéaire (Figure2.5b). Les jobs sont découpés en tâches qui doivents"exécuter sur toutes les machines.2.4Problème du plus court cheminLe problème du plus court chemin entre deux sommets dans un graphe orienté et valuépar des coûts positifs est un problème de théorie de graphe. Il est résout efficacement parl"algorithme de Dijkstra (1959) (Figure2.6).(a) Graphe orienté et valué(b) Plus court cheminFigure 2.6- Le plus court chemin du graphe orienté et valué de la figure (A) coloré enbleu dans la figure (B)2.5Problème de l"Arbre couvrant de poids minimumUn arbre est un graphe connexe sans cycles. La recherche d"un arbre de poids minimumqui couvre tous les sommets d"un graphe G = (V,E) est un problème polynomial (Figure2.7).(a) Graphe orienté et valué(b) Arbre couvrant de poids minimalFigure 2.7- Représentation d"un Arbre couvrant dans un Graphe orienté et valuéOptimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/202117Dr. Nada KHERICI