5. Венгерский метод
1. Из всей таблицы стоимости выбирают наименьшую (минимальный элемент в строке), клетку помечают * и расставляют максимальное количество груза и обнуляют эту стоимость.
2. Затем находят элементы с минимальной стоимостью и в строке, и в столбце, помечают их. Выбирают наиболее подходящий из них, расставляют максимальное количество груза и обнуляют его стоимость. Из каждой стоимости элемента в строке и в столбце, в которых находится данный элемент, вычитают его стоимость, а к остальным элементам её прибавляют. Определяют вектор невязок Q.
3. Выполняют до тех пор, пока не расставят все грузы.
Таблица 1.5.1
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
1 |
|
21 |
|
30 |
|
10 |
* |
7 |
|
19 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
2 |
|
26 |
* |
3 |
|
18 |
|
30 |
|
27 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
22 |
* |
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
27 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
18 |
|
16 |
|
13 |
|
17 |
|
18 |
|
19 |
16 |
16 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
|
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
19 |
0 |
14 |
17 |
18 |
|
|
|||||||||||||
Таблица 1.5.2
|
32 |
|
14 |
|
0 |
|
35 |
|
33 |
|
39 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
|
11 |
|
40 |
|
20 |
|
17 |
|
29 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
16 |
* |
13 |
|
28 |
|
40 |
|
37 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
* |
12 |
|
0 |
|
0 |
|
19 |
|
16 |
|
13 |
27 |
8 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
|
|
|||||||||
|
28 |
* |
6 |
|
0 |
|
27 |
|
28 |
|
29 |
16 |
16 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
|
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
14 |
17 |
18 |
|
|
|||||||||||||
Таблица 1.5.3
|
22 |
|
26 |
|
0 |
|
47 |
|
45 |
|
51 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
|
23 |
|
52 |
|
32 |
|
29 |
|
41 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
29 |
|
0 |
|
40 |
|
52 |
|
49 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
* |
0 |
|
0 |
|
0 |
|
7 |
|
4 |
|
1 |
27 |
8 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
|
|
|||||||||
|
16 |
|
18 |
|
0 |
|
39 |
|
40 |
|
41 |
16 |
16 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
14 |
17 |
18 |
|
|
|||||||||||||
Таблица 1.5.4
|
23 |
|
24 |
|
0 |
|
48 |
|
46 |
|
50 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
|
24 |
|
53 |
|
33 |
|
30 |
|
40 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
30 |
|
0 |
|
41 |
|
53 |
|
48 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
* |
19 |
|
0 |
|
6 |
* |
3 |
|
0 |
27 |
0 |
|||||||
|
|
|
|
|
|
|
|
|
|
8 |
|
|||||||||
|
17 |
|
19 |
|
0 |
|
40 |
|
41 |
|
40 |
16 |
16 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
14 |
17 |
18 |
|
|
|||||||||||||
Таблица 1.5.5
|
42 |
|
8 |
|
0 |
|
67 |
|
65 |
|
69 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
|
5 |
|
72 |
|
52 |
|
49 |
|
59 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
11 |
|
0 |
|
60 |
|
72 |
|
67 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
25 |
|
21 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
36 |
|
0 |
|
0 |
|
21 |
|
22 |
|
21 |
16 |
16 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
14 |
17 |
18 |
|
|
|||||||||||||
Таблица 1.5.6
|
63 |
|
29 |
|
0 |
|
88 |
|
84 |
|
48 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
* |
26 |
|
93 |
|
73 |
|
70 |
|
38 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
32 |
|
0 |
|
81 |
|
93 |
|
46 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
46 |
|
42 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
15 |
|
0 |
|
0 |
|
0 |
* |
1 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
8 |
17 |
0 |
|
|
|||||||||||||
Таблица 1.5.7
|
99 |
* |
3 |
|
0 |
|
114 |
|
110 |
|
74 |
24 |
14 |
||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
||||||||
|
0 |
|
0 |
|
67 |
|
47 |
|
44 |
* |
12 |
14 |
0 |
||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
0 |
|
6 |
|
0 |
|
107 |
|
119 |
|
72 |
19 |
11 |
||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
0 |
|
0 |
|
0 |
|
72 |
|
68 |
|
0 |
27 |
0 |
||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||||||||
|
41 |
|
0 |
|
0 |
|
0 |
* |
27 |
|
0 |
16 |
0 |
||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
||||||||||||
0 |
0 |
0 |
8 |
17 |
0 |
|
|
||||||||||||
Таблица 1.5.8
|
126 |
* |
30 |
|
0 |
|
141 |
|
83 |
|
101 |
24 |
14 |
|
|
|
|
10 |
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
94 |
|
74 |
* |
17 |
|
39 |
14 |
0 |
14 |
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
33 |
|
0 |
|
134 |
|
92 |
|
99 |
19 |
11 |
8 |
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
0 |
|
99 |
|
41 |
|
0 |
27 |
0 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||
* |
14 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
||||||
0 |
0 |
0 |
8 |
17 |
0 |
|
|
||||||
Таблица 1.5.9
|
143 |
* |
47 |
|
0 |
|
158 |
|
66 |
|
118 |
24 |
14 |
|
|
|
|
10 |
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
77 |
|
57 |
|
0 |
* |
22 |
14 |
0 |
14 |
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
50 |
|
0 |
|
151 |
|
75 |
|
116 |
19 |
11 |
8 |
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
0 |
|
116 |
* |
24 |
|
0 |
27 |
0 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||
* |
31 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
||||||
0 |
0 |
0 |
8 |
17 |
0 |
|
|
||||||
Таблица 1.5.10
|
96 |
|
0 |
|
0 |
|
111 |
* |
19 |
|
71 |
24 |
14 |
|||||||
|
|
|
|
10 |
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
124 |
|
101 |
|
0 |
* |
69 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
* |
3 |
|
0 |
|
198 |
|
122 |
|
163 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
163 |
|
0 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
78 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
8 |
17 |
0 |
|
|
|||||||||||||
Таблица 1.5.11
|
77 |
|
0 |
|
0 |
|
92 |
|
0 |
* |
52 |
24 |
0 |
|||||||
|
|
|
|
10 |
|
|
|
14 |
|
|
|
|||||||||
|
0 |
|
0 |
|
143 |
|
120 |
|
0 |
|
188 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
* |
21 |
|
0 |
|
217 |
|
103 |
|
182 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
182 |
|
0 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
97 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
8 |
3 |
0 |
|
|
|||||||||||||
Таблица 1.5.12
|
98 |
|
0 |
|
0 |
|
113 |
|
0 |
* |
73 |
24 |
0 |
|||||||
|
|
|
|
10 |
|
|
|
14 |
|
|
|
|||||||||
|
0 |
|
0 |
|
164 |
|
141 |
|
0 |
|
109 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
196 |
* |
82 |
|
161 |
19 |
11 |
|||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
209 |
|
0 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
118 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
8 |
3 |
0 |
|
|
|||||||||||||
Таблица 1.5.13
|
180 |
|
0 |
|
0 |
|
195 |
|
0 |
|
165 |
24 |
0 |
|||||||
|
|
|
|
10 |
|
|
|
14 |
|
|
|
|||||||||
|
0 |
|
0 |
|
256 |
|
233 |
|
0 |
|
201 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
114 |
|
0 |
* |
79 |
19 |
8 |
|||||||
8 |
|
|
|
|
|
|
|
3 |
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
301 |
|
0 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
210 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
8 |
0 |
0 |
|
|
|||||||||||||
Таблица 1.5.14
|
259 |
|
0 |
|
0 |
|
274 |
|
0 |
|
86 |
24 |
0 |
|
|
|
|
10 |
|
|
|
14 |
|
|
|
||
|
0 |
|
0 |
|
335 |
|
312 |
|
0 |
|
122 |
14 |
0 |
14 |
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
0 |
* |
35 |
|
0 |
|
0 |
19 |
8 |
8 |
|
|
|
|
|
|
|
3 |
|
|
|
||
|
0 |
|
0 |
|
0 |
|
380 |
|
0 |
|
0 |
27 |
0 |
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||
|
289 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
||||||
0 |
0 |
0 |
8 |
0 |
0 |
|
|
||||||
Таблица 1.5.15
|
294 |
|
0 |
|
0 |
|
239 |
|
0 |
|
121 |
24 |
0 |
|||||||
|
|
|
|
10 |
|
|
|
14 |
|
|
|
|||||||||
|
0 |
|
0 |
|
370 |
|
284 |
|
0 |
|
157 |
14 |
0 |
|||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
19 |
0 |
|||||||
8 |
|
|
|
|
|
8 |
|
3 |
|
|
|
|||||||||
|
0 |
|
0 |
|
0 |
|
345 |
|
0 |
|
0 |
27 |
0 |
|||||||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
|||||||||
|
324 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
16 |
0 |
|||||||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
|||||||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|
|||||||||||||
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|||||||||||||
Переходим к оптимизации опорного плана.
Таблица 1.5.16
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|||
|
|
|
|
10 |
|
|
|
14 |
|
|
|
||||
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
|||
14 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
|||
8 |
|
|
|
|
|
8 |
|
3 |
|
|
|
||||
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||||
|
18 |
|
16 |
|
13 |
|
7 |
|
18 |
|
19 |
16 |
|||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|||||||||
W=14+16+190+70+8*18+42+14*23+90+8*23+190=1262
Таблица 1.5.17
|
22 |
|
24 |
|
7 |
|
25 |
|
23 |
|
29 |
24 |
|||
|
|
|
|
10 |
|
8 |
|
6 |
|
|
|
||||
|
1 |
|
21 |
|
30 |
|
10 |
|
7 |
|
19 |
14 |
|||
6 |
|
|
|
|
|
|
|
8 |
|
|
|
||||
|
2 |
|
26 |
|
3 |
|
18 |
|
30 |
|
27 |
19 |
|||
16 |
|
|
|
|
|
|
|
3 |
|
|
|
||||
|
22 |
|
10 |
|
9 |
|
29 |
|
26 |
|
23 |
27 |
|||
|
|
19 |
|
|
|
|
|
|
|
8 |
|
||||
|
18 |
|
16 |
|
13 |
|
7 |
|
18 |
|
19 |
16 |
|||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|||||||||
W=6+38+190+70+8*25+42+6*23+8*7+90+8*23+190=1258
Таблица 1.5.17
|
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 |
|
|
|
|
|
|
|
8 |
|
||||
|
18 |
|
16 |
|
13 |
|
7 |
|
18 |
|
19 |
16 |
|||
|
|
|
|
|
|
6 |
|
|
|
10 |
|
||||
22 |
19 |
10 |
14 |
17 |
18 |
100 |
|||||||||
W=3+38+190+70+8*25+42+6*23+11*7+8*23+190=1192
