Transposer la matrice. Modèle mathématique du problème des transports. Matériel théorique sur le problème des transports

15.02.2019

L'un des plus courants et des plus populaires problèmes d'optimisation en logistique – problème de transport. DANS look classique il s'agit de trouver l'optimal ( ceux. associé à coûts minimes ) plan de transport de marchandises.

Par exemple, nous avons une chaîne de magasins de détail qui exige un certain montant marchandises. Il existe également un certain nombre d'entrepôts de fournisseurs où sont stockées les marchandises requises. De plus, chaque entrepôt dispose d’un stock différent de ces marchandises. De plus, nous connaissons les tarifs - les coûts de transport d'1 produit de chaque entrepôt à chaque magasin.

Il est nécessaire d'élaborer un plan de transport afin que les magasins reçoivent la quantité requise de marchandises avec au moindre coût pour le transport. C’est précisément dans de tels cas (et dans bien d’autres) que le problème des transports doit être résolu.

Matériel théorique sur le problème des transports

(Problème Monge-Kantorovitch) - problème de mathématiques programmation linéaire type spécialà propos de la recherche répartition optimale objets homogènes de la batterie aux récepteurs tout en minimisant les frais de déplacement.

Pour faciliter la compréhension, il est considéré comme un problème sur le plan optimal de transport des marchandises depuis les points de départ ( par exemple, les entrepôts) aux points de consommation ( par exemple, les magasins), avec des coûts de transport totaux minimes.

A la forme suivante :

Où: Z- les frais de transport des marchandises ;
X- le volume de chargement ;
C- coût (tarif) de transport d'une unité de marchandise ;
UN- stock fournisseur ;
B- demande du consommateur ;
m- nombre de fournisseurs ;
n- nombre de consommateurs.

Plan général pour résoudre un problème de transport par la méthode du potentiel

Le problème des transports peut être résolu diverses méthodes, en partant de la méthode simplexe et recherche simple, et en terminant par la méthode. L’une des méthodes les plus utilisées et les plus adaptées dans la plupart des cas est l’amélioration itérative du plan de transport.

Son essence est la suivante : nous trouvons un certain plan de référence et le vérifions pour optimalité (Z → min). Si le plan est optimal, une solution a été trouvée. Sinon, améliorez le plan autant de fois que nécessaire jusqu'à ce qu'il soit trouvé plan optimal.

Ci-dessous se trouve algorithme pour résoudre un problème de transport sous la forme la plus générale :

Construire une table de transport.
Vérification du problème pour la fermeture.
Compilation plan de référence.
Vérification du plan de prise en charge pour dégénérescence.
Calcul des potentiels pour le plan de transport.
Vérification de l'optimalité du plan de référence.
Redistribution des fournitures.
Si solution optimale trouvé, passez à l’étape 9, sinon, passez à l’étape 5.
Calcul des coûts totaux de transport de marchandises.
Construction d'un graphe de transport.

Instructions détaillées pour résoudre un problème de transport

1. Construire une table de transport

Nous construisons un tableau où nous indiquons les stocks de matériaux disponibles dans les entrepôts des fournisseurs ( Aï), et les besoins des usines ( Bj) dans ces matériaux.

Dans le coin inférieur droit des cellules du tableau, nous saisissons la valeur des tarifs pour le transport de marchandises ( Cij).

2. Vérification du problème pour la fermeture

Désignons le stock total de marchandises de tous les fournisseurs par le symbole UN, et la demande totale de fret pour tous les consommateurs est symbolisée B.

Tâche de transport appelé fermé, Si A = B. Si UNE≠B, alors le problème du transport s'appelle ouvrir. Au cas où problème clos Toutes les fournitures de fret seront retirées des fournisseurs et toutes les demandes des consommateurs seront satisfaites. Au cas où tâche ouverte Pour résoudre ce problème, vous devrez introduire des fournisseurs ou des consommateurs fictifs.

Vérifions la tâche pour la fermeture :

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, donc ce problème de transport est clos.

3. Etablir un plan de référence

Compose préliminaire ( justificatif) plan de transport. Il n’est pas nécessaire que ce soit optimal. Il ne s'agit que d'une sorte de « brouillon », de « croquis », en améliorant lequel nous arriverons progressivement au plan optimal.

