Содержание к диссертации
Введение
Глава 1. Исследование «игры» неравноправных противников 18
1. Введение 18
2. Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников 21
3. Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников, когда сообщается часть информации 34
Глава 2. Управление при неполной информации случайными процессами в условии неравноправия 50
1. Введение 50
2. Управляемые полумарковские процессы 51
3. Построение зависимых минимаксных (максиминных) стратегий управления и определение значений минимакса (максимина) при исследовании дробно-линейного целевого функционала 54
Глава 3. Полумарковское преобразование времени 79
1. Введение 79
2. Функционал накопления 79
3. Пример 84
4. Функционал достижения 98
Приложение 1 Пример. Анализ модели 102
- Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников
- Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников, когда сообщается часть информации
- Построение зависимых минимаксных (максиминных) стратегий управления и определение значений минимакса (максимина) при исследовании дробно-линейного целевого функционала
- Функционал накопления
Введение к работе
Настоящая работа посвящена проблемам управления полумарковскими процессами при неполной информации. Разработаны новые постановки задач управления ПМП и методы их решения. Управляемые ПМП широко используются при исследовании моделей надежности и массового обслуживания.
Постановка любой конкретной задачи оптимального управления включает в себя ряд факторов: математическую модель управляемого объекта, цель управления (именуемую иногда критерием качества), различного рода ограничения на траекторию системы, управляющее воздействие, длительность процесса управления, класс допустимых управлений и т.д.
Многочисленные методы управляемых систем массового обслуживания, модели управления запасами, контроля, детерминированные и вероятностные модели развивающейся экономики вкладываются в абстрактную модель управляемой системы, обладающей марковским свойством. Это свойство заключается в том, что будущее поведение системы полностью определяется ее состоянием в настоящий момент времени и управлением, принятом в этот момент времени. Связь с прошлым определяется только через управление, которое может выбираться на основе всей истории системы до настоящего момента. Исследование управляемой системы сводится к исследованию управляемого случайного процесса. Классификация моделей в зависимости от случайных процессов приведена в [19].
При исследовании управляемой системы нужно знать вероятностные характеристики случайного процесса. Вероятностные характеристики процесса зависят от вероятностных характеристик случайных величин. В моделях надежности - это случайная величина времени безотказной работы элемента (системы), доля времени нахождения объекта в исправном состоянии, случайное время от начала эксплуатации до момента наступления предельного состояния объекта и т.д. В системах массового обслуживания -это интенсивность прихода требований в систему, случайная величина длительности обслуживания требования, количество мест в очереди.
Достаточно часто эти характеристики случайных величин не известны. Для их получения проводят статистические испытания, на основании которых строятся интервалы для этих характеристик. Так как по статистическим данным получили множество характеристик, то получаем множество процессов, соответствующих множеству характеристик. Тогда исследование управляемой системы сводится к исследованию множества случайных процессов.
Одной из основных особенностей класса полумарковских процессов является замкнутость класса относительно преобразования замены времени достаточно общего вида, которое не сохраняет марковость. Одной из основных проблем теории полумарковских процессов является представление любого такого процесса в виде марковского процесса, преобразованного заменой времени [55, 56].
В работах приведены результаты исследования различных задач для марковских цепей с конечным множеством состояний. Доказаны теоремы об асимптотическом поведении характеристик, построенных на траекториях марковских цепей, и приведены примеры их применения.
Для управляемого полумарковского процесса динамика процесса описывается полумарковским ядром, зависящего от стратегии управления. Стратегия управления, в общем случае, зависит от выбранного управления в текущем состоянии системы.
Далее приводится обзор основных работ, посвященных проблемам и их решениям для марковских и полумарковских процессов.
В книге [57] изложены результаты исследований управляемых марковских цепей с конечным множеством состояний. Для построенной модели была предложена процедура целенаправленного поиска оптимальной стратегии, максимизирующей функционал дохода, построенный на траекториях марковской цепи.
Майн, Осаки [37] изучали марковские процессы принятия решений с конечным временем планирования. В этой работе авторы, для нахождения оптимальной стратегии, использовали принцип оптимальности и метод динамического программирования. С позиции линейного программирования предложенная процедура улучшения решения является таким расширением симплексного критерия, при котором последний используется одновременно во всех состояниях. Доказана теорема о сведении процедуры поиска оптимальной стратегии для дробно-линейного функционала к задаче линейного программирования при линейных ограничениях. Доказано, что алгоритм сходится к оптимальной стратегии за конечное число итераций.
Описываются управляемые полумарковские процессы с конечным множеством состояний [17] с конечным множеством управления. Джевелл привел алгоритмы поиска оптимальной однородной стратегии для задачи с бесконечным числом переходом и для задачи с бесконечным временем функционирования. Построенные алгоритмы последовательных приближений в пространстве стратегий для максимизации дохода остаются почти такими же, как и для марковских моделей, за исключением бесконечных случаев.
Авторы описывают [5] первые постановки минимаксных задач в теории надежности. Для конкретных моделей надежности ищутся минимаксные стратегии с некоторыми математическими ограничениями, например, известно математическое ожидание или фиксировано время проведения профилактик. Также могут существовать ограничения на вторые моменты. Приведены оценки для распределения с ограниченным математическим ожиданием.
В книге [3] доказана теорема о поведении оптимальной функции распределения для полумарковских процессов, ограниченная двумя другими функциями распределения. Теорема доказывает, что оптимальная функция распределения, ограниченная снизу и сверху двумя другими функциями, скачет с нижней границы на верхнюю, или идет по прямой до «пересечения» с одной из двух ограничивающих функций.
В книгах [34, 35, 51] изложено обобщение достижений о марковских и полумарковских процессах на момент издания и приведены некоторые обобщающие теоремы.
В книге [24] доказана теорема о том, что максимум (минимум) функционала дохода достигается на вырожденном множестве функций распределения, при некоторых ограничениях на подынтегральные функции функционала дохода, построенного на траекториях полумарковского процесса.
Решается задача [2] поиска минимакса (максимина) для дробно-линейных функционалов по двум множествам. Доказана теорема о структуре мер, которые позволяют искать внешний и внутренний экстремум при ограничениях на подынтегральные функции дробно-линейного функционала, построенного на траекториях полумарковского процесса. Доказана лемма о совпадении множеств функций распределения, на которых достигаются экстремумы дробно-линейного и специально подобранного линейного функционала. Но эта лемма не позволяет определить распределение, на котором достигается экстремум дробно-линейного функционала, исследуя линейный функционал, поскольку в его определении фигурирует неизвестная константа. Однако, если удается определить, что множество, на котором достигается экстремум специально подобранного линейного функционала, содержит подмножество, обладающее некоторыми специальными свойствами, то тогда экстремум дробно-линейного функционала можно искать по более узкому множеству распределений, обладающих этими свойствами. Основной результат работы заключается в том, что внутренний экстремум достигается на множестве вырожденных функций распределения и, следовательно, можно искать внешний экстремум линейного функционала.
В работе [23] предложен алгоритм целенаправленного поиска оптимальной стратегии в классе однородных конечных марковских цепей с конечным множеством состояний. В отличии от предыдущих результатов, полученных Ховардом, Джевеллом и Майн, Осаки, изучаются задачи управления с неполной информацией марковскими цепями, это означает, что для каждой стратегии существует множество марковских цепей и ищется двойной экстремум, то есть либо минимакс, либо максимин.
Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников
Исследование управляемой системы сводится к исследованию управляемого случайного процесса. Классификация моделей в зависимости от случайных процессов приведена в [19].
При исследовании управляемой системы нужно знать вероятностные характеристики случайного процесса. Вероятностные характеристики процесса зависят от вероятностных характеристик случайных величин. В моделях надежности - это случайная величина времени безотказной работы элемента (системы), доля времени нахождения объекта в исправном состоянии, случайное время от начала эксплуатации до момента наступления предельного состояния объекта и т.д. В системах массового обслуживания -это интенсивность прихода требований в систему, случайная величина длительности обслуживания требования, количество мест в очереди.
Достаточно часто эти характеристики случайных величин не известны. Для их получения проводят статистические испытания, на основании которых строятся интервалы для этих характеристик. Так как по статистическим данным получили множество характеристик, то получаем множество процессов, соответствующих множеству характеристик. Тогда исследование управляемой системы сводится к исследованию множества случайных процессов.
Одной из основных особенностей класса полумарковских процессов является замкнутость класса относительно преобразования замены времени достаточно общего вида, которое не сохраняет марковость. Одной из основных проблем теории полумарковских процессов является представление любого такого процесса в виде марковского процесса, преобразованного заменой времени [55, 56]. В работах [62, 68, 70, 87, 88, 94, 102, 71, 74, 76, 95] приведены результаты исследования различных задач для марковских цепей с конечным множеством состояний. Доказаны теоремы об асимптотическом поведении характеристик, построенных на траекториях марковских цепей, и приведены примеры их применения. Для управляемого полумарковского процесса динамика процесса описывается полумарковским ядром, зависящего от стратегии управления. Стратегия управления, в общем случае, зависит от выбранного управления в текущем состоянии системы. Далее приводится обзор основных работ, посвященных проблемам и их решениям для марковских и полумарковских процессов. В книге [57] изложены результаты исследований управляемых марковских цепей с конечным множеством состояний. Для построенной модели была предложена процедура целенаправленного поиска оптимальной стратегии, максимизирующей функционал дохода, построенный на траекториях марковской цепи. Майн, Осаки [37] изучали марковские процессы принятия решений с конечным временем планирования. В этой работе авторы, для нахождения оптимальной стратегии, использовали принцип оптимальности и метод динамического программирования. С позиции линейного программирования предложенная процедура улучшения решения является таким расширением симплексного критерия, при котором последний используется одновременно во всех состояниях. Доказана теорема о сведении процедуры поиска оптимальной стратегии для дробно-линейного функционала к задаче линейного программирования при линейных ограничениях. Доказано, что алгоритм сходится к оптимальной стратегии за конечное число итераций.
Описываются управляемые полумарковские процессы с конечным множеством состояний [17] с конечным множеством управления. Джевелл привел алгоритмы поиска оптимальной однородной стратегии для задачи с бесконечным числом переходом и для задачи с бесконечным временем функционирования. Построенные алгоритмы последовательных приближений в пространстве стратегий для максимизации дохода остаются почти такими же, как и для марковских моделей, за исключением бесконечных случаев.
Авторы описывают [5] первые постановки минимаксных задач в теории надежности. Для конкретных моделей надежности ищутся минимаксные стратегии с некоторыми математическими ограничениями, например, известно математическое ожидание или фиксировано время проведения профилактик. Также могут существовать ограничения на вторые моменты. Приведены оценки для распределения с ограниченным математическим ожиданием.
Исследование минимаксных стратегий и величины выигрыша в «игре» неравноправных противников, когда сообщается часть информации
В классической постановке задачи теории игр [50] задаются два семейства вероятностных пространств (Ui, В«, PJ, 1=1,2, где множества Счесть некоторые множества решений, которые может принять первый и второй игрок, (В, - сг-алгебры подмножеств множеств /,-, Р{ - вероятностные меры, определенные на сг-алгебрах ( РІЄЧ , % - заданные множества вероятностных мер.
Задача состоит в исследовании на экстремум линейного функционала где множество [/определяется равенством U=U] X U2, то есть U- множество пар (uj, U2), щеиь i=l,2, вероятностная мераР(В/,Д определена на сг-алгебре В подмножеств множества U, которая равна минимальной сг-алгебре, порожденной конечными суммами непересекающихся прямоугольников B=BjXB2 со сторонами ВієФі и B2E BZ И ДЛЯ ЭТОЙ меры справедливо равенство P(B],B2)=Pi(Bj)P2(B2). Таким образом семейства вероятностных мер %, определенные на с -алгебрах ( порождают семейство вероятностных мер % которые определены на сг-алгебре (В.
В теории игр меры PfE i=l,2, определяющие правило выбора решений игроками, независимы, то есть правило выбора решения /-м игроком в вероятностном смысле не зависит от того, какое решение принял игроку ij=l,2,№ Мера РІЄ% і=1,2 называется стратегией z -го игрока, а множество мер % - множеством допустимых стратегий /-го игрока. При этом дополнительным условием следует считать существование интеграла (1.1) для любых РІ є % і=1,2.
Рассматриваются игры с нулевой суммой, то есть функция Afuj.u определяет величину выигрыша второго игрока, если первый игр принял решение U], а второй игрок принял решение и2, щеии а величина A(u],U2) есть выигрыш первого игрока при тех же условиях. Другими словами, значение функции A(uj,U2) определяет величину проигрыша первого игрока. При фиксированных стратегиях Р\ и Р2 интеграл (1.1) определяет цену игры.
Игроки с противоречивыми интересами стремятся к различным целям: один стремится выбором своей стратегии Р] из множества допустимых стратегий ] минимизировать свой проигрыш, а другой стремится выбором своей стратегии Р2 из множества допустимых стратегий Ч максимизировать свой выигрыш. Поэтому возникают две задачи поиска экстремумов и таких стратегий Р(0){, i=l,2, при которых эти экстремумы достигаются. . Если определена стратегия Р( і первого игрока, на которой достигается минимум максимума (1.2) и этот игрок придерживается этой стратегии, то гарантировано, что в этой игре его ущерб не будет превышать величины этого минимума. Если определена стратегия Р(0)2 второго игрока, на которой достигается максимум минимума (1.3) и второй игрок придерживается этой стратегии, то гарантировано, что в этой игре его выигрыш не будет меньше величины этого максимума. Именно в этом состоит основной смысл принципа минимакса, который положен в основу сформулированных задач (1.2) и (1.3) теории игр.
Если в игре двух лиц существуют экстремумы (1.2) и (1.3), тогда меры Р ІЄ і=1,2, для которых выполняются неравенства при любых FiE t, i=l,2, называются ситуацией равновесия. Пара мер (Р(0)і, Р(0)2), Р(0)І %, і-1,2, для которых совпадают экстремумы называется седловой точкой. Очевидно, что для ситуации равновесия справедливы равенства (1.4). Ситуация равновесия (при ее существовании) в определенном смысле удовлетворяет обоих игроков, поскольку гарантирует оптимальные (минимальное и максимальное) значения ущерба и выигрыша. Из сказанного выше следует, что в теории игр исследуются: проблемы поиска стратегий, на которых достигается ситуация равновесия; условия, при которых такая ситуация существует; свойства стратегий, на которых достигается ситуация равновесия; исследуются условия, при которых ситуация равновесия достигается на вырожденных распределениях [50, 66, 67, 72, 79, 86,105]. При этом одним из основных ограничений классической задачи теории игр является предположение о независимости принятия решений конфликтующими сторонами. Если отказаться от условия независимости принятия решения, то противники становятся в определенном смысле неравноправными. Исследованию новой ситуации посвящены последующие материалы.
Построение зависимых минимаксных (максиминных) стратегий управления и определение значений минимакса (максимина) при исследовании дробно-линейного целевого функционала
В литературе [1, 2, 4, 17, 19, 23, 24, 57] известны исследования проблемы поиска минимакса (максимина) дробно-линейного функционала и вероятностных распределений, на которых он достигается. Такая проблема возникает при решении задачи поиска оптимальных стратегий управления некоторыми классами случайных процессов (марковскими, полумарковскими), когда критерием качества управления является аддитивный функционал, построенный на траекториях управляемого случайного процесса, и управление осуществляется в условиях неполной информации об исходных вероятностных характеристиках [1, 2, 4, 19, 23, 24].
В настоящей главе будет исследована проблема поиска минимакса (максимина) дробно-линейного функционала и вероятностных распределений, на которых он достигается, в условиях, когда принимаемые решения противников с противоречивыми интересами зависимы, то есть противники неравноправны.
Исследование базируется на результатах, позволяющих свести поиск экстремума дробно-линейного функционала к поиску экстремума специально подобранного линейного функционала. Управляемый полумарковский процесс X(t) с конечным множеством состояний Е={1,...п} задается однородной цепью Маркова (,, в, и), где ,єЕ, 6є[0, со), и &U. Цепь Маркова определяется полумарковским ядром считающий процесс, 60=0. Полумарковское ядро Q ij(t,B) определяет вероятностную меру на измеримом пространстве (U,B) В силу неравенства i(B) Q ij(t,B) существуют функции Qij(t,u), для которых Управляемый полумарковский процесс задается семейством матриц (Qi/t,u)), набором вероятностных мер Pt(B) и распределениемри ЦєЕ. В работе [17] приведены алгоритмы поиска оптимальной однородной стратегии для задачи с бесконечным числом переходом и для задачи с бесконечным временем функционирования. Построенные алгоритмы последовательных приближений в пространстве стратегий для максимизации дохода остаются почти такими же, как и для марковских моделей, за исключением бесконечных случаев. В работах [4, 24] доказано, что функционал, построенный на траекториях полумарковского процесса, является дробно-линейным функционалом относительно функций распределения Pt. Обозначим математическое ожидание времени непрерывного пребывания в состоянии і, при условии, что процесс находился в состоянии і, через J Математическое ожидание накопленного дохода за время непрерывного пребывания процесса в состоянии / обозначим через а ,-. Математическое ожидание накопленного дохода при принятом управлении и при условии, что процесс находился в состоянии / перейдет в состояние j, и время перехода равно / обозначим через Ry(t,u). Тогда справедливо равенство Для вложенной цепи Маркова существует стационарное распределение к. Стационарная вероятность п , - есть вероятность нахождения в состоянии , независимо от номера состояния п. В матричном виде П=ПР или П(1 Р)-Оу где П=(ггі,я2,...,ггп) Для существования единственного решения данной системы добавляют условие нормировки я, =7, п ,- 0. Для полумарковских процессов справедливо равенство Pij-Qij( ), Р=(ру), связывающее вероятности перехода полумарковского процесса и вложенной марковской цепи.
Функционал накопления
По условиям примера известно, что параметр А,,- принадлежит некоторому интервалу значений Atefa bJ, /=1,2.
Из теории [19, 23] известно, что один из управляющих полумарковским процессом может действовать детерминировано, то есть экстремум maxG(t)S(X,G(t)) может достигаться на множестве вырожденных функций распределений длительности обслуживания. Пусть в условиях данного примера maxG(t)S(X,G(t)) достигается на вырожденных функциях распределения длительности обслуживания, то есть выбирается время, в течение которого требование будет обслуживаться в каждом состояние.
Тогда задача поиска экстремума minxmaxc(t)S(X, G(t)) сводится к задачам поиска экстремума вида minjmaxtS(A,t). Управлять будем потоком входящих требований и длительностью обслуживания требований. Допустим, что управляющие системой могут действовать в соответствие с одним из вариантов: 1) управляющие не сообщают своего принятого решения друг другу, тогда анализируется экстремум вида minxmaxtS(X,t), 2) один из управляющих системой сообщает свое решение другому, тогда анализируется экстремум вида minxmaxt S(X,t), Про параметр интенсивности прихода требований в систему Ли /=1,2 известно, что он может принадлежать одному из множеств функций распределений: А) множество функций распределения с нормальным законом распределения с математическим ожиданием я,- и дисперсией jit i-1,2; Б) множество функций распределения с равномерным законом распределения. Задача 1) разбивается на три задачи поиска экстремума, зависящих от того, какому множеству функций распределений принадлежит параметр А,,-/=1,2. Для задачи 2) известно, что экстремум достигается на множестве вырожденных распределений. Если параметр X принадлежит множеству функций распределения с нормальным законом распределения с математическим ожиданием а и дисперсией а (случай А); и функция длительности обслуживания принадлежит множеству вырожденных функций распределений, то задача поиска экстремума minxmax (X,t) сводится к задаче поиска экстремума maxtS(t). Если параметры Я принадлежат классу распределений с нормальным законом N(a,q), то функционал дохода S(t) представляет собой функционал, зависящий от І В Приложении 2 приведены численные значения функционала при различных значениях констант с о и с$)=с& i=2,3,4,5. Если параметр X принадлежит множеству функций распределения с равномерным законом распределения (случай Б); и функция длительности обслуживания принадлежит множеству вырожденных функций распределений, то задача поиска экстремума тгпхтах (Я,і) сводится к задаче поиска экстремума max,S(t). В Приложении 3 приведены численные значения функционала при различных значениях констант с0 и Ci(t)=Cit, 1=2,3,4,5. В Приложении 4 приведены численные значения функционала при различных значениях констант со и Ci(t)=Cit, і=2,3,4,5 для задачи 2), то есть сообщаем полностью принятое решение. Приведем результаты исследования для случая, когда в нормальном законе распределения не известна дисперсия сг{ при известном математическом ожидании щ, /=1,2, то есть это случай, в котором сообщают часть решения (нам не известно точное нормальное распределение, а знаем только класс нормальных распределений с заданным математическим ожиданием). В формулах для числителя и знаменателя при неизвестной дисперсии получим функционал дохода, зависящий от двух переменных дисперсии и длительности обслуживания. Задача поиска экстремума вида minxmaxG(t)S(hG(t)) сводится в задаче поиска экстремума minjnaxt(a)S(cr,t). В Приложении 5 приведены численные значения функционала при различных значениях констант со и с$)=с$, i=2,3,4,5. Из приведенных результатов видно, на сколько отличаются значения функционала дохода в зависимости от «количества» информации. Также на величину дохода влияет, к какому классу функций распределения принадлежит параметр X (интенсивность потока входящих требований) и функция длительности обслуживания. Величина дохода в случае, когда параметр X принадлежит классу функций распределений с равномерным законом, значительно меньше, чем в случае, когда параметр X принадлежит классу функций распределений с нормальным законом. В Приложениях 4, 5 приведены численные значения функционала, из которых видно, на сколько увеличивается доход, если сообщаем решение полностью. Наибольшую величину дохода можно получить, в случае сообщения принятого решения полностью. При сообщении части принятого решения или в случае определения величины экстремума функционала дохода, когда не известно принятое решение, значительно уменьшает величину дохода.
