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

Предметом исследования в настоящей диссертации являются задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений (МО). Упомянутые дискретно-непрерывные экстремальные задачи возникают в качестве естественного развития задачи коммивояжера (ЗК) [30]. Последняя связана с оптимизацией маршрута при посещении конечной системы «городов» (под маршрутом понимается перестановка индексов «городов», соответствующая очередности их обхода) в условиях заданной матрицы затрат (каждый элемент матрицы есть величина затрат на перемещение из «города» с номером, равным индексу строки, в «город» с номером, равным индексу столбца). Для целей решения ЗК построено много алгоритмов, точных и приближенныхсм. в этой связи [30]—[32]. Сейчас отметим только метод ветвей и границ [37, с. 37] и модификацию метода динамического программирования (ДП) для решения ЗК [3], [38]- последний будем активно использовать в условиях более общей задачи маршрутизации последовательного обхода множеств. Решение ЗК связано с перебором очень большого числа вариантов (АН вариантов в задаче обхода N «городов»). Поэтому большое значение имеет построение приближенных методов решения ЗК (простейший метод такого рода базируется на примитивном принципе: иди в «ближайший город»).

Многочисленные потребности решения прикладных задач вынуждают рассматривать различные обобщения ЗК. В числе последних особо отмстим задачу маршрутизации последовательного обхода множеств (см., в этой связи, задачи посещения кластеров, упоминаемые в [30, с.7]- кроме того, см. исследования [28], [50], [51]). Это могут быть задачи, имеющие смысл облета островов архипелага, задачи размещения компонент радиоаппаратуры на печатных платах, простейшие модели задач авиапожарного патрулирования лесов. Упомянутые (и рассматриваемые далее) задачи маршрутизации последовательного обхода множеств являются, в отличие от ЗК (и «прямых» ее обобщений) дискретно-непрерывными экстремальными задачами: наряду с выбором нумерации элементарных задач (дискретная составляющая), требуется оптимизировать трассы движения по множествам (непрерывная компонента). Последний аспект является особенно существенным в маршрутных задачах управления, когда требуется оптимизировать перемещение динамической системы по множествам в фазовом пространстве этой системы. Особо отметим в этой связи подход, развиваемый свердловской школой H.H. Красовского. Речь идет, в частности, о построении вариантов принципа максимума JT.C. Поитрягина [35], базирующихся па идеях двойственности [25] линейных задач управления и задач выпуклого программирования. Данное направление связано прежде всего с работами H.H. Красовского, А. Б. Куржанского, Ю. С. Осипова и А. И. Субботина. На этой основе в [10], [11] были разработаны конструкции решения задач последовательного управления линейными системами, логически связанные с проблемой оптимизации трасс в задаче последовательного обхода множеств (отметим вариант принципа максимума JT.C. Понтрягина для нелинейной задачи последовательного управления в [12], [13], а также исследования Ю. И. Бердышева [Т]—[9] в области решения задач управления, связанных с посещением упорядоченной системы множеств). Игровые варианты задач последовательного управления рассматривались в работах [27], [29], [52]. Заметим, что некоторые маршрутные (по смыслу) задачи оптимизации на классе ломаных рассматривались в [5]- при этом использовались методы теории приближения функций.

В [20] был построен вариант метода ДП для решения дискретно-непрерывной задачи последовательного обхода конечной системы множеств в конечномерном пространстве. За этой статьей последовала серия работ, развивающая подход на основе метода ДП для различных классов задач дискретно-непрерывной оптимизации. Рассматривались задачи последовательного обхода сечений МО [18], [23], [39], [40], [45], [48] (особенность исследований в [39], [40], [45], [48] связана с допущением о том, что вычисления в схеме решения, использующей метод ДП, выполняются с погрешностями). В [21] была построена «сквозная» процедура решения маршрутно-распределительной задачи последовательного обхода множеств несколькими участниками, основанная на методе ДП. Развитие этих методов стимулировало исследования в области задач распределения заданий между исполнителями [22], [36], [46]. Одно из естественных возможных применений этих исследований связано с задачей нескольких коммивояжеров. Разумеется, конструкции ДП, применяемые в задачах последовательного обхода множеств, имеют своей основой обшую теорию, связанную с работами Р. Беллмана [2], [4]- абстрактные версии ДП и решения конкретных классов задач дискретной оптимизации с использованием метода ДП см. в [33]. Наконец исследования [3], [38] в области построения варианта метода ДП для ЗК послужили естественным ориентиром для разработки конструкций метода ДП для задач маршрутизации последовательного обхода множеств и сечений МО.

