Remerciez-le!

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

Plan du Rapport de recherche Présentation : 1) Problème de Transport : a) Défin

Plan du Rapport de recherche Présentation : 1) Problème de Transport : a) Définition b) Objectif c) Modélisation (formulation mathématique) d) Application d’un algorithme sur un cas de problème pratique e) Résolution du cas précédent par un logiciel 2) Problème d’affectation : a) Définition b) Objectif c) Modélisation (formulation mathématique) d) Application d’un algorithme sur un cas de problème pratique e) Résolution du cas précédent par un logiciel 3) Problème de Flot maximal et de Flot à coût minimal : a) Définition b) Objectif c) Modélisation (formulation mathématique) d) Application d’un algorithme sur un cas de problème pratique e) Résolution du cas précédent par un logiciel 4) Problème de Tournées de Véhicules a) Définition b) Objectif c) Modélisation (formulation mathématique) d) Application d’un algorithme sur un cas de problème pratique Présentation : Toute entreprise qu’elle que soit sa taille, son domaine d’activité est amené à faire face à des problèmes de gestion au quotidien. Parmi ces problèmes, on cite les problèmes de flot, d’affectation et de transport qui nécessitent la mise en œuvre d’un procédé de prise de décision rationnel, notamment la recherche opérationnelle, à cause de leur niveau de complexité particulièrement élevé et à cause des coûts supplémentaires qu’ils génèrent s’ils sont mal gérés. Ce qui souligne l’importance qu’occupe ce type de problème dans la gestion quotidienne de l’entreprise. C’est pour cette raison que le but de notre travail est de présenter des méthodes faciles de formulation et de résolution de ce genre de problème. Et pour cela, nous avons divisé notre travail en quatre parties, où nous allons aborder dans un premier temps le problème de transport, et ensuite nouas allons présenter le problème d’affectation, nous traitons aussi un problème de flot et plus précisément le problème de flot maximal ainsi que des algorithmes de résolution appropriés. Et enfin nous allons traiter les problèmes des tournées des véhicules. Durant notre recherche nous essaierons de résoudre quelque cas par l’utilisation des programmes informatiques. I- Problème de Transport a) Définition : Le problème de transport est une classe spéciale du problème de programmation linéaire. Il traite de la situation dans laquelle une marchandise est transportée à partir de sources aux destinations. b) Objectif : Est de déterminer la quantité de marchandise à être transportée de chaque source à chaque destination afin que le coût total du transport soit minimal. c) Modélisation (formulation mathématique) : Données :  un ensemble K d'usines,  un ensemble L de clients,  les offres ak des usines,  les demandes bl des clients,  les coûts de transports unitaires c(k,l) On suppose que: Hypothèse 1: où ak>0 et bl > 0. Le problème de transport peut être modélisé de la méthode suivante : Sous l’hypothèse (1), (T) est dit : « Le problème Standard de Transport » (PST) a) T Alors on crée un client fictif : b) Alors on crée un entrepôt fictif : d) Application d’un algorithme sur un cas de problème pratique : d-1) Enoncé du problème : La société GALAXY ELECTRONICS est spécialisée dans la vente d’articles électroménager, cette dernière doit livrer ses 4 clients, qui lui achètent respectivement 10, 8, 5 et 7 de produit. Il lui reste exactement 30 articles mais ils sont répartis sur 3 entrepôts : 6, dans le 1er, 9 dans le 2ème et 15 dans le 3ème .Les coûts de transport, en DH/A, entre chaque entrepôts Ri et chaque point de livraison Lj sont donnés dans le tableau suivant: Points de livraison Entrepôt L1 L2 L3 L4 R1 4 3 7 2 R2 3 4 5 2 R3 5 6 9 7 Quel est le nombre des articles envoyer des entrepôts vers chaque point de livraison en respectant l’offre et en satisfaisant la demande au moindre coût ? d-2) solution : On pourrait résoudre ce problème à l’aide de l’algorithme du simplexe, mais on va préférer un algorithme spécifique (le Stepping-Stone) qui tiendra compte des particularités du problème posé pour en simplifier la résolution. L’algorithme du Stepping-Stone sera un algorithme itératif (donc par étapes successives) visant à améliorer (donc faire baisser le coût global) une solution de base. Il nous faut donc une solution de départ pour démarrer l’algorithme. d-2-1) Obtention d’une solution de base par la méthode de Balas-Hammer : Cette méthode, appelée aussi méthode de la différence maximale, fera intervenir les coûts unitaires de transport et sera donc, en général, assez proche de l’optimum. Pour chaque rangée (ligne ou colonne) du tableau des coûts, on déterminera l’élément le plus petit et celui qui lui est immédiatement supérieur et on calculera leur différence (notée ∆) Points de livraison Entrepôt L1 L2 L3 L4 L’offre ∆ R1 4 3 7 2 6 1 R2 3 4 5 2 9 1 R3 5 6 9 7 15 1 Demande 10 8 5 7 ∆ 1 1 2 5 Dans la rangée correspondant à la différence maximale (ici la colonne L4) on remplira la case contenant le plus petit élément (ici la case R1L4 ou R2L4) avec le minimum de l’offre de la ligne et de la demande de la colonne. Puis on recommencera le processus autant de fois que nécessaire en supprimant à chaque fois l’origine dont l’offre est entièrement utilisée et/ou la destination dont la demande est complètement satisfaite. Points de livraison Entrepôt L1 L2 L3 L4 L’offre ∆ R1 4) 3) 7) 2) 6 1 R2 3) 4) 5) 2) 7 9 2 1 R3 5) 6) 9) 7) 15 1 Demande 10 8 5 7 0 ∆ 1 1 2 5 Points de livraison Entrepôt L1 L2 L3 L’offre ∆ R1 4) 3) 7) 6 1 R2 3) 4) 5) 2 2 0 1 R3 5) 6) 9) 15 1 Demande 10 8 5 3 ∆ 1 1 2 Points de livraison Entrepôt L1 L2 L3 L’offre ∆ R1 4) 3) 7) 3 6 3 1 R3 5) 6) 9) 15 1 Demande 10 8 3 0 ∆ 1 1 2 Points de livraison Entrepôt L1 L2 L’offre ∆ R1 4) 3) 3 3 1 R3 5) 10 6) 5 15 1 Demande 10 8 ∆ 1 1 Solution de base est : Nombre d’article L1 L2 L3 L4 R1 3 3 R2 2 7 R3 10 5 Z=(10*5)+(5*6)+(2*5)+(7*2)+(3*7)+(3*3) = 134 d-2-2) Déroulement de l’algorithme : On peut appliquer l’algorithme à n’importe laquelle des solutions de base. On va l’appliquer, par exemple, à la solution fournie par la méthode de Balas-Hammer. L’algorithme consiste à modifier la solution pour une qui soit meilleure, donc à rendre non vide une case vide du tableau des quantités On choisira la case qui permet la plus grande baisse du coût global de transport Pour la déterminer, on calculera : a) les potentiels associés aux origines et aux destinations b) les variations de coût unitaire pour chaque case vide (δ) c) les quantités maximales qu’on peut ajouter à chaque case vide (q) a) Comment déterminer les potentiels ? On utilisera le tableau des coûts limité aux cases où la quantité transitée est non nulle : coût L1 L2 L3 L4 R1 4 3 7 2 R2 3 4 5 2 R3 5 6 9 7 q L1 L2 L3 L4 R1 3 3 R2 2 7 R3 10 5 L1 L2 L3 L4 R1 3 7 R2 5 2 R3 5 6 On déterminera les potentiels de proche en proche : on commencera par une destination, puis une origine, puis une destination…..en soustrayant de R à L et en ajoutant de L à R. On fixera le premier potentiel arbitrairement et…suivre les flèches (on soustrait des destinations aux origines et on ajoute des origines aux destinations) (1) L1 L2 L3 L4 Pot R1 3 7 R2 5 2 R3 5 6 0 pot 5 (2) L1 L2 L3 L4 Pot R1 3 7 R2 5 2 R3 5 6 0 Pot 5 6 (1) L1 L2 L3 L4 Pot R1 3 7 3 R2 5 2 R3 5 6 0 pot 5 6 (4) L1 L2 L3 L4 Pot (5) L1 L2 L3 L4 Pot (6) L1 L2 L3 L4 Pot R1 3 7 3 R2 5 2 R3 5 6 0 pot 5 6 10 R1 3 7 3 R2 5 2 5 R3 5 6 0 Pot 5 6 10 R1 3 7 3 R2 5 2 5 R3 5 6 0 pot 5 6 10 7 b) Comment déterminer les δ ? Pour chaque case nulle, on calculera δ en ajoutant au coût unitaire de la case le potentiel de l’origine associée et en retranchant le potentiel de la destination correspondante : coûts L1 L2 L3 L4 Pot R1 4 2 3 R2 3 4 5 R3 9 7 0 pot 5 6 10 7 δ L1 L2 L3 L4 Pot R1 2 -2 3 R2 3 3 5 R3 -1 0 0 pot 5 6 10 7 c) Comment déterminer les q ? On déterminera les quantités qu’on peut ajouter aux cases vides uniquement pour celles dont le δ est négatif ; il uploads/Management/ sujets-de-recherche.pdf