Некоторые маршрутные задачи последовательного обхода множеств

• Автор: Ченцов, Алексей Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Екатеринбург
• Количество страниц: 174 с. : ил.

Оглавление

Список сокращений

Введение
Глава I. Модификации метода динамического программирования в задачах последовательного обхода сечений многозначных отображений
1. Введение

2. Обход сечений многозначных отображений

3. Метод ДП в условиях неточного определения функции Веллмана

4. Построение оптимальных маршрутов и трасс

5. Метод ДП для задач, где стоимость перехода зависит от номеров предыдущего и последующего многозначных отображений

6. Некоторые вопросы аппроксимации целевых множеств.

7. Принцип граничных решений

8. Некоторые результаты вычислительного эксперимента.86 Глава И. Итерационные методы в задаче последовательного обхода множеств
1. Введение
2. Эквивалентность задачи последовательного обхода множеств и задачи реконструкции системы "городов".
3. Метод итераций в задаче последовательного обхода..
4. Некоторые результаты вычислительного эксперимента.
Список литературы
Приложение

Список сокращений
ДП — динамическое программирование. ЗК — задача коммивояжера.
ЗР — задача реконструкции.
МО — многозначное отображение.
ОМЗ — основная маршрутная задача.

Введение
Предметом исследования в настоящей диссертации являются задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений (МО). Упомянутые дискретно-непрерывные экстремальные задачи возникают в качестве естественного развития задачи коммивояжера (ЗК) [30]. Последняя связана с оптимизацией маршрута при посещении конечной системы "городов" (под маршрутом понимается перестановка индексов "городов", соответствующая очередности их обхода) в условиях заданной матрицы затрат (каждый элемент матрицы есть величина затрат на перемещение из "города" с номером, равным индексу строки, в "город" с номером, равным индексу столбца). Для целей решения ЗК построено много алгоритмов, точных и приближенных; см. в этой связи [30]—[32]. Сейчас отметим только метод ветвей и границ [37, с. 37] и модификацию метода динамического программирования (ДП) для решения ЗК [3], [38]; последний будем активно использовать в условиях более общей задачи маршрутизации последовательного обхода множеств. Решение ЗК связано с перебором очень большого числа вариантов (N1 вариантов в задаче обхода N "городов"). Поэтому большое значение имеет построение приближенных методов решения ЗК (простейший метод такого рода базируется на примитивном принципе: иди в "ближайший город").
Многочисленные потребности решения прикладных задач вынуждают рассматривать различные обобщения ЗК. В числе последних особо отметим задачу маршрутизации последовательного обхода множеств (см., в этой связи, задачи посещения кластеров, упоминаемые в [30, с.7[; кроме того, см. исследования [28], [50], [51]). Это могут быть задачи, имеющие
Итак, на каждом j-м шаге (у € 1,Л0 имеем уравнение Веллмана
(1.2.8) (для аддитивного критерия) или (1.2.9) (для критерия типа "максимум") в виде (] > 2): в случае аддитивного критерия:
V(xj-hl, N {гь-.,ij-i}) = min min [ck(xj-l,y)+
kel,N{ii,...,ij-i) yeAk(xj-i) (1-4.7)
V{y, (1,N {г‘і,гу_!}) {к})]; в случае критерия тина "максимум":
V(xj-i,l,N{ii,...,ij-i})= min min тах{с*;(ж^_і, у),
У(у, (1, N Оъ..., гх-і}) {А;})).
(1.4.8)
Решая (1.4.7) или (1.4.8), мы находим номер очередного задания ij и точку X■) Є Аі](хіі_і) из "области достижимости" для той позиции, в которой мы в данный момент находимся такие, что справедливы равенства: для аддитивного критерия
1,N {ii,..., ij~і}) — dj(xj-i, xj) + V{xj, 1, N Oi,ij}),
l/0°,i,7V) = Y.CiXxi-uxi) + 10^,1, IV Ob i=i
(1.4.9)
для критерия типа "максимум":
V(Х]-Ь 1, N Оь Ъ-1» = тах(с^.(ж^_1, жД У(х^, 1, IV Ов •••; 0»)>
У (я0,1, IV) = тах(тахсг,(ж;_1, ад), У (т,-, 1, N О'В...; гу})).
/е1,у
(1.4.10)
Этот процесс продолжается до тех пор, пока мы не исчерпаем множество
индексов заданий 1, N, т.е. пока еще есть невыполненные задания. А именно, если мы находимся на Ом шаге, то продолжаем данный процесс, решая уравнение (1.4.7) (для аддитивного критерия) или (1.4.8) (для критерия