Главная страница

РГР_М_1_. Решение задач линейного программирования в пакетах Mathcad и ms excel


Скачать 1.5 Mb.
НазваниеРешение задач линейного программирования в пакетах Mathcad и ms excel
Дата19.12.2021
Размер1.5 Mb.
Формат файлаdoc
Имя файлаРГР_М_1_.doc
ТипЛабораторная работа
#309155
страница6 из 7
1   2   3   4   5   6   7

Лабораторная работа 4. Реализация алгоритмов решения задачи коммивояжёра.



Задача коммивояжера и ее модификации часто встречаются на практике, например, при планировании различных перевозок [6,7]. Она может быть сформулирована следующим образом. Имеется nгородов, при этом расстояния между любой парой городов iи jизвестны и составляют cij, i,j = 1,…,n. Если между городами нет пути, то cij = . Также полагают, что cii = , i = 1,…,n. Таким образом, исходные данные задачи коммивояжера задаются матрицей C:
.


Коммивояжер, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них ровно один раз, и вернуться в исходный город. Объезд городов, удовлетворяющих этим требованиям, называется маршрутом коммивояжера. Длина маршрута равна сумме расстояний всех входящих в маршрут переездов из города в город. Требуется найти маршрут минимальной длины.

Математическая модель задачи коммивояжера имеет и другие интерпретации, например, задача о перенастройке оборудования, задача о прокладке коммуникаций и другие [7].

Для решения задачи коммивояжера разработан ряд алгоритмов точного и приближенного решения: метод ветвей и границ [3], алгоритмы локального поиска [6] и другие.

В случае небольших n (n < 10) задача коммивояжера может быть решена методом полного перебора всех возможных маршрутов. Число таких маршрутов равно n!/2.

При больших n точное решение задачи, как и в случае задачи о рюкзаке, может потребовать значительных затрат машинного времени. Поэтому актуальной является разработка приближенных алгоритмов. Самый известный приближенный алгоритм – это так называемый алгоритм “иди в ближайший” или “жадный” алгоритм. Он заключается в следующем. Из текущего города коммивояжер идет в ближайший город, в котором он еще не был, а после обхода всех городов возвращается в исходный город.


Варианты заданий. Разработать алгоритм полного перебора и «жадный» алгоритм для задачи коммивояжера [8]. Найти точное и приближенное решение задачи коммивояжера, используя реализованные алгоритмы.





1)



6

9

2

4




6



2

6

2




6

3



3

3




5

7

3



6




3

2

2

5



























2)



9

12

7

10




9



7

2

4




2

4



3

5




8

7

1



5




3

4

3

5









3)



3

8

2

4




2



1

4

3




2

2



4

5




3

6

4



2




9

1

10

5



























4)



2

7

8

4




3



2

2

8




9

8



3

3




6

1

1



7




3

5

2

4









5)



6

1

3

6




1



5

7

3




2

7



4

1




3

1

9



3




1

4

5

3



























6)



4

6

3

4




5



2

5

4




9

2



2

3




3

3

2



9




1

7

3

2









7)



1

4

2

6




3



6

8

5




3

9



3

2




1

1

4



5




8

4

2

4



























8)



4

7

9

4




3



1

3

2




10

9



1

7




4

6

1



9




5

2

3

7


1   2   3   4   5   6   7


написать администратору сайта