Метод гілок та меж для рішення задач цілочисельного програмування

курсовая работа

Алгоритм рішення

Дана матриця відстаней, представлена в таблиці 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

гамільтон модель задача комівояжер

Делись добром ;)