Определение оптимального замкнутого маршрута
1,если коммивояжер из пункта i переезжает в пункт j,
0, если не поедет,
где i,j - 1, 2, ., n. Требуется минимизировать выражение:
(2.1)
при следующих ограничениях:
,
где Ui и Uj – произвольные вещественные значения.
Первое ограничение означает, что коммивояжер из каждого пункта выезжает только один раз; второе ограничение означает, что коммивояжер въезжает в любой пункт только один раз; третье ограничение обеспечивает замкнутость маршрута, содержащего п пунктов, и отсутствие петель.
Для решения задач дискретного программирования широко применяются комбинаторные методы, основная идея которых заключается в замене полного перебора всех решений их частичным перебором. Одним из таких методов является .метод ветвей и границ, в основе которого лежат следующие построения, позволяющие существенно уменьшить объем перебора решений:
• вычисление нижней границы (оценки);
• разбиение на подмножества, т. е. ветвление;
• пересчет оценок;
• нахождение решений;
• определение признака оптимальности;
• оценка точности приближенного решения.
Для реализации метода ветвей и границ применительно к задаче о коммивояжере необходимо конкретизировать правила ветвления, вычисления оценок и нахождения решений.
Описание алгоритма метода ветвей и границ. Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем.
1. Обозначим через G0 множество всех циклов, среди которых отыскивается кратчайший цикл t*: l(t*)=min l(t). При этом под циклом будем понимать набор из n упорядоченных пар городов, образующих замкнутый маршрут, который проходит через каждый город только один раз:
t=[(i1,i2),(i2,i3),…,(in-1,in),(in,i1)].
Длина цикла равна (2.2)
2. Вычислим оценку для множества G0.Для этого введем понятие приведенной матрицы и процесса приведения.
Пусть hi=minj Сij,
тогда Cij'=Сij-hi³0 и l(t)=.
Пусть Hj=mini Cij',
тогда Cij''=Cij'-Hj³0 и l(t)=.
Полученная матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается hΣ. Оптимальный план задачи о коммивояжере с матрицей С" является оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l(t) на приведенной матрице будет меньше длины цикла l(t) на исходной матрице на сумму приводящих констант: l(t)=l(t)+hΣ.
Популярные материалы:
Силы, действующие в кривошипно-шатунного механизма
Сила инерции от возвратно-поступательных движущихся масс:
.
Центробежная сила инерции КR является результирующей двух сил:
- силы инерции вращающихся масс шатуна
.
силы инерции вращающихся масс кривошипа
.
Суммарная сила Р (кН):
Р ...
Определение длины вытяжных путей
Длина вытяжных путей рассчитывается по длине составов, подлежащих расформированию и формированию.
Длину вытяжного пути вычисляем по формуле:
= lсост + lдоп , м (6)
где lдоп дополнительная длина вытяжного пути (принимаем 10 м), (м)
То ...
Экономическая целесообразность создания крытого
вагона со сдвижной крышей
Экономическая целесообразность создания крытого вагона со сдвижной стеклопластиковой крышей в соответствии с «Методическими рекомендациями по оценки экономической эффективности инвестиций», утверждёнными ОАО «РЖД» в 2005г. должна основыва ...