Algorithme de Transport:

1 Enoncé du problème

Un certain bien B est disponible dans m dépôts D1, D2, .. Dm en quantités respectives Qd1, Qd2, .., Qdm. Par ailleurs n clients: C1, C2,..,Cn réclament des quantités de ce même bien dans des quantités respectives qc1, Qc2,..,Qcn.

Tout dépôt peut livrer tout client, mais les coûts unitaires de livraison sont variables: on note c(i, j) le coût de livraison unitaire du client Cj par le dépôt Di.

L'objectif est de livrer tout le monde en minimisant le coût total.

Hypothèse de travail: On suppose que Qd1+Qd2+….+Qdm = Qc1+Qc2+….Qcn (cette hypothèse pourra être assouplie).

1.1 Un exemple

Exemple: Donnons la matrice des coûts:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10
D2	2		1		2		2		3		1
Q=21
D3	1		2		1		1		2		1
Q=30
D4	4		4		4		2		1		4
Q=10

2 Recherche d'une solution initiale.

Pour utiliser l'algorithme, on doit trouver une solution initiale satisfaisant à quelques principes.

Si m est le nombre de lignes et n celui des colonnes, on doit avoir au moins nm-n-m+1 cases nulles. ou au plus m+n-1 cases non nulles.

L'idéal est d'avoir exactement m+n-1 cases > 0, sinon on dit que l'on a une solution dégénérée et l'algorithme est un peu plus délicat.

On appelle solution de base une telle solution.

On travaillera sur des tableaux dont "chaque case" a la structure suivante:

Coût
	Quantité

2.1 Méthode du coin Nord-Ouest

Cette méthode permet de trouver une solution de base. Elle propose une façon d'affecter méthodiquement des quantités aux clients.

On commence par la case (C1,D1) que l'on affecte de la quantité Q11 = Min(Qd1,Qc1)

Si Q11 = Qd1, D1 est vide, mais C1 n'est peut être pas satisfait, on complète en utilisant le dépôt D2 et ainsi de suite jusqu'à satisfaction de C1.

Dans ce cas le dernier dépôt utilisé n'est peut être pas vide, il va continuer en livrant le client C2 du maximum qu'il peut. etc..

Si Q11 = Qc1, C1 est satisfait, mais D1 n'est peut être pas vide, il va maintenant livrer C2 au maximum de ses possibilités restantes. Une fois D1 vide, D2 prend le relais pour livrer le client en cours, etc..

Cette méthode fournit souvent une première solution de base. Par contre elle ne tient pas compte des considérations économiques et peut donc être très éloignée de la solution optimale. D'autres méthodes sont plus efficaces.

2.1.1 Cas de dégénérescence.

Elle se produit quand un dépôt se vide en même temps qu'un client obtient entière satisfaction.

Il faut alors utiliser des techniques différentes pour pouvoir démarrer (Voir plus loin).

2.1.2 Application sur l'exemple

On propose: En gris le cheminement des affectations des quantités Dépots-Clients

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10		10
D2	2		1		2		2		3		1
Q=21		3		18
D3	1		2		1		1		2		1
Q=30				2		18		4		4		2
D4	4		4		4		2		1		4
Q=10												10

m = 4, n = 6.: m.n-m-n+1 = 15.

On peut constater que l'on a exactement 15 zéros.

Le coût total de cette répartition est donc de 132.

2.2 Idée de l'algorithme: Notion de cycle d'échanges:

On peut vérifier dans l'exemple ci dessus que toute cellule "nulle" peut être connectée à un ensemble de cellules non nulles de manière à proposer un cycle d'échange:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10		10
D2	2		1		2		2		3		1
Q=21		3		18
D3	1		2		1		1		2		1
Q=30				2		18		4		4		2
D4	4		4		4		2		1		4
Q=10												10

Par exemple, on choisit de faire entrer la case (D4,C1). On cherche alors un G-cycle qui n'utilise que des cases "non nulles":