Il y a différents méthodes pour trouver un plan de référence. Les plus courants sont les suivants :

a) Méthode de l'angle nord-ouest. Montrer

L'essence de la méthode est simple : les cellules de la table de transport sont remplies séquentiellement au maximum volumes possibles transport, dans le sens de haut en bas Et de gauche à droite. Autrement dit, la cellule en haut à gauche est remplie en premier ( cellule "nord-ouest"), puis le suivant à droite, etc. Alors va à nouvelle ligne et remplissez-le à nouveau de gauche à droite. Et ainsi de suite jusqu'à ce que la table soit complètement remplie.

Une description détaillée de la méthode et un exemple peuvent être trouvés.

b) Méthode des éléments minimaux. Montrer

La méthode est que pour remplir les cellules de la table de transport, sélectionnez une cellule avec minimal valeur tarifaire. Ensuite, la cellule suivante avec le tarif le plus bas est sélectionnée et ainsi de suite jusqu'à ce que le tableau soit rempli ( tous les stocks et besoins seront remis à zéro).

c) Rapprochement de Vogel. Montrer

La base de la méthode est de trouver différences(modulo) entre une paire de tarifs minimaux dans chaque ligne et colonne. Puis dans la ligne ou la colonne avec le plus grand la différence remplit la cellule le plus petit tarif. Ensuite, toutes ces actions sont répétées à nouveau, seulement dans ce cas les cellules remplies ne sont plus prises en compte.
Une description détaillée de l'approximation de Vogel et un exemple peuvent être trouvés

d) Méthode de double préférence. Montrer

L'essence de la méthode est que les cellules avec le tarif le plus bas sont marquées en lignes puis en colonnes. Ensuite, les cellules sont remplies dans l'ordre suivant : d'abord les cellules avec deux marques, puis avec un, enfin sans marques.
Une description détaillée de la méthode et un exemple peuvent être trouvés

4. Vérification du plan de prise en charge de la dégénérescence

Les cellules du tableau dans lesquelles sont enregistrés les transports différents de zéro sont appelées basique, et le reste (vide) - gratuit.

Le plan s'appelle dégénérer, si le nombre de cellules de base qu'il contient est inférieur à m + n -1. Si lors de la résolution du problème un plan dégénéré est obtenu, alors il doit être reconstitué en insérant un transport nul dans le nombre de cellules manquantes et en transformant ainsi ces cellules en cellules de base ( le solde global et le coût total de transport du plan ne changeront pas). Cependant, il est impossible de reconstituer le plan en choisissant des cellules au hasard. Le plan doit être acyclique !

Un plan est dit acyclique si ses cellules de base ne contiennent pas de cycles. Faire du vélo dans la table de transport il y a plusieurs cellules reliées par une polyligne fermée de sorte que deux sommets adjacents de la polyligne soient situés soit dans la même ligne, soit dans la même colonne. Ci-dessous se trouve exemple de boucle:

Une ligne brisée peut avoir des points d'auto-intersection, mais pas dans les cellules du cycle.

Nombre de cellules de base = 5

m + n – 1 = 3 + 3 – 1 = 5

Par conséquent, le plan de transport initial n’est pas dégénéré.

5. Calcul des potentiels pour le plan de transport

Pour analyser les plans résultants et leur amélioration ultérieure, il convient de saisir caractéristiques supplémentaires points d’origine et de destination, appelés potentiels.

Cette méthode d'amélioration du plan de transport s'appelle méthode potentielle . Il existe d’autres méthodes pour améliorer de manière itérative le plan de transport, mais nous ne les considérerons pas ici.

Comparons donc chaque fournisseur Ai et chaque consommateur Bj avec les valeurs Interface utilisateur Et Vj en conséquence, de sorte que pour toutes les cellules de base du plan, la relation suivante soit satisfaite :

Ui + Vj = Cij

Ajouter au tableau des transports ligne supplémentaire et une colonne pour Ui et Vj.

Supposons que U1 = 0.

On peut alors trouver V3 = C13 – U1 = 1 – 0 = 1.

Connaissant la V3, on peut désormais retrouver U3 :

Par analogie, on calcule tous les potentiels restants :

6. Vérification de l'optimalité du plan à l'aide de la méthode du potentiel

Pour chaque cellule libre du plan, on calcule les différences

ΔCij = Cij – (Ui + Vj)

