Методы решения игровых задач дискретного управления линейных последовательностных машин тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ОСНОВНЫЕ ИГРОВЫЕ ЗАДАЧИ ДНЯ ЛИНЕЙНЫХ

ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН.

§ I.I Аналитическое описание линейных последовательностных машин над полем

§ 1.2 О псевдобулевом представлении уравнении многошагового перехода ЛПМ.

§ 1.3 Постановка игровых задач для двоичных

§ 1.4 Учет фактора информированности при игре

ГЛАВА П. ОБ УСЛОВИЯХ ОКОНЧАНИЯ ИГРЫ В ЗАДАЧАХ

ПРЕСЛЕДОВАНИЯ ДО ЛПМ.

§ 2.1 О допустимых решениях задачи преследования двоичных ЛПМ.

§ 2.2 Решение задачи преследования для ЛПМ методом оператора ортогонального проектирования

§ 2.3 Общий случай.

ГЛАВА Ш. УСЛОВИЯ ОПТИМАЛЬНОСТИ ТИПА ДИНАМИЧЕСКОГО

И ПСЕВДОБУЛЕВОГО ПРОГРАММИРОВАНИЯ.

§ 3.1 Аналог уравнения Беллмана для игровых задач конечных ЛПМ.

§ 3.2 Методы псевдобулевого программирования в дшнимаксных задачах.дискретного.управления двоичных ЛПМ.

§ 3.3 Решение задачи на случай информированности сторон.

§ 3.4 Основные соотношения между задачами

ГЛАВА 1У. УСЛОВИЯ ОПТИМАЛЬНОСТИ С ПОМОЩЬЮ АНАЛОГОВ

ФУНКЦИЙ ГАМИЛЬТОНА-ПОНТРЯГИНА В МИНИМАКСНЫХ ЗАДАЧАХ ДИСКРЕТНОГО УПРАВЛЕНИЯ ДВОИЧНЫХ ЛПМ

§ 4.1 Условие оптимальности в максиминных зада«-чах дискретного управления двоичной.ЛПМ. при априорной информированности

§ 4.2 Условие оптимальности в максиминных задачах дискретного управления двоичной ЛПМ . при последовательной информированности.

§ 4.3 Способы вычисления оптимальных управлений

§ 4.4 Об одном численном споеобе нахождения оптимальных гарантирующих.стратегий.в.чистых стратегиях.

ГЛАВА У. НЕКОТОРЫЕ ОБОБЩЕНИЯ.

§ 5.1 О решении задачи.преследования.для рi .-. ичных ЛПМ.

§ 5.2 О применении алгоритмов обобщенного псевдобулев ого программирования в минимаксных задачах дискретного.управления.для.т. ичных ЛПМ.

§ 5.3 Об алгоритме типа динамического программирования для решения минимаксных.игр.преследования р -ичных ЛПМ. ЮО

§ 5.4 Об игровой задаче для двоичных ЛПМ с аддитивной. бернуллиевой шумовой последовательностью. Рандомизированные стратегии . Ю

ВЫВОДЫ.

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

Новый важный этап в развитии теории ЛПМ связан с постановкой и решением для ЛПМ различных оптимизационных задач. Исследованию различных аспектов задач оптимального управления конечных систем, в том числе и ЛПМ посвящена работы В.С.Михале-вича, Н.Н.Моисеева, Я.З.Цыпкина, Д.А.Поспелова, Ю.С.Попкова, Р.Г.Фараджева, З.И.Аскеровой, М.Ш.Байбатшаева, М.И.Гараева, А.И.Кашшнского, Р.М.Карзона, К.С.Мамедова и других авторов, в которых получены необходимые (или достаточные) условия оптимальности, развиты вычислительные алгоритмы, указаны практические приложения некоторых классов двоичных комбинационных систем, линейных и нелинейных последовательностных машин (ПМ), а также в последнее время для двоичных последовательностно-клеточных ПМ.

Следующий новый шаг в развитии теории оптимальных процессов двоичных ПМ связан с рассмотрением для этих систем различных игровых задач динамики. Все это говорит об актуальности игровых задач динамики для двоичных ЛПМ. Тем не менее, игровые задачи для конечных систем к настоящему времени недостаточно исследованы, хотя многошаговые максиминные (минимаксные) задачи для обычных линейных и нелинейных дискретных систем были хорошо изучены в работах А.Блакьера, Ю.П.Иванилова, Г.Лейтмана, А.И.Пропоя, Б.Н.Пшеничного, Н.Ю.Сатимова, Ю.С.Никольского, А.А. Чикрия и др.

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

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

