На правах рукописи

Мерзлова Елена Юрьевна

ОБ ОПТИМАЛЬНОМ УПРАВЛЕНИИ ПОЛУМАРКОВСКИМИ

ПРОЦЕССАМИ ДВУМЯ ИГРОКАМИ С ПРОТИВОРЕЧИВЫМИ

ИНТЕРЕСАМИ

01.01.05 – Теория вероятностей и математическая статистика

Автореферат

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

Москва 2006

Работа выполнена на кафедре исследования операций Московского института электроники и математики.

Научный руководитель: доктор физ.-мат. наук, профессор Каштанов В. А.

Официальные оппоненты:

доктор физ.-мат. наук, профессор Рыков В.В.

(Российский государственный университет нефти и газа им. И.М. Губкина) доктор тех. наук, профессор Афанасьев В.Н.

(Московский институт электроники и математики)

Ведущая организация - Институт проблем информатики РАН.

Защита состоится 13 июня 2006 г. в 16-00 на заседании диссертационного совета К 212.133.01 в Московском институте электроники и математики по адресу: 109028, г. Москва, Б.

Трехсвятительский пер., 3/12.

С диссертацией можно ознакомиться в Научной библиотеке Московского института электроники и математики.

Автореферат разослан 25 апреля 2006г.

Ученый секретарь диссертационного совета к.ф-м.н., доцент Е.Р. Хакимуллин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Вероятностные характеристики процесса зависят от вероятностных характеристик случайных величин. На практике характеристики случайных величин часто не известны, в связи с этим получаем множество управляемых систем. Используя методы, приведенные в работе, выбираем оптимальное управление системой.

Большой вклад в развитие теории, методов анализа и оптимального управления систем внесли Р. Ховард, Х. Майн, С. Осаки, В. Джевелл, Р.

Барлоу, Ф. Прошан, Ивченко Г.И., Каштанов В.А., Коваленко И.Н., Е.Ю.

Барзилович, Рыков В.В., Гихман И.И., Скороход А.В. и другие.

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

Цель диссертационной работы. Развитие теории управления случайными процессами и системами массового обслуживания с неполной информацией, методы их анализа, разработка методов оптимизации управления, в зависимости от «количества» и «качества» неполноты информации.

Основные задачи

.

1. Разработка новых постановок задач оптимального управления полумарковскими процессами.

полумарковскими процессами с неполной информацией. Определение структуры оптимальных стратегий управления.

траекториях управляемого полумарковского процесса.

Методы исследования. Использовались методы и результаты теории вероятности, математической статистики, теории управляемых случайных процессов, теории полумарковских процессов, теории массового обслуживания, теории игр.

Основные результаты и научная новизна.

1. Сформулированы новые постановки задач оптимального управления ПМП.

2. Исследована структура оптимальных стратегий управления.

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

новыми.

теоретический и практический характеры. Полученные в ней результаты представляют вклад в развитие теории управляемых ПМП, методы их анализа.

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

Апробация работы. Результаты докладывались и обсуждались на Всероссийской школе-коллоквиуме по стохастическим методам в 2001г.г, научно-технической конференция студентов, аспирантов и молодых специалистов в МГИЭМ 2001 и 2002 г.

Публикации. По результатам диссертации опубликовано 13 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и шести приложений. Объем диссертации - 156 страниц. Список литературы включает 105 наименования.

СОДЕРЖАНИЕ РАБОТЫ

.

Введение содержит общую характеристику работы.

В первой главе поставлена новая задача поиска экстремума минимакса или максимина для линейных функционалов.

Пусть заданы два измеримых пространства (Ui,Bi), i=1,2, где множества Ui есть некоторые множества решений, которые может принять первый и второй игрок, Bi - -алгебры подмножеств множеств Ui. Как и ранее определяем множество U как множество пар (u1,u2), uiUi, i=1,2, то есть U=U1XU2. Определим -алгебру B подмножеств множества U как непересекающихся прямоугольников B=B1ХB2 со сторонами B1B1 и B2B2.

