игры4
.docxМинистерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)
Кафедра комплексной информационной безопасности электронно-вычислительных систем (КИБЭВС)
ЗАДАЧА КОММИВОЯЖЁРА
Отчет по лабораторной работе №4
по дисциплине «Теория игр и исследование операций»
Студент гр. 739-1
_______Климанов М.Д.
08.06.2022
Руководитель
Доцент кафедры КИБЭВС, к.т.н.
_______ Шабля Ю.В.
__.__.2022
Томск 2022
ХОД РАБОТЫ
Для поступления в ВУЗ или техникум абитуриенту нужно подать документы в разные учебные заведения: «ТУСУР», «СибГМУ», «ТГАСУ», «ТГПУ», «ТПУ», «ТГУ», «ТТИТ», «ТИТ», «ТБМК», «ТПТ». При этом начать и закончить маршрут необходимо из «ТУСУР».
Перемещение между адресами осуществляется пешком. В качестве целевой функции нужно выбрать суммарную длину пути, которую необходимо минимизировать.
С помощью системы 2ГИС требуется составить таблицу с информацией о кратчайшем пути для каждой пары пунктов назначения (рисунок 1).
Рисунок 1 – Таблица с исходными данными
Следующим шагом необходимо выполнить редукцию по строкам и столбцам, используя встроенную функцию «МИН()» (рисунки 2 и 3).
Рисунок 2 – Редукция по строкам
Рисунок 3 – Редукция по столбцам
На рисунке 4 представлена таблица после редукций по строкам и столбцам.
Рисунок 4 – Полученная матрица после редукции по строкам и столбцам
Далее нужно рассчитать оценки нулевых клеток, с помощью встроенной функции «НАИМЕНЬШИЙ()» с параметром 2, которая будет возвращать второе наименьшее число в рамках строки или столбца (рисунок 5).
Рисунок 5 – Поиск вторых наименьших значений по строкам и столбцам
После чего необходимо вычислить оценки для нулевых клеток (рисунок 6).
Рисунок 6 – Оценки для нулевых клеток
Из рисунка видно, что максимальная оценка 0,79 получена для пути из «ТБМК» до «ТПТ». Тогда нужно преобразовать матрицу (рисунок 7),
Рисунок 7 – Матрица после исключения маршрута
Затем нужно снова выполнить редукцию по строкам и столбцам для преобразованной матрицы.
Для полученной редуцированной по строкам и столбцам матрице необходимо вычислить оценки для нулевых клеток.
После нескольких преобразований матрицы нужно составить оптимальный маршрут:
«ТУСУР» - «ТГУ» - «ТГАСУ» - «ТБМК» - «ТПТ» - «ТИТ» - «СибГМУ» - «ТГПУ» - «ТТИТ» - «ТПУ» - «ТУСУР».
При этом суммарная длина маршрута равна 11,44 км (рисунок 8).
Рисунок 8 – Расчет целевой функции
Заключение
В ходе выполнения данной лабораторной работы познакомились с целочисленным линейным программированием на примере задачи коммивояжёра и её реализация в математических пакетах.