3. Метод двойного предпочтения
Обычно используют, если таблица стоимостей велика и перебор всех элементов затруднителен. В каждом столбце отмечают * клетку с наименьшей стоимостью. Затем тоже проделывают и в каждой строке, получая в некоторых клетках **. В эти клетки помещают максимально возможные объемы перевозок , каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам *. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.
Таблица 1.3.1
|
22 |
|
24 |
* |
7 |
|
25 |
|
23 |
|
29 |
24 |
- |
|
- |
|
- |
|
13 |
|
1 1 |
|
- |
|
|
** |
1 |
|
21 |
|
30 |
* |
10 |
* |
7 |
* |
19 |
14 |
1 4 |
|
- |
|
- |
|
- |
|
1 |
|
- |
|
|
* |
2 |
|
26 |
* |
3 |
|
18 |
|
30 |
|
27 |
19 |
8 |
|
- |
|
10 |
|
1 |
|
- |
|
- |
|
|
|
22 |
* |
10 |
* |
9 |
|
29 |
|
26 |
|
23 |
27 |
- |
|
19 |
|
- |
|
- |
|
6 |
|
2 |
|
|
|
18 |
|
16 |
* |
13 |
|
17 |
|
18 |
* |
19 |
16 |
- |
|
- |
|
- |
|
- |
|
- |
|
16 |
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 14+16+190+30+13*25+18+11*23+7+6*26+46+16*19=1352
Таблица 1.3.2
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|
|
|
|
10 |
|
1 4 |
|
|
|
|
|
|
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
3 |
|
|
|
|
|
|
|
11 |
|
|
|
|
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|
|
19 |
|
|
|
|
|
6 |
|
2 |
|
|
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|
|
|
|
|
|
|
|
1 |
|
16 |
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 3+38+190+70+14*25+11*7+6*26+46+16*19=1234
Таблица 1.3.2
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|
|
|
|
10 |
|
8 |
|
6 |
|
|
|
|
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
3 |
|
|
|
|
|
|
|
11 |
|
|
|
|
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|
|
19 |
|
|
|
|
|
6 |
|
8 |
|
|
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|
22 |
19 |
10 |
14 |
17 |
18 |
100 |
||||||
W = 3+38+190+70+8*25+6*17+6*23+11*7+6*26+8*23+190=1192
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят:
W = 1192