Определение оптимального замкнутого маршрута
Рисунок 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={ |
Популярные материалы:
Составление рациональных транспортных схем и
возможных вариантов закрепления флота
Движение судов при перевозках грузов должно быть организованно так, чтобы производительность работы флота судоходного предприятия была наибольшей, а себестоимость перевозок наименьшей, что достигается минимальными балластными пробегами.
...
Анализ технологической операции
025 Операция. Шлифовальная. После проведения всех основных восстановительных
операций необходимо произвести механическую обработку для доведения до номинального размера. Так как припуск на механическую обработку невелик (0,13мм), то сразу ...
Изучение требований безопасности к технологическому процессу и оборудованию
депо автосцепной ремонт неисправность
Во избежание случаев травматизма, повреждения инструмента, оборудования запрещается находиться на рабочих местах, производственных помещениях, территории депо в состоянии алкогольного, наркотического ...
