Метод коммивояжёра

i j12345678min1∞020∞∞∞∞∞2∞∞0∞74∞∞∞320∞0385∞∞42∞0∞∞5∞∞∞5∞6∞∞∞0∞306∞3740∞7007∞∞∞1∞∞∞008∞∞∞∞41∞∞∞min∞∞∞∞000∞∞Включаем ребро (8,7), исключая все элементы 8-ой строки и 7-го столбца, а элемент 7,8 заменяем надля исключения образования негамильтонова цикла. В результате получаем следующую сокращенную матрицу:i j1234568min1∞020∞∞∞∞2∞∞0∞74∞∞320∞038∞∞42∞0∞∞5∞∞5∞6∞∞∞0306∞3740∞007∞∞∞1∞∞00min∞∞∞∞0031Сумма констант приведения сокращенной матрицы равна 1. Нижняя граница подмножества (8,7) равна: H(8,7) = 16 +3 =19 < 19. Поскольку нижняя граница этого подмножества (8,7) меньше, чем подмножества (8*,7*), то ребро (8,7) включаем в маршрут.Определяем следующее ребро ветвления.i j12345681∞020(0)∞∞∞20∞0(1)∞16∞320(0)∞413∞42∞0∞∞1∞5∞62∞∞0(1)36∞3740(1)∞07∞∞51∞80Так как наибольшая сумма констант совпадает, то выберем одну из них, например, для ребра (6,5), следовательно, множество разбивается на два подмножества (6,5) и (6*,5*). Нижняя граница гамильтоновых циклов этого подмножества: H(6*,5*) = 16 + 2 = 18.Аналогичные преобразования приводят к оптимальному решению:Представим решение на графе (рисунок 3).Рисунок 3 – Результаты решения задачи коммивояжераЗаключениеАнализ объектов, процессов, явлений и систем предполагает не только исследование понятийного аппарата, но и оценку изменений, что наиболее целесообразно проводить с применением методов математического моделирования, что позволяет исследовать состояние объекта исследования в различных условиях.В рамках настоящего исследования для достижения цели и задач выполнен теоретический анализ особенностей решения задачи коммивояжера, сформулированы основные определения и понятия теории графов, которые составляют основу для решения задачи коммивояжера.Кроме того, приведена классификация зада коммивояжера по различным основания.В практической части настоящего исследования представлена практическая реализация решения задачи коммивояжера. Анализ показал, что математическое моделирование обладают широким спектром методов и средств для анализа, оценки и исследования различных объектов, процессов, явлений и систем, что проявляется в универсальности их использования на практике.Список использованной литературыАсанов М.О., Баранов В.А., Расин В.В. Дискретная математика: Графы, Матроиды, Алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2014, 288 с.Агальцов, В.П. Математические методы в программировании: Учебник / В.П. Агальцов, И.В. Волдайская. - М.: ИД ФОРУМ, 2015. - 240 c.Баллод Б.А. Методы и алгоритмы принятия решений в экономике: учебное пособие/ Баллод Б.А., Елизарова Н.Н.— М.: Финансы и статистика, 2014.— 224 c.Введение в математическое моделирование. Учебное пособие / Под ред. В.П. Трусова, М.: Логос, 2014 г. 440с.Колесников А.В., Кириков И.А., Листопад С.В., Румовская С.Б., Доманицкий А.А. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред. А.В. Колесникова. — М.: ИПИ РАН, 2014. — 295 с.Князьков, В. С. Введение в теорию графов / В. С. Князьков, Т. В. Волченская. — 2-е изд. —М. : Интернет-Университет Информационных Технологий (ИНТУИТ), 2016. — 76 c.Лебедев В.В. Математическое моделирование социально-экономических процессов / В.В. Лебедев. - М.: Наука, 2015. – 229 с.Седова, Н. А. Теория ориентированных графов: учебное пособие / Н. А. Седова, В. А. Седов. —Саратов : Ай Пи Эр Медиа, 2019. — 77 c.Таха, Хемди А. Введение в исследование операций, 8-издание,: Пер. с англ. – М.: Издательский дом «Вильямс», 2015. – 912 с.: ил. – Парал. Тит.англ.Ульянов М.В., Фомичев М.И. Ресурсные характеристики способов организации дерева решений в методе ветвей и границ для задачи коммивояжера // Бизнес – информатика, № 4. 2015. С. 54-62.Федосеев В.В. Математическое моделирование в экономике и социологии труда. Методы, модели, задачи: учебное пособие/ Федосеев В.В.— М.: ЮНИТИ-ДАНА, 2014.— 167 c.Храмова, Т. В. Дискретная математика. Элементы теории графов: учебное пособие / Т. В. Храмова. —Новосибирск : Сибирский государственный университет телекоммуникаций и информатики, 2014. — 43 c.