ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута сообщения между городами не существует, а также для всех i=j полагаем, что dij=?. На этом основании расстояния между городами удобно представить в виде матрицы.
Рис. 1. Неориентированный граф задачи коммивояжера
Если городам поставить в соответствие вершины графа (рис. 1), а соединяющим их дорогам дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной, а длина контура определяется суммой длин всех дуг, входящих в контур. Таким образом, необходимо построить кольцевой маршрут проезда всех городов минимальной длины, начиная с любого пункта и в любую сторону.
Поскольку всего городов п, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько - оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т. е. . Расстояния между городами запишем в виде соответствующей матрицы и обозначим ее через D. Если в задаче n городов, то D является матрицей размером с неотрицательными элементами, которые отображают длины дуг в сети городов. При n=5 количество возможных, вариантов маршрутов равно. Расстояния между городами заданы матрицей в табл. 1.
Таблица 1
I J |
1 |
2 |
3 |
4 |
5 |
1 |
? |
90 |
80 |
40 |
100 |
2 |
60 |
? |
40 |
50 |
70 |
3 |
50 |
30 |
? |
60 |
20 |
4 |
10 |
70 |
20 |
? |
50 |
5 |
20 |
40 |
50 |
20 |
? |
Маршрут можно представить в виде замкнутого контура, представляющего собой кольцевой маршрут, например, для графа, изображенного на рис. 1. Возможный вариант можно записать в виде совокупности соответствующих пар дуг:
Длина маршрута равна сумме соответствующих длин дуг матрицы расстояний, тогда целевую функцию можно записать так:
Для любого допустимого маршрута каждая строка и каждый столбец матрицы расстояний D содержат только по одному элементу. Решением задачи является определение кольцевого маршрута минимальной длины.
Похожие статьи
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
ВВЕДЕНИЕ - Задача коммивояжера
Данная работа посвящена теме "Задача о коммивояжере". Задача коммивояжера заключается в определении такой последовательности объезда городов, которая...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) - Линейное программирование в экономике
Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между...
-
В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...
-
Общая постановка задачи исследования операций - Экономико-математические методы
Все факторы, входящие в описание операции, можно разделить на две группы: Постоянные факторы (условия проведения операции), на которые мы влиять не...
-
Найти при помощи метода ячеек значение интеграла , Где - область, ограниченная функциями . 2. Теоретическая часть Рассмотрим K-мерный интеграл вида: (1)...
-
Постановка задачи - Экономико-математические методы
Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого...
-
Введение - Постановка задачи прогнозирования продуктивности агроэкосистем
В последнее время все чаще возникают трудноформализуемые задачи, то есть такие, для которых алгоритм решения либо не является единственным, либо не...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Рассматриваемая задача оптимизации ИП основывается на двухкритериальной модели Г. Марковица с незначительной корректировкой (вместо поиска долей каждого...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Постановка задачи - Методика решения задачи целочисленного программирования
Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...
-
ЗАКЛЮЧЕНИЕ, СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ - Задача коммивояжера
Задача коммивояжер граф моделирование В данной курсовой работе был рассмотрен один из видов задач теории графов и сетевого моделирования "Задачу о...
-
Постановка задачі - Економетричні моделі
Задача. Для виготовлення чотирьох видів продукції використовують три види сировини. Запаси сировини, норми його витрати і прибуток від реалізації...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Постановка задачи За сельскохозяйственной артелью "Горизонт" закреплено 3 890 га сельскохозяйственных угодий, в том числе 3406 га пашни, 389 га сенокосов...
-
Данные об исследуемой культуре - Постановка задачи прогнозирования продуктивности агроэкосистем
В результате численных экспериментов были обнаружены следующие недостатки модели: Структуру сети и ее обучение необходимо проводить под каждую конкретную...
-
Обслуживание с ожиданием - Задачи линейного програмирования
СМО с ожиданием распространены наиболее широко. Их можно разбить на 2 большие группы - Разомкнутые и Замкнутые . Эти системы определяют так же, как...
-
Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Стан об'єкта керування характеризується n-мірної вектор функцією, наприклад, функцією часуТак, шестивимірна вектор-функція часу цілком визначає положення...
-
На підприємствах, основним видом діяльності яких є торгівля, головним об'єктом керування з точки зору економіки виступає ланцюжок "гроші - постачальник -...
-
Організаційна структура підприємства ЗАТ "Годинникар" є юридичною особою і діє на підставі статуту і законодавства України. Підприємство створено...
-
Одним із перспективних напрямів при дослідженні кристалів ZnS:Mn є дослідження температурних характеристик його спектрів. Нова інформація в цьому напрямі...
-
Постановка задачи. - Оценка чувствительности рисков при изменении определяющих факторов
Вернемся к постановке задачи анализа чувствительности приоритетов инновационно-инвестиционных проектов. Выше отмечено, насколько широка область их...
-
Содержательная постановка задачи. - Методика решения задачи целочисленного программирования
Нефтеперерабатывающий завод производит три вида продукции: бензин, керосин и дизельное топливо. Процесс переработки нефти происходит в два этапа: этап...
-
Пусть - вектор параметров задачи (вектор варьируемых параметров), где - n-мерное арифметическое пространство (пространство параметров). Множеством...
-
Обычно, для различных интервалов энергий используют разные типы установок, которые предназначены для измерения спектров нейтронов методом времени...
-
Литература - Многокритериальная постановка задачи выбора проектов целевых программ
1. Залиханов М. Ч. Устойчивое развитие России: перспективы и угрозы // Безопасность Евразии. 2001. №2. С. 518-525. 2. Кочкаров А. А., Малинецкий Г. Г....
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Экономические задачи, сводящиеся к транспортной модели Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида...
-
Обычно субъект экономической жизни стремится достичь сразу многих целей. Например, он стремится одновременно следовать и внутренним, и внешним целям, тем...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Как известно, человечество в своем стремительном развитии старается все более расширить сферы своей деятельности, сталкиваясь при этом с множеством новых...
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера