Определение оптимального замкнутого маршрута
Рисунок 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={ |
Популярные материалы:
Мероприятия по обеспечению безопасности дорожного движения
Эффективность и надежность эксплуатации подвижного состава во многом зависит от безопасной работы автотранспорта. В настоящее время этому вопросу уделяется особое внимание. Наше государство выделяет огромные средства, которые направлены н ...
Финансовый анализ проекта
Таблица 3.8 Расчет выручки и дохода от продажи продукции
Наименование показателей
Обозначение
Значение показателей по итогам года
2012
2013
Цена единицы услуги (с НДС), тыс. руб.
р
0,9
0,957
Объем реал ...
Определение ординат для разбивки переводной кривой стрелочного перевода
Начало координат для разбивки переводной кривой расположено на рабочей грани рамного рельса против корня остряка, точка (рис. 3.2).
Координаты точек в конце переводной кривой определяются по формулам:
где - начальное значение орди ...