Національна академія наук України

Інститут кібернетики ім. В.М. Глушкова

Ч о р н е й Р у с л а н К о с т я н т и н о в и ч

УДК 519.217.8

Задачі управління марковськими процесами

з післядією

01.05.01 – теоретичні основи інформатики та кібернетики

Автореферат дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ 2000

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор

Кнопов Павло Соломонович,

завідуючий відділом Інституту кібернетики

ім. В.М. Глушкова НАН України

Офіційні опоненти: доктор фізико-математичних наук, професор

Кириченко Микола Федорович,

провідний науковий співробітник Інституту

кібернетики ім. В.М. Глушкова НАН України,

кандидат фізико-математичних наук,

старший науковий співробітник

Краснитський Сергій Михайлович,

професор Київського державного університету технологій та дизайну.

Провідна установа: Київський університет ім. Тараса Шевченка, кафедра теорії ймовірностей механіко-математичного факультету, м. Київ

Захист відбудеться « 28 » квітня 2000 р. о 1100 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені

В.М. Глушкова НАН України за адресою:

03680 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий « 27 » березня 2000 р.

Учений секретар

спеціалізованої вченої ради Синявський В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. При дослідженні складних технічних, фізичних і економічних проблем все більше застосування знаходить теорія управління марковськими процесами. У першу чергу це зумовлено тим, що марковськими процесами зручно описувати фізико-технічні та економічні закономірності явищ. При цьому важливим є можливість застосування для обчислень високопродуктивної комп’ютерної техніки, що за нинішніх умов дозволяє широко застосовувати результати досліджень у цьому напрямку.

Задачі управління марковськими процесами досі розглядалися в основному для одномірного випадку. В багатовимірному випадку в більшій частині робіт лише узагальнювались ті чи інші поняття, які були введені для одномірного випадку. В пропонованій дисертаційній роботі вводиться поняття марковського процесу на графі, яке відрізняється оригінальним підходом щодо впорядкування часового аргументу, а саме: кожний наступний стан деякої вершини графа залежить від стану її повного околу в попередній момент часу. Повний окіл трактується як множина, що складається з вершин, які сполучаються ребрами з даною вершиною, і даної вершини. При такому означенні марковості системи більшість результатів, отриманих для одномірного випадку, потребують детальної перевірки та доведень, оскільки на даний випадок вони безпосередньо не переносяться.

Дослідження дисертаційної роботи є актуальними, оскільки введене поняття марковості, як правило, відображає властивості реальних фізичних та економічних явищ. Наприклад, якщо простір керувань деякої вершини складається лише з двох станів, то така система може бути описана моделлю Ізінга, достатньо вивченій в статистичній фізиці, а якщо трактувати вершини графа як фірми (або організації), ребра – як їх взаємодію, а множину рішень вершини як множину технологій, то дана задача управління марковським процесом перетворюється в задачу вибору технології деякою фірмою в кожен момент часу (наприклад, на рік) для того, щоб мінімізувати середні затрати в одиницю часу.

Мета і задачі дослідження. Мета роботи полягає в розробці та обгрунтуванні моделей управління марковськими процесами на графі, знаходженні достатніх умов існування оптимальних нерандомізованих стаціонарних стратегій для випадків скінченності та нескінченності просторів станів системи та керуючих впливів, для моделі з переходом управління з однієї вершини до іншої, а також достатніх умов існування ціни гри та оптимальних стратегій для ігрової постановки.

Наукова новизна одержаних результатів. Уперше був запропонований системний підхід до управління марковськими процесами, який полягає в оригінальному означенні еволюції керованої системи, а саме: наступний стан елемента системи залежить не лише від свого попереднього стану і керування, а й від стану свого околу. На дану модель було поширено результати попередніх досліджень для звичайного випадку управління марковськими процесами.

Практичне значення одержаних результатів. Теоретичні результати дисертації можуть бути використані для дослідження економічних закономірностей явищ, зокрема, якщо інтерпретувати вершини графа, на якому введений керований процес, як організації або фірми, а ребра як їх взаємодію. Дана робота також може викликати інтерес для керування фізико-технічними системами та хімічними процесами, в яких прослідковується залежність між сусідніми елементами керованої системи. В роботі наводяться приклади використання результатів даної дисертації в економіці та статистичній фізиці.

