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.

3
3
D1D2D3Offre (Disponibilités)
S1
S2
S3
Demande (Besoins)
Optimisation des Flux et Réseaux Logistiques

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

Solution de Base Réalisable Initiale (SBRI)
Méthode du Coin Nord-Ouest (NWC)

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.

Solution de Base Réalisable Initiale (SBRI)
Méthode du Moindre Coût (Coût Minimum)

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.

Algorithme Exact d'Optimalité
Méthode MODI (Distribution Modifiée / Potentiels u-v)

É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.

Supply: Origines S₁, S₂, S₃ avec capacités de 100, 300 et 300 unités.
Demand: Destinations D₁, D₂, D₃ avec besoins de 300, 200 et 200 unités.
Offre totale = 700 unités | Demande totale = 700 unités (Système Équilibré).
Origin / DestinationDestination 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 Requirement300200200700

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.

Coût Total Coin Nord-Ouest = (100 × 8) + (200 × 10) + (100 × 5) + (100 × 8) + (200 × 15) = 800 + 2 000 + 500 + 800 + 3 000 = 7 100 €.

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.

Coût Total Moindre Coût = (100 × 4) + (100 × 5) + (200 × 6) + (300 × 7) = 400 + 500 + 1 200 + 2 100 = 4 200 €.

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.

Coût Minimal Optimal Global = 4 200 € (Conforme au solveur en ligne).

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.