Данная диссертация состоит из Введения, двух глав и приложения.

1. Александрян P.A., Мирзаханян Э. А. Общая топология. — М.: Высшая школа, 1979. — 336 с.

2. Беллмаи Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1974 432 с.

3. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. — М.: Мир, 1964. — Т. 9- С. 219−228.

4. Беллман Р., Калаба Р. Динамическое программирование и основы современной теории управления. М.: Наука, 1969.

5. Бердышев В. И., Кондратьев В. П. О наилучшей траектории, соединяющей упорядоченный набор множеств. Свердловск: ИММ УНЦ АН СССР, 1986.

6. Бердышев В. И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложений. — Екатеринбург: УрО РАН, 1999. 295 с.

7. Бердышев Ю. И. Об одной задаче последовательного сближения нелинейной управляемой системы третьего порядка с группой движущихся точек // ПММ. 2002. Т. 66. Вып. 5. С. 742−753.

8. Бердышев Ю. И. О задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнения. 2002. Т. 38. № 11. С. 1451−1461.

9. Бердышев Ю. И. Об оптимальном по быстродействию последовательном обходе нелинейной управляемой системой третьего порядка совокупности точек // Изв. Академии наук. Теория и системы управления. 2002. № 3. С. 41−48.

10. Бердышев Ю. И., Ченцов А. Г. К вопросу о редукции некоторых линейных задач оптимального управления с интегральными ограничениями // Кибернетика. 1990. № 4. С. 59−64.

11. Бердышев Ю. И., Ченцов А. Г. Оптимизация функционала на классе ломаных // Некоторые вопросы оптимизации разрывных функций. Свердловск, 1984. С. 29−42.

12. Бердышев Ю. И., Ченцов А. Г. О некоторых задачах последовательной оптимизации управляемых систем // Рукопись в деп. в ВИНИТИ. — 1983. № 109−83 Деп. — 99 с.

13. Бердышев Ю. И., Ченцов А. Г. Оптимизация взвешенного критерия в одной задаче управления // Кибернетика. 1986. № 2. С. 59−87.

14. Буслаева JI.T., Ченцов А. Г. К вопросу о декомпозиции процесса последовательного выбора вариантов // Математическое моделирование. — 1991. Т. З, т. — С. 103−113.

15. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. — М.:Наука, 1977.— 624с.

16. Данфорд Н., Шварц Дж.Т. Линейные операторы. Общая теория.— М.: Изд-во иностр. лит-ры, 1962. — 895с.

17. Деньдобренко Б. Н., Малика A.C. Автоматизация конструирования РЭА. М.: Высш. школа, 1980. — 384 с.

18. Зобнин Б. Б., Коротасва JI.H., Ченцов А. Г. Об одной задаче маршрутной оптимизации и ее приложениях // Пробл. передачи информации. 1997. Т.ЗЗ. Вып. 4. С. 1−18.

19. Келли Дж.Л. Общая топология.— М.: Наука, 1981— 431 с.

20. Коротаева JI.H., Сесекин А. Н., Ченцов А. Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журнал вычислительной математики и математической физики. 1989. — Т.29, № 8. — С. 1107−1113.

21. Коротаева J1.H., Назаров Э. М., Ченцов А. Г. Об одной задаче о назначениях // Журнал вычислительной математики и математической физики. 1993. — Т. ЗЗ, т. — С. 483−494.

22. Коротаева J1.H., Трухин М. П., Ченцов А. Г. К вопросу о маршрутизации соединений // АиТ. 1997. — № 2. — С. 175−192.

23. Коротаева JI.H., Ченцов А. Г. Об одном обобщении задачи коммивояжера «на узкие места» // Журнал вычислительной математики и математической физики. 1995. — Т.35, № 7. — С. 1067−1076.

24. Красовский H.H. Теория управления движением. — М.: Наука, 1968. 476 с.

