Реферат: Нижние оценки в задаче коммивояжера

Нижние оценки в задаче коммивояжера

Примитивная оценка. Плата за выезд i = 1,…, n.

Плата за въезд j = 1,…, n.

Теорема.

Доказательство. Положим 1  i, j  n. Тогда Аналогично, 1  i, j  n, и

∎

Оценка линейного программирования

Введем переменные

Математическая модель

при ограничениях



(исключение подциклов)

xij{0,1}, i,j J.

Заменяя xij{0,1} на 0  xij  1, получаем задачу линейного программирования, которая дает нижнюю оценку для оптимума, не хуже
предыдущей.

1–Деревья для симметричных матриц

Хотим найти гамильтонов цикл минимального веса.
Необходимо найти:

ровно n ребер,

которые покрывают все вершины,

имеют минимальный суммарный вес и

каждая вершина инцидентна ровно двум ребрам.

Заменим последнее условие на следующее:

одна заданная вершина инцидентна ровно двум ребрам.

Ослабили условия, значит, получим нижнюю оценку.

Алгоритм построения 1-дерева

Удаляем заданную вершину и строим остовное дерево минимального веса (алгоритм Крускала, Прима).

Добавляем два ребра минимального веса, проходящих через
заданную вершину, получаем 1-дерево.

^ Задача о назначениях

Дано: n рабочих, n станков,

cij — время выполнения работы i-рабочим на j-м станке.

Найти расстановку рабочих по станкам с минимальным суммарным рабочим временем.

Переменные задачи: .

Математическая модель:

при ограничениях



xij{0,1}, 1 i,j  n.

Оптимальное решение задачи о назначениях дает нижнюю оценку для задачи коммивояжера, не хуже чем оценка 1–деревьев.

Определение. Пусть  = (1,…, n) — некоторый вектор. Элемент cij называется -минимальным, если cij – j cik – k для всех 1 k  n.

Теорема. Пусть для некоторого  существует набор -минимальных элементов (c1 j(1),…, cnj(n)) по одному в каждой строке и столбце. Тогда этот набор является оптимальным решением задачи.

Доказательство. Решение (c1 j(1),…, cnj(n)) является допустимым и



В правой части равенства первая сумма является минимальной среди всех допустимых назначений, а вторая сумма является константой, то есть полученное решение является оптимальным. ∎

Определение. Для вектора  выделим в каждой строке по одному
-минимальному элементу и назовем его -основой. Другие
-минимальные элементы будем называть альтернативными
-основами. Число столбцов матрицы cij без -основ назовем
дефектом.


Общая идея алгоритма

Начинаем с   0. На каждом этапе алгоритма дефект уменьшается на 1, т.е. не более чем за n этапов найдем оптимальное решение задачи.


Описание одного этапа



Выберем столбец без -основы и обозначим его S1.

Увеличить на максимальное так, чтобы все -минимальные элементы остались -минимальными (возможно ). Получим для некоторой строки i1 новый -минимальный элемент назовем его альтернативной основой для строки i1.












S1






























































































i1




Для строки i1 столбец j(i1) с -основой пометим меткой S2.









S2

S1






























































































i1



Увеличим и на максимальное  так, чтобы все -основы остались -минимальными элементами.


Найдем новую альтернативную основу в одном из столбцов S1или S2. Пусть она оказалась в строке i2. Пометим столбец j(i2) меткой S3 и будем продолжать этот процесс до тех пор пока не встретим столбец с двумя или более основами.


S3




S2

S1






















i2






































































i1




Строим новый набор из -основ. Заменой основы в строке назовем следующую операцию: альтернативная основа становится основой, а старая перестает быть основой.

5.1. Произведем замену основ в строке, где лежит последняя альтернативная основа (строка ik). Тогда в столбце j(ik) число основ уменьшится на 1, но останется положительным.


S3




S2

S1






















i2






































































i1


В столбце, где появилась новая основа, возьмем старую основу и в этой строке тоже проведем замену основ и т.д. до тех пор, пока не
доберемся до столбца ^ S1. В итоге, столбец S1 получит основу, а число основ в столбце j(ik) уменьшится на 1.

S3




S2

S1






















i2






































































i1

Упражнение. Оценить трудоемкость алгоритма решения задачи о
назначениях. Придумать алгоритм решения задачи с трудоемкостью O(n3).

Метод ветвей и границ

В основе метода лежит принцип «разделяй и властвуй».

Пусть ^ D — множество допустимых решений задачи

min {f(x) | xD},

и для любого подмножества d  D умеем вычислять:

LB(d) — нижнюю оценку для минимума f(x), xd,

UB(d) — верхнюю оценку для минимума f(x), xd,

т. е.

LB(d)  min {f(x) | xd}  UB(d), для любого d  D.

Основная идея

Пусть x* — текущий рекорд и сначала f(x*) = UB(D). Вычисляем LB(D) и, если LB(D) = UB(D), то STOP, x* — оптимальное решение задачи.
В противном случае разбиваем D на подмножества D = d1  ….  dk.