Par exemple (et ici c'est le seul possible)

(D4,C1); (D4,C6); (D3,C6); (D3,C2); (D2,C2); (D2,C1); et (D4,C1) qui ferme le cycle

L'idée est de charger la cellule (D4,C1) par transfère de quantités sur les cellules du G-cycle. La limite sera la plus petite quantité à ôter:

Schéma du transfert:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10		10
D2	2		1		2		2		3		1
Q=21	--	3	++	18
D3	1		2		1		1		2		1
Q=30			--	2		18		4		4	++	2
D4	4		4		4		2		1		4
Q=10	++										--	10

Il reste à voir sur combien d'unités on peut opérer: Ceci correspond à la plus petite quantité détenue par une case non vide "à vider". Il s'agit de la case (D3,C2) qui contient 2 unités.

Résultat:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10		10
D2	2		1		2		2		3		1
Q=21		1		20
D3	1		2		1		1		2		1
Q=30				0		18		4		4		4
D4	4		4		4		2		1		4
Q=10		2										8

On calcul le "coût" de l'opération (transfert d'une unité):

(D4,C1) ajout d'une unité = +4

(D4,C6) retrait d'une unité = -4

(D3,C6) ajout d'une unité = +1

(D3,C2) retrait d'une unité = -2

(D2,C2) ajout d'une unité = +1

(D2,C1) retrait d'une unité = -2

Total -2. Donc l'opération est intéressante.

Le résultat en une baisse de 4 €.

Il reste que l'on a choisi arbitrairement la cellule (D4,C1), d'autres peuvent être plus intéressantes.

3 Algorithme

3.1 Evaluation des G-cycles possibles:

3.1.1 Arbre associé à une solution de base:

On construit le graphe biparti obtenu en reliant les dépôts d'une part les clients d'autre part par des arètes correspondants aux cellules non vides Si la solution est de base cela implique que ce graphe est un arbre, et donc que pour tout couple (Dépôt, client) il existe une unique chaîne les reliant (Un G-cycle).

3.1.2 Evaluation des marges:

On n'utilise que les cellules non nulles en supposant la situation non dégénérée!!

On associe à chaque dépôt un nombre U(i), et à chaque client un autre nombre V(j), on appelle marges ces nombres (associés à une itération particulière de l'algorithme).

On prend comme référence une des cellules non vides (en général celle qui correspond au dépôt avec le coût le plus élevé parmi les livraisons non nulles, ici c'est 4). Comme il y a plusieurs postulants on en choisit un. On pose U(4) = 0, mais ceci est arbitraire, car tout est constant à une translation prés, et seul les différences entre les marges vont nous intéresser (analogie avec le potentiel en électricité).

On construit les autres marges de proche en proche par la relation c(i,j) = U(i) + V(j)

On peut aussi travailler directement sur la matrice. On met dans la marge à gauche 0 sur le dépôt ayant le coût le plus élevé, puis on propage de proche en proche.

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12	Marge
D1	4		3		3		5		3		4		0
Q=10		10
D2	2		1		2		2		3		1		-2
Q=21		3		18
D3	1		2		1		1		2		1		-1
Q=30				2		18		4		4		2
D4	4		4		4		2		1		4		2
Q=10												10
Marge		4		3		2		2		3		2

3.1.3 Evaluation d'un G-cycle

On construit un G-cycle concernant une cellule vide: (D4,C1) par exemple:

On vérifie sur le graphe la chaîne:

(D4,C1); (D4,C6); (D3,C6); (D3,C2); (D2,C2); (D2,C1); et (D4,C1):

(D4,C1) ajout d'une unité = +c(D4,C1)

(D4,C6) retrait d'une unité = -c(D4,C6) = -V(D4)-V(C6)

(D3,C6) ajout d'une unité = +c(D3,C6) = +V(D3)+V(C6)

(D3,C2) retrait d'une unité = -c(D3,C2) = -V(D3)-V(C2)

(D2,C2) ajout d'une unité = +c(D2,C2) = +V(D2)+V(C2)

(D2,C1) retrait d'une unité = -c(D2,C1) = -V(D2) -V(C1).

Le coût du cycle se réduit donc à c(D4,C1) - V(D4) - V(C1).

On va donc associer à chaque cellule nulle son coût réduit. Cette information est intégrée dans le tableau de travail comme ci-dessous:

Coût	Coût réduit
	Quantité

Une fois calculé tous les coûts réduits, choisir la plus petite valeur négative et recommencer.

Une fois que toutes les valeurs sont positives (ou nulles) , on a atteint l'optimum.

Application à notre exemple:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12	Marge
D1	4		3	0	3	1	5	3	3	0	4	2	0
Q=10		10
D2	2		1		2	2	2	2	3	2	1	1	-2
Q=21		3		18
D3	1	-2	2		1		1		2		1		-1
Q=30				2		18		4		4		2
D4	4	-2	4	-1	4	0	2	-2	1	-4	4		2
Q=10												10
Marge		4		3		2		2		3		2

On choisit le coût réduit le plus négative: m(D4,C5) = -4.

On utilise le G-Cycle (D4,C5); (D3,C5); (D3,C6); (D4,C6). qui permet de transférer 4 unités.

	C1=13	C2=20	C3=18	C4=4	C5=4	C6=12
D1=10	10
D2=21	3	18
D3=30		2	18	4	0	6
D4=10					4	6

et une économie de 24 euros!.

On recommence ensuite le même processus.

L'algorithme consiste donc

a) A trouver une répartition "de base"

b) A calculer les marges correspondantes

