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

Шимиев, Гашим Вели оглы АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Баку МЕСТО ЗАЩИТЫ
1984 ГОД ЗАЩИТЫ
   
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. Г.В.Шшев