Для каждого подмножества вычисляем UB(di), LB(di), i = 1,…, k.

Если f(x*) > UB(di), то меняем рекорд.

Если LB(di)  f(x*), то выбрасываем

di, иначе дробим di на подмножества.

Так как D — конечное множество,
топроцесс конечен и дает точное
решение задачи.

Описание метода

На каждом шаге имеется

рекорд x*;

просмотренная часть P  D, для которой f(x)  f(x*), xP;

разбиение множества D \ P на подмножества .

Шаг состоит в следующем.

Выбрать элемент разбиения, например, ;

Вычислить Если то сменить рекорд x*.

Вычислить



Если то добавить к P и перейти к следующему шагу.

Если но в множестве удалось найти наилучший элемент : то добавить
к P; если то положить .

Если но элемент найти не удалось, то разбиваем на подмножества и переходим к следующему шагу, имея новое разбиение для D \ P.

^ Метод В&Г для задачи коммивояжера


Разбиение множества D представляется в виде бинарного дерева.

Каждой вершине дерева соответствует частичный тур и список запретов.

Например, вершине d6 соответствует

частичный тур 1,5 и запреты {4,3}

на выход из города 5.

^ Метод В&Г для задачи коммивояжера

Примитивная нижняя оценка для вершины дерева,

н


с15
апример, d6 при n = 5:



Задача о назначениях:


с53

с54

с51


при c53 = c54 = c51 = +.


Верхняя оценка — алгоритм «Иди в ближайший».

^ Выбор переменной для ветвления

Основная идея — угадать оптимальное решение
на подмножестве и ветвиться по дугам этого тура:

для частичного тура i1,…, ik выбираем минимальный элемент в строке ik матрицы

для частичного тура i1,…, ik строим верхнюю оценку и ветвимся по дуге (i1,…, ik+1).

для частичного тура i1,…, ik решаем задачу о назначениях и ветвимся вдоль цикла, проходящего через вершину ik.

^ Выбор подмножества из разбиения D \ P

Две основные схемы:

многосторонняя схема ветвления, когда выбирается подмножество d такое, что

LB(d ) = min {LB(di) | i = i1,…, ik}.

Среди элементов разбиения выбирается подмножество с наименьшей нижней границей.

односторонняя схема ветвления, когда всегда выбираем последний элемент

Первая схема требует много оперативной памяти, но в среднем просматривает меньше вершин, чем вторая. Возможна комбинация этих схем: сначала первая, пока хватает памяти, затем вторая.

^ Влияние основных элементов на трудоемкость

Верхняя оценка UB

Нижняя оценка LB

Схема ветвления и выбор переменной для ветвления


f(x*)

OPT

H






Итерации


1

2

3

……

H= min LB(di)

i1,…,ik

Задача коммивояжера в Интернет


TSPBIB Home Page http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html

The Hamiltonian Page: Hamiltonian cycle and path problems, their generalizations and variations

http://www.ing.unlp.edu.ar/cetad/mos/Hamilton.html


Fractal Instances of the Traveling Salesman Problem

http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html


DIMACS: The Traveling Salesman Problem

http://www.research.att.com/~dsj/chtsp/


Задача маршрутизации

Дано: множество клиентов J = {2, 3, …, n},

j = 1 — гараж,

множество грузовиков K = {1,…, m}

Qk — грузоподъемность k-го грузовика

qj — вес груза для j-го клиента

сij — расстояние между клиентами i и j.

Найти: набор циклов, начинающихся и заканчивающихся в гараже
j = 1 (по одному циклу на транспортное средство) такой, что суммарная длина циклов была бы минимальной и позволила бы обслужить всех клиентов данным набором транспортных средств.

^ Математическая модель

Переменные задачи






xijk =

1, если транспорт k посещает клиента j сразу после клиента i,

0 в противном случае






yik =

1, если транспорт k посещает клиента i,

0 в противном случае


Модель



при ограничениях





, для всех S  {2,…, n}, kK

yik{0,1}, xijk{0,1}, i,j  J, kK.

Возможные обобщения модели

Каждый клиент имеет «временное окно», в течение которого транспортное средство должно его посетить.

Клиенты могут не только получать продукцию, но и отправлять ее в гараж.

Обслуживание клиентов происходит не мгновенно, а в течение определенного времени: разгрузка, загрузка, оформление документов и т.п.

Транспортное средство может несколько раз вернуться в гараж (пройти несколько циклов).

Транспортное средство имеет временное окно (рабочий день
водителя) для обслуживания клиентов.

Целевые функции

Суммарное расстояние или расход бензина (каждое транспортное средство имеет свой расход на 100 км).

Зарплата водителей и эксплуатационные расходы на транспортные средства.

Оптимизация парка транспортных средств (расширить или
сузить, заменить тяжелые на легкие или наоборот, …).

Оптимальное размещение гаражей, их количество и вместимость.

Системы поддержки решений по оперативному управлению транспортными средствами, замена водителей, форс-мажорные обстоятельства, изменения потребностей клиентов,….






Лекция 4. Задача коммивояжера. Часть 2