# Solveur du problème de transport (flot de coût minimal)

Résout le problème de transport équilibré comme un flot de coût minimal (2–8 origines × 2–8 destinations ; l'égalité offre totale = demande totale est exigée) : chaque augmentation expédie par le plus court chemin du réseau résiduel (SPFA tolère les coûts négatifs des arcs résiduels) et les opposés des distances cumulées sont exactement les duaux MODI (u_i, v_j). Affiche chaque chemin augmentant, le plan d'expédition complet, les totaux par ligne/colonne et la matrice des coûts réduits avec le certificat d'optimalité (tous ≥ 0, = 0 sur les cellules de base). Classique : offres [30,40,30], demandes [20,30,30,20], coûts [[2,3,1,4],[4,2,5,3],[3,1,4,2]] → coût total minimal 200.

> Page canonique: https://elysiatools.com/fr/tools/transportation-problem

- **Catégorie:** Math & Numbers

- **Mots-clés:** problème de transport, flot de coût minimal, méthode modi, méthode uv, variables duales, recherche opérationnelle, logistique, plan d'expédition, offre demande

## Présentation

Le solveur de problème de transport calcule le plan d'expédition optimal à coût minimal pour un réseau équilibré de 2 à 8 origines et 2 à 8 destinations. En modélisant le problème sous forme de flot de coût minimal avec l'algorithme SPFA sur réseau résiduel, l'outil fournit les étapes d'augmentation de flot, les variables duales MODI (u_i, v_j), la matrice des coûts réduits et le certificat d'optimalité.

## Entrées

- **Matrice des coûts (lignes = origines, une par ligne)** (textarea): Unit shipping cost from each source (row) to each destination (column). 2–8 rows × 2–8 columns.
- **Offre (par origine)** (text): Amount available at each source, one per matrix row (non-negative).
- **Demande (par destination)** (text): Amount required at each destination, one per matrix column (non-negative).
- **Décimales** (number)

## Quand l'utiliser

- Lorsque vous devez allouer des stocks entre plusieurs entrepôts et points de vente au coût logistique total le plus bas.
- Pour valider des exercices de recherche opérationnelle nécessitant la méthode des potentiels MODI (u-v) et le contrôle d'optimalité par coûts réduits.
- Dès que l'offre totale de vos sources est exactement égale à la demande globale de vos destinations d'expédition.

## Fonctionnement

- Saisissez la matrice des coûts unitaires de transport (lignes = origines, colonnes = destinations), ainsi que les vecteurs d'offre et de demande séparés par des virgules.
- L'algorithme vérifie l'équilibre parfait entre l'offre et la demande totales, puis applique des augmentations de flot le long des chemins les plus courts du réseau résiduel.
- Le solveur calcule les potentiels duaux (u_i, v_j) associés aux distances résiduelles cumulées et génère la matrice des coûts réduits pour certifier l'absence de coûts négatifs.
- Consultez le plan de transport final détaillé, les flux acheminés par chaque route, le coût global minimal ainsi que les totaux de contrôle par ligne et colonne.

## Cas d'usage

- Optimisation de la distribution logistique entre usines de fabrication et centres de distribution régionaux.
- Résolution académique de problèmes de transport de recherche opérationnelle avec génération des variables duales u et v.
- Attribution de commandes d'approvisionnement entre plusieurs fournisseurs concurrents et plateformes de livraison.

## Questions fréquentes

### Que faire si mon problème n'est pas équilibré (offre différente de la demande) ?

Vous devez ajouter une source fictive (si la demande excède l'offre) ou une destination fictive (si l'offre excède la demande) avec un coût unitaire nul ou de pénalité pour équilibrer les totaux.

### Quelles dimensions de matrices de transport sont acceptées ?

L'outil accepte des configurations allant de 2 à 8 origines (lignes) et de 2 à 8 destinations (colonnes).

### Comment le solveur garantit-il l'optimalité de la solution ?

Il vérifie que tous les coûts réduits calculés via les variables duales MODI sont supérieurs ou égaux à zéro, et exactement nuls sur les cellules de base utilisées.

### Pourquoi l'algorithme SPFA est-il utilisé plutôt que Dijkstra ?

Le réseau résiduel contient des arcs inverses de coût négatif lors des réallocations de flot, ce que l'algorithme SPFA traite sans bloquer.

### Les valeurs d'offre, de demande et de coût peuvent-elles comporter des décimales ?

Oui, les valeurs décimales positives ou nulles sont acceptées et la précision d'affichage est configurable de 0 à 8 décimales.

## Outils associés

- [Solveur de programmation linéaire par simplexe (deux phases)](https://elysiatools.com/fr/tools/linear-programming-simplex): Résout les petits programmes linéaires (2–6 variables, 1–8 contraintes) par la méthode du simplexe en deux phases : max/min et contraintes ≤/≥/= (second membre négatif normalisé ; ≥/= passent par la phase 1 avec variables artificielles), règle de Bland contre le cyclage ; chaque itération affiche la variable entrante/sortante et l'objectif, avec la solution optimale x*, la valeur objectif et le statut (optimal/illimité/infaisable), vérifiés par substitution. Classiques : max 3x+5y s.t. x≤4, 2y≤12, 3x+2y≤18 → (2,6), z=36 ; min 2x+3y s.t. x+y≥4, x+3y≥6 → (3,1), z=9.
- [Calculateur de Vitesse Critique d'Arbre](https://elysiatools.com/fr/tools/shaft-critical-speed): Calcule la vitesse critique (de résonance) d'un arbre. ω_n = √(k/m), n_cr = (60/2π)·√(k/m) tr/min. Inclut la fréquence propre f_n (Hz).
- [Signataire de certificat PAdES PDF](https://elysiatools.com/fr/tools/pdf-pades-certificate-signer): Signe les PDF avec un certificat PKCS#12 et une signature CAdES détachée ETSI.
- [Recherche de racines primitives modulo n](https://elysiatools.com/fr/tools/primitive-root-finder): Recherche les racines primitives modulo n : vérifie que n ∈ {2, 4, p^k, 2p^k} (groupe multiplicatif cyclique), trouve la plus petite racine avec son certificat g^(φ/q) ≠ 1 pour chaque nombre premier q | φ(n), compte les racines comme φ(φ(n)), en liste jusqu'à 50 ou vérifie si l'ordre d'un candidat g vaut φ(n). Jusqu'à 10¹².
- [Vérificateur de résidu quadratique (symboles de Legendre/Jacobi)](https://elysiatools.com/fr/tools/quadratic-residue-checker): Calcule le symbole de Jacobi (a/n) (n impair jusqu'à 10¹⁸ ; Legendre si n est premier) : modulo un nombre premier, a^((n−1)/2) ≡ 1 signifie résidu quadratique et Tonelli–Shanks (ou la formule directe si p ≡ 3 (mod 4)) fournit les racines ±√a ; le symbole −1 certifie que a n'est PAS un résidu. Pour un module composé le symbole n'est que nécessaire : −1 prouve la non-résiduosité, +1 reste non concluant (résolu par force brute quand n ≤ 10⁵). Classique : 10 est un résidu quadratique mod 13 avec racines ±6.
- [Calculatrice Scientifique](https://elysiatools.com/fr/tools/scientific-calculator): Calculatrice scientifique avancée avec support des fonctions mathématiques complexes et expressions
- [Calculateur de Raideur de Ressort](https://elysiatools.com/fr/tools/spring-rate-calculator): Calcule la raideur d'un ressort hélicoïdal cylindrique. k = G·d⁴ / (8·D³·n) (N/mm). Inclut des valeurs prédéfinies de G pour les matériaux courants.
- [Calculateur de Module de Young](https://elysiatools.com/fr/tools/youngs-modulus-calculator): Module de Young en zone élastique linéaire E = σ/ε (loi de Hooke). Choisissez module, contrainte ou déformation : pour E donnez σ et ε ; pour σ donnez E et ε ; pour ε donnez E et σ. Chaque direction prend les deux autres valeurs positives et calcule la troisième ; résultat en MPa avec lecture en GPa.

## Exemples

- [Exemples de Traitement d'Images Android Java](https://elysiatools.com/fr/samples/android-image-processing-java): Exemples de traitement d'images Android Java incluant lecture/écriture, mise à l'échelle et conversion de format
- [Exemples de Traitement d'Images Android Kotlin](https://elysiatools.com/fr/samples/android-image-processing-kotlin): Exemples de traitement d'images Android Kotlin incluant lecture/écriture, mise à l'échelle et conversion de format
- [Exemples de Traitement d'Images Web Python](https://elysiatools.com/fr/samples/web-image-processing-python): Exemples de traitement d'images Web Python utilisant PIL/Pillow incluant la lecture, l'enregistrement, le redimensionnement et la conversion de format
- [Exemples de Traitement d'Images Web Rust](https://elysiatools.com/fr/samples/web-image-processing-rust): Exemples de traitement d'images Web Rust incluant lecture/écriture, redimensionnement et conversion de format