Файл: информационные технологии.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Методичка

Дисциплина: Информатика

Добавлен: 19.10.2018

Просмотров: 1245

Скачиваний: 10

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Задание 1. Решение задач линейного программирования в MS Excel.

Варианты заданий. Решить задачи ЛП в MS Excel.

Задание 2. Решение транспортной задачи в пакете MS Excel.

Варианты заданий. Решить транспортную задачу в MS Excel.

Задание 3. Решение задачи о рюкзаке приближенными и точными алгоритмами.

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






Задание 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



9)

3

7

3

8


9

2

2

4


7

9

9

3


4

7

3

9


5

1

5

5



10)

3

1

2

3


8

3

4

3


3

1

6

2


1

8

9

4


3

7

4

1









11)

8

4

7

3


9

3

1

8


4

9

4

7


3

3

6

5


6

4

2

6









12)

4

8

5

3


6

4

5

2


1

5

9

2


11

3

12

4


2

3

7

6


13)

4

9

2

1


9

1

11

5


7

4

1

3


7

6

3

3


2

11

4

4








14)

2

10

5

3


8

7

7

4


4

3

4

3


1

6

3

5


5

4

8

4



15)

6

3

1

6


4

3

5

3


9

3

4

4


2

6

2

7


3

1

1

9









16)

8

3

9

2


4

9

3

2


6

1

4

3


2

3

8

4


4

1

1

9



17)

1

3

1

3


2

9

4

2


9

3

7

5


7

2

1

7


1

4

6

3









18)

5

2

3

9


3

3

4

3


1

8

4

8


2

3

2

5


4

5

7

2



19)

4

1

3

6


7

2

4

4


4

9

1

5


8

1

4

3


3

9

2

3









20)

5

3

5

6


1

6

9

4


5

2

10

1


3

6

4

9


4

5

2

3



21)

6

8

2

4


1

6

4

3


9

3

6

4


5

5

2

7


3

2

1

3









22)

4

3

7

2


8

6

1

2


4

9

2

3


2

3

8

4


4

5

1

9










23)

7

3

1

3


6

9

4

3


9

3

7

5


4

5

2

7


1

4

6

3






















24)

5

2

3

3


3

3

4

2


1

2

9

8


2

3

2

5


4

5

4

2



25)

4

3

2

6


4

9

5

1


7

3

3

4


2

6

1

7


3

5

1

9









26)

4

3

1

2


8

7

3

5


4

2

4

3


2

3

2

6


4

5

1

9



27)

1

3

2

3


8

5

4

2


6

3

7

3


3

2

1

4


9

4

2

3









28)

5

4

3

3


8

3

4

2


1

6

4

3


2

3

1

5


4

5

7

9



29)

8

1

3

4


2

2

4

4


3

10

2

5


8

7

4

6


3

9

2

3









30)

8

3

5

6


7

6

4

4


5

2

2

1


3

3

4

7


4

6

2

3



22


Смотрите также файлы