Problématique de transport

SOMMAIRE
INTRODUCTION 1. PROBLEME DE TRANSPORT 1.1 PRESENTATION 1.2 CAS PRATIQUE A.LA REGLE DU COIN NORD-OUEST B.METHODE DES APPROXIMATIONS DE VOGEL (M.A.V.)

2. PROBLEME D’AFFECTATION 2.1 Formulation 2.2 Méthode Hungarienne (König)

3. PROBLEME DE FLOTS 3.1Définition de flot 3.2 Exemple de flot complet 3.3 Algorithme de FORD FULKERSON 3.4 PROBLEME DU FLOT DE COUT MINIMAL: ALGORITHME DEBUSACKER ET GOWEN EXEMPLE (ALGORITHME DE BUSACKER ET GOWEN) CONCLUSION

1

INTRODUCTION
La recherche opérationnelle est une méthode d’analyse scientifique d’un problème. Cette méthodologie est une mélange d’analyse et de méthodes mathématique réunies pour aider un décideur à prendre une décision. Crée en Angleterre durant la seconde guerre mondiale, elle servait à résoudre les problèmesmilitaires (placements de radar, gestion des convois, etc.). Elle consiste à recevoir un maximum d’information sur le problème afin de proposer des solutions mais surtout pas de décider laquelle est la meilleure. La solution choisie dépend surtout des intérêts du décideur.

Domaines d’application
La recherche opérationnelle a maintenant de nombreux domaines d’application dont:

Les problèmescombinatoires
Essentiellement lorsque l’on a trop de combinaisons pour les traiter cas par cas. Par exemple 20! Pour un ordinateur qui traite 1M/sec, cela mettrai 77 096 ans!!! C’est le premier domaine application avec l’utilisation des graphes et de la programmation linéaire.

Les problèmes aléatoires
Notamment la gestion de files d’attente. Par exemple: un guichet supporte une arrivée de personnetoutes les 4 minutes en moyenne et la sert en 3 minutes. On pourrait croire qu’un seul employé suffit mais un modèle mathématique pourra démontrer qu’il faut en fait 2 employés (pour gérer les heures de pointes).

Les problèmes de concurrence
Notamment tout ce qui concerne la théorie des jeux.

2

1. PROBLEME DE TRANSPORT 1.1 PRESENTATION
Dans le cadre de la supply chain, le transportreprésente l’activité responsable du déplacement des marchandises et des matières. Le déplacement des matières premières, des composants et des produits finis entre le fournisseur, le fabricant, le centre de distribution et le client, constitue une part importante du coût final du produit. La visibilité de ces marchandises lors du transit est un gage de qualité de service pour le client. Les activitésliées à l’industrie du transport sont très variées et vont de l’envoi en express d’une simple lettre jusqu’au transport d’un chargement de bois en grume entre la scierie et le chantier. Le secteur du transport doit faire face à des besoins très variés. Le paramétrage de multiples scénarios de transport permet de répondre à ces besoins. L’ampleur des types d’expédition est très variable. Le poids,la distance et le délai de livraison sont quelques uns des facteurs permettant de déterminer le type d’expédition le plus approprié. Le P.T est un problème classique de la R.O La solution du P.T est celle qui permet de transporter les flux du point de départ au point d’arrivée. La solution doit également être la plus économique.

Énoncé général du problème de transport

Problème deProgrammation linéaire doté d’une structure particulière.

3

où

ai ? bj ? cij ? xij ?

la quantité de biens à acheminer de la source i aux n destinations, la quantité de biens nécessaire pour satisfaire à la demande à la destination j, coût unitaire de transport entre une source i et une destination j, la qté transportée de l’origine i à la destination j.

4

A

5

Moyennant la conditionA précédente, le problème de transport possède toujours une solution optimale (finie).

xij = ai bj

? ai

est un exemple.

i

6

1.2 Cas pratique : transport de fuel-oïl

Un revendeur de fuel-oïl domestique doit livrer 4 clients, qui lui achètent respectivement 10, 8, 5 et 7 m3 de produit. Il lui reste exactement 30 m3 de fuel-oïl domestique, mais ils sont répartis sur 3…