Определение оптимального замкнутого маршрута

Информация » Стратегия управления доставкой груза на транспорте » Определение оптимального замкнутого маршрута

Страница 2

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Σ.

Страницы: 1 2 3 4

Популярные материалы:

Смета текущих затрат
Цель составления сметы текущих (эксплуатационных) затрат – обоснованное определение потребности в трудовых, материальных и финансовых ресурсах для выполнения намеченных объемов продукции, определение состава затрат, получение необходимой ...

Расчет фонда заработной платы вспомогательных рабочих
Тарифная зарплата определяется произведением соответствующих должностных окладов на 11 месяцев работы: ЗПТАР=СОКЛ*11, где СОКЛ – оклад, руб. Результаты вычислений сведем в таблицу: Тип деятельности Кол-во чел. Оклад Тарифна ...

Разработка расписания движения грузовых автомобилей
Ритмичная работа подвижного состава на линии невозможна без четкого и оперативного планирования, составления графиков и расписаний движения. График строят в координатах «путь - время». По оси абсцисс в соответствии с принятым масштабом о ...