25. Красовский H.H. Игровые задачи о встрече движений. — М.: Наука, 1970. 420 с.

26. Красовский H.H., Лукоянов Н. Ю. Задача конфликтного управления с наследственной информацией // ПММ, 1996. Т. 60, Вып. 6. С. 885−900.

27. Лейтен А. К. Некоторые модификации задачи коммивояжера // Тр. ВЦ Тарт. ун-та, 1973. Вып. 28. С. 44−58.

28. Лукоянов Н. Ю. К вопросу вычисления цены дифференциальной игры для позиционного функционала // ПММ, 1998. Т. 62, Вып. 4. С. 586 597.

29. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Вопросы теории // А и Т. 1989. — № 9. — С. 3−34.

30. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Точные алгоритмы // А и Т. 1989. — № 10. — С. 3−29.

31. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Приближенные алгоритмы // А и Т. — 1989. — № 11. — С. 3−26.

32. Мину М. Математическое программирование. М.: Наука, 1990.

33. Панасюк А. И., Панасюк В. И. Асимптотическая магистральная оптимизация управляемых систем. — Минск: Наука и техн., 1986. — 296 с.

34. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. — М.: Наука, 1976. 392 с.

35. Сабирянова К. Г., Ченцов А. Г. Динамическое программирование в задаче оптимизации покрытия. // А и Т. 1994. № 3. С. 54−64.

36. Сергиенко И. В., Каспшицкая М. Ф. Модели и методы решения на ЭВМ комбинаторных задач большой размерности. — Киев: Наукова думка, 1981. -288 с.

37. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. // Кибернетический сборник. — М.:Мир, 1964. Т. 9 — С. 202−218.

38. Ченцов A.A., Ченцов А. Г. О решении задачи маршрутной оптимизации методом динамического программирования // А и Т. 1998. К29. С. 117 — 129.

39. Ченцов A.A., Ченцов А. Г. О решении задачи маршрутной оптимизации методом динамического программирования // Изв. Академии наук. Теория и системы управления. 1999. № 3. С. 76 87.

40. Ченцов A.A., Ченцов А. Г. Редукция задач маршрутной оптимизации // А и Т. 2000. то. С. 136 150.

41. Ченцов A.A., Ченцов А. Г. Об одном приближенном методе решения задач маршрутной оптимизации / Алгоритмы и программные средства параллельных вычислений: Екатеринбург: УрО РАН, 2000 г., Вып. 4. С. 287 302.

42. Ченцов A.A. Метод итераций в обобщенной задаче коммивояжера на узкие места / Алгоритмы и программные средства параллельных вычислений: Екатеринбург: УрО РАН, 2001 г., Вып. 5. С. 287−302.

43. Ченцов A.A., Ченцов А. Г. К вопросу о решении задачи последовательного обхода множеств с использованием «незамкнутой» задачи коммивояжера // А и Т. 2002. № 11.

44. Ченцов А. А., Ченцов А. Г. Маршрутизация последовательного обхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функции Беллмана // Проблемы управления и информатики. 1999 — № 2. — С. 113−127.

45. Ченцов А. Г., Ченцов П. А. К вопросу о построении процедуры разбиtения конечного множества на основе метода динамического программирования // А и Т. 2000. т. С. 129−142.

46. Энгелькинг Р. Общая топология, — М.: Мир, 1986.— 751с.

47. Chentsov А.А., Chentsov A.G.Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations // Mathl. Comput. Modelling. 2001. — Vol. 33, — pp. 801−819.

48. Chentsov A.G., Korotayeva L.N. The Dinamic Programming Method in the Generalized Salesman Problem // Mathl. Comput. Modelling. — 1997. Vol. 25, No.l. — pp. 93−105.

49. Henry-Labordere A.L. The record-balancing problem: a dynamic programming solution of a generalized travelling salesman problem // R. I. R. O. 1969. V. 3 №. P. 43−49.

50. Laporte G., Nobert Y. Generalized travelling salesman problem through n-sets of nodes: an integer programming approach // INFOR. 1983. V. 21. m. P. 61−75.

51. Krasovskii A.N. and Krasovskii N.N. Control under lack of information. Berlin. Berlin etc.: Birkhauser, 1995. 322 p.