M茅thode du coin Nord-Ouest
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 |
30 |
| Demandes |
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 |
30 |
| Demandes |
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 |
30 |
| Demandes |
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 |
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
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
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
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.
Cet article est issu de
wikipedia. Texte licence:
CC BY-SA 4.0, Des conditions suppl茅mentaires peuvent s鈥檃ppliquer aux fichiers multim茅dias.