Пусть задано множество - семейство вероятностных мер, определенных на -алгебре B. Каждое распределение Р(B), BB, определяет вероятность того, что игроки приняли решения uiUi, i=1,2, для которых справедливо включение (u1,u2)В. Семейство вероятностных порождает два семейства вероятностных мер i, i=1,2, мер определенных на –алгебре Bi и задаваемых равенствами Р1(B1)=Р(B1U2) и Р2(B2)=Р(U1B2), где B1B1, B2B2. Так как для любых B1B1, B2B выполняются неравенства Р1(B1)Р(B1В2) и Р2(B2)Р(В1B2), то по теореме Радона-Никодима существуют функции Рi(Bi/uj), для которых справедливы равенства Функция Рi(Bi/uj) - есть условная вероятность принятия решения i-м игроком из множества Bi, BiBi, при условии, что j-ый игрок принял решение uj, i,j=1,2, ij. Равенства (1) позволяют утверждать, что семейство распределений порождает два семейства условных распределений i(uj), ij, i,j=1,2, Рi(Bi/uj)i(uj), определенных на –алгебрах Bi. Эти условные распределения будем называть условными стратегиями.

Если решения принимаются игроками независимо, то условная вероятность Рi(Bi/uj) не зависит от решения uj. Этот случай соответствует исследованиях предполагается, что зависимость мер имеет место (если специально не оговорено противное).

