Задача коммивояжера (решение методом ветвей и границ + графическое представление процесса ветвления).
Полное описание заданий с исходными данными представлено в демо-файле "Описание работы".
Если вам нужна работа с другими исходными данными (другой вариант), то напишите мне в личку (Marka37) и обсудим подробности.
Работа выполнена в 2020 году. Объем работы – 18 стр. Оформление в Word. Шрифт – 14, интервал – 1,5.
Работа сделана с подробными пояснениями к решению.
Постановка задания
Компания «Альфа» производит бытовую технику, которую ежедневно поставляет в пять магазинов «Домбыт», «Техника», «Атлант», «Техномаркет», «Комфи» с помощью грузового автомобиля. Расстояния между всеми пунктами известны и заданы в километрах (таблица 1).
С целью экономии времени и средств необходимо найти такой маршрут передвижения, при котором, побывав в каждом магазине по одному разу, автомобиль вернулся бы в компанию «Альфа», проделав минимально возможный путь.
Таблица 1
Компания «Альфа» Магазин «Домбыт» Магазин «Техника» Магазин «Атлант» Магазин «Техно-маркет» Магазин «Комфи»
Компания «Альфа» ∞ 14 32 53 8 44
Магазин «Домбыт» 53 ∞ 2 14 30 39
Магазин «Техника» 50 53 ∞ 52 2 17
Магазин «Атлант» 10 58 54 ∞ 52 51
Магазин «Техно-маркет» 18 13 4 58 ∞ 15
Магазин «Комфи» 39 48 46 9 2 ∞
Постановка задания
Компания «Альфа» производит бытовую технику, которую ежедневно поставляет в пять магазинов «Домбыт», «Техника», «Атлант», «Техномаркет», «Комфи» с помощью грузового автомобиля. Расстояния между всеми пунктами известны и заданы в километрах (таблица 1).
С целью экономии времени и средств необходимо найти такой маршрут передвижения, при котором, побывав в каждом магазине по одному разу, автомобиль вернулся бы в компанию «Альфа», проделав минимально возможный путь.
Таблица 1
Компания «Альфа» Магазин «Домбыт» Магазин «Техника» Магазин «Атлант» Магазин «Техно-маркет» Магазин «Комфи»
Компания «Альфа» ∞ 14 32 53 8 44
Магазин «Домбыт» 53 ∞ 2 14 30 39
Магазин «Техника» 50 53 ∞ 52 2 17
Магазин «Атлант» 10 58 54 ∞ 52 51
Магазин «Техно-маркет» 18 13 4 58 ∞ 15
Магазин «Комфи» 39 48 46 9 2 ∞
1. Казанская О.В., Юн С.Г., Альсова О.К. Модели и методы оптимизации. Практикум: уч. пособие - Новосибирск: Изд-во НГТУ, 2012.- 204 с.
2. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное пособие / А.В. Пантелеев, Т.А. Летова. - СПб.: Лань, 2015. - 512 c.
3. Тюхтина А.А. Методы дискретной оптимизации: Часть 1: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2014. – 62 с