et écrivez les valeurs résultantes dans les coins inférieurs gauches des cellules correspondantes.

Le plan est optimal, si toutes les différences ΔCij ≥ 0.

DANS dans ce cas plan - sous-optimal(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. Redistribution des fournitures

Trouvons la cellule avec le plus grand valeur absolue différence négative ΔCij et construire un cycle dans lequel, à l'exception de cette cellule, toutes les autres sont basiques. Un tel cycle existe toujours et est unique.

Marquons la cellule avec une différence négative ΔCij avec un signe « + », la suivante avec un signe « - », et ainsi de suite, une par une.

Ensuite, nous trouvons la valeur minimale de la charge dans les cellules du cycle avec le signe « - » (ici c'est 5) et la saisissons dans la cellule libre avec le signe « + ». Ensuite, nous parcourons séquentiellement toutes les cellules du cycle, en leur soustrayant et en leur ajoutant alternativement la valeur minimale (conformément aux signes avec lesquels ces cellules sont marquées : où moins est soustrait, où plus est ajouté).

Nous obtenons nouveau plan de référence transport:

Puisqu’il y a plus de cellules de base que m + n – 1, nous rendons libre la cellule de base de valeur nulle :

On calcule à nouveau les valeurs potentielles et la différence ΔCij :

Cette fois toutes les différences ΔCij des cellules sont positives, donc, solution optimale trouvée.

8. Si la solution optimale est trouvée, passez à l'étape 9, sinon passez à l'étape 5.

Nous avons trouvé la solution optimale, alors passons au point 9.

9. Calcul des coûts totaux de transport de marchandises

Calculons frais de port totaux cargaison ( Z), correspondant au plan optimal que nous avons trouvé, selon la formule :

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 deniers. unités

Le coût total de livraison de tous les produits, pour une solution optimale, est de 110 tanière. unités

10. Construction d'un graphe de transport

Après avoir trouvé le plan de transport optimal, nous le construirons. Les sommets du graphique seront « entrepôts » et « magasins ». Aux sommets nous indiquons les volumes correspondants de réserves et de besoins. Les arcs reliant les sommets du graphe correspondront à des transports non nuls. Nous signerons chacun de ces arcs, indiquant le volume de fret transporté.

Le résultat sera un graphique similaire à celui présenté ci-dessous :

Ça y est, le problème des transports est résolu. Félicitations!

Application pratique du problème des transports

Le problème du transport est utilisé dans de nombreux cas. Il s’agit de l’optimisation de l’approvisionnement en matières premières et fournitures pour entreprises manufacturières. Il s'agit de l'optimisation de la livraison des marchandises des entrepôts vers magasins de détail. C'est de l'optimisation transport de passagers, et bien plus encore.

Galyautdinov R.R.

Sous le nom de problème de transport, un large éventail de problèmes sont combinés avec un modèle mathématique unique. Ces problèmes appartiennent aux problèmes de programmation linéaire et peuvent être résolus à l’aide de la méthode bien connue du simplexe. Cependant, un problème typique de transport a grand nombre variables et sa résolution à l’aide de la méthode du simplexe est fastidieuse. D'autre part, la matrice du système de restrictions du problème des transports est tout à fait unique, donc pour le résoudre, méthodes spéciales. Ces méthodes, comme méthode simplexe, nous permettent de trouver la solution de support initiale, puis, en l'améliorant, d'obtenir la séquence solutions de support, qui se termine par une solution optimale.

Caractéristiques générales du problème des transports

Condition:
La cargaison homogène est concentrée chez m fournisseurs dans des volumes a 1, a 2, ... a m.
Cette cargaison doit être livrée à n consommateurs dans des volumes b 1, b 2 ... b n.
Connu C ij, je=1,2,...m; j=1,2,...n — le coût de transport des unités de fret de chaque i-ème fournisseur à chaque j-ème consommateur.
Il est nécessaire d'élaborer un plan de transport dans lequel les stocks de tous les fournisseurs sont intégralement transportés, les demandes de tous les consommateurs sont pleinement satisfaites et les coûts totaux de transport de toutes les marchandises sont minimes.

Les données initiales de la tâche de transport sont écrites sous forme de tableau :

Les données initiales de la tâche peuvent être présentées comme :

vecteur A=(a 1 ,a 2 ,...,a m) stocks des fournisseurs
vecteur B=(b 1 ,b 2 ,...,b n) demandes des consommateurs
matrices de coûts :

Modèle mathématique du problème des transports

Les variables (inconnues) du problème de transport sont x ij , i=1,2,...,m j=1,2,...,n - le volume de transport du i-ème fournisseur à chaque j-ème consommateur.
Ces variables peuvent être écrites sous forme de matrice de transport :

Puisque le produit C ij *X ij détermine les coûts de transport des marchandises du i-ème fournisseur au j-ème consommateur, les coûts totaux de transport de toutes les marchandises sont égaux à :

Selon les conditions du problème, il convient d'assurer un minimum de coûts totaux.
La fonction objectif du problème a donc la forme :

Le système de contraintes du problème se compose de deux groupes d’équations.
Le premier groupe de m équations décrit le fait que les stocks de tous les m fournisseurs sont intégralement exportés et a la forme :

Le deuxième groupe de n équations exprime l’exigence de satisfaire complètement les demandes de tous les n consommateurs et a la forme :

Compte tenu de la condition de non-négativité des volumes de trafic, le modèle mathématique ressemble à ceci :

Dans le modèle considéré du problème de transport, on suppose que les stocks totaux des fournisseurs sont égaux à la demande totale des consommateurs, c'est-à-dire :

Un tel problème est appelé problème avec le bon équilibre , et le modèle du problème fermé. Si cette égalité n’est pas satisfaite, alors le problème est appelé problème avec mauvais équilibre, et le modèle du problème est ouvrir.

Formulation mathématique du problème du transport est : trouver variables de tâche X=(x ij), i=1,2,...,m; j=1,2,...,n, satisfaisant le système de restrictions (numéro 2 sur le modèle mathématique), (3), les conditions de non-négativité (4) et assurant un minimum fonction objectif (1)

Exemple 34.1

Créer un modèle mathématique du problème de transport dont les données initiales sont données dans le tableau 34.2

Solution:
1. Nous introduisons des variables de tâche (matrice de transport) :

2. Nous notons la matrice des coûts :

3. La fonction objectif du problème est égale à la somme des produits de tous les éléments correspondants des matrices C et X.

Cette fonction, qui détermine les coûts totaux de tous les transports, doit atteindre une valeur minimale.

4. Créons un système de contraintes pour le problème.
La somme de toutes les expéditions de la première ligne de la matrice X doit être égale aux stocks du premier fournisseur, et la somme des transports de la deuxième ligne de la matrice X doit être égale aux stocks du deuxième fournisseur :

Cela signifie que les stocks des fournisseurs sont intégralement supprimés.

Les montants de transport dans chaque colonne de la matrice X doivent être égaux aux demandes des consommateurs correspondants :

Cela signifie que les besoins des consommateurs sont pleinement satisfaits.

Il faut également prendre en compte que le transport ne peut pas être négatif :

Répondre: Ainsi, le modèle mathématique du problème considéré s'écrit comme suit :
Trouvez les variables du problème qui fournissent un minimum de la fonction objectif (1) et satisfont le système de contraintes (2) et les conditions de non-négativité (3).

Instructions. Pour obtenir une solution au problème des transports en mode en ligne sélectionner la dimension de la matrice tarifaire (nombre de fournisseurs et nombre de magasins).

Les éléments suivants sont également utilisés avec cette calculatrice :
Méthode graphique pour résoudre ZLP
Méthode simplexe pour résoudre ZLP
Résoudre un jeu matriciel
Grâce au service en ligne, vous pouvez déterminer le prix d'un jeu matriciel (limites inférieure et supérieure), vérifier la disponibilité point de selle, trouver une solution à une stratégie mixte en utilisant les méthodes suivantes : minimax, méthode du simplexe, méthode graphique (géométrique), méthode de Brown.

Extremum d'une fonction de deux variables
Problèmes de programmation dynamique

La première étape pour résoudre le problème des transports est de déterminer son type (ouvert ou fermé, ou sinon équilibré ou déséquilibré). Méthodes approximatives ( méthodes pour trouver un plan de référence) permettre deuxième étape de solution en un petit nombre d'étapes, obtenir une solution acceptable, mais pas toujours optimale, au problème. Ce groupe de méthodes comprend les méthodes suivantes :

suppression (méthode de double préférence) ;
coin nord-ouest ;
élément minimum ;
approximations de Vogel.

Solution de référence au problème du transport

La solution de référence au problème du transport est toute solution réalisable pour laquelle les vecteurs de condition correspondant aux coordonnées positives sont linéairement indépendants. Pour vérifier indépendance linéaire vecteurs de conditions correspondant aux coordonnées d'une solution admissible, des cycles sont utilisés.
Faire du vélo Une séquence de cellules dans une table de tâches de transport est appelée dans laquelle deux et seules cellules adjacentes sont situées dans la même ligne ou colonne, et la première et la dernière sont également dans la même ligne ou colonne. Un système de vecteurs de conditions de problème de transport est linéairement indépendant si et seulement si aucun cycle ne peut être formé à partir des cellules correspondantes du tableau. Par conséquent, une solution admissible au problème de transport, i=1,2,...,m; j=1,2,...,n n'est une référence que si aucun cycle ne peut être formé à partir des cellules du tableau qu'il occupe.

Méthodes approximatives pour résoudre le problème du transport.
Méthode de croisement (méthode de double préférence). S'il y a une cellule occupée dans une ligne ou une colonne d'un tableau, elle ne peut être incluse dans aucun cycle, puisqu'un cycle a deux et seulement deux cellules dans chaque colonne. Par conséquent, vous pouvez rayer toutes les lignes du tableau qui contiennent une cellule occupée, puis rayer toutes les colonnes qui contiennent une cellule occupée, puis revenir aux lignes et continuer à rayer les lignes et les colonnes. Si, à la suite de la suppression, toutes les lignes et colonnes sont barrées, cela signifie qu'à partir des cellules occupées du tableau, il est impossible de sélectionner une partie qui forme un cycle et que le système de vecteurs de conditions correspondants est linéairement indépendant, et la solution est une solution de référence. Si, après suppression, certaines cellules restent, alors ces cellules forment un cycle, le système de vecteurs de conditions correspondants est linéairement dépendant et la solution n'est pas une solution de référence.
Méthode de l'angle nord-ouest consiste à parcourir séquentiellement les lignes et les colonnes de la table de transport, en commençant par la colonne de gauche et ligne supérieure, et en inscrivant le maximum d'expéditions possibles dans les cellules appropriées du tableau afin que les capacités du fournisseur ou les besoins du consommateur indiqués dans la tâche ne soient pas dépassés. Dans cette méthode, aucune attention n'est accordée aux prix de livraison, car on suppose une optimisation supplémentaire des expéditions.
Méthode des éléments minimaux. Doté d'une simplicité cette méthode encore plus efficace que, par exemple, la méthode Northwest Angle. De plus, la méthode des éléments minimaux est claire et logique. Son essence est que dans le tableau de transport, les cellules avec les tarifs les plus bas sont remplies en premier, puis les cellules avec les tarifs les plus élevés. Autrement dit, nous choisissons le transport avec le coût minimum de livraison du fret. C’est une décision évidente et logique. Certes, cela ne conduit pas toujours au plan optimal.
Méthode d'approximation de Vogel. Avec la méthode d'approximation de Vogel, à chaque itération, la différence entre les deux tarifs minimaux qui y sont inscrits se retrouve pour toutes les colonnes et toutes les lignes. Ces différences sont enregistrées dans une ligne et une colonne spécialement désignées dans le tableau des conditions problématiques. Parmi les différences indiquées, le minimum est choisi. Dans la ligne (ou colonne) à laquelle correspond cette différence, le tarif minimum est déterminé. La cellule dans laquelle il est écrit est renseignée à cette itération.

Exemple n°1. Matrice tarifaire (ici le nombre de fournisseurs est de 4, le nombre de magasins est de 6) :

	1	2	3	4	5	6	Réserves
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	100	60
Besoins	10	30	40	50	70	30

Solution. Étape préliminaire résoudre un problème de transport revient à déterminer son type, s'il est ouvert ou fermé. Vérifions la condition nécessaire et suffisante pour la résolution du problème.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
La condition d’équilibre est remplie. Répond à des besoins égaux. Le modèle du problème de transport est donc fermé. Si le modèle était ouvert, il serait nécessaire d'introduire des fournisseurs ou des consommateurs supplémentaires.
Sur deuxième étape Le plan de référence est recherché selon les méthodes indiquées ci-dessus (la plus courante est la méthode du moindre coût).
Pour démontrer l’algorithme, nous présentons seulement quelques itérations.
Itération n°1. Élément de matrice minimum égal à zéro. Pour cet élément, les stocks sont de 60 et les besoins sont de 30. Nous en sélectionnons le nombre minimum 30 et le soustrayons (voir tableau). Parallèlement, on raye la sixième colonne du tableau (ses besoins sont égaux à 0).

3	20	8	13	4	x	80
4	4	18	14	3	0	60 - 30 = 30
10	4	18	8	6	x	30
7	19	17	0	1	x	60
10	30	40	50	70	30 - 30 = 0	0

Itération n°2. Encore une fois, nous recherchons le minimum (0). Dans la paire (60 ; 50), nous sélectionnons le nombre minimum 50. Rayons la cinquième colonne.

3	20	8	x	4	x	80
4	4	18	x	3	0	30
10	4	18	x	6	x	30
7	19	17	0	1	x	60 - 50 = 10
10	30	40	50 - 50 = 0	70	0	0

Itération n°3. Nous continuons le processus jusqu'à ce que nous ayons sélectionné tous les besoins et fournitures.
Itération n° N. L'élément que vous recherchez est 8. Pour cet élément, les ressources sont égales aux besoins (40).

3	x	8	x	4	x	40 - 40 = 0
x	x	x	x	3	0	0
x	4	x	x	x	x	0
x	x	x	0	1	x	0
0	0	40 - 40 = 0	0	0	0	0

	1	2	3	4	5	6	Réserves
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
Besoins	10	30	40	50	70	30

Comptons le nombre de cellules occupées du tableau, il y en a 8, mais cela devrait être m + n - 1 = 9. Le plan de support est donc dégénéré. Nous construisons nouveau plan. Il faut parfois construire plusieurs plans de référence avant d’en trouver un non dégénéré.

	1	2	3	4	5	6	Réserves
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
Besoins	10	30	40	50	70	30

On obtient ainsi le premier plan de support, qui est valable, puisque le nombre de cellules occupées du tableau est 9 et correspond à la formule m + n - 1 = 6 + 4 - 1 = 9, soit le plan de référence est non dégénéré.
Troisième étape consiste à améliorer le plan de référence trouvé. Ici, ils utilisent la méthode du potentiel ou la méthode de distribution. A ce stade, l'exactitude de la solution peut être contrôlée via la fonction de coût F(x) . S'il diminue (sous réserve de minimiser les coûts), alors la solution est correcte.

Exemple n°2. En utilisant la méthode du tarif minimum, présentez un premier plan pour résoudre un problème de transport. Vérifiez l'optimalité en utilisant la méthode du potentiel.

	30	50	70	10	30	10
40	2	4	6	1	1	2
80	3	4	5	9	9	6
60	4	3	2	7	8	7
20	5	1	3	5	7	9

Exemple n°3. Quatre usines de confiserie peuvent produire trois types de produits de confiserie. Coûts de production d'un quintal (quintal) de produits de confiserie par chaque usine, capacité de production les usines (centaines par mois) et les besoins quotidiens en produits de confiserie (centaines par mois) sont indiqués dans le tableau. Élaborer un plan de production de confiserie qui minimise les coûts totaux de production.

Note. Ici, on peut d'abord transposer le tableau des coûts, puisque pour la formulation classique du problème du transport, les capacités (de production) viennent en premier, puis les consommateurs.

Exemple n°4. Pour la construction des installations, les briques sont fournies par trois usines (I, II, III). Les usines disposent respectivement de 50, 100 et 50 000 unités dans les entrepôts. briques Les objets nécessitent respectivement 50, 70, 40 et 40 000 pièces. briques Les tarifs (den. unités/milliers d'unités) sont indiqués dans le tableau. Créez un plan de transport qui minimise les coûts totaux de transport.

sera fermé si :
A) a=40, b=45
B) a=45, b=40
B) a=11, b=12
Condition du problème de transport fermé : ∑a = ∑b
Nous trouvons : ∑a = 35+20+b = 55+b ; ∑b = 60+une
On obtient : 55+b = 60+a
L'égalité ne sera observée que lorsque a=40, b=45