Практическая работа по "Экономике"
Автор: anna142 • Сентябрь 18, 2021 • Практическая работа • 603 Слов (3 Страниц) • 180 Просмотры
Задание
Решить задачу о коммивояжёре методов ветвей и границ. Исходные данные представлены в таблице.
Таблица 1 – Исходные данные
- | 40 | 34 | 50 | 10 | 44 |
18 | - | 3 | 38 | 52 | 10 |
23 | 12 | - | 47 | 42 | 5 |
54 | 29 | 56 | - | 9 | 2 |
17 | 31 | 23 | 8 | - | 4 |
28 | 53 | 58 | 15 | 41 | - |
Решение.
Найдем минимальные значения по строкам.
Таблица 2
6x6 | 1 | 2 | 3 | 4 | 5 | 6 | h1 |
1 | - | 40 | 34 | 50 | 10 | 44 | 10 |
2 | 18 | - | 3 | 38 | 52 | 10 | 3 |
3 | 23 | 12 | - | 47 | 42 | 5 | 5 |
4 | 54 | 29 | 56 | - | 9 | 2 | 2 |
5 | 17 | 31 | 23 | 8 | - | 4 | 4 |
6 | 28 | 53 | 58 | 15 | 41 | - | 15 |
Cледовательно, h1=10+3+5+2+4+15=39
Далее вычтем минимальные значения по строкам из каждый строки и найдем минимальные значения по столбцам (таблица 3).
Таблица 3
6x6 | 1 | 2 | 3 | 4 | 5 | 6 |
1 | - | 30 | 24 | 40 | 0 | 34 |
2 | 15 | - | 0 | 35 | 49 | 7 |
3 | 18 | 7 | - | 42 | 37 | 0 |
4 | 52 | 27 | 54 | - | 7 | 0 |
5 | 13 | 27 | 19 | 4 | - | 0 |
6 | 13 | 38 | 43 | 0 | 26 | - |
h2 | 13 | 7 | 0 | 0 | 0 | 0 |
Cледовательно, h2=13+7+0+0+0+0=20. Далее вычтем минимальные значения по столбцам из каждого столбца (таблица 4).
h = 39+20=59
Данное значение является нижней оценка длины маршрута.
Для каждого нуля находим сумму минимальных элементов из соответствующих ему строки и столбца и выбираем наибольшую сумму θ (таблица 4).
Строку и столбец, образовавшие наибольшую сумму необходимо вычеркнуть.
Таблица 4
6x6 | 1 | 2 | 3 | 4 | 5 | 6 | θ |
1 | - | 23 | 24 | 40 | 0 | 34 | 30 |
2 | 2 | - | 0 | 35 | 49 | 7 | 21 |
3 | 5 | 0 | - | 42 | 37 | 0 | 20;0 |
4 | 39 | 20 | 54 | - | 7 | 0 | 7 |
5 | 0 | 20 | 19 | 4 | - | 0 | 0;0 |
6 | 0 | 31 | 43 | 0 | 26 | - | 0;4 |
Далее аналогичным образом рассчитаем h1 и h2 – минимальные значения по строкам и столбцам (таблица 5). При этом поставим запрет на обратный путь (5;1).
...