LAKHAL Radouane VAZQUEZ Emmanuel	E3-2006/07 Recherche Opérationnelle

Plan

1. Description du problème.
2. Formalisation du problème.
3. L'examen d'une méthode de résolution.
4. La résolution d'un sous problème .
5. Cahier des charges pour un futur projet.
6. Bibliographie.

I. Description du problème

L'entreprise XXX située aux États-Unis est spécialiste de la fabrication des écrous, boulons et fixations de toutes catégories. Cette entreprise dispose de nombreux entrepôts aux États Unis et au Mexique.

Parmi ces principaux clients, on trouve l'entreprise ZZZ situé au Mexique et qui représente 15 % du marché. Cette dernière commande ses produits dans cinq des entrepôts du groupe.

La société XXX transmet à un prestataire YYY la charge de transport pour collecter les produits de la commande de l'entreprise ZZZ auprès des 5 entrepôts concernés. Apres que XXX reçoit la commande de ses clients , le responsable du materials planner vérifie via le logiciel AS400, la disponibilité des différentes pièces commandées dans les différentes entrepôts afin de pouvoir fixer les produits à collecter pour chaque camion.

Le problème consiste à minimiser le coût de transport avec la détermination du nombre et du type de camions à envoyer à chaque entrepôt pour collecter la totalité de la commande de l'entreprise ZZZ.

(cliquer pour agrandir)

II. Formalisation du problème

Les produits demandés par le client ZZZ existent dans 5 entrepôts. Soient i =1..5

Le logiciel AS400 donne la quantité de produits à collecter de chaque entrepôt. Soient :

Le prestataire YYY dispose de quatre types de camion à savoir :

Camion type A de capacité C1 (C1=2)
Camion type B de capacité C2 (C2=4)
Camion type C de capacité C3 (C3=6)
Camion type D de capacité C4 (C4=8)

Le système nous permet de trouver les valeurs de Ai, Bi, Ci et Di avec i=1..5 dans l'objectif de minimiser le coût de transport.

Une formulation de ce problème est possible par la programmation linéaire.

1)La fonction objective

Minimiser le coût de transport ;

2)Les contraintes

La capacité du camion / des camions envoyé(s) à chaque entrepôt est supérieure à la quantité à en collecter ;

2 A1 + 4 B1 + 6 C1 + 8 D1 >= 9
2 A2 + 4 B2 + 6 C2 + 8 D2 >= 7
2 A3 + 4 B3 + 6 C3 + 8 D3 >= 1
2 A4 + 4 B4 + 6 C4 + 8 D4 >= 5
2 A5 + 4 B5 + 6 C5 + 8 D5 >= 4

2 A1: envoyer un camion de type A de capacité 2 à l'entrepôt 1.

A1 + B1 + C1 + D1 ≥>= 0
A2 + B2 + C2 + D2 >= 0
A3 + B3 + C3 + D3 >= 0
A4 + B4 + C4 + D4 >= 0
A5 + B5 + C5 + D5 >= 0

3)Variables

INT A1
INT A2
INT A3
INT A4
INT A5
INT B1
INT B2
INT B3
INT B4
INT B5
INT C1
INT C2
INT C3
INT C4
INT C5
INT D1
INT D2
INT D3
INT D4
INT D5

III. L'examen d'une méthode de résolution

Programmation Linéaire