Особистий внесок здобувача. Всі результати дисертації автор одержав самостійно. У спільній з П.С. Кноповим роботі [1] автор дисертації довів можливість вибору оптимальних керувань в задачі управління марковськими процесами на графі в припущенні скінченності простору керуючих впливів серед однорідних марковських.

Апробація результатів дисертації. Результати досліджень, що включені до дисертації, доповідались на міжнародній конференції в Любліні «XX Int. Seminar on Stability Problems For stochastic Models, Lublin–Naleczov, 5–11 September, 1999» і на семінарах в Інституті кібернетики ім. В.М. Глушкова НАН України та Київському університеті ім. Тараса Шевченка.

Публікації. Результати дисертації опубліковані в трьох статтях.

Структура та обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел. Загальний обсяг роботи складає 150 сторінок, список використаних джерел нараховує 150 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі описується стан проблеми на сьогоднішній час, обгрунтовується актуальність вибраної теми та анонсуються основні результати дисертаційної роботи.

У першому розділі досліджується питання про знаходження оптимальних стратегій управління марковськими процесами на графі для критерію мінімізації середніх затрат в одиницю часу за умови скінченності просторів станів кожної з вершин і керуючих впливів серед однорідних марковських нерандомізованих стратегій.

Нехай – деякий локально-скінченний граф із множиною вершин і множиною ребер ; – ребро графа, що сполучає вершини та . Назвемо околом вершини множину вершин, що сполучені ребром з вершиною , тобто . Повним околом вершини будемо називати величину , що містить окіл вершини і саму вершину , тобто .

Нехай – множина станів елемента , – множина станів системи. В кожен момент часу для -ї вершини задана множина рішень , яка складається з елементів. Імовірнісна еволюція системи описується перехідними імовірностями

, , | (1)

які залежать від рішень -ї вершини .

Тут і надалі верхні індекси вказують на момент часу, а нижні – на належність даної величини, якщо не обумовлено іншого.

У кожен момент часу параметр приймає значення, спираючись на результати попередніх спостережень: .

Означення 1.2. Набір функцій , , … , задає керування .

Через вибране таким чином керування набір перехідних ймовірностей (1) для кожного фіксованого початкового стану визначає імовірнісну міру в просторі послідовностей . Одержаний процес будемо називати керованим за допомогою керування .

Означення 1.3. Керування називається марковським, якщо

.

Означення 1.4. Керування називається однорідним марковським, якщо для всіх і .

Позначимо сукупність всіх керувань . Нехай , – деякі фіксовані підмножини (які можуть бути різними для різних значень ), кожна з яких обмежує область значень рішення в момент часу , якщо .

Означення 1.5. Керування називається допустимим, якщо при кожному значення функції .

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

().

Припустимо, що

,

де .

Позначимо , якщо . Очевидно, що .

Припустимо, що , причому . Позначимо .

Нехай .

будемо позначати витрати -ї вершини, якщо і -ю вершиною приймається рішення . Тоді очікувані середні витрати -ї вершини за час

, | (2)

де означає математичне сподівання керованого процесу за умови, що .

Проблема полягає в знаходженні керування , яке б мінімізувало

. | (3)

Нехай .

Означення 1.6. Керування називається оптимальним, якщо для всіх маємо .

Нехай

. | (4)

Теорема 1.1. Якщо простори і складаються із скінченної кількості точок і виконується умова (4), то в задачі мінімізації функціоналу (3) в класі існує оптимальне однорідне марковське керування, для якого справедливе співвідношення , , , де ергодичні імовірності задовольняють рівняння , .

На основі результатів теореми 1.1 отримується задача лінійного програмування.

На завершення першого розділу наводяться приклади застосування керованих марковських процесів в економіці та статистичній фізиці.

У другому розділі знаходяться достатні умови існування стаціонарних нерандомізованих стратегій та деякі можливості виконання цих умов у випадку нескінченності просторів станів системи та керуючих впливів. Означення графа, околу і повного околу вершини графа ті ж.