Общая методика исследований опирается на фундаментальные результаты теории ЛПМ, математической теории систем, теории линейных многошаговых игр, теории максиминных задач дискретного управления, теории динамического и целочисленного программирования. В работе частично используются также некоторые результаты дискретной математики.

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

ВЫВОДЫ

1. Впервые поставлены и решены основные игровые задачи дискретного управления двоичных ЛПМ.

2. Предложен метод оператора ортогонального проектирования над полями Галуа и даны его применения для решения задачи теории преследования (наведения) конечных ЛПМ: с помощью данного метода доказаны теоремы о завершении игры преследования ЛПМ из любого начального положения.

3. Получены условия оптимальности (случай седловой точки, оптимальных гарантирующих стратегий) уравнения Беллмана в максиминных (минимаксных) задачах Дискретного управления конечных ЛПМ.

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

5. Доказываются теоремы о соотношениях между максиминными (минимаксными) задачами двоичных ЛПМ.

6. Доказаны новые теоремы о необходимых условиях оптимальности с помощью аналогов функций Гамильтона-Понтрягина для двоичных ЛПМ в случаях априорной и последовательной информированности.

7. Исходя из полученных условий оптимальности развиты вычислительные алгоритмы для нахождения оптимальных стратегий в игровых задачах двоичных ЛПМ.

8. Развит метод решения игровой задачи для двоичных ЛПМ с аддитивной бернуллиевой помехой в рандомизированных стратегиях, как игровая задача для одного класса стохастической ПМ.

1. АЗИМОВ А.Я., ФАН ЗУЙ ХАЙ. Об одном способе преследования в теории линейных дискретных игр с интегральными ограничениями на управление. - Баку, 1980. - 35с. Рукопись представлена АТУ им.С.М.Кирова. Деп. в ВИНИТИ 18 июля 1980,3164-80.

2. ЕАЙЕАТШАЕВ М.Ш., ПОПКОВ Ю.С. Об одной задаче квадратичной оптимизации двоичных нелинейных последовательностных машин. Автоматика и телемеханика, 1978, № 12, с.37-47.

3. БЕРЖ К. Теория графов и ее применение. М.: Мир, 1962. -316с.

4. ЕИРКГОФ Г., БАРТИ Т. Современная прикладная алгебра. М.: Мир, 1976. - 400с.

5. БОЛТЯНСКИЙ В.Г. Оптимальное управление дискретными системами. М.: Наука, 1973. - 446с.

6. БУСЛЕНКО В.Н. Автоматизация имитационного моделирования сложных систем. М.: Наука, 1977. - 240с.

7. ВАРШАМОВ P.P. Методологические особенности развития прикладной математики как теоретической основы кибернетики. -Ереван, Изд-во АН Арм.ССР, 1974.

8. ВОРОБЬЕВ Н.Н. Теория игр. Лекции для экономистов-кибернетиков. Л.: Изд-во ЛГУ, 1974.

9. ВАСИЛЬЕВ Ф.П. Методы решения экстремальных задач. М.: Наука, 1981. - 400с.

10. ВОЛЬФСОН И.Е. Об одной игровой задаче на графе. Изв.АН СССР, Тех.кибернетика, 1980, # I, с.183-190.

11. ГЕРМЕЙЕР Ю.Б. Введение в теорию исследования операций . -М.: Наука, 1971. 384с.

12. ГИНДИКИН С.Г. Алгебра логики в задачах. М.: Наука, 1972.

13. ГУСЯТНИКОВ П.Б., НИКОЛЬСКИЙ М.С. Об оптимальности времени преследования. ДАН СССР, 1969, т.184, № 3, с.518-521.

14. ДЕМЬЯНОВ В.Ф., ВАСИЛЬЕВ Л.В. Не дифференцируемая оптимизация.- М.: Наука, 1981. 384с.

15. ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ. т.1. М.: Наука, 1974. - 312с.

16. ЕРЕШКО Ф.И., ПРОПОЙ А.И. К теории динамических игр. Изв.АН СССР, Техническая кибернетика, 1970, № 2, с.42-48.

17. ИВАНИЛОВ Ю.П., ЛОТОВ А.В. Математические модели в экономике.- М.: Наука, 1979.

18. КАЛМАН Р., ФАЛБ П., АРБИБ М. Очерки по математической теории систем. М.: Мир, 1971, - 386с.

19. КАПЛИНСКИЙ А.И., ПРОПОЙ А.И. О соотношениях между стохастическими многошаговыми играми. Изв.АН СССР, Техническая кибернетика, 1972, № 6, с.45-50.

20. КАПЛИНСКИЙ А.И., ПРОПОЙ А.И. О стохастических многошаговых играх. Изв.АН СССР, Техническая кибернетика, 1973, Jfc 2, с.19-23.

