Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Методы решения игровых задач дискретного управления линейных последовательностных машин

Диссертация: Методы решения игровых задач дискретного управления линейных последовательностных машин
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • ГЛАВА I. ОСНОВНЫЕ ИГРОВЫЕ ЗАДАЧИ ДНЯ ЛИНЕЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН
    • I. I Аналитическое описание линейных последовательностных машин над полем
      • 1. 2. О псевдобулевом представлении уравнении многошагового перехода ЛПМ
      • 1. 3. Постановка игровых задач для двоичных
      • 1. 4. Учет фактора информированности при игре
  • ГЛАВА II. ОБ УСЛОВИЯХ ОКОНЧАНИЯ ИГРЫ В ЗАДАЧАХ ПРЕСЛЕДОВАНИЯ ДО ЛПМ
    • 2. 1. О допустимых решениях задачи преследования двоичных ЛПМ
    • 2. 2. Решение задачи преследования для ЛПМ методом оператора ортогонального проектирования
    • 2. 3. Общий случай
  • ГЛАВА III. УСЛОВИЯ ОПТИМАЛЬНОСТИ ТИПА ДИНАМИЧЕСКОГО И ПСЕВДОБУЛЕВОГО ПРОГРАММИРОВАНИЯ
    • 3. 1. Аналог уравнения Беллмана для игровых задач конечных ЛПМ
    • 3. 2. Методы псевдобулевого программирования в дшнимаксных задачах.дискретного.управления двоичных ЛПМ
    • 3. 3. Решение задачи на случай информированности сторон
    • 3. 4. Основные соотношения между задачами
  • ГЛАВА 1. У. УСЛОВИЯ ОПТИМАЛЬНОСТИ С ПОМОЩЬЮ АНАЛОГОВ ФУНКЦИЙ ГАМИЛЬТОНА-ПОНТРЯГИНА В МИНИМАКСНЫХ ЗАДАЧАХ ДИСКРЕТНОГО УПРАВЛЕНИЯ ДВОИЧНЫХ ЛПМ
    • 4. 1. Условие оптимальности в максиминных зада"-чах дискретного управления двоичной.ЛПМ. при априорной информированности
    • 4. 2. Условие оптимальности в максиминных задачах дискретного управления двоичной ЛПМ. при последовательной информированности
    • 4. 3. Способы вычисления оптимальных управлений
    • 4. 4. Об одном численном споеобе нахождения оптимальных гарантирующих.стратегий.в.чистых стратегиях
  • ГЛАВА V. НЕКОТОРЫЕ ОБОБЩЕНИЯ
    • 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,
  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. Г. В.Шшев
Заполнить форму текущей работой

На отлично!