іднімаю 10 від шкірного елемента цього рядка матриці. Отримайте матрицю следующего вигляд:
Нижня межа, Мінімальна довжина маршруту комівояжера буде дорівнюваті:
+ 10=одна тисяча чотиреста сімдесят сім.
визначавши КОЕФІЦІЄНТИ для шкірного з нулів матриці. Коефіцієнт дорівнює сумі мінімальніх елементів того рядка и стовпця на перетіні якіх ВІН находится:
G35=0 + 22=22; G45=0 + 0=0; G 46 =0 + 141=141 ;
G54=0 + 27=27; G61=0 + 10=10; G64=0 + 0=0.
Вибирай максимальний G46=141, вікреслюю з попередньої матриці 4 рядок и 6 стовпець, на місце (6; 4) ставлю?.
получил матрицю следующего вигляд:
Нижня межа, Мінімальна довжина маршруту комівояжера НЕ змініться І буде дорівнюваті: 1 477.
визначавши КОЕФІЦІЄНТИ для шкірного з нулів матриці. Коефіцієнт дорівнює сумі мінімальніх елементів того рядка и стовпця на перетіні якіх ВІН находится:
G35=22 + 141=163; G 54 =27 + 141=168;
G61=22 + 141=163.
Вибирай максимальний G54=168, вікреслюю з попередньої матриці 5 рядок і 4 стовпець.
получил матрицю следующего вигляд:
Нижня межа, Мінімальна довжина маршруту комівояжера буде дорівнюваті: 1477.
знаходжусь ребра графу, ними будут ті ребра, Які вікреслювалісь з матриць на попередніх етапах І що залиша в Последний матриці:
(2; 3), (1; 2), (4; 6), (5; 4), (3; 1), (3; 5), (6; 1), (6; 5).
будую граф з Даними ребрами рис. 3:
Рис. 3.
Відповідь: нижня межа, Мінімальна довжина маршруту комівояжера складатіме 1477. Граф, что збережений на рис. 3 буде оптимальним, при підсумовуванні ребер (что залиша в ході розвязка задачі) графа на рис. 3. смороду дадуть значення, Пожалуйста дорівнює +1477.
Список використаної літератури
1. Скляренко С.М. поштовий зв'язок: Підруч. Для вищ. навч. закл. Для спеціальностей за безпосередньо «Телекомунікації»/С.М. Скляренка, В.К. Стеклов, Л.Н. Беркман; за заг. ред. В.К. Стеклова.- 2-ге вид., Стереотип.- К .: Техніка, 2004. - 904 с.
. Ящук Л.О., Кріль С.С. Мережі та системи поштового зв язку/О .: ОНАЗ ім. О.С. Попова, 2008. - 224 с.
. Брагін А.С. Петрова В.М. Шматко В.С. Основи поштового зв'язку та его технології: Навч. посібник для студ. Вищих навч. закл., Які навч. за безпосередньо «Телекомунікації».- К .: Політехніка, 2004. - 439 c.