c) A calculer les coûts réduits.

e) A trouver un coût réduit négatif, en (I,J) par exemple. Sinon Fini.

f) A trouver un G-Cycle passant par (I,J)

g) A transférer circulairement les unités du bien à travers le G-cycle.

h) recommencer.

3.2 Cas particulier

3.2.1 Cas où la demande globale diffère de l'offre globale.

Ø Si l'offre excède la demande, on crée une demande fictive égale à la différence avec des coûts de transport identiques (pourquoi pas nuls).

Ø Si la demande excède l'offre, on crée une offre fictive égale à la différence avec des coûts de transport identiques.

Dans les 2 cas les quantités affectées ne perturberont pas les autres affectations.

3.2.2 Problèmes de dégénérescence:

On reprend le cas suivant, avec la répartition initiale (seulement 8 cases non nulles)

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12
D1	4		3		3		5		3		4
Q=10								4		4		2
D2	2		1		2		2		3		1
Q=21		13		8
D3	1		2		1		1		2		1
Q=30				12		18		<e>
D4	4		4		4		2		1		4
Q=10												10

3.2.3 Ajout de quantité fictives

Il apparaît que ce graphe n'est pas connexe. On peut le rendre connexe en imaginant que D3 envoie une petite quantité e à C4. A partir de là on considère que la case (D3,C4) fait partie des cases non nulles.

A partir ce de moment il est donc possible de calculer les marges et les coût réduits comme avant.

Le choix d'une case à améliorer étant fait, on cherche un G-cycle associé. Plusieurs situations sont alors possibles:

1) Le G-cycle ne passe pas par la case ajoutée. Celle-ci reste avec une quantité e.

2) Le G-cycle passe par la case ajoutée et:

a) La case ajoutée est une case où l'on ajoute: En ce cas tout va bien, et il y a disparition du problème de dégénérescence (en ce qui concerne cette case).

b) La case ajoutée est une case où l'on enlève: Il y a alors déplacement de la quantité e. On pose par principe que pour n'importe quelle quantité non nulle Q, Q+e = Q et Q-e = Q. Par contre la case à améliorer (Q = 0) se trouve elle avec cette quantité e. Il y a donc déplacement de la quantité e de sa case d'origine vers la case à améliorer.

Remarque: Le problème de dégénérescence demeure, on n'a fait que le déplacer sans rien améliorer.

