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 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 Initialement + 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 30Demandes 15 20 5 25 14
+ Transports Sources/Destinataires 1 2 3 4 5 1 2
Étape 1 + 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 30Demandes 15 20 5 25 14
+ Transports Sources/Destinataires 1 2 3 4 5 1 15 2 0
Étape 2 + 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 30Demandes 0 20 5 25 14
+ Transports Sources/Destinataires 1 2 3 4 5 1 15 20 2 0 0
Étape 3 + 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 30Demandes 0 0 5 25 14
+ Transports Sources/Destinataires 1 2 3 4 5 1 15 20 5 2 0 0 0
Étape 4 + 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 30Demandes 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
+ 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= 14Demandes 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 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.
Catégorie:Algorithme