Определение оптимального замкнутого маршрута
Рисунок 2.2 – Схема возможных маршрутов коммивояжера
Постановка задачи. Имеется п пунктов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Задана матрица lij транспортных расстояний между этими пунктами (время перевозки или поездки из пункта i в пункт j). Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным.
Решение. Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j - номера пунктов выезда и въезда, lij – расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что lij в общем случае может быть не равно расстоянию в обратном направлении lij ≠ lji.
Таблица 2.1 - Расстояния между пунктами
|
Из пункта i |
В пункт j | |||||
|
1 |
2 |
3 |
4 |
5 |
6 | |
|
1 |
l11 |
l12 |
l13 |
l14 |
l15 |
l16 |
|
2 |
l21 |
l22 |
l23 |
l24 |
l25 |
l26 |
|
3 |
l31 |
l32 |
l33 |
l34 |
l35 |
l36 |
|
4 |
l41 |
l42 |
l43 |
l44 |
l45 |
l46 |
|
5 |
l51 |
l52 |
l53 |
l54 |
l55 |
l56 |
|
6 |
l61 |
l62 |
l63 |
l64 |
l65 |
l66 |
Построим математическую модель задачи, введя булевы переменные:
|
xij={ |
Популярные материалы:
Сложность и надёжность судового дизеля
Значение технического термина «сложность» прежде всего связана с многоэлементностью, составным характером того или иного устройства, явления.
Сложные - это общее название системы, состоящих из большого числа неодинаковых взаимосвязанных ...
Перечень вопросов, подлежащих исследованию в автотехнической экспертизе
1. Расчет скорости движения ТС перед началом торможения.
2. Определение места расположения ТС относительно места наезда на пешехода в момент возникновения опасности.
3. Определение величины остановочного пути ТС в сложившейся дорожно-тр ...
Пульт управления
На станциях, где строилась маршрутно-релейная централизация неблочного типа, в качестве аппарата управления применяли пульт табло. Лицевая панель пульта выполнена в виде светосхемы станции, на которой расположены кнопки маршрутного управл ...