Il faut alors prendre garde de ne pas boucler !!

3.2.4 Perturbation.

Une autre technique consiste à utiliser un problème perturbé qui ne conduira jamais à des cas de dégénérescence.

Pour cela on ajoute à chacune des m ressources Q(i) une petite valeur e > 0, (par exemple 1/m) et on ajoute également à la n ième demande la quantité m e.

La contrainte d'égalité de la demande globale et de l'offre globale sont toujours satisfaites.

Théorème:

Il peut y avoir dégénérescence d'un problème de transport si et seulement si il existe des sous ensembles M de {1,…m} et N de {1…n} tels que la somme des offres sur M soit égale à la somme des demandes sur N.

On peut alors démontrer que ce problème ne peut conduire à une dégénérescence.

Une fois la solution atteinte il reste à éliminer les effets de la perturbation.

3.3 Méthode de Balas – Hammer (méthode des regrets).

La méthode du coin Nord-Ouest ne tient pas compte de la matrice des coûts, elle risque donc de proposer une solution de départ éloignée de la solution optimale (ce qui implique de nombreuses itérations). On a donc chercher à produire une solution de départ la meilleur possible.

Principe:

a) Pour chaque ligne et chaque colonne chercher le coût c(i, j) le plus faible et le coût immédiatement supérieur (ou éventuellement égal). On calcule ensuite pour chaque ligne et colonne la différence entre ces 2 coûts. Ils représentent le "regret" que l'on peut éprouver en ne prenant pas le coût le plus faible.

b) On choisit la ligne ou la colonne où apparaît la différence la plus grande (regret maximum) , et dans cette ligne ou colonne, l'élément de coût minimal. Soit (I,J) la case ainsi obtenue.

c) On affecte la case (I,J) de la quantité maximum compatible avec les contraintes, ce qui sature soit la ligne I soit la colonne J.

d) On enlève la ligne I ou la colonne J ainsi saturée, et on recommence jusqu'à épuisement.

Exemple:

	C1	Q=13	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	C6	Q=12-12	Regret
D1	4		3		3		5		3		4		1
Q=10
D2	2		1		2		2		3		1<		1
Q=21-12												12
D3	1		2		1		1		2		1		1
Q=30
D4	4		4		4		2		1		4		1
Q=10
Regret	1		1		1		1		1		3

Si plusieurs solutions sont possibles on en choisit une, on élimine la ligne ou la colonne saturée.

	C1	Q=0	C2	Q=20	C3	Q=18	C4	Q=4	C5	Q=4	Regret
D1	4		3		3		5		3		1
Q=10
D2	2		1		2		2		3		1
Q=9
D3	1<		2		1		1		2		1
Q=17		13
D4	4		4		4		2		1		1
Q=10
Regret	1		1		1		1		1

	C2	Q=10	C3	Q=18	C4	Q=4	C5	Q=4	Regret
D1	3<		3		5		3		2
Q=0		10
D2	1		2		2		3		1
Q=9
D3	2		1		1		2		1
Q=17
D4	4		4		2		1		1
Q=10
Regret	1		1		1		1

	C2	Q=1	C3	Q=18	C4	Q=4	C5	Q=4	Regret
D2	1<		2		2		3		1
Q=0		9
D3	2		1		1		2		1
Q=17
D4	4		4		2		1		1
Q=10
Regret	1		1		1		1

	C2	Q=1	C3	Q=1	C4	Q=4	C5	Q=4	Regret
D3	2		1<		1		2		1
Q=0				17
D4	4		4		2		1		1
Q=10
Regret	2		3		1		1

Le dépot D3 est vide !! d'où:

	C2	Q=1	C3	Q=1	C4	Q=4	C5	Q=4	Regret
D4	4		4		2		1		1
Q=10		1		1		4		4
Regret	-				-		-

Soit un total de 101 à comparer avec les 132 obtenus avec la méthode du coin Nord-Ouest.

Remarque: là aussi la solution proposée n'est pas nécessairement non dégénérée.