Aller au contenu

Méthode du coin Nord-Ouest

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources ().

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.

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Méthode_du_coin_Nord-Ouest&oldid=124942190 ».