Методическое пособие 577
.pdfТаблица 30
Редукция столбцов
Санаторий |
1 |
3 |
4 |
5 |
6 |
7 |
2 |
M |
3 |
17 |
6 |
7 |
0 |
3 |
4 |
M |
9 |
0 |
4 |
9 |
4 |
17 |
17 |
M |
17 |
0 |
36 |
5 |
0 |
0 |
25 |
M |
0 |
0 |
6 |
25 |
21 |
0 |
13 |
M |
35 |
7 |
10 |
16 |
17 |
0 |
18 |
M |
min |
90 |
0 |
0 |
0 |
0 |
0 |
Найдем оценки для нулевых ячеек (табл. 31). Максимальная оценка соответствует ячейке 6-4. Мы нашли еще один отрезок пути: 6→4. Вычеркиваем 6-ю строку и 4-й столбец (табл. 32), а в ячейке 4-6 ставим М.
Таблица 31
Нахождение оценок
Санаторий |
1 |
3 |
4 |
5 |
6 |
7 |
2 |
M |
3 |
17 |
6 |
7 |
0 [3] |
3 |
4 |
M |
9 |
0 [4] |
4 |
9 |
4 |
17 |
17 |
M |
17 |
0 [17] |
36 |
5 |
0 [4] |
0 [3] |
25 |
M |
0 [0] |
0 [0] |
6 |
25 |
21 |
0 [22] |
13 |
M |
35 |
7 |
10 |
16 |
17 |
0 [10] |
18 |
M |
Таблица 32
Редукция матрицы
Санаторий |
1 |
3 |
5 |
6 |
7 |
2 |
M |
3 |
6 |
7 |
0 |
3 |
4 |
M |
0 |
4 |
9 |
4 |
17 |
17 |
17 |
M |
36 |
5 |
0 |
0 |
M |
0 |
0 |
7 |
10 |
16 |
0 |
18 |
M |
50
Находим минимум по строкам (табл. 33), проводим редукцию строк (табл. 34), определяем минимум по столбцам (табл. 35) и выполняем редукцию столбцов (табл. 36).
Таблица 33
Нахождение минимума по строкам
|
Санаторий |
1 |
|
|
3 |
|
|
5 |
|
6 |
|
|
7 |
|
|
min |
|
|||||
|
2 |
M |
|
3 |
|
|
6 |
|
7 |
|
|
0 |
|
|
0 |
|
|
|||||
|
3 |
4 |
|
|
|
M |
|
0 |
|
4 |
|
|
9 |
|
|
0 |
|
|
||||
|
4 |
17 |
|
17 |
|
17 |
M |
|
36 |
|
17 |
|
|
|||||||||
|
5 |
0 |
|
|
0 |
|
|
|
M |
0 |
|
|
0 |
|
|
0 |
|
|
||||
|
7 |
10 |
|
16 |
|
0 |
|
18 |
|
M |
|
0 |
|
|
||||||||
|
|
|
Редукция строк |
|
|
|
|
|
|
|
Таблица 34 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Санаторий |
1 |
|
|
3 |
|
|
5 |
|
6 |
|
|
7 |
|
|
min |
||||||
|
2 |
M |
|
3 |
|
|
6 |
|
7 |
|
|
0 |
|
|
0 |
|
|
|||||
|
3 |
4 |
|
|
|
M |
|
0 |
|
4 |
|
|
9 |
|
|
0 |
|
|
||||
|
4 |
0 |
|
|
0 |
|
|
0 |
|
M |
|
19 |
|
17 |
|
|
||||||
|
5 |
0 |
|
|
0 |
|
|
|
M |
0 |
|
|
0 |
|
|
0 |
|
|
||||
|
7 |
10 |
|
16 |
|
0 |
|
18 |
|
M |
|
0 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 35 |
|
|
Нахождение минимума по столбцам |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
Санаторий |
|
1 |
|
3 |
|
5 |
|
6 |
|
7 |
|
|
|
|||||||
|
2 |
|
|
|
M |
|
3 |
|
6 |
|
7 |
|
0 |
|
|
|
||||||
|
3 |
|
|
4 |
|
|
M |
|
0 |
|
4 |
|
9 |
|
|
|
||||||
|
4 |
|
|
0 |
|
0 |
|
0 |
|
M |
|
19 |
|
|
|
|||||||
|
5 |
|
|
0 |
|
0 |
|
M |
|
0 |
|
0 |
|
|
|
|||||||
|
|
7 |
|
|
10 |
|
16 |
|
0 |
|
18 |
|
M |
|
||||||||
|
|
min |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
||||||
51
Таблица 36
Редукция столбцов
Санаторий |
1 |
3 |
5 |
6 |
7 |
2 |
M |
3 |
6 |
7 |
0 |
3 |
4 |
M |
0 |
4 |
9 |
4 |
0 |
0 |
0 |
M |
19 |
5 |
0 |
0 |
M |
0 |
0 |
7 |
10 |
16 |
0 |
18 |
M |
min |
0 |
0 |
0 |
0 |
0 |
Найдем оценки для нулевых оценок (табл. 37). Максимальная оценка соответствует ячейке 7-5. Мы нашли еще один участок пути: 7→5. Вычеркиваем 7-ю строку и 5-й столбец (табл. 38), а в ячейке 5-7 ставимМ.
Таблица 37
Нахождение оценок
Санаторий |
|
1 |
3 |
|
|
5 |
6 |
|
7 |
|
||||
2 |
|
M |
3 |
|
|
6 |
7 |
|
0 [3] |
|
||||
3 |
|
4 |
|
M |
0 [4] |
4 |
|
9 |
|
|||||
4 |
|
0 [0] |
0 [0] |
|
0 [0] |
|
M |
19 |
|
|||||
5 |
|
0 [0] |
0 [0] |
|
|
M |
0 [4] |
|
0 [0] |
|
||||
7 |
|
10 |
16 |
|
0 [10] |
18 |
|
M |
|
|||||
|
|
Редукция матрицы |
|
|
|
|
Таблица 38 |
|||||||
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Санаторий |
|
1 |
|
3 |
|
6 |
|
7 |
|
|
|
||
|
|
2 |
|
M |
|
3 |
|
7 |
|
0 |
|
|
|
|
|
|
3 |
|
4 |
|
M |
|
4 |
|
9 |
|
|
|
|
|
|
4 |
|
0 |
|
0 |
|
M |
|
19 |
|
|
|
|
|
|
5 |
|
0 |
|
0 |
|
0 |
|
M |
|
|
|
|
52
Находим минимум по строкам (табл. 39), проводим редукцию строк (табл. 40), определяем минимум по столбцам (табл. 41) и выполняем редукцию столбцов (табл. 42).
Таблица 39
Нахождение минимума по строкам
Санаторий |
1 |
3 |
6 |
7 |
min |
|
2 |
M |
3 |
7 |
0 |
0 |
|
3 |
4 |
M |
4 |
9 |
4 |
|
4 |
0 |
0 |
M |
19 |
0 |
|
5 |
0 |
0 |
0 |
M |
0 |
|
Редукция строк |
|
|
Таблица 40 |
|||
|
|
|
||||
|
|
|
|
|
|
|
Санаторий |
1 |
3 |
6 |
7 |
min |
|
2 |
M |
3 |
7 |
0 |
0 |
|
3 |
0 |
M |
0 |
5 |
4 |
|
4 |
0 |
0 |
M |
19 |
0 |
|
5 |
0 |
0 |
0 |
M |
0 |
|
Таблица 41
Нахождение минимума по столбцам
Санаторий |
1 |
3 |
6 |
7 |
2 |
M |
3 |
7 |
0 |
3 |
0 |
M |
0 |
5 |
4 |
0 |
0 |
M |
19 |
5 |
0 |
0 |
0 |
M |
min |
0 |
0 |
0 |
0 |
53
Таблица 42
Редукция столбцов
Санаторий |
1 |
3 |
6 |
7 |
2 |
M |
3 |
7 |
0 |
3 |
0 |
M |
0 |
5 |
4 |
0 |
0 |
M |
19 |
5 |
0 |
0 |
0 |
M |
min |
0 |
0 |
0 |
0 |
Найдем оценки для нулевых оценок (табл. 43). Максимальная оценка соответствует ячейке 2-7. Нашли еще один участок пути: 2→7. Вычеркиваем 2-ю строку и 7-й столбец
(табл. 44).
Таблица 43
Нахождение оценок
Санаторий |
|
1 |
3 |
|
|
6 |
7 |
|
|||
2 |
|
M |
3 |
|
|
7 |
0 [8] |
|
|||
3 |
|
0 [0] |
M |
|
|
0 [0] |
5 |
|
|||
4 |
|
0 [0] |
0 [0] |
|
|
M |
19 |
|
|||
5 |
|
0 [0] |
0 [0] |
|
0 [0] |
M |
|
||||
|
Редукция матрицы |
|
Таблица 44 |
||||||||
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|||
|
Санаторий |
1 |
|
3 |
|
6 |
|
|
|||
|
|
3 |
|
0 |
|
M |
|
0 |
|
|
|
|
|
4 |
|
0 |
|
0 |
|
M |
|
|
|
|
|
5 |
|
0 |
|
0 |
|
0 |
|
|
|
Далее в получившейся матрице найдем минимум по строкам и минимум по столбцам. Найдем оценки для нулевых ячеек
(табл. 45).
54
Таблица 45
Вычисление оценок
Санаторий |
1 |
3 |
6 |
3 |
0 [0] |
M |
0 [0] |
4 |
0 [0] |
0 [0] |
M |
5 |
0 [0] |
0 [0] |
0 [0] |
Максимальная оценка соответствует ячейке 5-6. Нашли еще один участок пути: 5→6. Вычеркиваем 5-ю строку и 6-й столбец (табл. 46).
Таблица 46
Редукция матрицы
Санаторий |
1 |
3 |
3 |
0 |
M |
4 |
0 |
0 |
Далее опять найдем минимум по строкам и минимум по столбцам. Выполним редукцию строк и столбцов. В получившейся матрице найдем оценки для нулевых ячеек (табл. 47).
Таблица 47
Вычисление оценок
Санаторий |
1 |
3 |
3 |
0 [∞] |
M |
4 |
0 [0] |
0 [∞] |
Нашли еще один отрезок пути: 4→3. И конечный отрезок пути: 3→1. Таким образом, задача коммивояжера успешно решена, оптимальный (кратчайший) путь найден. Ему соответствует следующий маршрут: 1→2→7→5→6→4→3 (рис. 19).
55
Рис. 19. Итоговый маршрут
Рассмотрим еще один пример. Требуется доставить лекарственные препараты из центрального склада в 5 городских больниц города Воронежа. Время в пути между пунктами приведены в табл. 48. Требуется найти оптимальный (кратчайший) замкнутый маршрут, проходящий через каждый пункт один раз и обеспечивающий минимальное время на переезд.
|
Матрица исходных данных |
|
Таблица 48 |
||||
|
|
|
|
||||
|
|
|
|
|
|
|
|
Больницы |
ГКБ №8 |
БСМП №10 |
ВОКБ №1 |
|
БСМП №1 |
|
ОДКБ №2 |
ГКБ №8 |
M |
21 |
37 |
|
30 |
|
27 |
БСМП №10 |
30 |
M |
23 |
|
39 |
|
14 |
ВОКБ №1 |
47 |
29 |
M |
|
36 |
|
38 |
БСМП №1 |
27 |
44 |
44 |
|
M |
|
48 |
ОДКБ №2 |
40 |
11 |
34 |
|
51 |
|
M |
Находим минимум по строкам (табл. 49), проводим редукцию строк (табл. 50), определяем минимум по столбцам (табл. 51) и выполняем редукцию столбцов (табл. 52).
56
Таблица 49 Нахождение минимального элемента по строкам
Больницы |
ГКБ №8 |
БСМП |
ВОКБ №1 |
БСМП №1 |
ОДКБ №2 |
min |
|
|
№10 |
|
|
|
|
ГКБ №8 |
M |
21 |
37 |
30 |
27 |
21 |
БСМП №10 |
30 |
M |
23 |
39 |
14 |
14 |
ВОКБ №1 |
47 |
29 |
M |
36 |
38 |
29 |
БСМП №1 |
27 |
44 |
44 |
M |
48 |
27 |
ОДКБ №2 |
40 |
11 |
34 |
51 |
M |
11 |
|
|
Редукция строк |
|
Таблица 50 |
||
|
|
|
|
|
||
|
|
|
|
|
|
|
Больницы |
ГКБ №8 |
БСМП №10 |
ВОКБ №1 |
БСМП №1 |
|
ОДКБ №2 |
ГКБ №8 |
M |
0 |
16 |
9 |
|
6 |
БСМП №10 |
16 |
M |
9 |
25 |
|
0 |
ВОКБ №1 |
18 |
0 |
M |
7 |
|
9 |
БСМП №1 |
0 |
17 |
17 |
M |
|
21 |
ОДКБ №2 |
29 |
0 |
23 |
40 |
|
M |
|
|
|
|
|
Таблица 51 |
Нахождение минимального элемента по столбцам |
|||||
|
|
|
|
|
|
Больницы |
ГКБ №8 |
БСМП №10 |
ВОКБ №1 |
БСМП №1 |
ОДКБ №2 |
ГКБ №8 |
M |
0 |
16 |
9 |
6 |
БСМП №10 |
16 |
M |
9 |
25 |
0 |
ВОКБ №1 |
18 |
0 |
M |
7 |
9 |
БСМП №1 |
0 |
17 |
17 |
M |
21 |
ОДКБ №2 |
29 |
0 |
23 |
40 |
M |
min |
0 |
0 |
9 |
7 |
0 |
|
|
Редукция столбцов |
|
Таблица 52 |
|
|
|
|
|
||
|
|
|
|
|
|
Больницы |
ГКБ №8 |
БСМП №10 |
ВОКБ №1 |
БСМП №1 |
ОДКБ №2 |
|
|
|
|
|
|
ГКБ №8 |
M |
0 |
7 |
2 |
6 |
БСМП №10 |
16 |
M |
0 |
18 |
0 |
ВОКБ №1 |
18 |
0 |
M |
0 |
9 |
БСМП №1 |
0 |
17 |
8 |
M |
21 |
ОДКБ №2 |
29 |
0 |
14 |
33 |
M |
57
Найдем оценки для нулевых оценок (табл. 53). Максимальная оценка соответствует ячейке 4-1. Мы нашли один отрезок пути: БСМП №1 → ГКБ №8. Вычеркиваем 4-ю строку и 1-й столбец (табл. 54), а в ячейке ГКБ №8 − БСМП №1 ставим М.
|
Вычисление оценок нулевых клеток |
Таблица 53 |
|||
|
|
||||
|
|
|
|
|
|
Больницы |
ГКБ №8 |
БСМП №10 |
ВОКБ №1 |
БСМП №1 |
ОДКБ №2 |
ГКБ №8 |
M |
0[2] |
7 |
2 |
6 |
БСМП №10 |
16 |
M |
0[7] |
18 |
0[6] |
ВОКБ №1 |
18 |
0[0] |
M |
0[2] |
9 |
БСМП №1 |
0[24] |
17 |
8 |
M |
21 |
ОДКБ №2 |
29 |
0[14] |
14 |
33 |
M |
|
Редукция матрицы |
Таблица 54 |
||
|
|
|||
|
|
|
|
|
Больницы |
БСМП №10 |
ВОКБ №1 |
БСМП №1 |
ОДКБ №2 |
ГКБ №8 |
0 |
7 |
2 |
6 |
БСМП №10 |
M |
0 |
18 |
0 |
ВОКБ №1 |
0 |
M |
0 |
9 |
ОДКБ №2 |
0 |
14 |
33 |
M |
Так как минимальным элементом во всех строках и столбцах является 0, то перейдем к следующему пункту.
Найдем оценки для нулевых оценок (табл. 55). Максимальная оценка соответствует ячейке 3-3. Мы нашли один отрезок пути: ВОКБ №1 → БСМП №1. Вычеркиваем 3-ю строку и 3-й столбец (табл. 56), а в ячейке БСМП №1 – ВОКБ №1 ставим М.
|
Вычисление оценок нулевых клеток |
Таблица 55 |
||
|
|
|||
|
|
|
|
|
Больницы |
БСМП №10 |
ВОКБ №1 |
БСМП№1 |
ОДКБ №2 |
|
|
|
|
|
ГКБ №8 |
0[6] |
7 |
М |
6 |
БСМП №10 |
M |
0[7] |
18 |
0[6] |
ВОКБ №1 |
0[0] |
M |
0[18] |
9 |
ОДКБ №2 |
0[14] |
14 |
33 |
M |
58
|
Редукция матрицы |
Таблица 56 |
||
|
|
|
||
|
|
|
|
|
Больницы |
БСМП №10 |
ВОКБ №1 |
ОДКБ №2 |
|
ГКБ №8 |
0 |
7 |
6 |
|
БСМП №10 |
M |
0 |
0 |
|
ОДКБ №2 |
0 |
14 |
M |
|
Так как минимальным элементом во всех строках и столбцах является 0, то перейдем к следующему пункту. Найдем оценки для нулевых оценок (табл. 57). Максимальная оценка соответствует ячейке 3-1. Мы нашли один отрезок пути: ОДКБ №2 → БСМП №10. Вычеркиваем 3-ю строку и 1-й столбец (табл. 58), а в ячейке БСМП №10 − ОДКБ №2 ставим М.
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 57 |
|
|
|
Вычисление оценок нулевых клеток |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
Больницы |
|
БСМП №10 |
|
ВОКБ №1 |
|
ОДКБ №2 |
|||||||
ГКБ №8 |
|
0[6] |
|
|
7 |
|
|
6 |
|
||||
БСМП №10 |
|
M |
|
|
0[7] |
|
|
0[6] |
|
||||
ОДКБ №2 |
|
0[14] |
|
|
14 |
|
|
|
M |
|
|||
|
|
|
Редукция матрицы |
|
|
|
Таблица 58 |
||||||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|||||||
|
Больницы |
|
ВОКБ №1 |
|
ГДКБ №2 |
||||||||
|
|
ГКБ №8 |
|
|
7 |
|
|
|
6 |
|
|
||
|
БСМП №10 |
|
|
0 |
|
|
|
М |
|
||||
Определим минимальные элементы по строкам (табл. 59), проведем редукцию строк (табл. 60).
Таблица 59 Нахождение минимального элемента по строкам
Больницы |
ВОКБ №1 |
ОДКБ №2 |
min |
ГКБ №8 |
7 |
6 |
6 |
БСМП №10 |
0 |
М |
0 |
59