Читать курсовая по математике: "Решение задачи коммивояжера методом ветвей и границ" Страница 3


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

переменных , если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений (1)

Условия (2) – (4) в совокупности обеспечивают, что каждая переменнаяравна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).

Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) – (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла.

Для того, чтобы исключить при постановке задачи все возможные подциклы в систему ограничений задачи включают следующее ограничение: , где ,и . 4. Алгоритм решения Дана матрица расстояний, представленная в таблице 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

1

∞

5

14

19

0

15

2

0

∞

8

2

30

10

3

22

0

∞

28

14

6

4

3

0

17

∞

23

2

5

7

0

17

12

∞

49

6

37

12

0

4



Интересная статья: Быстрое написание курсовой работы