Автоматика и телемеханика, № 12, 2014
© 2014 г. С.И. СЕРГЕЕВ, д-р физ.-мат. наук (abra_888@mail.ru) (Московский государственный университет экономики, статистики и информатики)
ЗАДАЧА КОММИВОЯЖЕРА НА МАКСИМУМ. I
Известны некоторые оценки результатов оптимального критерия качества для задачи коммивояжера на максимум. Эти оценки составляют для симметричных задач ~ 75 %, а для несимметричных ~ 57 %. Предлагаются оценки: для симметричных задач - больше, чем ~ (99,0-99,7) %, для несимметричных задач - больше, чем ~ (99,0-99,23) %. Все оценки получены увеличением ряда задач, встречающихся при решении задачи коммивояжера на максимум.
1. Введение
Задача коммивояжера (ЗК), как известно из [1—3], имеет многочисленные результаты и заключается в следующем. Имеется N городов, обозначенных номерами i, заданы действительными числами расстояния Cj ^ 0 между городами г и j, где i,j € {l,iV}. При выходе из заданного города требуется обойти оставшиеся N — 1 городов по одному разу и затем вернуться в заданный город так, чтобы общее пройденное расстояние было минимальным (максимальным).
Задача коммивояжера, являясь NP-трудной, относится к числу сложных задач дискретной оптимизации. Число существующих алгоритмов как точных, так и приближенных, разработанных для решения ЗК, превышает несколько сотен, и попытки их классификации предпринимались неоднократно [1—3]. Эффективность приближенных алгоритмов оценивается либо на основании численного эксперимента по сравнению результатов решения на однотипных тестовых задачах, либо на основании гарантированных оценок точности по функционалу, являющихся достаточно грубыми (даже для ЗК на максимум) из-за свойств самих оценок, а не качества решений, получаемых с помощью приближенных алгоритмов. В статье предлагаются новые алгоритмы решения ЗК на максимум (ЗК (на максимум)). Эти алгоритмы опираются на работы [4, ч. III и IV] и [5, 6], посвященные решению ЗК на минимум. Кроме того, для ЗК (на минимум и максимум) предлагаются и приближенные алгоритмы решения задачи.
2. Постановка ЗК
Существует несколько близких формулировок ЗК как задачи линейного целочисленного программирования [1—3]. Выберем среди них в качестве ос-
новной формализацию в виде [4, ч. III и IV; 7]:
(2.1)
I = ^^ ^^ CijUij ^ max,
i&N j&N
(2.2a)
J^uij = 1 j e N,
(2.26)
ieN
= 1, i e N,
j&N
(2.3)
(2.4)
Uij = {0,1}, i, j e N,
X)Euij ^ 1, Z С N,
iezjez
где TV = {1,??.}, Z U Z = W, Cjj ^ 0 - действительные числа и условия (2.4) справедливы для любых подмножеств Z таких, что 2 ^ |Z| ^ п — 2, а символ |Z| обозначает число элементов в подмножестве Z. Связи (2.4) означают, что для любого подмножества Z С N должна найтись пара городов i e Z, j e Z такая, что участок пути из i-го города в j-й содержится в пути коммивояжера.
Как известно, ЗК тесно связана с задачей назначения (ЗН) (2.1)-(2.3) [1-3]. Одними из первых оценок нижних границ для ЗК могут служить оценки ~ О(п3) [8-10] и ~ О(п2'5) [11] для ЗН. Решив первую ЗН с выделенным функционалом, переходим к решению второй ЗН, увеличивая прежний функционал и т.д. вплоть до решения функционала ЗК [12]. Последовательное решение ЗН вплоть до получения ЗК требует времени и неизвестна оценка трудоемкости этого процесса. ЗН используется в [13] для получения ЗК с экспериментальными задачами: t = 5,45 ■ 10-5п3'46 (асимметричная ЗК, n ^ 80) и t = 5,94 ■ 10-5п4'54 (симметричная ЗК, n ^ 30).
Другой алгоритм использования ЗН в ЗК (на минимум) используется в [4, ч. III и IV]. Здесь не требуется обязательного последовательного решения от одной ЗН к другой вплоть до получения решения ЗК [12]. Начиная с решения первой ЗН решают следующую ЗН применением специальных операций ЗН (см. в разделе 4 п.п. 1, 2, 3, 4,а, 4,б) [4, ч. III и IV] и нелинейных разрешающих функций [5, 6]. Такой переход от одной ЗН к другой ЗН отличается от разработанного в [12]. Заметим, что нижняя граница составляет для симметричной ЗК ~ (99,0-99,7) % (экспериментальная оценка) от оптимального критерия качества [1, с. 373], а для несимметричной ЗК ~ (99,0-99,23) % (экспериментальная оценка) [1, с. 367]. Эти границы используются в рамках линейного задания разрешающей функции <^(t, y) и наибольших результатов достигают с применением двухиндексной модели (здесь оценки приведены для задач ЗК (на минимум)). Применение нелинейного задания разрешающей функции <^(t, y) с введением одноиндексной модели ЗК должно увеличить указанные проценты. Заметим, что точные оценки [14-16], отличающиеся от симметричной ЗК (на максимум), составляют ~ 75 % от оптимального решения и ~ 57 % от несимметричной ЗК (на максимум).
Применим к задаче (2.1)-(2.4) теорию, развитую для решения несимметричной ЗК [4, ч. III и IV; 5, 6]. Для этого перейдем от задачи (2.1)-(2.4) к эк-
вивалентной задаче оптимизации многошагового процесса управления с двухмерным аргументом и применим к исследованию последней задачи методы теории оптимального управления в форме достаточных условий оптимальности отыскания глобального минимума [7, 17, 18]. Необходимые результаты по исследованию линейной функции <^(t,y) приведены в разделах 4 и 5, а нелинейной функции - в разделе 6.
3. Реализация элементарной операции улучшения функции ^(t,y)
Будем рассматривать многошаговый процесс управления с двухмерным аргументом, характеризуемый аргументом t, состоянием y и управлением u, пробегающими множества T, Y, U соответственно. Пусть T - прямое произведение множеств Tk (k = 1, 2), где Tk - целочисленный ряд {0,1,..., Tk},
Y и U - векторные пространства размерности n и r соответственно. Каждому t € T поставлено в соответствие подмножество V* прямого произведения
Y х U. Для всех пар функций {y, u} задано множество D допустимых пар с помощью условий
(3.1) (y, u) € V* Vt € T
и с помощью динамических уравнений
/О О N Vti+Ite = /К^ЗА^)) , . -j—.
(3.2а) (i = 0,l,...,Tj, з = 1,2; г =
yti,t2+i = f2(t,y,u)
(3.26) y*=o = 0, yLr, = Уад (г = Ml; i = 1,2),
где i = (ii, i2)• Введем в рассмотрение множества функций fj{t,y,u) = = {fj(t,y,u)} (г = 1,п, j = 1,2). Пусть Е - множество пар функций {у,и}, удовлетворяющих (3.1). На множестве E зададим функционал вида
Т1 — 1 Т2 — 1
(3.3) I = £ £/0(t,y,u),
tl=0 *2=0
где /0(t, y,u) - заданная на T х Y х U функция.
На функции (y, u) € D кроме перечисленных условий наложены дополнительные условия. Введем в рассмотрение множества V* и V* - проекции множества V* на множества U и Y соответственно, S С T и W. Здесь множество S - совокупность значений t = (ti,t2), образующих границу прямоугольника T : 0 ^ t1 ^ Ti, 0 ^ t2 ^ т2; W - множество функций y, заданных на S и таких, что y € V*, t € S. Ставятся две задачи.
А. Отыскание допустимого процесса, где требуется найти последовательность процессов {yt,ut}q С E, сходящуюся в специально оговоренном смысле [7] к D:
(3.4) {yt,ût}q^D.
Б. Максимизация функционала I на D, когда кроме (3.4) от последовательности {yt,Ut}q требуется, чтобы
(3.5) /(yt,щ) —> d = maxi.
Метод решения обеих задач основан на аппарате принципа оптимальности
[17, 18].
Введем в рассмотрение функцию <^(t,y) = {^1,^2}, определенную на прямом произведении T х Y, и построим с ее помощью следующие конструкции:
R(t,y,u) = -<£i[ti + 1,t2,fi(t,y,u)] + <£i(t,y) — — ^2[tl, t2 + 1, /2(t, y, u)] + ^2(t, y) + f 0(t, y, u),
T2 — 1
G[y(t e S)]= E t2=0
tl=T1
T1-1
+ E
tl=0 ¿1=°
t2=T2
¿2=0
(3.6)
^(t) = max R(t,y,u), 0 = maxG[y(t € S)], (y,u)ev1 yew
T1 — 1 T2 — 1
L(p, y, u) = G[y(t € S)] + E E R(t, y, u),
t1=0 t2=0 T1 — 1 T2 — 1
i(p) = 0 + E E^)-
t1=0 t2=0
Пусть П - класс функций ^>(t, y) = {^1, ^>2}, отображающих прямое произведение T х Y в Y, непрерывных и непрерывно-дифференцируемых и, кроме того, имеющих дополнительное условие: функция R(t, y, u) в (3.6) определена и непрерывна, и величины ^(t) и 0 тоже определены. Тогда справедливы следующие результаты при любом ^ € П.
Теорема 1. Чтобы пара функций {y,u} € D максимизировала функционал I на D, достаточно существования такой функции ^>(t,y) = {^1,^2} € € П, чтобы
( R(t,y,u) = fj,(t), t<=T\S;
1 ' j G[y(t € 5)] = в.
Лемма 1. При любом ^ € П (3.8) l(^) ^ d.
Справедливость результатов теоремы 1 и леммы 1 для задачи (3.1)-(3.3) установлена в [4, ч. I] (для ЗК (на минимум)). Универсальный прием решения поставленных задач A и Б состоит в следующем: отыскать последовательность } С П такую, что ) ^ min^en l(^) = d. Искомая последовательность строится с помощью элементарной операции (ЭО) улучшения функции ^>(t, y) начиная с произвольного ^>о € П. Приведем основные конструкции этой операции.
Пусть имеется функция ^>д(¿, у) € П, которой соответствуют в силу конструкций (3.6) Ед(£, у, г/,), Сд[у(1 € 5)] и 1д((р)', множество У*д пар (у,и), обеспечивающих максимум Кд(1,у,и) на множество \¥д функций у(1 € 5), обеспечивающих максимум Сд[у(1 € 5)] на множество Ед пар функций, удовлетворяющих условиям (у, и) € У*д при всех £ € Т\Б] уг € \¥д, ¿ей*. Функцию ^>д(¿, у) будем искать в виде:
(3.9) у) = ^д& у) + Ад у^
где 7д(¿, у) и Ад - функция и положительное число, подлежащие определению. Определим функционал
Т2 — 1 ¿2=0
¿д(У,и) = X)
¿1=Т1 Т1-1 ¿1=0 ¿1=0
¿2 =Т2
+
¿2=0
(3.10) Т1 1Т2 1
¿1=0
+ Е Ё {-^ + 1,*2; Л(*,у,и)] + -
' " ¿2=0
-72(^1,^2 + 1; /2(^,у,м)] + 72(*,
Обозначим через В,д(1,у,и, \), Ед(Х), А) и т.д. конструкции, соответствующие функции = ^>д + Ад7д.
Введем понятие ЭО улучшения функции у). Функция ^>д+1 строится в виде (3.9), где 7д и Ад > 0 выбираются произвольно в пределах требований:
(3.11а) ¿д(у, и) > 0,
хотя бы при одном значении (у,и) € -Кд+1 = Ед(\д)\ и
(3.11б) ^д+1 = ^д + Ад 7д € П.
Условия (3.11б), как правило, легко удовлетворяются априорным заданием свойств функции 7д(¿,у), и реализация ЭО сводится, по сути, к реализации условия (3.11а). Подробности реализации условий (3.11) и характер сходимости решений поставленных выше задач А и Б исследуются в [4, 7]. Применим результаты по реализации ЭО улучшения функции у) к ЗК в форме (2.1)-(2.4).
4. Метод улучшения линейной разрешающей функции ^ (£, у)
Введем в рассмотрение распределение (р, д) = (р^р2, д1^),д2(^))
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.