Теперь с учетом введенных выше обозначений цена игры (целевой определен равенствами которые позволяют сформулировать две игровые задачи.

Если принять во внимание первое равенство в соотношении (2), то минимизировать свой проигрыш выбором стратегии Р1(B1) из множества допустимых стратегий 1, Р11, а второй стремится максимизировать свой выигрыш выбором стратегии Р2(B2/u1) из множества условных стратегий 2(u1), Р2(B2/u1)2(u1), то есть стратегия второго игрока, определяемая мерой Р2(В/u1), зависит от принятого решения первым игроком. Другими словами, второй игрок знает решение, принятое первым, или первый игрок сообщает свое решение другому игроку. В этом смысле игроки становятся неравноправными, так как один из них сообщает свое решение другому.

Если использовать второе равенство в соотношении (1.6) и для такого представления формулировать игровую задачу, то получаем, что второй игрок сообщает первому свое принятое решение и его стратегия зависит от решения, принятого первым игроком.

Эти задачи можно записать в виде двух «игр», заключающихся в определении стратегий, на которых достигаются экстремумы где функция Рj(иj/ui) - есть условная вероятность принятия решения j-м игроком из множества Bj, BjBj при условии, что i-ый игрок принял решение ui, i,j=1,2 и величин этих экстремумов.

Тогда справедлива теорема.

Пусть для любых управлений uiUi существуют такие u*j(ui)Uj, А(u1,u*2(u1))=maxu2U2А(u1,u2), и пусть множества допустимых стратегий i и i(uj), ujUj, i,j=1,2, ij содержат все детерминированные стратегии, то есть *ii, *j(ui)j(ui), i,j=1,2, ij.

Тогда детерминированных стратегий *1, *2(u1) и *2, *1(u2) соответственно, и Справедлива теорема о том, что расширение возможностей игрока, получающего информацию о решении, принятом другим игроком, не увеличивает его выигрыш (не уменьшает его проигрыш).

Если выполняются условия теоремы 1.1, то экстремумы достигаются на вырожденных распределениях и выполняются равенства противоречивыми интересами, в которой противники неравноправны и один из них может сообщать другому не полностью принятое решение, а только его часть.

определен равенствами Тогда для игроков с противоречивыми интересами сформулированы две задачи, заключающиеся в определении стратегий, на которых достигаются экстремумы minP1111minP1212(u11)maxP2(u11)2(u11)J(P11,P12(и11),P2(и11)), maxP2121maxP2222(u21)minP1(u21)1(u21)J(P1(и21),P21,P22(и21)), где функция Рj(иjj, иji/ui1) - есть условная вероятность принятия решения j-м игроком из множества Bj, BjBj и i-м игроком решения uiBi при условии, что i-ый игрок принял решение ui1, i,j=1,2.

Исследуется класс стратегий, для которого справедлива теорема.

Теорема 1.3.

Пусть для любого решения и11U11 (и21U21) существует экстремум и пусть существует экстремум minP1111minP1212(u11)maxP2(u11)2(u11) J(P11,P12(и11),P2(и11))= maxP2121maxP2222(u21)minP1(u21)1(u21) J(P1(и21),P21,P22(и21))= тогда справедливы равенства minP1111minP1212(u11)maxP2(u11)2(u11)J(P11,P12(и11),P2(и11))= =minP11*11minP1212(u11)maxP2(u11)2(u11)J(P11,P12(и11),P2(и11)), maxP2121maxP2222(u21)minP1(u21)1(u21)J(P1(и21),P21,P22(и21))= =maxP21*21maxP2222(u21)minP1(u21)1(u21)J(P1(и21),P21,P22(и21)).

Справедливы теоремы (теоремы 1.4-1.7) о величинах дохода для трех видов задач: классическая постановка задачи, один из противников сообщает полностью принятое решение и один из противников сообщает только часть принятого решения и соотношение величин дохода для каждой постановки задачи.

Пусть заданы множества i, i(uj) i,j=1,2, ij. Тогда для любых Рi, Рij и Рi(uj), ij, i,j=1,2, справедливо неравенство minP1111minP1212(u11)maxP2(u11)2(u11) J(P11,P12(и11),P2(и11)) Пусть заданы множества i, ij и i(uj) i,j=1,2, ij. Тогда для любых Рi, Рij и Рi(uj), ij, i,j=1,2, справедливо неравенство maxP2121maxP2222(u21)minP1(u21)1(u21) J(P1(и21),P21,P22(и21)).

Пусть заданы множества i, ij и i(uj) i,j=1,2, ij. Тогда для любых Рi, Рij и Рi(uj), ij, i,j=1,2, справедливо неравенство maxP2121maxP2222(u21)minP1(u21)1(u21)J(P1(и21),P21,P22(и21)) Пусть заданы множества i, ij и i(uj) i,j=1,2, ij. Тогда для любых Рi, Рij и Рi(uj), ij, i,j=1,2, справедливо неравенство minP111minP1212(u11)maxP2(u11)2(u11) J(P11,P12(и11),P2(и11)).

В главе 2 сформулированы задачи поиска экстремума минимакса экстремумы для полумарковских процессов с конечным множеством состояний E={1, 2, …, n}. Множество управления U имеет вид U=U1xU2, где U1=(u11, u12, …, u1n), U2=(u21, u22, …, u2n). Функции А(и1,и2) и В(и1,и2) будут функциями от многих переменных, то есть и1=(и11, и12, …, и1n), и2=(и21,и22, …, и2n). Далее для простоты будем писать А(и1,и2) и В(и1,и2).

Тогда функционал дохода имеет вид U1xU U1xU Сформулированы задачи поиска экстремума минимакса (максимина) и функций распределения, на которых достигаются экстремумы Н(1)= {P1(u2): I(P1(u2), P2)=minF1(u2)1(u2)I(F1(u2), P2)}, H(2)= {P2(и1): I(P1, P2(и1))=maxF2(u1)2(u1) I(P1, F2(и1))}, где функционалы Функционалы J(P1, Р2(и1)), J(Р1(u2), P2) определяются равенствами Для введенных обозначений справедлива лемма 2.2 о совпадении множеств функций распределения, на которых достигаются внутренние экстремумы дробно-линейных функционалов и специально подобранных линейных функционалов.

Если функция В(и1,и2)0 и при любом P2 существует Если при любом P1 существует С помощью леммы 2.2 доказывается теорема 2.3 о виде функций распределения, на которых достигаются экстремумы (3) и (4).

Пусть функции А(и1,и2) и В(и1,и2) непрерывны на U=U1xU2, функция В(и1,и2) сохраняет знак и В(и1,и2)0 и существуют экстремумы и пусть множества допустимых функций распределения i(uj), ujUj, i,j=1,2, ij содержат все детерминированные функции распределения, то есть *j(ui)j(ui).

Пусть управления uiUi, i=1,2, являются вектором, то есть ui=(ui1,ui2). Для управлений uij, j,i=1,2, справедливы следующие свойства:

a) uikUik, k,i=1,2; b) Ui1XUi2 =Ui, i=1,2 и с) (u11,u12,u21,u22)U11XU12XU XU22=U.

