Определение оптимального замкнутого маршрута
Рисунок 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={ |
Популярные материалы:
Общие вопросы охраны труда
Охрана труда — система правовых, социально-экономических, организационно-технических, санитарно-гигиенических и лечебно-профилактических мероприятий и средств, направленных на сохранение здоровья и трудоспособности человека в процессе раб ...
Методы амортизации
Линейный, согласно которому амортизируемая стоимость объекта равномерно списывается (распределяется) в течение срока его службы. Предполагается, что амортизация зависит только от длительности срока службы. Сумма амортизационных отчислений ...
Выбор расчетных положений и определение сил, действующих на рыхлитель
В процессе работы на дорожно-строительную машину действуют два вида сил: активные силы (сила тяжести машины и рабочего оборудования, сила тяги машины, силы, приложенные к штоку исполнительного гидроцилиндра и.т.п.) и реактивные силы, кото ...