21. КАПЛИНСКИЙ А.И., КРАСНЕНКЕР А.С., ЦЫПКИН Я.З. Рандомизация и сглаживание в задачах и алгоритмах адаптации. Автоматика и телемеханика, 1974, № 6, с.47-57.

22. КАРЗОН P.M. Элементы теории оптимального управления двоичных линейных последовательностных машин. Дис. на соиск.учен.степ.канд.физ-мат.наук. Баку, 1980. - 130с.

23. КАРЛИН С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964. - 838с.

24. КАРМАНОВ В.Г, Математическое программирование. М.: Наука, 1975. - 272с.

25. К0Н0НЕНК0 А.Ф. О многошаговых конфликтах с обменом информацией. ЖВМиМФ, 1974, № 4.

26. КОРБУТ А.А., ФИНКЕЛЬШТЕЙН; Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368с.

27. КРАСОВСКИЙ Н.Н. Игровые задачи о встрече движений. М.: Наука, 1970. - 420с.

28. КРАСОВСКИЙ Н.Н., СУББОТИН А.И. Позиционные дифференциальные игры. М.:' Наука, 1974. - 456с.

29. КУММЕР Б. Игры на графах. М.: Мир, 1982. - 112с.

30. МАМЕДОВ К.С., КАРЗОН P.M. К решению задачи оптимального управления двоичной последовательностной машины. Баку, 1980 20с. - Рукопись представлена АГУ им.С.М.Кирова. Деп. в ВИНИТИ 20 марта 1980, 1088-80.

31. МОИСЕЕВ Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975. - 528с.

32. МОИСЕЕВ Н.Н. Математические задачи системного анализа. -М.: Наука, 1981. 487с.

33. ПАЦЮКОВ В.П. Дифференциальные игры при различной информированности игроков. М.: Сов.радио, 1976. - 199с.

34. ПЕТРОСЯН Л.А., ТОМСКИЙ Г.В. Геометрия простого преследования. Новосибирск: Наука, 1983. - 143с.

35. ПИТЕРСОН У., УЭЛДОН У. Коды, исправляющие ошибки. М.: Мир, 1976. - 594с.

36. ПОНТРЯГИН Л.С. К теории дифференциальных игр. УМН, 1966, т.21, № 4, с.219-274.

37. ПОНТРЯГИН Л.С. О линейных дифференциальных играх. I ДАН СССР, 1967, т. 174, JS 6, с.1278-1280.

38. ПОНТРЯГИН Л.С., БОЛТЯНСКИЙ В.Г., ГАМКРЕЛИДЗЕ Р.В., МИЩЕНКО Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1983. - 392с.

39. ПОСПЕЛОВ Д.А. Логические методы анализа и синтеза схем. -М.: Энергия, 1974.

40. ПРОПОЙ А.И. Минимаксные задачи управления при априорной информированности. Автоматика и телемеханика, 1969, № 7,с.73-80.

41. ПРОПОЙ А.И. Минимаксные задачи управления при последовательной информированности. Автоматика и телемеханика, 1970,1. I, с.65-76.

42. ПРОПОЙ А.И. Элементы теории оптимальных дискретных процессов. М.: Наука, 1973. - 256с.

43. ПРОПОЙ А.И. О многошаговых играх с последовательной информированностью. В кн.: Исследование операций: Сб.статей -М.: ВЦ АН СССР, 1974, с.69-78.

44. НШЕНИЧНЫЙ Б.Н. Структура дифференциальных игр. ДАН СССР, 1969, т.184, J* 2,

45. РОМАНОВСКИЙ И.В. Алгоритмы решения экстремальных задач. -М., Наука, 1977. 352с.

46. СААТИ Г. Целочисленные методы оптимизации и связанные с ниш экстремальные проблемы. М.: Мир, 1973. - 302с.

47. САТИМОВ Н.Ю. Задача убегания для одного класса нелинейных дискретных игр. Изв.АН СССР, Техническая кибернетика, 1973, & 6, с.45-48.

48. Современное состояние теории исследования операций. М.: Наука, 1979. - 463с.

49. ФАРАДЖЕВ Р.Г. Линейные последовательностные машины. М.: Сов.радио, 1975. - 248с.

50. ФАРАДЖЕВ Р.Г. О принципе псевдолинейности для функции алгебры логики и его применении к статистическим задачам конечных систем. Автоматика и телемеханика, 1975, № 7, с.53-62.

51. ФАРАДЖЕВ Р.Г., ДАНГ КИМ ЛОНГ, ШИМИЕВ Г.В. Максиминные задачи дискретного управления с последовательностными машинами. В кн.: Вопросы нефтяной технической кибернетики. Сб.статей MB и ССО СССР - Баку, 1978, с.3-10.