Нехай , , – деякі повні сепарабельні метричні простори. – множина станів системи, – -алгебра борелівських підмножин , , відповідно. Нехай задано повний сепарабельний метричний простір , – -алгебра борелівських підмножин .

Нехай – багатозначна функція, що співставляє кожному деяку непорожню, замкнену множину таку, що множина вимірна по Борелю в добутку просторів , тобто функція співставляє кожному стану повного околу вершини множину допустимих рішень (керувань).

Основне припущення щодо ймовірнісної еволюції керованої системи буде полягати в тому, що

,

| (5)

, | (6)

де , ,

і при фіксованих , () і , – імовірнісні міри на і , , відповідно, а при фіксованих і , , – вимірні по Борелю функції на і , , відповідно.

Стратегія , допустима для керованої системи, визначається як послідовність , де – імовірнісна міра на , що зосереджена на та вимірним чином залежить від – історії керованої системи до моменту часу (). Стратегію назвемо марковською, якщо , . Марковську стратегію назвемо стаціонарною, якщо міра , , і стаціонарною нерандомізованою, якщо міра вироджена для будь-якого . Ясно, що стаціонарну нерандомізовану стратегію можна ототожнити з борелівською функцією , причому для будь-якого .

Позначимо – клас всіх допустимих стратегій, – клас стаціонарних нерандомізованих стратегій.

Вибором стратегії ми визначаємо випадковий процес, який назвемо випадковим процесом, що керується стратегією .

Якщо в стані прийняте рішення , то очікуваний прибуток вершини за один крок буде рівним . Припустимо, що функція вимірна по Борелю на і , .

Визначимо такий критерій якості керування:

,

де – математичне сподівання, що відповідає процесу, керованому стратегією за умови .

Стратегія – оптимальна щодо -критерію, якщо

, .

Теорема 2.2. Нехай існують стала і обмежена борелівська функція на , такі, що

при всіх . Тоді , .

Якщо при цьому для деякої стратегії

при всіх , то – -оптимальна і .

Далі за допомогою деяких припущень показуються деякі можливості виконання достатніх умов існування нерандомізованих стаціонарних стратегій.

У третьому розділі розглядається ігрова постановка задачі управління марковськими процесами на графі з двома гравцями, що мають протилежні інтереси. Знаходяться достатні умови існування ціни гри та оптимальних стратегій для обох гравців.

Означення графа, околу та повного околу вершини графу, просторів , , , , -алгебр і такі ж, як і вище, за виключенням того, що множина ребер позначається . Означення простору і -алгебри аналогічне до означення простору і -алгебри .

Нехай – повний сумісний окіл вершин і , – сумісний окіл вершин і .

У кожен момент часу гравець () вибирає рішення на основі повної інформації про стан повного околу вершини (), якою він керує, до даного моменту часу включно та всіх попередніх рішень обох гравців. Після цього гравець отримує суму , а гравець – суму , , , причому

, | (7)

, | (8)

де () – сума, що виплачується вершиною (множиною вершин) вершині (множині вершин) .

Основне припущення щодо імовірнісної еволюції керованої системи буде полягати в тому, що

, ;

| (9)

,

, | (10)

де ,

, , і , , при фіксованих , , , і , – імовірнісні міри на , , і , , відповідно, а при фіксованих , , – вимірні по Борелю функції на , , і , , відповідно.

Будемо припускати, що функції (7), (8) і перехідні ймовірності (9), (10) вимірні по сукупності змінних і , , , , .

Величини , , , і визначають стохастичну гру.

Допустима стратегія гравця визначається як послідовність , де – імовірнісна міра на , вимірна по сукупності змінних. Стратегію гравця назвемо напівмарковською, якщо , , і стаціонарною, якщо існує борелівська функція , така, що , . Тут – множина всіх імовірнісних мір на з топологією слабкої збіжності. Допустимі стратегії гравця визначаються аналогічно.

