Méthode du coin Nord-Ouest

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (octobre 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

La méthode du coin Nord-Ouest, ou MCNO (North-west Corner Method, NWCM), est utilisée pour trouver une solution à un programme de transport sans prise en compte du coût.

Il existe des algorithmes permettant de trouver une solution optimale sur le plan des coûts, comme l'algorithme de Balas-Hammer.

Principe[modifier | modifier le code]

Cette méthode s'applique sur une matrice de coûts de transports entre sources et destinataires.

Elle consiste à remplir une matrice de transports en parcourant linéairement la matrice des coûts.

Exemple[modifier | modifier le code]

Initialement[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	49
2	5	2	6	12	5	30
Demandes	15	20	5	25	14

Transports
Sources/Destinataires	1	2	3	4	5
1
2

Étape 1[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	49
2	5	2	6	12	5	30
Demandes	15	20	5	25	14

Transports
Sources/Destinataires	1	2	3	4	5
1	15
2	0

Étape 2[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	49-15= 34
2	5	2	6	12	5	30
Demandes	0	20	5	25	14

Transports
Sources/Destinataires	1	2	3	4	5
1	15	20
2	0	0

Étape 3[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	34-20= 14
2	5	2	6	12	5	30
Demandes	0	0	5	25	14

Transports
Sources/Destinataires	1	2	3	4	5
1	15	20	5
2	0	0	0

Étape 4[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	14-5= 9
2	5	2	6	12	5	30
Demandes	0	0	0	25	14

Transports
Sources/Destinataires	1	2	3	4	5
1	15	20	5	9
2	0	0	0	16

Étape 5[modifier | modifier le code]

Coûts / Besoins / Stocks
Sources/Destinataires	1	2	3	4	5	Stocks
1	10	6	3	5	25	0
2	5	2	6	12	5	30-16= 14
Demandes	0	0	0	0	14

Transports
Sources/Destinataires	1	2	3	4	5
1	15	20	5	9	0
2	0	0	0	16	14

Coût de la solution[modifier | modifier le code]

La solution trouvée avec cette méthode n'est pas optimale sur le plan des coûts.

On trouve ici : 15*10 + 20*6 + 5*3 + 9*5 + 0*25 + 0*5 + 0*2 + 0*6 + 16*12 + 14*5 = 592.