52. ФАРАДЖЕВ Р.Г. Принципы построения, исследования и применения последовательностных машин. Автореф. на соиск.учен. степ.докт.техн.наук. - М.: 1983. - 42с.

53. ФЕДОРОВ В.В. Численные методы максимина. М.: Наука, 1979.- 278с.

54. ЦЫПКИН Я.З. Адаптация и обучение в автоматических системах.- М.: Наука, 1968. 400с.

55. ЧАКИ Ф. Современная теория управления. М.: Мир, 1975 -424.

56. ЧЕРНОУСКО Ф.Л., МЕЛИКЯН А.А. Игровые задачи управления и поиска. М.: Наука, 1978. - 270с.

57. ЧИКРИЙ А.А. Об одном классе линейных дискретных игр качества. Кибернетика, 1971, & 6, с.103-106.

58. ЧИКРИЙ' А.А. О линейных дискретных играх качества. Кибернетика, 1971, № 5, с.90-99.

59. ШИМИЕВ Г.В. Игра преследования с конечными линейными после-довательностными машинами над полем Е. Изв.АН Аз.ССР, сер.физ-техн. и мат.наук, 1978, № 6, с.49-54.

60. ШИМИЕВ Г.В., ФАРАД5КЕВ Р.Г. Задача убегания с линейными последовательностными машинами. Изв.АН Аз.ССР, сер.физ-техн. и мат.наук, 1981, № 3, с.15-20.

61. ШИМИЕВ Г.В. О максиминных задачах дискретного управления для систем, описываемых модулярными разностными уравнениями.- Баку, 1982. 13с. - Рукопись представлена ИММ АН Азерб. ССР. Деп. в ВИНИТИ 9 июля 1982, № 3870-82.

62. ШИМИЕВ Г.В. Условия оптимальности в игровых задачах для конечных систем. В кн.: Тезисы докладов конференции молодых ученых по математике и механике, посвященной 25-летию образования ИММ АН Азерб.ССР. - Баку: Элм, 1984, с.252-254.

63. ШИМИЕВ Г.В. Игровые задачи для конечных систем, описываемых над полем frF(p) . В кн. : Тезисы докладов конференции молодых ученых по математике и механике, посвященной 25-летию образования ИММ АН Азерб.ССР. - Баку: Элм, 1984,с.255-258.

64. ШИМИЕВ Г.В. Условия оптимальности в минимаксных задачах дискретного управления для двоичных ЛПМ. Баку, 1984. -15с. - Рукопись представлена ИММ АН Азерб.ССР. Деп.в ВИНИТИ 2 июля 1984, Я 4521-84.

65. ШИМИЕВ Г.В. Игровые задачи быстродействия (преследования) для конечных ЛПМ. Баку, 1984. - 22с. - Рукопись представлена ИММ АН Азерб.ССР. Деп.ВИНИТИ 2 июля 1984, № 4522-84.

66. ЮДИН Д.Б., ГОЛЬШТЕЙН Е.Г. Новые направления в линейном программировании. М.: Сов.радио, 1966. - 524с.

67. Ь^ЪУ-оЪ^г Л. Ъ. Л/е&гмалд. con,cLiioKb' 40ъ optlntcdLircdie^itb си. cU^fexjUoiLciZ

68. ClwcL coutzol РъоИл ms — ЗГЛМ Jpu-гиА^ сиcjov&UOI -\9(>5 } аЫ5 doli ; 5.

69. Hassouvu А/? cjtOT-CK/w^ SorH.esL-иГаъ С. (pwda JldxUlivzkztwiiML Vbocse jLlHcart. Sjt,<jju.eM.ii<xl —

70. EE Tuut5 OK- Co^puierS; <{912^ fi'.io^ p. Н19-НЛ5 .

71. Р^Ьет. I. HOLVvlviui. (Sivy.*,

72. ВсС&хи. XUtkooLs In OptbcdioK. кгьъа.'ьск .

73. WiicUM^i^ y Зрш^еъ wisttLQ ? btiM-^ fltM*- Y&i,к .

74. Утверздшэ" истор СКВ ШМ АН Лэерб.ССРй.т.н. &. Л.Искевдер-заде 1981г.1. Aictо внедрении опттдазации длин монтажных связей

75. Зав. лаб. тех. окон. . исследований \с- ~

76. Доц.АГУ mi.C.U.KiipoBa Бедущкй KonoTpyivnopк.т.н. А.Алекперов1. О Р.Г.&арадвев1. Г.В.Шшев