Вибором стратегій гравця і гравця ми визначаємо випадковий процес, який, не дивлячись на (9), (10), не є марковським, оскільки вибір рішення в будь-який момент часу може залежати від минулого. Назвемо цей процес випадковим процесом, керованим стратегіями і .

Визначимо такі критерії якості керувань для гравців і :

,

,

де ,

– математичне сподівання, що відповідає процесу, керованому стратегіями і .

Стратегію будемо називати -оптимальною для гравця , якщо для всіх і .

Стратегію будемо називати -оптимальною для гравця , якщо для всіх і .

Якщо стратегія -оптимальна для гравця , стратегія -оптимальна для гравця , то значення відповідних функціоналів при використанні даних стратегій, тобто і , , будемо називати ціною гри для гравців і , відповідно.

Позначимо

,

, .

Теорема 3.1. Нехай існують стаціонарні стратегії гравця і гравця , сталі , і обмежена борелівська функція на , такі, що

,

,

,

,

для всіх ,

тоді стратегія – -оптимальна для гравця , стратегія – -оптимальна для гравця , а ціна гри для гравців і тотожно рівна і , відповідно.

У четвертому розділі розглядається задача управління марковським процесом на графі за умови, що в кожен момент часу керування може переходити від однієї вершини до іншої (сусідньої). Для даної задачі отримано аналоги результатів другого розділу, тому приведемо лише її постановку.

Нехай, як і в попередніх розділах, – локально-скінченний граф з множиною вершин і множиною ребер . Означення околу та повного околу вершини таке ж. Нехай , , – деякі повні сепарабельні метричні простори ( – множина станів вершини ). – множина станів системи, – -алгебри борелівських підмножин , , відповідно. Нехай заданий повний сепарабельний метричний простір (множина керуючих впливів системи), – -алгебра борелівських підмножин .

Нехай – багатозначна функція, що співставляє кожному і кожній вершині деяку непорожню, замкнену множину , таку, що множина вимірна по Борелю в добутку просторів , тобто функція співставляє кожному стану системи і керуючій вершині множину допустимих рішень (керувань).

У кожен момент часу на підставі інформації про стан повного околу керуючої вершини і керування, система приймає рішення про перехід до однієї із вершин повного околу вершини (тобто вона може залишатися на місці) за допомогою перехідних ймовірностей , , , вимірних по сукупності змінних.

Далі, у вершині , в яку потрапила система, приймається керування , на підставі інформації про всі стани системи, керуючі вершини та керувань до теперішнього моменту часу. Основне припущення щодо імовірнісної еволюції керованої системи буде полягати в тому, що

(11)

де , ,

, ,

.

Допустима стратегія для керованої системи визначається як послідовність , де – імовірнісна міра на , яка зосереджена на та вимірним чином залежить від – історії керованої системи до моменту часу . Стратегію назвемо марковською, якщо , . Марковську стратегію назвемо стаціонарною, якщо , і стаціонарною нерандомізованою, якщо міра вироджена для будь-якого і довільної вершини , тобто стаціонарну нерандомізовану стратегію можна ототожнити із борелівською функцією , причому для будь-яких і .

Позначимо – клас всіх допустимих стратегій, – клас стаціонарних нерандомізованих стратегій.

Вибором стратегії ми визначаємо випадковий процес, який, не дивлячись на (11), не є марковським, оскільки вибір керування в будь-який момент часу може залежати від усієї історії . Назвемо цей процес випадковим процесом, що керується стратегією , перехідні імовірності якого .

Якщо в стані – керуюча вершина і система приймає рішення , то очікуваний прибуток системи за один крок дорівнює . Припустимо, що функція вимірна по Борелю на і , . Визначимо такий критерій якості керування:

,

де – математичне сподівання, що відповідає процесу, керованому стратегією , перехідні ймовірності якого , за умови, що , .

Стратегія – оптимальна, якщо , , .

ВИСНОВКИ

У дисертації одержано такі основні результати:

1.

2.

3.

4.

Основним математичним апаратом дослідження марковських процесів прийняття рішень на графі були рівняння Беллмана, теорема Банаха про нерухому точку.

Основні положення дисертації опубліковані в таких працях:

