Некоторые минимаксные задачи управления и маршрутизации тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Введение.

Глава 1. Задача обхода системы множеств в классе позиционных стратегий

1.1. Постановка задачи последовательного обхода системы множеств в классе позиционных стратегий

1.2. Уравнение Беллмана

1.3. Оптимальная минимаксная стратегия

1.4. Задача на узкие места

1.5. Эвристические стратегии

Глава 2. Минимаксные задачи последовательного управления

2.1. Одна минимаксная задача управления с импульсным ограничением на управление и ее расширение в в классе конечно-аддитивных мер

2.2. Необходимые условия оптимальности обобщенного управления

2.3. Задача последовательного программного уклонения для собственно линейной системы с комбинированным ограничением на управления

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

2.5. Примеры.

Настоящая диссертационная работа посвящена минимаксным задачам последовательного управления с элементами маршрутизации.

В последние годы классические задачи комбинаторной оптимизации (в первую очередь, задача коммивояжера (ЗК), задача о наикратчайших путях (ЗНП), задача о минимальном остовном дереве) стали изучаться в обобщенной постановке, когда вместо фиксированного узла Х{ рассматривается множество М^, которому может принадлежать узел Х{. Преимуществом таких обобщенных постановок задач комбинаторной оптимизации является то, что появляется дополнительная свобода варьировать узлы Х{ для достижения лучшего качества (скажем, при проектировании конкретной технической системы).

В настоящей работе делается следующий шаг в этом направлении, и предлагается постановка, в которой проектировщик не имеет возможности выбирать точки Х{ или управлять ими. Таким образом, получаем игровую ситуацию, когда распоряжение точками Х{ отдается игроку-противнику или (противостоящей) природе. Множествами моделируется (непредсказуемое) поведение точек Х{ (они могут представлять собой, в зависимости от конкретной задачи, помехи, ошибки, возмущения, шумы, сбои и т.п., или разумные управления игрока-противника).

Особый интерес представляют позиционные динамические задачи (ЗК, ЗНП и др.), когда решения принимаются игроками в динамике, в зависимости от предыдущих действий противника. Построение позиционных стратегий управления (т.е. правил принятия решений по принципу обратной связи) является новым, неисследованным и трудным кругом задач. Основной вопрос при решении задач этого класса заключается в следующем: как конструировать позиционное управление в динамической игре с комбинаторным функционалом, и как сформулировать и решить задачу в замкнутом виде?

В настоящей работе вводится и изучается игровая обобщенная ЗК в классе позиционных стратегий. Для постановки и решения задачи используется подход, связанный с минимизацией гарантированного результата в классе позиционных стратегий, см. монографии H.H. Кра-совского, А.И. Субботина, А.Г. Ченцова [25, 27, 63, 95].

Обобщенная (неигровая) ЗК и ее решение методом динамического программирования рассматривались А.Г. Ченцовым и его сотрудниками [23, 83]. Следует отметить, что многие комбинаторные задачи могут быть переформулированы в виде ЗК или обобщенной ЗК. Как отмечается в литературе, ЗК занимает центральное место в комбинаторной оптимизации, и она явилась прототипической задачей современной комбинаторной оптимизации. Простота ее формулировки сочетается с трудностью решения. Многие подходы к решениям, ставшие стандартными в комбинаторной оптимизации, сначала были развиты и опробованы в контексте ЗК. Таким образом, в данной работе объединяются рамки и инструментарий теории динамических игр (программное движение, позиционная стратегия, движение, порожденное позиционной стратегией, многократный минимакс, позиционный минимакс, и др.) и весьма нетривиальная комбинаторная задача, каковой является обобщенная ЗК. Таким образом, тематика первой части органически связана с задачами управления.

Вторая часть диссертации посвящена программным минимаксным задачам оптимального управления. Основой рассматриваемых далее конструкций является теория принципа максимума JI.C. Понтрягина. Здесь рассматриваются, в частности, задачи сближения и уклонения траекторий управляемой системы относительно дискретной по времени системы выпуклых компактов, при различных типах ограничений на управление. В идейном отношении предлагаемые конструкции следуют подходу [24, 25], который предполагает совместное исследование пары экстремальных задач (оптимального управления и математического программирования), находящихся в двойственности. Такой подход дает возможность в целом ряде случаев для решения задач оптимального управления использовать методы математического программирования, получая эквивалентные по результату конечномерные экстремальные задачи. В [25] подход был продвинут на случай задачи сближения с выпуклым компактом в заданной момент времени (при геометрических ограничениях на управления). В работе H.H. Красовского [28] для решения задач оптимизации впервые была применена проблема моментов. Различные задачи управления на основе функционального подхода рассматривались в работах Ф.М. Кирилловой, Р. Габасова, А.Б. Куржан-ского, Ю.С. Осипова [12,36-41].

В работах [4-7,34,44,75,86] рассматривались задачи последовательного управления по отношению к системе выпуклых компактов, когда производится совокупная минимизация системы невязок; такие постановки связывают конструкции теории оптимального управления и теории маршрутных задач.

В ряде прикладных задач приходится решать вопросы взаимодействия двух управляемых систем с импульсными управлениями; это взаимодействие может проходить в условиях неполной информации и, возможно, конфликтности. Задачи управления с обратной связью традиционно являются одним из предметов теории дифференциальных игр (см., например, [25]—[27],[63, 95]). Также приходится работать и с минимаксными задачами программного управления (см., например, [24]-[27],[11, 13, 63]). В главе II исследуется минимаксная задача импульсного программного управления в условиях, когда о фазовом состоянии одного из объектов имеется лишь неполная информация. В смысле исследуемых ограничений, основной интерес представляет ограничение на полный импульс управляющей программы и(-), поскольку для многих задач механики, космической навигации, экономики, биомедицины, радиотехники и др. актуальны именно такие ограничения на управляющее воздействие. Для решения в замкнутом виде этой и ряда других задач, рассматриваемых в диссертации, используются процедуры компактифи-кации в классах обобщенных управлений-мер.

Цель работы.

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

Методы исследования.

Используются методы теории оптимального управления, дифференциальных игр, функционального анализа, теории меры, комбинаторной оптимизации.

Научная новизна работы.

1. Построена теория позиционного управления в минимаксных задачах последовательного обхода конечной системы множеств.

2. Получены необходимые условия оптимальности в классе конечно-аддитивных управлений-мер для задач управления линейными системами с импульсными ограничениями и разрывными коэффициентами при управлении, включая задачи последовательного сближения с системой выпуклых компактов.

3. Получены необходимые условия оптимальности в задаче программного уклонения для собственно линейной системы.

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

1. Батухтин В.Д., Красовский H.H. Задача программного управления на максимин//Изв. АН СССР. Техн. киберн. - 1972. - N 6. - С. 35-44.

2. Беллман Р. Применение динамического программирования к задаче коммивояжера/Киберн. сборник. 1964. - Т. 9. - С. 219-222.

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

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

5. Бердышев Ю.И., Ченцов А.Г. Оптимизация взвешенного критерия в одной задаче управления// Кибернетика. 1986. - N 1. - С. 59-64.

6. Бердышев Ю.И. Об одной задаче последовательной оптимизации без декомпозиции во времени//Кибернетика. 1987. - N 4. - С. 3235.

7. Бердышев Ю.И. К задаче последовательного обхода нелинейным объектом совокупности гладких многообразий//Диффер. уравнения и процессы управления. 1998. - N 2. С. 3-27.

8. Боткин Н.Д., Пацко B.C. Универсальная стратегия в дифференциальной игре с фиксированным моментом окончания//Пробл. упра-вл. и теории информ. 1982. - Т. 11, N 6. - С. 419-432.

9. Бурбаки Н. Общая топология. Основные структуры.- М.: Наука, 1968.- 272 с.

10. Варадарайн B.C. Меры на топологических пространствах//Мат. сборник. 1961 - Т. 55(97), N 1. - С. 35-100

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

12. Габасов Р., Кириллова Ф. Качественная теория оптимальных процессов. М.: Наука, 1971. - 508 с.

13. Гамкрелидзе Р.В. Основы оптимального управления. Тбилиси: Изд-во Тбил. ун-та, 1977. - 254 с.

14. Голыптейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 1971. 351 с.

15. Гурман В.И. Принцип расширения в задачах управления. М.: Наука, 1985. - 288 с.

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

17. Даффин Р.Дж. Бесконечные программы//Линейные неравенства и смежные вопросы.- М., 1959. С. 263-267.

18. Еремин И.И., Мазуров В.Д.,Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. -335 с.

19. Завалищин С.Т., Ушаков В.Н. Задача о приведении при ограничениях на полные импульсы управляющих сил//Прикл. Мат. Мех. -1975. Т. 39, Вып. 2. - С. 216-224.

20. Завалищин С.Т., Сесекин А.Н. Импульсные процессы. Модели и приложения. М.: Наука, 1991. - 256 с.

21. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач.-М.: Наука, 1974. 479 с.

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

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

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

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

26. Красовский H.H. Управление динамической системой: Задача о минимуме гарантированного результата. М.: Наука, 1985.- 516 с.

27. Красовский H.H., Субботин А.И. Позиционные дифференциальные игры.- М.: Наука, 1974. 456 с.

28. Красовский H.H. К теории оптимального регулирования//Автом. Телемех. 1957. - Т. 18, N 11. - С. 960-970.

29. Красовский H.H., Третьяков В.Е. К задаче преследования в случае ограничений на импульсы управляющих сил//Диффер. уравнения.- 1966. Т. 2, N 5. - С. 587-599.

30. Красовский H.H. Минимаксное поглощение в игре сближе-ния//Прикл. Мат. Мех. 1971. - Т. 35, вып. 6. - С. 945-951.

31. Красовский H.H. Программные конструкции для позиционных дифференциальных игр//Докл. АН СССР. 1973. - Т. 211, N 6. С. 1287-1290.

32. Красовский H.H. Аппроксимационные и формальные моде-ли//Матем. сборник. 1978. - Т. 107, N 4. - С. 541-571.

33. Кряжимский A.B., Осипов Ю.С. Устойчивые решения обратных задач динамики управляемых систем//Тр. МИАН. 1988. - Т. 185. -С. 126-146.

34. Кряжимский A.B., Савинов В.Б. О задаче коммивояжера с движущимися объектами//Изв. РАН. Техн. киберн. 1993. - N 4. - С. 233-238.

35. Куратовский К. Топология. Т. 1. М.: Наука, 1966. - 595 с.

36. Куржанский A.B., Осипов Ю.С. К задаче об управлении с ограниченными фазовыми координатами//Прикл. Мат. Мех. 1968. -Т. 32, N 2. - С. 194-202.

37. Куржанский A.B., Осипов Ю.С. Об одной задаче управления при ограниченных координатах//Изв. АН СССР. Техн. киберн. 1970.- N. 5. С. 22-28.

38. Куржанский A.B., Осипов Ю.С. К задачам об управлении при стесненных координатах//Прикл. Мат. Мех. 1969. - Т. 33, N 4. - С. 705-719.

39. Куржанский A.B., Осипов Ю.С. К задачам программного преследования в линейных системах//Изв. АН СССР. Техн. киберн. 1970.- N 3. С. 18-29.

40. Куржанский A.B., Осипов Ю.С. К управлению линейной системой обобщенными воздействиями//Диффер. уравнения. 1969. - Т. 5, N 8.- С.1360-1370.

41. Куржанский A.B. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977. - 392 с.

42. Левитин A.B. О задаче оптимального управления с ограничениями на фазовые координаты//Вестн. Моск. ун-та. Сер I, математика, механика.- 1971. N 3 - С. 59-76.

43. Миллер Б.М. Метод разрывной замены времени в задачах оптимального управления импульсными и дискретно-непрерывными системами// Автом. и Телемех. 1993. - N 12. - С. 3-32.

44. Морина С.И., Серов В.П., Ченцов А.Г. К вопросу о построении функции Беллмана в некоторых задачах оптимального управления с комбинированными ограничениями//Изв. АН СССР. Мех. Тверд. Тела. 1989. - N 4.- С. 9-16.

45. Неве Ж. Математические основы теории вероятностей.- М.: Мир, 1969. 309 с.

46. Орлов Ю.В. Теория оптимальных систем с обобщенными управлениями. М.: Наука, 1988. - 192 с.

47. Понтрягин J1.C. Обыкновенные дифференциальные уравнения. -М: Наука, 1965. 322 с.

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

49. Пшеничный Б.Н., Онопчук Ю.Н. Линейные дифференциальные игры с интегральными ограничениями//Изв. АН СССР. Техн. ки-берн. 1968. - N 1. - С. 13-22.

50. Серов В.П., Ченцов А.Г. Конечно-аддитивные меры и расширения некоторых линейных задач оптимального управления/ Урал, политехи. ин-т. Свердловск, 1988. - 38 с. - Деп. в ВИНИТИ N 4200-В88.

51. Серов В.П., Ченцов А.Г. Конечно-аддитивное расширение линейных задач оптимального управления с интегральными ограничениями/ Урал, политехи, ин-т.- Свердловск, 1989. 59 с. - Деп. в ВИНИТИ N 6644-В89.

52. Серов В.П., Ченцов А.Г. Конечно-аддитивные меры и релаксации задач оптимального управления/Тез. докл. VII Всесоюзн. конф. "Качеств, теория диффер. уравнений'.' Рига, 1989. - С. 202.

53. Серов В.П., Ченцов А.Г. Об одной конструкции расширения задачи управления с интегральными ограничениями// Диффер. уравнения. 1990.- Т. 26, N 4.- С. 607-617.

54. Серов В.П., Ченцов А.Г. О программной линейной игровой задаче наведения при ограничении на импульс управляющей си-лы//Автом. и Телемех. 1993. - N 5. - С. 61-74.

55. Серов В.П. Компактификация задачи управления разрывной системой с ограничением на ресурс/ Тез. докл. VII Всесоюзн. конф. "Управл. в мех. сист." Свердловск, 1990. - С. 95-96.

56. Серов В.П. Оценивание израсходованного ресурса управления игрока-противника как проблема моментов// Изв. РАН. Техн. ки-берн. 1994. - N 6. - С. 215-222.

57. Сесекин А.Н. Об оптимальном управлении линейной системой с ограниченным ресурсом//Нелинейные задачи в обобщенных функциях. Свердловск: Институт матем. и механ., 1988. - С. 77-84.

58. Сикорский Р. Булевы алгебры. М.: Мир, 1969. - 376 с.

59. Субботин А.И., Ушаков В.Н. Альтернатива для дифференциальной игры сближения-уклонения при интегральных ограниченияхна управления игроков//Прикл. Мат. Мех. 1975. - Т. 39, вып. 3. -С. 387-396.

60. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона -Якоби. М.: Наука, 1991. - 215 с.

61. Субботина H.H., Субботин А.И. Альтернатива для дифференциальной игры сближения-уклонения при ограничениях на импульсы управлений игроков//Прикл. Мат. Мех. 1975. - Т. 39, вып. 3. С. 397-406.

62. Субботина H.H. Универсальные оптимальные стратегии в позиционных дифференциальных играх// Диффер. уравнения. 1983. -Т. 19, N 1. - С. 1890-1896.

63. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981. - 288 с.

64. Ухоботов В.И. Линейная дифференциальная игра с ограничениями на импульсы управлений//Прикл. матем. и механ. 1988. - Т. 52, вып. 3. - С. 355-362.

65. Ухоботов В.И., Титов О.Ю. Линейная дифференциальная игра импульсной встречи с выпуклым терминальным множеством//Ве-стник Челяб. унив. 1999. - N 2. - С. 113-119.

66. Фань-Цзы. Теорема о минимаксе//Бесконечные антагонистические игры. -М.: Физматгиз, 1963. С. 31-39.

67. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения/Киберн. сборник. 1964. - Т. 9. - С. 202218.

68. Ченцов А.Г. Игровая задача сближения в собственно линейной си-стеме//Изв. АН СССР. Техн. киберн. 1977. - N2. - С. 3-7.

69. Ченцов А.Г. Приложения теории меры к задачам управления. -Свердловск: Средн.-Урал. кн. изд-во, 1985. 128 с.

70. Ченцов А.Г. Конечно-аддитивные меры и релаксации экстремальных задач.- Екатеринбург: Наука, 1993. 232 с.

71. Ченцов А.Г. К вопросу о корректном расширении одной задачи о выборе плотности вероятности при ограничениях на систему математических ожиданий//Успехи Мат. Наук. 1995. - Т. 50, вып. 5. -С. 223-242.

72. Ченцов А.Г. К вопросу о корректном расширении некоторых неустойчивых задач управления с интегральными ограничения-ми//Изв. Акад. Наук. Сер. Матем. 1999. - Т. 63, N 3. - С. 185-223.

73. Ченцов А.Г. Универсальная версия обобщенных интегральных ограничений в классе конечно-аддитивных мер, I, II//Изв. вузов. Мат. 1999. - N 7. - С. 67-74; - 2000. - N 2. - С. 69-76.

74. Черноусько Ф.Л., Меликян A.A. Игровые задачи управления и поиска. М.: Наука, 1978. - 272 с.

75. Чикрий A.A., Белоусов A.A. О задаче обхода множеств//Методы решения сложных задач математического программирования. Киев: Институт киберн., 1985. - С. 25-29.

76. Шефер X. Топологические векторные пространства. М.: Мир, 1971. - 360 с.

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

78. Янг JI. Лекции по вариационному исчислению и теории оптимального управления. М.: Мир, 1974. - 488 с.

79. Bhaskara Rao K.P.S., Bhaskara Rao M. Theory of charges. A study of finitely additive measures.- London: Acad. Press, 1983.- 253 p.

80. Chentsov A.G. Finitely additive measures and relaxations of extremal problems.- New York: Plenum Publ. Corp., 1996. 244 p.

81. Chentsov A.G. Asymptotic attainability. Kluwer: Dordrecht, 1997. -322 p.

82. Chentsov A.G., Serov V.P. Representation for some set-theoretic limits in the class of two-valued finitely additive measures//Funct. Differ. Equat. 1996. - Vol. 3, N 3-4. - P. 265-278.

83. Chentsov A.G., Korotayeva L.N. The dynamic programming method in the generalized traveling salesman problem//Mathl. Comput. Modell.- 1997. Vol. 25, N 1. - P. 93-105.

84. Chentsov A.G. Finitely additive measures and problems of asymptotic analysis//Proc. IFAC Workshop "Nonsmooth and Discontinuous Problems of Control and Optimization". P. 1-12. -Oxford: Pergamon, 1999.

85. Chentsov A.G. Universal properties of generalized integral constraints in the class of finitely additive measures//Funct. Differ. Equat. 1998.- Vol. 5, N 1-2. P. 69-105.

86. Chikrii A.A. Conflict-Controlled Processes. Dordrecht: Kluwer. - 1997.- 340 p.

87. Clarke F.H., Ledyaev Y.S., Subbotin A.I. The synthesis of universal feedback pursuit strategies in differential games//SIAM J. Contr. Optim. Vol. 35, N 2. - P. 552-561.

88. DeFinetti B. Theory of probability. A critical introductory treatment. Vol. I. John Wiley & Sons, 1970. - 300 p.

89. Diestel J., Uhl J.J.,Jr. Vector measures. Providence: Amer. Math. Sos., 1977. 322 p.

90. Dubins L.E, Savage L. How to gamble if you must. New-York: McGrow-Hill, 1965. - 255 p.

91. Fichtenholz G., Kantorovitch L. Sur les operations linearies dans l'espace des function bornees//Studia Math. 1934 - Vol.5. - P. 6998.

92. Friedman A. Differential Games. New York: Wiley Interscience, 1971. - 350 p.

93. Hewitt E., Josida K. Finitely additive measures//Trans. Amer. Math. Sos. 1952. - Vol. 72, no. 1. - P. 46-66.

94. Hildebrandt Т.Н. On bounded functional operations//Trans. Amer. Math. Sos.- 1934.- Vol. 36.- P. 868-875.

95. Krasovskii N.N., Subbotin A.I. Game-theoretical control problems. -New York: Springer, 1987. 517 p.

96. Maynard H. A Radon-Nikodym theorem for finitely additive bounded measures// Pacific J. Math. 1979. - Vol. 83. - P. 401-413.

97. Osipov Yu.S., Kryazhimski A.V. Inverse problems for ordinary differential equations: Dynamical Solutions. London: Gordon and Breach, 1995. 756 p.

98. Parikh, S.C., Frisch I.T. Finding the most reliable routes in communication systems//IEEE Trans. Commun. Syst. 1963. - Vol. 11, N 4. - 402-406.

99. Serov V.P. The estimate of control resourses spent by player-opponent as a moment problem//Тез. докл. II Межд. Семинара "Негладкие иразрывные задачи управления и оптимизации". Челябинск, 1993. - С. 123-125.

100. Serov V.P. Optimal feedback strategy in the game variant of generalized travelling salesman problem//Proc. 11th IFAC Workshop "Control applications of Optimization". Vol. 2. - Oxford: Pergamon, 2000. -P. 635-640.

101. Serov V.P. Adherence approach in the moment problems: Convergence for unbounded case//Prepr. 5th IFAC Symposium "Nonlinear Control Systems". Vol. 2. - St. Petersburg, 2001. - P. 477-482.