Таким образом, для функционала дохода справедливы представления где и=(и11,и12, и21, и22) и каждое иks k,s=1,2 имеет вид иks=(иk1,иk2, …, иkn).

экстремумы Объединив полученные результаты для полумарковских процессов с неполной информацией, получили цепочку неравенств о величинах дохода, то есть справедливо Далее для модели массового обслуживания Mk/Gk/1/1 вычислены все результаты в случае, когда управление не сообщается, сообщается частично или сообщается полностью.

Для модели системы массового обслуживания Mk/Gk/1/1 с неполной информацией, приведены численные результаты, показывающие работу теоретических результатов. В Приложении 1 приведено подробное построение аддитивного функционала дохода S(,G(t)). Необходимо найти minmaxG(t)S(,G(t)).

По условиям примера известно, что параметр i принадлежит некоторому интервалу значений i[ai,bi], i=1,2.

Из приведенных результатов видно, на сколько отличаются значения функционала дохода в зависимости от «количества» информации. Также на величину дохода влияет, к какому классу функций распределения принадлежит параметр (интенсивность потока входящих требований) и функция длительности обслуживания.

Величина дохода в случае, когда параметр принадлежит классу функций распределений с равномерным законом, значительно меньше, чем в случае, когда параметр принадлежит классу функций распределений с усеченным нормальным законом.

В Приложениях 4, 5 приведены численные значения функционала, из которых видно, на сколько увеличивается доход, если сообщаем решение.

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

В главе 3 приведены результаты исследования задачи, поиска вида функционала, построенного на траекториях полумарковских процессов, если заданы функционал дохода и функционал ресурса. Изучается полумарковский процесс с конечным множеством состояний Е и два аддитивных функционала, построенных на его траекториях, которые обозначим {(t), (t), S(t)}, где (t) – полумарковский процесс, S(t) – функционал дохода и (t) – функционал ресурса.

Обозначим через Di(x) условное математическое ожидание дохода S к моменту t при условии, что процесс (t) стартовал из состояния i и к моменту t потрачен ресурс x, то есть Di(x)=M{S/(0)=i, (t)=x}.

Справедливы теоремы о структуре условного математического ожидания дохода как для функционала накопления, так и для функционала достижения.

Теорема 3.1. Пусть множество состояний Е полумарковского процесса образует один эргодический класс, нет мгновенных состояний и - хотя бы для одного i распределение iEQij(t) – не арифметическое, - функции Rij(t), сij(t) –интегрируемы по Риману на [0,), - функции cij(x,t) удовлетворяют следующим условиям:

1. cij(x)cij(t,x) 0tx, неубывающие функции, 2. cij(0,x)=0, cij(0,0)=0, 3. cij(x)0 неотрицательные функции, 4. хотя бы для одного i существует j, для которого выполняется 5. для однозначного определения обратной функции к функции cij(x) считаем, что если для некоторых х функция cij(x) постоянна, то для обратной функции будем брать максимальное значение х, если для всех j функция cij(x)=0, то полагаем х=.

i=jEt[0,)Rij(t)dQij(t), µi=jEt[0,)cij(t)dQij(t), =(1,2,…,n) где нормированное решение алгебраической системы =P, P стохастическая матрица с элементами pij=Qij().

Теорема 3.2. Если полумарковский процесс имеет конечное множество состояний Е, Е0=(1, 2, …, n) подмножество невозвратных