1.

2.

3.

4.

Чорней Р.К. Задачі управління марковськими процесами з післядією. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2000.

Дисертацію присвячено питанню управління марковськими полями на графах. Особливістю є означення марковості, а саме: стан деякої вершини графа залежить від стану її повного околу і рішення в попередній момент часу. Показано актуальність такого підходу до означення марковості. Доведено, що оптимальні стратегії в задачі мінімізації функціоналу середніх затрат в одиницю часу при скінченності просторів станів системи та простору керуючих впливів для деякої вершини можна вибрати в класі нерандомізованих однорідних марковських стратегій. При нескінченності просторів значень кожної з вершин і керуючих впливів для задачі керування однією вершиною і задачі переходу керування від однієї вершини до іншої отримано достатні умови існування оптимальних нерандомізованих стаціонарних стратегій і деякі можливості виконання цих достатніх умов при критерії якості середніх доходів в одиницю часу. Отримано достатні умови існування оптимальних нерандомізованих стаціонарних стратегій і тотожної рівності сталій ціни гри для обох гравців в стохастичній грі на графі.

Ключові слова: марковість, управління, нерандомізована стаціонарна стратегія, стохастична гра.

Чорней Р.К. Задачи управления марковскими процессами с последействием. – Рукопись.

Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2000.

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

В разделе 1 рассматривается задача управления марковскими полями на графе при условии, что фазовое пространство системы и множество управляющих воздействий состоят из конечного числа точек. Критерием качества управления является минимизация средних затрат некоторой вершины в единицу времени. При помощи рассмотренных свойств дисконтированного критерия качества управления доказывается, что в классе нерандомизированных однородных марковских стратегий существует единственная оптимальная стратегия. Далее, на основании этих результатов в качестве примера приводится задача линейного программирования для отыскания оптимальной стратегии, а также даются примеры использования результатов исследования рассматриваемой модели в экономике (если вершины графа интерпретировать как организации или фирмы, ребра – как их взаимодействие, а управляющие воздействия как выбор конкурирующих технологий) и статистической физике (модель Изинга).

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

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

В разделе 4 поставлена задача перехода управления системой из одной вершины к другой (соседней) при помощи некоторых переходных вероятностей, зависящих от состояния управляющей вершины и ее окрестности, а также от выбранного ею управляющего воздействия. Критерием качества является максимизация прибыли системы в единицу времени. Для этой задачи на основании результатов раздела 2 получены достаточные условия существования оптимальных нерандомизированных стационарных стратегий и некоторые возможности выполнения этих достаточных условий с помощью введения некоторых естественных предположений. Как и в разделе 2 вводятся некоторые операторы, доказывается их сжимаемость, и исходя из этого показывается возможность существования единственного решения уравнения оптимальности.

Ключевые слова: марковость, управление, нерандомизированная стационарная стратегия, стохастическая игра.

Chorney R.K. Problems of Markov processes control with an aftereffect. – Manuscript.

Thesis for the Degree of Candidate of Phisics-Mathematical Science in Speciality 01.05.01 – Theoretical Foundations of Informatic and Cybernetics. – V.M.Glushkov Institute Cybernetics of National Academy of Science of Ukraine, Kyiv, 2000.

The disertation is devoted to Markov fields control on graphs. Peculiarity is definition of Markov property, that is, the state of a certain vertex depends on state of its full neiborhood and its decision at a previous moment. Actuality of given method of approach to definition of Markov property is shown. It is proved that optimal strategy in problem of minimizing of average expenses functional per time unit in case of finite action space and finite phase space we can choose in nonrandomized homogeneous strategy class. If phase space and action space are infinite for problem of one vertex control and problem of transition of control from vertex to vertex sufficient conditions of existence of optimal nonrandomized stationary strategies and a some probabilities of accomplishment of these sufficient conditions for average cost criteria per time unit are obtained. Sufficient conditions of existence of nonrandomised stationary strategy and a game value is identically equal to a constant for both Players in stochastic game on graph is obtained.

Key words: Markov property, control, nonrandomized stationary strategy, stochastic game.