Calculateur du Problème de Transport (Coin Nord-Ouest, Coût Minimum et MODI)
Calculez la Solution de Base Réalisable Initiale par le Coin Nord-Ouest ou le Coût Minimum, et optimisez vos coûts d'acheminement avec la méthode MODI.
| D1 | D2 | D3 | Offre (Disponibilités) | |
|---|---|---|---|---|
| S1 | ||||
| S2 | ||||
| S3 | ||||
| Demande (Besoins) |
Le Problème de Transport : Coin Nord-Ouest, Moindre Coût et Méthode MODI
Guide académique complet pour modéliser des réseaux d'expédition, construire une solution de base réalisable et optimiser avec l'algorithme MODI (u-v).
1. Quel problème résout le Modèle de Transport ?
Le Problème de Transport est une déclinaison de la Programmation Linéaire servant à concevoir le plan d'acheminement le plus économique entre m points d'origine (usines, entrepôts) aux capacités finies, et n points de destination (magasins, centres de consommation) aux demandes fixées. Lorsque l'offre totale égale la demande totale (∑ sᵢ = ∑ dⱼ), le modèle est équilibré. L'objectif est de minimiser Z = ∑∑ cᵢⱼ xᵢⱼ sous contraintes de bilan.
2. Méthodologie : De la Solution Initiale à l'Optimum
Affectation géométrique débutant en cellule (1, 1). On affecte min(s₁, d₁), on sature une ligne ou colonne, puis on progresse vers la droite ou le bas. Ne tenant aucun compte des coûts unitaires, elle donne un point de départ rapide mais rarement économique.
Algorithme glouton priorisant la case libre présentant le coût unitaire cᵢⱼ le plus faible. En maximisant les flux sur les liaisons les plus avantageuses, elle aboutit fréquemment à un coût très proche de l'optimum global.
Équivalent dual du Simplexe pour les réseaux. En posant uᵢ + vⱼ = cᵢⱼ sur les cases de base, on déduit les potentiels duaux uᵢ et vⱼ. On calcule ensuite les coûts réduits Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) des cases vides. Si tous les Δᵢⱼ ≥ 0, la solution est optimale. Sinon, un cycle fermé (stepping-stone) permet de réajuster les flux.
3. Exemple Académique Résolu : 3 Origines × 3 Destinations
Comparez les méthodes initiales et validez l'optimum numérique calculé par notre moteur.
| Origin / Destination | Destination 1 (D₁) | Destination 2 (D₂) | Destination 3 (D₃) | Supply Capacity |
|---|---|---|---|---|
| Origine 1 (S₁) | 8 € | 4 € | 12 € | 100 |
| Origine 2 (S₂) | 10 € | 5 € | 6 € | 300 |
| Origine 3 (S₃) | 7 € | 8 € | 15 € | 300 |
| Demand Requirement | 300 | 200 | 200 | 700 |
A. Déroulement par le Coin Nord-Ouest
Cellule (S₁, D₁) : affecter min(100, 300) = 100. S₁ est épuisée. Cellule (S₂, D₁) : affecter min(300, 200) = 200. D₁ est saturée. Cellule (S₂, D₂) : affecter min(100, 200) = 100. S₂ est épuisée. Cellule (S₃, D₂) : affecter min(300, 100) = 100. D₂ est saturée. Cellule (S₃, D₃) : affecter les 200 unités restantes.
B. Déroulement par le Moindre Coût
1. Coût minimal global en case (S₁, D₂) à 4 € : allouer min(100, 200) = 100. S₁ est épuisée. 2. Prochain coût minimal en (S₂, D₂) à 5 € : allouer min(300, 100 restants) = 100. D₂ est saturée. 3. Case (S₂, D₃) à 6 € : allouer min(200 restants, 200) = 200. S₂ et D₃ sont saturées. 4. Case (S₃, D₁) à 7 € : allouer min(300, 300) = 300. S₃ et D₁ sont saturées.
C. Vérification d'Optimalité MODI
Sur les cases de base (S₁, D₂), (S₂, D₂), (S₂, D₃) et (S₃, D₁), le calcul des potentiels uᵢ et vⱼ indique que tous les coûts réduits Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) sont supérieurs ou égaux à zéro (Δᵢⱼ ≥ 0). Aucune opportunité négative n'existant, l'affectation du Moindre Coût constitue l'optimum global exact.
Analyse d'Efficacité : Économie de 2 900 €
Le choix de la règle du Moindre Coût par rapport au Coin Nord-Ouest fait chuter le coût de 7 100 € à 4 200 €, soit une économie immédiate de 2 900 € (réduction de 40,8 %) avant même la moindre boucle d'itération.
4. Pièges et Erreurs Classiques d'Examen
Oublier d'Équilibrer l'Offre et la Demande
Si l'offre excède la demande, ajoutez une destination fictive de coût unitaire nul. Si la demande excède l'offre, ajoutez une source fictive.
Dégénérescence de la Base (Moins de m + n - 1 Cases)
Une base requiert exactement m + n - 1 variables allouées (ici 3 + 3 - 1 = 5). En cas de saturation simultanée, affectez une quantité infinitésimale ε à une case indépendante pour pouvoir calculer u et v.
Boucles Stepping-Stone Invalides
Le circuit fermé d'amélioration ne peut effectuer ses changements de direction (virages à 90°) que sur des cases basiques occupées.