Метод гілок та меж для рішення задач цілочисельного програмування
Алгоритм рішення
Дана матриця відстаней, представлена в таблиці 1. Необхідно за допомогою алгоритму Літтла вирішити завдання комівояжера.
Табл.1
|
ji |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
? |
7 |
16 |
21 |
2 |
17 |
|
|
2 |
13 |
? |
21 |
15 |
43 |
23 |
|
|
3 |
25 |
3 |
? |
31 |
17 |
9 |
|
|
4 |
13 |
10 |
27 |
? |
33 |
12 |
|
|
5 |
9 |
2 |
19 |
14 |
? |
51 |
|
|
6 |
42 |
17 |
5 |
9 |
23 |
? |
1) Праворуч до таблиці приєднуємо стовпець Ui, в якому записуємо мінімальні елементи відповідних рядків. Віднімаємо елементи Ui з відповідних елементів рядка матриці.
|
ji |
1 |
2 |
3 |
4 |
5 |
6 |
Ui |
|
|
1 |
? |
7 |
16 |
21 |
2 |
17 |
2 |
|
|
2 |
13 |
? |
21 |
15 |
43 |
23 |
13 |
|
|
3 |
25 |
3 |
? |
31 |
17 |
9 |
3 |
|
|
4 |
13 |
10 |
27 |
? |
33 |
12 |
10 |
|
|
5 |
9 |
2 |
19 |
14 |
? |
51 |
2 |
|
|
6 |
42 |
17 |
5 |
9 |
23 |
? |
5 |
2) Внизу отриманої матриці приєднуємо рядок Vj, в якій записуємо мінімальні елементи стовпців. Віднімаємо елементи Vj з відповідних стовпців матриці.
|
ji |
1 |
2 |
3 |
4 |
5 |
6 |
Ui |
|
|
1 |
? |
7 |
16 |
21 |
2 |
17 |
2 |
|
|
2 |
13 |
? |
21 |
15 |
43 |
23 |
13 |
|
|
3 |
25 |
3 |
? |
31 |
17 |
9 |
3 |
|
|
4 |
13 |
10 |
27 |
? |
33 |
12 |
10 |
|
|
5 |
9 |
2 |
19 |
14 |
? |
51 |
2 |
|
|
6 |
42 |
17 |
5 |
9 |
23 |
? |
5 |
3) У результаті обчислень отримуємо матрицю, наведену по рядках і стовпцях, яка зображена у вигляді таблиці 2.
Табл.2
|
ji |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
? |
5 |
14 |
17 |
019 |
13 |
|
|
2 |
03 |
? |
8 |
02 |
30 |
8 |
|
|
3 |
22 |
04 |
? |
26 |
14 |
4 |
|
|
4 |
3 |
00 |
17 |
? |
23 |
04 |
|
|
5 |
7 |
07 |
17 |
10 |
? |
47 |
|
|
6 |
37 |
12 |
08 |
2 |
18 |
? |
4) Знаходимо константу приведення:
.
Таким чином, нижньою межею множини всіх гамільтонових контурів буде число .
5) Знаходимо ступеня нулів повністю наведеної матриці. Для цього як би замінити в ній всі нулі на знак «?» і встановлюємо суму мінімальних елементів відповідного рядка і стовпця. Ступені нулів записані в правих верхніх кутах клітин, для яких .
6) Визначаємо максимальну ступінь нуля. Вона дорівнює 19 і відповідає клітині (1, 5). Таким чином, претендентом на включення до гамільтонів контур є дуга (1, 5).
7) Розбиваємо безліч всіх гамільтонових контурів на два: і . Матрицю з дугою (1; 5) отримуємо табл.2 шляхом викреслювання рядка 1 і стовпця 5. Щоб не допускати утворення негамільтонова контуру, замінюємо елемент (5; 1) на знак «?».
|
ji |
1 |
2 |
3 |
4 |
6 |
|
|
2 |
0 |
? |
8 |
0 |
8 |
|
|
3 |
22 |
0 |
? |
26 |
4 |
|
|
4 |
3 |
0 |
17 |
? |
0 |
|
|
5 |
? |
0 |
17 |
10 |
47 |
|
|
6 |
37 |
12 |
0 |
2 |
? |
8) Матрицю гамільтонових контурів отримаємо з таблиці 2 шляхом заміни елементу (1, 5) на знак «?».
|
ji |
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
? |
5 |
14 |
17 |
? |
13 |
5 |
|
|
2 |
0 |
? |
8 |
0 |
30 |
8 |
||
|
3 |
22 |
0 |
? |
26 |
14 |
4 |
||
|
4 |
3 |
0 |
17 |
? |
23 |
0 |
||
|
5 |
7 |
0 |
17 |
10 |
? |
47 |
||
|
6 |
37 |
12 |
0 |
2 |
18 |
? |
||
|
14 |
9) Робимо додаткове приведення матриці контурів: : = 0. Нижня межа множини дорівнює .
10) Знаходимо константу приведення для множині контурів:. Отже, нижня межа множини дорівнює .
11) Порівнюємо нижні межі підмножин і . Так як , то подальшого розгалуження піддаємо множини.
На рис.1 представлено розгалуження по дузі (1, 5).
рис.1
Переходимо до розгалуження підмножини . Його наведена матриця представлена в таблиці нижче.
|
ji |
1 |
2 |
3 |
4 |
6 |
|
|
2 |
03 |
? |
8 |
02 |
8 |
|
|
3 |
22 |
04 |
? |
26 |
4 |
|
|
4 |
3 |
00 |
17 |
? |
04 |
|
|
5 |
? |
010 |
17 |
10 |
47 |
|
|
6 |
37 |
12 |
010 |
2 |
? |
12) Дізнаємося ступеня нулів матриці. Претендентами на включення до гамільтонів контур будуть кілька дуг (5, 2) і (6, 3). Для подальших розрахунків виберемо дугу (6, 3). Розбиваємо множину на дві підмножини: і (табл. 3 та 4). Щоб не допустити утворення негамільтонова контуру, у таблиці 3 замінюємо елемент (3; 6) на знак «?»
Табл.3
|
ji |
1 |
2 |
4 |
6 |
|
|
2 |
0 |
? |
0 |
8 |
|
|
3 |
22 |
0 |
26 |
? |
|
|
4 |
3 |
0 |
? |
0 |
|
|
5 |
? |
0 |
10 |
47 |
Табл.4
|
ji |
1 |
2 |
3 |
4 |
6 |
||
|
2 |
0 |
? |
8 |
0 |
8 |
||
|
3 |
22 |
0 |
? |
26 |
4 |
||
|
4 |
3 |
0 |
17 |
? |
0 |
||
|
5 |
? |
0 |
17 |
10 |
47 |
||
|
6 |
37 |
12 |
? |
2 |
? |
2 |
|
|
8 |
Визначимо константи приведення для цих матриць, . Отже, , . Так як , то подальшого розгалуження підлягає підмножина . Знаходимо ступеня нулів матриці.
|
ji |
1 |
2 |
4 |
6 |
|
|
2 |
03 |
? |
02 |
8 |
|
|
3 |
22 |
022 |
26 |
? |
|
|
4 |
3 |
00 |
? |
08 |
|
|
5 |
? |
010 |
10 |
47 |
Претендентом до включення в гамільтонів контур стане дуга (3, 2). Розбиваємо множину на дві і .
|
ji |
1 |
4 |
6 |
||
|
2 |
0 |
0 |
8 |
||
|
4 |
3 |
? |
0 |
||
|
5 |
? |
10 |
47 |
10 |
Очевидно, , . Отже, чергового розгалуження потрібно піддати підмножина .
|
ji |
1 |
2 |
4 |
6 |
||
|
2 |
0 |
? |
0 |
8 |
||
|
3 |
22 |
? |
26 |
? |
22 |
|
|
4 |
3 |
0 |
? |
0 |
||
|
5 |
? |
0 |
10 |
47 |
Переходимо до розгалуження підмножини . Його наведена матриця представлена в таблиці нижче.
|
ji |
1 |
4 |
6 |
|
|
2 |
03 |
00 |
8 |
|
|
4 |
3 |
? |
011 |
|
|
5 |
? |
037 |
37 |
Визначаємо ступеня нулів. Претендентом на включення до гамільтонів контур є дуга (5, 4). Розбиваємо безліч на дві підмножини: і .
|
ji |
1 |
6 |
|
|
2 |
0 |
8 |
|
|
4 |
3 |
0 |
|
ij |
1 |
4 |
6 |
||
|
2 |
0 |
0 |
8 |
||
|
4 |
3 |
? |
0 |
||
|
5 |
? |
? |
37 |
37 |
Знаходимо нижні межі , . Отже, чергового розгалуження потрібно піддати підмножина . Але його матриця має розмірність . Тому в гамільтонів контур слід включити дуги, що відповідають у матриці нульовим елементам. Це дуги (2; 1) і (4, 6).
На рис.2 представлено дерево розгалужень. Визначимо отриманий гамільтонів контур. До нього увійшли дуги . Довжина контуру дорівнює . Так як кордони обірваних гілок більше довжини контуру 1 - 5 - 4 - 6 - 3 - 2 - 1, то цей контуру має найменшу довжину.
Рис.2
гамільтон модель задача комівояжер