L'objectif de la programmation linéaire est de trouver la valeur optimale d'une fonction linéaire sous un système d'équations d'inégalités de contraintes linéaires. La fonction à optimiser est baptisée "fonction économique" (utilisée en économie dans le cadre d'optimisations) et on la résout en utilisant une méthode dite "méthode simplexe".

La recherche opérationnelle à pour domaine l'étude de l'optimisation de processus quels qu'ils soient. Il existe de nombreux algorithmes s'inspirant des problèmes du type exposés lors de notre étude de la programmation linéaire. Nous nous attarderons en particulier sur l'algorithme plus utilisé qui est "l'algorithme du simplexe".

Deux cas de résolution se présentent selon la disponibilité des types d'article dans les différents entrepôts:

• Si les types de produits diffèrent d'un entrepôt a un autre il serai nécessaire d'envoyer au minimum à chaque entrepôt ainsi le équations des contraintes deviennent :

2 A1 + 4 B1 + 6 C1 + 8 D1 >= 9
2 A2 + 4 B2 + 6 C2 + 8 D2 >= 7
2 A3 + 4 B3 + 6 C3 + 8 D3 >= 1
2 A4 + 4 B4 + 6 C4 + 8 D4 >= 5
2 A5 + 4 B5 + 6 C5 + 8 D5 >= 4
A1 + B1 + C1 + D1 >= 1
A2 + B2 + C2 + D2 >= 1
A3 + B3 + C3 + D3 >= 1
A4 + B4 + C4 + D4 >= 1
A5 + B5 + C5 + D5 >= 1

• Si les différents types de produits existent dans les différents entrepôts il serai possible qu'il y aie un / des entrepôt(s) auquel(s) il ne serai pas nécessaire d'envoyer des camions, ainsi les équations seront :

2 A1 + 4 B1 + 6 C1 + 8 D1 >= 18
2 A2 + 4 B2 + 6 C2 + 8 D2 >= 7
2 A3 + 4 B3 + 6 C3 + 8 D3 >= 4
2 A4 + 4 B4 + 6 C4 + 8 D4 >= 9
2 A5 + 4 B5 + 6 C5 + 8 D5 >= 5
A1 + B1 + C1 + D1 >= 0
A2 + B2 + C2 + D2 >= 0
A3 + B3 + C3 + D3 >= 0
A4 + B4 + C4 + D4 >= 0
A5 + B5 + C5 + D5 >= 0

IV. La résolution d'un sous problème de petite taille (illustration de l'utilisation effective d'un logiciel spécialisé).

Résolution du problème de l'entreprise ZZZ (les 5 entrepôts)

Pour simplifier la résolution du problème, on se limitera dans un premier temps à 5 entrepôts.

Avec les contraintes que nous avons déjà défini, nous allons résoudre ce problème avec des données aléatoires en utilisant LINDO.

LINDO est un logiciel d'optimisation des modèles de programmation linéaire.

En utilisant le progiciel Lindo, la solution optimale obtenue est la suivante:

A2
A3
A4
B1
B4
B5
C1
C2
L'optimum c'est d'envoyer 3 types de camion :
3 A pour les entrepôts 2,3 et 4
3 B pour les entrepôts 1,4 et 5
2C pour les entrepôts 1 et 2.

Nous allons remplacer les données aléatoires avec nos données réelles :

Avec :
A : c'est un camion de capacité de 38 palettes équivalent de 525433 pièces.
B : c'est un camion de capacité de 33 palettes équivalent de 456297 pièces.
C : c'est un camion de capacité de 27 palettes équivalent de 373334 pièces.
D : c'est un camion de capacité de 20 palettes équivalent de 276544 pièces.
1: l'entrepôt de UT
2: c'est l'entrepôt de IA
3: c'est l'entrepôt de NC
4: c'est l'entrepôt de MI
5: c'est l'entrepôt de TX

La fonction objective :

Les contraintes:

525433 A1 + 456297 B1 + 373334 C1 + 276544 D1 >= 350000
525433 A2 + 456297 B2 + 373334 C2 + 276544 D2 >= 340000
525433 A3 + 456297 B3 + 373334 C3 + 276544 D3 >= 390000
525433 A4 + 456297 B4 + 373334 C4 + 276544 D4 >= 0
525433 A5 + 456297 B5 + 373334 C5 + 276544 D5 >= 0
A1 + B1 + C1 + D1 >= 0
A2 + B2 + C2 + D2 >= 0
A3 + B3 + C3 + D3 >= 0
A4 + B4 + C4 + D4 >= 0
A5 + B5 + C5 + D5 >= 0

les Variables:

INT A1
INT A2
INT A3
INT A4
INT A5
INT B1
INT B2
INT B3
INT B4
INT B5
INT C1
INT C2
INT C3
INT C4
INT C5
INT D1
INT D2
INT D3
INT D4
INT D5

Résultats

• le coût de transport minimal obtenue est:4000$
• Le coût de transport est minimal lorsque on envoie :
  • Un camion de capacité de 33 palettes à l'entrepôt de NC
  • 2 camions de capacité de 27 palettes, 1 vers l'entrepôt UT et l'autre vers l'entrepôt IA

V. Cahier des charges pour un futur projet

1) Contexte du travail :

Afin de satisfaire sa clientèle en terme de délais et coûts de livraison, l'entreprise XXX transmet la charge de transport à un prestataire YYY et le guide en lui précisant le nombre et le type de camions à envoyer et le circuit minimal à parcourir pour la collecte de la globalité de la commande hebdomadaire dans l'ensemble des entrepôts dont elle dispose dans le territoire américain.

L'entreprise XXX envoie régulièrement, chaque mercredi de chaque semaine, un camion à chaque entrepôt pour la collecte des produits. Actuellement, l'entreprise XXX n'étudie ni la capacité nécessaire et suffisante de camions à envoyer à chaque entrepôt ni la possibilité à disperser les différents types de produits dans les différents entrepôts pour minimiser le nombre de camions à envoyer et la distance à parcourir.

2) Objectif du travail

3) Cadre du travail

4) Démarche du travail

• la possibilité de disperser les différents types de produits dans les différents entrepôts afin de garder une diversité importante en chaque.
• la possibilité de changer la fréquence d'envoi des camions aux divers entrepôts selon la fréquence des commandes afin de diminuer les délais de livraisons clients.
• la méthode du "voyageur de commerce" pour retrouver le plus court chemin à parcourir par un nombre variable de camions.
• la possibilité de retrouver le meilleur compromis Nombre et Capacité nécessaires et suffisants des camions à envoyer.

5) Les paramètres influançant sur le coût de transport

• la disponibilité des produits dans les entrepôts.
• les coûts de transport entre deux entrepôts et entre chaque entrepôt et la plateforme.
• Le nombre et la capacité des divers camions dont dispose le prestataire.
• Le temps nécessaire pour aller d'un entrepôt à un autre.
• Les moyens de stockage dans chaque entrepôt.