Гарантии в многокритериальных динамических задачах

Сорокин, Константин Сергеевич

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

Сорокин, Константин Сергеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2009 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Гарантии в многокритериальных динамических задачах»

Автореферат диссертации на тему "Гарантии в многокритериальных динамических задачах"

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

||111111111}||11

003479873

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

Сорокин Константин Сергеевич

Гарантии в многокритериальных динамических задачах

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ I 5 ОНТ 2009

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

Москва - 2009

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

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

профессор В. И. Жуковский

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

профессор В. А. Горелик

кандидат физико-математических наук, доцент В. С. Молоствов

Ведущая организация: Факультет прикладной математики -

процессов управления Санкт-Петербургского государственного университета

Защита диссертации состоится 23 октября 2009 г. в 11.00 на заседании диссертационного совета Д 501.001.44 при Московском государ ственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москв Ленинские горы, МГУ, второй учебный корпус, факультет вычислительной ма тематики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительно математики и кибернетики МГУ. С текстом автореферата можно ознакомить' на официальном сайте ВМиК МГУ http://cs.msu.ru в разделе «Наука» - «Ра бота диссертационных советов» - «Д 501.001.44»

Автореферат диссертации разослан «■#.» сентября 2009 г.

Ученый секретарь диссертационного совета профессор

Н. П. Трифонов

Общая характеристика работы

Актуальность темы

Работа посвящена исследованию активно развивающегося в последние годы направления теории принятия решений: многокритериальным задачам при неопределенности. При этом к решению предъявляется дополнительное требование оптимального сочетания исходов и сожалений-рисков (последние в формализации Сэвиджа). Рассматривается как статический случай (глава 1), так и динамический (глава 2). Эти задачи находится на стыке теорий многокритериальных задач и принятия решения в условиях неопределенности, а в динамическом случае - еще и теории дифференциальных игр.

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

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

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

Принятие решения в задаче многокритериальной оптимизации обычно сводится к выбору ЛПР одной альтернативы из некоторого допустимого множества. Последствия такого выбора оцениваются не непосредственно, а за счет

набора значений функций (в дальнейшем - критериев), определенных на мн жестве допустимых альтернатив: чем больше значение каждой из функций, те «лучше» выбранная альтернатива. Основная проблема (и отличие от класси ческих задач оптимизации) состоит в том, что критериев несколько, следова тельно, обычного понятия максимума недостаточно и нужно вводить специаль ное понятие «векторного максимума». Основные варианты такого понятия был предложены в работах Парето и Гурвица (максимум по Слейтеру). Современ ное состояние классической теории принятия решения в многокритериальны задачах отражено в известной монографии В. В. Подиновского и В. Г. Ногина M

Отметим, что и в многокритериальных задачах, и в задачах при неопреде ленности отсутствует единый подход к понятию решения; когда же рассматри ваются МЗН, то единства в определении «хорошего» решения нет тем более.

Впервые, по-видимому, на МЗН обратили внимание Р. Ауманн и Б. Пеле в И при определении а- и /^-оптимальности. На основе этих понятий в И был предложено обобщение понятия минимакса на случай антагонистической игрь с векторной функцией выигрыша (векторный минимакс). В диссертационно работе используется векторный аналог седловой точки (по Слейтеру или Пар то). И, если МЗН образована за счет расширения однокритериальной задачи то понятия векторной седловой точки по Слейтеру, векторной седловой точк по Парето и «обычной» седловой точки в исходной задаче оказываются тесн связанными, что выявлено в разделе 1.4 диссертации. Если же перейти к есте ственному обобщению этой задачи и считать, что исходная задача также был многокритериальной, то столь тесная связь пропадает и получается, что перехо к расширенной задаче (то есть использование функций сожаления, построении отдельно по каждому критерию наравне с исходными критериями) существенн расширяет множество решений.

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

[1] В. В. Подиновский, В. Д. Ногин. Парето-оптимальные решения многокритериальных задач. — М.: Наука 1982.

[2] R. J. Аитапп, В. Peleg. Von Neumann-Morgenstern solutions to cooperative games without side payments / Bull. Amer. Math. Soc.- I960. - Vol. 66.-Pp. 173-179.

[3] G. Jentzsch. Some thoughts on the theory of cooperative games // Advances in game theory. Ann. Math Studies.- 1964,- Vol. 52,- Pp. 407-442.

[4] Ю.Б. Гермейер. Введение в исследование операций. — M.: Наука, 1971.

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

Задача о сужении множества всех максимальных по Слейтеру (или Парето) значений критериев эффективности на основании информации о «важности» критериев рассматривалась неоднократно (см., например, работы '5'6'71 и библиографию к ним), однако обычно используется информация об относительной важности критериев (например, «первый критерий важнее второго в 2 раза»), тогда как вопрос о соотношении коэффициентов свертки и результирующих значений критериев обычно остается в стороне. А его решение позволило бы выбирать соответствующий предпочтениям ЛПР элемент из множества векторных оптимумов без предварительного построения всего этого множества. Исследованию вопроса посвящен раздел 1.6.

В главе 2 рассматриваются динамические многокритериальные задачи при неопределенности (ДМЗН). В отличие от обычных (статических) МЗН, здесь предполагается, что управляемая система изменяется во времени и ЛПР может получать ту или иную информацию об этом функционировании, например, в виде обратной связи. Математическая формализация постановки такой задачи основывается на теориях оптимального управления и дифференциальных игр. Обращаясь к теории дифференциальных игр, будем считать первым игроком ЛПР, а вторым — лицо, «руководящее» выбором реализации неопределенного фактора.

В разделе 2.1 обсуждаются типы альтернатив ЛПР в зависимости от характера информации, получаемой ЛПР в процессе функционирования системы. Если никакой информации не поступает, то как альтернатива ЛПР, так и реализация неопределенного фактора формируются как функции от времени; тогда будем говорить, что ЛПР использует программные альтернативы или просто программы. Формализация таких задач и методика их решения основывается на теории оптимального управления, созданной Л. С. Понтрягиным И и его сотрудниками и получившей в дальнейшем широчайшее развитие. Принцип максимума используется для построения решения ДМЗН в классе программных альтернатив и неопределенностей. Игровые постановки таких задач активно изучались Л. А.

[5] В. А. Горелик, Т. П. Фомина. Основы исследования операций. — М.: МПГУ, 2004.

[6] В. Д. Ногин. Принятие решений в многокритериальной среде: количественный подход. — М.: ФИЗМАТ-ЛИТ, 2002.

[7] В. В. Подиновский. Количественная важность критериев // Автоматика и телемеханика.— 2000.— №5.-С. 110-123.

[8] Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко. Математическая теория оптимальных процессов. — М.: Наука, 1976.

Петросяном в И (в классе кусочно-программных стратегий), где к требованиям оптимальности добавились требования динамической устойчивости принципов оптимальности.

Если же ЛПР в процессе функционировании динамической системы получает информацию о текущем состоянии системы — позиции, то говорят, что ЛПР выбирает свою альтернативу из класса позиционных стратегий. По-видимому, впервые такие задачи были рассмотрены в известной книге Айзекса 1101 В дальнейшем позиционные дифференциальные игры получили развитие и теоретическое обоснование в работах Н. Н. Красовского, А. И. Субботина и их учеников tnl В данном случае по аналогии предполагаем, что неопределенный фактор формируется в том же классе позиционных стратегий, что использует ЛПР, то есть нет информационной дискриминации неопределенного фактора. Формализация МДЗН, основывающаяся на классе позиционных альтернатив и неопределенностей, отнесена в раздел 2.2.

В случае, когда предполагается неравнозначность в информированности ЛПР и неопределенного фактора, а именно, когда ЛПР в каждый момент времени «знает» не только текущую позицию, но и текущее значение неопределенного фактора, будем говорить, что ЛПР использует в качестве альтернатив класс контрстратегий. При этом возможен как вариант, при котором неопределенность использует программу, так и вариант позиционной реализации неопределенности. В разделе 2.4 активно используется пара позиционная контрстратегия - программная неопределенность. Заметим, что линейно-квадратичные ДМЗН в том виде, в котором они приводятся в разделах 2.2 и 2.4, подробно рассматривались (как в многокритериальной, так и в игровой постановках) в работах В. И. Жуковского и его учеников.

Цель работы

В проводимом в диссертации исследовании ставятся следующие цели:

• выяснить общие свойства гарантий по исходам и сожалениям в одно- и многокритериальных задачах при неопределенности; на их основе предложить конструктивные методы построения всего множества таких гарантий;

• исследовать возможность применения принципа максимума Понтрягина для построения гарантии по исходам и сожалениям в динамических многокритериальных задачах при неопределенности;

[9] L. A. Petrosian. Differential Games of Pursuit. — London, Singapore: World Sei. Publ. Co. Pt. Ltd., 1993.

[10] P■ Айзеке. Дифференциальные игры. — M.: Мир, 1965.

[11] Н. Н. КрасовскиО, А. И. Субботин. Позиционные дифференциальные игры. — М.: Наука, 1974.

• исследовать класс линейно-квадратичных динамических многокритериальных задач при неопределенности на предмет существования гарантированного по исходам и рискам решения; получить (при выполнении условий существования) явный вид такого решения.

аучная новизна работы

се основные результаты работы являются новыми и состоят в следующем:

1. для однокритериальной задачи при неопределености установлено соотношение между седловой точкой и векторными седловыми точками (по Слей-теру и Парето) в расширенной задаче (при учете двух критериев — исхода и сожаления);

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

3. для линейно-квадратичных динамических многокритериальных задач при неопределенности в классе контрстратегия ЛПР - программная неопределенность построен явный вид гарантированного по исходу и сожалению решения.

Теоретическая и практическая значимость

езультаты диссертации имеют теоретическую направленность. Полученные в азделах 1.3-1.5 свойства гарантий по исходу и сожалению носят конструктивный характер и могут быть положены в основу практических алгоритмов решения многокритериальных задач при неопределенности. Установленная в разделе 1.6 теорема позволяет точнее очертить сферу применимости методов и алгоритмов систем поддержки принятия решений в многокритериальной среде. Методы решения динамических многокритериальных задач из разделов 2.2 и 2.4 могут использоваться при исследовании некоторых классов динамических задач принятия решения, а также при создании соответствующих программных продуктов.

Методы исследования

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

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

Апробация работы

Основные результаты работы докладывались автором на научно-исследовательском семинаре «Прямые и обратные задачи оптимального управления» на факультете ВМиК МГУ имени М. В. Ломоносова и совместном семинаре программы «Динамические системы» Международного института прикладного системного анализа и факультета ВМиК МГУ, а также на ряде конференций [3, 2, 7, 10].

Публикации

Основные результаты работы представлены в статьях [1, 5, 8, 9] и материалах конференций. Кроме того, автором были написаны раздел 3.8 [4] из монографии '121 и раздел 3.6 [6] из монографии I13', оба упомянутых раздела содержат результаты численного расчета модельных примеров, непосредственно перекликающихся с материалами настоящей работы.

Структура и объем диссертации

Диссертация состоит из введения, двух глав и списка литературы, содержащего 83 наименования. Общий объем составляет 121 страницу печатного текста. Работа включает 7 графиков.

Краткое содержание работы

В главе 1 рассматриваются многокритериальные задачи при неопределенности (МЗН); в разделе 1.1 приводится постановка такой задачи в общем виде:

Г = (Л-,У,Я® ,у)), (1)

здесь :,у) = N = {1, ...,п}, п е N. С данной МЗН соотносятся

две (чисто оптимизационные) многокритериальные задачи:

_Г(з;') = (Г, **(*'.»))._

[12] В. И, Жуковский, М. Е. Салуквадзе. Риски и исходы в многокритериальных задачах управления. — Тбилиси: Интелекти, 2004.

[13] В. И. Жуковский. Конфликты и риски. - М.: РосЗИТЛП, 2007.

Г(у*) = (Х,Р(х,у*)).

В разделе 1.2 для этих задач имеются определения максимума (минимума) по Слейтеру и Парето. Приведем лишь одно из этих понятий.

Определение. Неопределенность у5 € У называется минимальной по Слейтеру для задачи Г(х*), если при любых у £ У несовместна система неравенств

Щ(х*,у8)>Ъ(х*,у) (»ело.

Кроме того, в разделе обсуждаются свойства этих векторных оптимумов.

В разделе 1.3 рассматривается задача (1) при п = 1 (то есть, однокритериаль-ная задача при неопределенности). Для нее функция сожаления используется в виде

Ф(х, у) - у) - тах Р(г, у),

где Ф (х,у) численно оценивает потери ЛПР от того, что он выбрал данную конкретную альтернативу, а не наилучшую (при заданной неопределенности).

Определение. Гарантированным по сожалению решением задачи (1) при п = 1 назовем пару (я;0, Ф°) бХхК, определяемую цепочкой равенств

Ф° = тахттФ(х,у) - ттФ(х0,у).

х£Х у£У уёУ

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

В разделе 1-4 осуществляется переход от однокритериальной задачи при неопределенности к расширенной (двухкритериальной) задаче, в которой к исходному критерию эффективности (исходу) добавляется функция сожаления

Г = (Х>К,№,1/),Ф(®,у)}). (2)

Приводится определение гарантированного по исходу и сожалению решения в виде слейтеровской седловой точки. Далее Р^ >5 Р^ Р/1^ > Р-2\ г £ М; ^(1) ^ |Г(2) ^ >5

Определение. Пара (:со, Уо) £ X х У называется слейтеровской седловой точкой в задаче (2), если У(х,у) 6 X х У выполнено

{Р(х,уо),Ф(х,уо)) {Р(х0,уо),Ф(хй,у0)) {Р{х0,у),Ф(х0,у)).

Доказываются следующие утверждения.

Утверждение. Если (хо>Уо) € X х У — слейтеровская седловая точка в задаче (2), то Ф(х0,у0) = 0.

Утверждение. Если {ха,уо) £ X х У — седловая точка в задаче (1) при п = 1, то она же будет слейтеровской седловой точкой в двухкритериальной задаче (2).

Приводятся примеры, подтверждающие строгость данного включения. Аналогично рассматривается случай сравнения векторов по Парето: F« >Р F® ^ i € N, 3j € N Ff] > Ff\ F® F® & >p F(2).

Определение. Пара (xq, yo) G X xY называется паретовской седловой точкой в задаче (2), если У(х, у) G X х Y выполнено

(F(x,y0),$(x,y0)) (F(xo,yo),${xo,yo)) (F(x0,y),${x0,y)).

Утверждение. Любая паретовская седловая точка в задаче (2) будет одновременно и слейтеровской.

Утверждение. Если i/o) G X х Y — паретовская седловая точка в дву-критериальной задаче (2), то Ф(хо, Уо) = 0.

Утверждение. Если (хо, уо) G X х Y — паретовская седловая точка в дву-критериальной задаче (2), то {хо,Уо) — седловая точка в исходной задаче (1).

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

Пусть (при n—l)W — множество всех седловых точек в исходной задаче (1),

a Ws и Wp — множество всех слейтеровских и паретовских точек соответственно

в двухкритериальной задаче (2). Обозначим х*(у) = ArgmaxF(x,у), а у*(я) =

хех

— ArgminF(z,y).

уеХ

Теорема. Если в задаче (1) функция сожаления существует, то выполнена цепочка включений:

WP С W С Ws.

Теорема. Если в задаче (1) Ух G X у*{х) содержит ровно один элемент, а также Vtyi, у2 G Y будет х*{у\) П х*{у2) = 0, то

WP = W = W8.

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

Г = (X, Y, {F1(x, у), F2(x, у), Фг(х, у), Ф2(х, у)}). (3)

Для нее доказывается эквивалентность следующих двух понятий:

Определение. Пара (хо, уо) Е X х Y называется слейтеровской седловой точкой в задаче (3), если V(x, у) G X х Y выполнено:

(Е(х,у0),Ф(х,у0)) №,й),Ф(ю1»)) ?s (F(x0,y),^{x0,y)).

Определение. Пара (ото, Уо) Е X х Y называется слейтеровской седловой очкой в задаче (3), если V(x,y) € X X Y выполнено:

F{x,y0) F{x0,y0),

{F{xq, уо), Ф{хо, уо)) (F{x0,y),${x0,y)).

налогичные определения и утверждение приводятся и для сравнения векторов о Парето.

В следующем пункте рассматривается пример — скалярная линейно-квадра-ичная задача при неопределенности (с ограничениями).

([-1,1], [-1,1], {F1(x,y),F2(x, у)}),

десь

Fi(x, у) = ~\х2 + 2ху + ^у2 + 2х- 2у,

3 3

F2{x, у) = + 4ху + -у2 -2х + 2у.

ля нее строятся функции сожаления по каждому критерию, после чего зада-а численно решается как в исходном варианте (без учета сожаления ЛПР), ак и в расширенном варианте. Приводится сравнение результатов - множества [ейтеровских седловых точек как в первом, так и во втором случае. После чего рассматривается фактически та же задача, только в общем виде без ограничений:

Ti = (R, R, {AiX2 + В{ху + Ciy2 + 2щх + 2ay}i=it2).

' этой формуле Ai, Bi, Си ец, Ci — постоянные, причем будем предполагать, что Ai < 0, Bi ф 0, а С{ > 0.

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

Ф{{х,у) = Ar\AiX + Вщ + а{)2 (* = 1,2). Таким образом, приходим к расширенной задаче

(К, R, {AiX2 + BiXy + Ciy2 + 2 счх + 2 ay, Af^AtX + B{y + ai)2}i=i,2).

Отметим, что функция сожаления строго вогнута и по х и по у (так как А < 0 и А~гВ2 < 0). Это значит, что отдельно по каждой функции сожаления минимума по у не существует. Тем не менее, удается доказать следующее утверждение.

Утверждение. Пара (хо,уо) является слейтеровской седловой точкой в задаче Г\ тогда и только тогда, когда выполнено

1. За е [0,1]; а(А\Ха + Biy0 + oi) + (1 - а)(А2х0 + В2у0 + о2) = О,

2. 3)0 6(0,1], 37 €[0,1], 3yeR:

( 7(i4i®0 + Biy + ai) + (1 - i)(A2x0 + B2y + a2) = 0, \ ß(Bixо + Ciy + d) + (1 - ß){B2xо + C2y + c2) = 0.

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

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

• n Е N, n ^ 2 - количество критериев в задаче, будем также применять множество N — {1, ...,п},

• множество коэффициентов важности: Лп = {а = (cti,..., а„)т| щ € [0,1],

IXi а, = 1},

• множество значений критериев: X С К", X ф 0, предполагается, что X компактно, тогда, если compR" — множество всех компактных подмножеств R", то X G comp Кп.

Вводится функция свертки (общего вида):

F : compR" хД"-» К",

эта функция по компактному множеству X С R" и вектору коэффициентов важности а «возвращает» точку ха G X.

Задача формулируется следующим образом: необходимо построить такую функцию F, чтобы для нее были выполнены следующие три условия:

1. VX G comp R", Va € Л", Зха е S(X): ха = F(X,a) (достаточность),

2. VX 6 compR", Va € S{X), Зах е Лп : х = F(X, ах) (необходимость),

3. VX б compR", Vi<=N,i^n, Va,/? е Лп : оц > & => F{{X,a) > Fi{X,ß) (монотонность).

На содержательном уровне первое и второе условия означают, что перебирая все возможные а G Лп, можно найти все максимальные по Слейтеру точки из X и только их, а третье задает связь между набором коэффициентов важности а и тем ха £ X, что этому набору соответствует, и обладающее свойством:

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

Показывается, что классические свертки (Карлина и Гермейра), вообще го-оря, не удовлетворяют всему набору этих аксиом — и не напрасно, ведь дока-ывается следующая основная теорема этого раздела.

Теорема. Если п = 2, то существует функция F, удовлетворяющая усло-иям 1-3. Если n ^ 3, то такой функции не существует.

Сначала устанавливается утверждение о несуществовании, потом показыва-тся, что при определенных предположениях и п = 2 свертки Карлина и Гер-ейера удовлетворяют условиям теоремы, наконец, конструируется свертка, до-азывающая утверждение теоремы при п = 2 для любого X 6 comp R™.

В главе 2 рассматриваются многокритериальные динамические задачи при еопределенности; в разделе 2.1 приводится общая постановка задачи. Предпо-агается, что динамика управляемой системы описывается обыкновенным век-орным дифференциальным уравнением

х = f(t,x,u,z), to^t^ú, x(t0) = x0, (4)

де 17 т и(-) б Sí и Z -г z(-) G Z — альтернатива ЛПР и реализация неопре-еленного фактора соответственно, а эффективность выбора ЛПР оценивается екторным критерием

Ji{to, х(.), «(•), *(■)) = фЩ + J f!{t, x{t), u[t], z[t])dt, i € N.

алее обсуждаются различные классы альтернатив ЛПР и реализаций неопре-еленностей. Снова приводится определение функции сожаления:

ФДС/, Z) - Ji(U, Z) - max J¡(V, Z), i E N,

Ven

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

Г° = (Е -5- (4), {21, Z}, {J(U, Z), Ф(U, Z)}), де n-вектора J = (Ju..., Jn), Ф = (Фь..., Ф„).

Ниже приводится основное понятие главы 2.

Определение. Тройка ([/*, ./*, Ф*) € 21 х Е2п называется слейгперовским гарантированным по исходу и сожалению решением ДМЗН, если существует

£ 2 такое, что

1. з* = 7(£/*, г*), Ф* = Ф(и*, г*у,

2. II* является максимальной по Слейтеру в динамической многокритериальной задаче, которая получается из Г° при 2 =

3. 2* является минимальной по Слейтеру в динамической многокритериальной задаче, которая получается из Г° при II = 11*.

В разделе 2.2 рассматривается классическая '121 задача, с которой фактически и началось исследование принципа минимаксного сожаления в динамическом случае. Под линейно-квадратичной многокритериальной позиционной динамической задачей при неопределенности (ДМЗН) понимается упорядоченный набор

<2,21,2, ли, Я, *,,*„)), (5)

где динамика системы 2 описывается векторным обыкновенным дифференциальным уравнением

х = Ах + и + г + а(г), ж(*0) =г06 Кш,

21 есть множество позиционных стратегий II у ЛПР:

21 = {и 4- и{г, х) | и{Ь, х) = РЦ)х + р{г) УР(-) е Стхт[0,1?], р(.)бСт[0,<?]},

2 — множество позиционных неопределенностей

2 = {г~ х) | х) = Я{г)х +

€ <?тхтМ], ?(•) € Ст[0,$]}.

Критерий эффективности задается векторным функционалом

3 = (»Д,..., <7П), г-ая компонента которого имеет вид:

^{и, г, хо) = зЦ$)С{х{$) + 2с$®(0)+

■в

+ У {«'М[ДиИ + 2 К&Щ + 2 М&Щ + ¿ЩЦяЩ + 2ЛЦх(4)]+

«0

+ х'^вгх^) + 2<1[иЩ + 21\гЩ + 2&({)}<& (г £ Г*),

ыше использованы заданные априори постоянные т х т-матрицы А, С{,

¿, С?,-, Ки Л^, ¿¿, то-вектора с,-, /,-, причем Д-, ¿¿, (3,- и С,- симметричны, тредполагается, что компоненты т-вектора а(£) непрерывны по £ € [О, I?]; штрих ■верху означает операцию транспонирования; множество порядковых номеров ритериев N = {1,..., п).

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

В разделе 2:3 рассматривается динамическая задача в классе программных

ьтернатив и неопределенностей:

х = }(Ь,х,и,г), а:(0) = Хо, 1€Г,

и{Ь) £ Р С К*, € Я С Кл, «(•) 6 £2(0,0], *(■) £ Ь\{0, «9],

п.в. п.в.

■д

и, г) = дг{х(д)) + //?(£,х,и, г)<И (г = 1,...,2. о

десь ЛПР выбирает функцию и(Ь) £ Ь2[0, г)}, определенную на отрезке [0,1?] и довлетворяющую ограничению и(Ь) £ Р почти всюду, независимо от его выбо-а реализуется неопределенность и(<) £ Ь\[0, г?], определенной на отрезке [0, х)\ и довлетворяющую ограничению г>(4) £ <5 почти всюду. Далее строится решение ифференциального уравнения (в смысле Каратеодори) х = /(¿,д;,и(£), (0) = яо- На всех возможных тройках (х(£), и (*),«(£)| г £ [£о>^]) определен екторный критерий «/(я, и, и) 7 = (■/[,..., ./„), который и оценивает эффектив-ость выбранной ЛПР альтернативы.

Параллельно с общей формулировкой рассматривается конкретный пример:

х = -х + и + г, х(0) = 1, а; £ К,

и € К, V £ К, «(•) £ Ь2{0,1], «(•) € 12[0,1],

1 1

Л (я,«,«) = ®(1) + /(-я2 + г2)сй, «,= -®(1) + /(-и2 + -*2)<й.

о о

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

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

В разделе 2-4 рассматривается вариант линейно-квадратичной задачи (5) классе контрстратегий с дополнительными предположениями относительно ди намики реализации неопределенного фактора:

Г = (2,Я„2<1 Ди,г,Ь0,х о)),

где

^сГ-г- х = Ах + и + А\г + а(4), ¡г(4о) = Жо,

21* = {и -7- и(г, х, г) I х, г) = Р{г)х + <2(1;)г + р{Ь)

VP(•) € Стхт[0Л т-) е СтхьМ, Р(.) 6 СтМ},

3 = 4- «И | ¿(4) = Вг + 6(4), У*[4о] = ¿о 6 М*},

7 = (7ь..., ./„).

Здесь А; х к матрица В постоянна, Ь(Ь) £ Ск[0, Щ. Заметим, что источником при нятого в описания множества неопределенности послужила модель Эванс из I14); все множество неопределенностей получаем, когда начальное значе ние го «пробегает» все евклидово пространство М*, а множество контрастрате гий 21г, — когда матрицы Р(4),ф(£) и вектор р(£) «пробегают» все множеств непрерывных на [0,т3] матриц (соответственно векторов).

Оказывается, что этого класса альтернатив достаточно для построения функ ции сожаления. Следуя традиции рассмотрения данного класса задач '12', функ ция сожаления понимается здесь как разность между наилучшим и реализовав шимся вариантом (то есть отличается от рассмотренной выше только знаком), помощью метода динамического программирования удается доказать, что есл выполнены условия (И < 0 -гФ- итРи — определенно отрицательна)

А < 0, С< < 0, в( - М/ДПм* < 0 (г € 1Г),

то можно построить явный вид компонент г 6 ЛГ, векторно

функции сожаления.

Имея такое представление функции сожаления, можно перейти к определе нию понятия решения.

Определение. Тройку (VФя) £ 21г х К2" назовем гарантированны по исходам и сожалениям решением задачи Г в контрстратегиях, если пр любом выборе начальной позиции (¿о, хо) € [0, $) х Мт существует неопреде ленностъ Дз € при которой = J(US, ¿о, £о), Ф5 = ¿о> ^о),

1°) контрстратегия Сявляется максимальной по Слейтеру в п—крите риальной динамической задаче

_о, Яо));_

[14] В. А. Колемаев. Математическая экономика. — М.: ЮНИТИ, 2002.

2°) неопределенность Zs минимальна по Слейтеру в 2п—критериальной задаче

(Е(и = и5), щи3, г, ¿0, ®о), -ф (и8, г, *0)}}.

Далее, с использованием свертки Карлина и метода динамического программирования, строится максимальная по Слейтеру контрстратегия.

Утверждение. Если удалось найти постоянные а £ Ап такие, что Иа < < 0 и специальная система уравнений типа Риккати (2.51) имеет продолжи-мое на отрезок [0, г?] решение 0а, то контрстратегия

С/5 -5- я, г) = -В;1 [(* + Ка)г + (0а + Ма)х + (& + 4)], (6)

где Еаи£а — решение специальной системы (2.53) ((2.51) и (2.53)см. в тексте диссертации).

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

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

Тем самым результаты параграфов 2.2 и 2.4 дают ответы на поставленные в монографии I12, с' 3451 вопросы относительно применения принципа минимаксного сожаления в линейно-квадратичных ДМЗН. В самой монографии рассматривался гибридный случай, сожаление оценивается при дополнительных предположениях относительно динамики неопределенного фактора, а при решении расширенной задачи авторы возвращаются к случаю равноправных альтернативы ЛПР и реализации неопределенности.

Автор выражает глубокую благодарность своему научному руководителю Владиславу Иосифовичу Жуковскому за постоянное внимание к работе.

Список публикаций автора по теме диссертации

[1] В. И. Жуковский, К. С. Сорокин. Риски и исходы в одной многокритериальной динамической задаче // Известия Института Математики и Информатики УдГУ. Вып. 2(30). - Ижевск: УдГУ, 2004. - С. 53 - 64.

[2] В. И. Жуковский, К. С. Сорокин. Риски в многокритериальных задачах // Нелинейный динамический анализ — 2007. Тезисы докладов международного конгресса. — Санкт-Петербург: СПбГУ, 2007. — С. 90.

[3] К. С. Сорокин. Гарантированное по исходам и рискам решение одной двух-критериальной задачи // Автоматика-2004: Материалы 11-ой международной конференции по автоматическому управлению. — Киев: Национальный университет пищевых технологий, 2004. — С. 39.

[4] К. С. Сорокин. §3.8. Скалярный случай // В. И. Жуковский, М. Е. Са-луквадзе. Риски и исходы в многокритериальных задачах управления. — Тбилиси: Интелекти, 2004. - С. 321-335.

[5] К. С. Сорокин. Гарантированное по исходам и рискам решение одной двух-критериальной динамической задачи // Сборник статей молодых учёных факультета ВМиК МГУ, выпуск №2. - М.:МГУ, 2005. - С. 1 - 11.

[6] К. С. Сорокин. §3.6. Модельный пример // В. И. Жуковский. Конфликты и риски. - М.: РосЗИТЛП, 2007.- С. 417-431.

[7] К. С. Сорокин. Риски в многокритериальных динамических задачах // Дифференциальные уравнения и топология: Международная конференция, посвященная 100-летию со дня рождения Л.С. Понтрягина: Тезисы докладов. — Москва: М.: Издательский отдел факультета ВМиК МГУ имени М.В. Ломоносова; МАКС Пресс, 2008. - С. 398.

[8] К. С. Сорокин. Существование гарантированного по исходам и рискам решения одной многокритериальной задачи // Вест. Моск. университета, сер. 15, вычисл. матем., киберн. — 2008. — № 1. —С. 19-25.

[9] К. С. Сорокин. Гарантированное по исходам и рискам решение одной многокритериальной динамической задачи // Автоматика и телемеханика. — 2009.-№3.-С. 123 - 135.

[10] К. С. Сорокин. О коэффициентах важности в задачах многокритериальной оптимизации // VI Всероссийская конференция «Проблемы оптимизации и экономические приложения»: материалы конференции (Омск, 29 июня

4 июля 2009) / Омский филиал Института математики им. С.Л. Соболев СО РАН. - Омск: полиграфический центр КАН, 2009. - С. 191.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 21.09.2009 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 488. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. M.B. Ломоносова, 2-й учебный корпус, 627 к.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Сорокин, Константин Сергеевич

Введение

1 Гарантии по исходу и сожалению

1.1 Постановка задачи.

1.2 Векторные оптимумы.

1.2.1 Оптимумы по Слейтеру.

1.2.2 Оптимумы по Парето.

1.3 Принцип минимаксного сожаления.

1.3.1 Формализация сожаления по Сэвиджу.

1.3.2 Некоторые свойства функции сожаления.

1.4 Гарантия по исходу и сожалению как решение однокритериальной задачи.

1.4.1 Аналог седловой точки (по Слейтеру).

1.4.2 Аналог седловой точки (по Парето)

1.4.3 Связь с седловой точкой в исходной задаче.

1.5 Гарантия по исходу и сожалению как решение двукритериальной задачи.

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

1.5.2 Скалярная линейно-квадратичная задача с ограничениями

1.5.3 Скалярная линейно-квадратичная задача без ограничений

1.6 Некоторые свойства скалярных сверток критериев.

1.6.1 Связь между коэффициентами свертки и значениями критериев.

1.6.2 Основная теорема

1.6.3 Двумерный случай.

2 Гарантиии в некоторых динамических многокритериальные задачах

2.1 Сожаление по Сэвиджу в динамических задачах.

2.1.1 Возможные классы альтернатив и неопределенностей

2.1.2 Функция сожаления в динамических задачах.

2.1.3 Определение решения ДМЗН.

2.2 Линейно-квадратичная задачи.

2.2.1 Постановка задачи.

2.2.2 Функции сожаления.

2.3 Программные стратегии.

2.3.1 Постановка задачи.

2.3.2 Функции сожаления.

2.3.3 Расширенная задача.

2.4 Случай программной неопределенности.

2.4.1 Постановка задачи.

2.4.2 Формализация сожаления.

2.4.3 Построение функции сожаления для г-го критерия

2.4.4 Формализация 5—гарантированного решения.

2.4.5 Построение максимальной по Слейтеру контрстратегии (шаг 2).

2.4.6 Явный вид Ji{Us, Z,t0,x0) (шаг 3)

2.4.7 Векторные гарантии (шаги 4,5).

2.4.8 Основные результаты для МДЗН.

Введение диссертация по математике, на тему "Гарантии в многокритериальных динамических задачах"

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

Во-первых, это — многокритериальная задача принятия решения. А значит «качество» принятого решения оценивается не по одному критерию, а сразу по нескольким. Такие задачи характерны, в первую очередь, для экономической проблематики, когда следует учесть интересы различных сторон или когда нет возможности сводить различные экономические факторы к одному (например, временные и финансовые затраты).

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

В-третьих, при решении задачи требуется учитывать не только исход, но и сожаление, которое для многокритериальных задач еще нуждается в подходящей формализации. В работе используется подход Сэвиджа [80], в котором численное значение сожаления полагается равным разности между наилучшим (если бы реализация неопределенности была заранее известна) и рассматриваемым вариантом. Из этого принципа следует, что решая задачу нужно ответить не только на вопрос ЛПР «Что делать?», но и на вопросы: «На что можно рассчитывать, действуя таким образом?», «О чем придется потом пожалеть, действуя таким образом?». То есть требуется найти векторную гарантию по исходу и сожалению, а также оптимальную (в смысле оптимизации этой векторной гарантии) альтернативу.

Сочетание этих особенностей в одной задаче требует некоторых пояснений. Краеугольным камнем формулировки задачи является вопрос принятия решения в условиях неопределенности. Таким образом предполагается, что помимо выбора ЛПР на итоговый результат влияет еще и некоторый неопределенный фактор. Здесь обычно различают два направления:

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

2. о неопределенном факторе известны лишь границы возможного изменения его значения, а какая-либо вероятностная информация отсутствует.

Предпринятые в этой работе исследования относятся только ко второму направлению.

Если рассматривать задачу при неопределенности как «наследника» классической задачи оптимизации, то обычное понятие максимума перестает быть удовлетворительным в качестве решения задачи — разве что было бы известно заранее, какая именно неопределенность реализуется. Если же ЛПР приходится учитывать возможность реализации любой неопределенности, то требуется некоторый дополнительный принцип, который бы позволил адекватно формализовать и построить решение задачи при неопределенности.

Известен ряд принципов решения однокритериальной задачи при неопределенности: максиминной полезности [82], принцип минимаксного сожаления

80] (идея которого и использована в настоящей работе), принцип пессимизма-оптимизма [41], принцип недостаточного основания [70]. Каждый из этих принципов формирует критерий, использование которого приводит ЛПР к однозначному ответу. Так принципу максиминной полезности Вальда отвечает максиминный критерий, принципу минимаксного сожаления Сэвиджа — критерий минимаксного сожаления, принципу пессимизма-оптимизма Гурви-ца — критерий показателя пессимизма-оптимизма, принципу недостаточного основания Лапласа — критерий Байеса-Лапласа. Каждый из этих принципов имеет свои достоинства и недостатки (им посвящена статья Г. Чернова [73]). Все перечисленные четыре критерия названы [41, с. 22] (для теории принятия решения при неопределенности) классическими. Они послужили основой для создания производных критериев, наиболее полное изложение которых можно найти в [41]; ряд производных критериев предложены также Ю.Б. Гермейером [8] и Э.Й. Вилкасом [6].

Принцип минимаксного сожаления предполагает, что строится функция, оценивающая сожаления ЛПР в том, что он выбрал данную конкретную альтернативу, а не наилучшую, если бы знал реализовавшуюся неопределенность. В дальнейшем будем называть эту функцию функцией сожаления ЛПР или просто функцией сожаления; она строго определяется в разделе 1.3. Дальше к этой функции применяется максиминный критерий Вальда (на самом деле минимаксный, так как ЛПР стремится минимизировать свое сожаление). Однако такому классическому подходу присущ ряд недостатков, которые обсуждаются разделе 1.3. Отметим также, что негативным свойствам принципа минимаксного сожаления уделяется значительное внимание в монографии [35].

По форме функция сожаления является критерием эффективности, альтернативным исходному. При этом основные свойства критерия сохраняются, например, если множества всевозможных альтернатив ЛПР и реализаций неопределенных факторов компактны, а критерий эффективности непрерывен по совокупности аргументов, тогда функция сожаления также будет непрерывной (см. п. 1.3.2). Этим обосновывается возможность рассматривать функцию сожаления наравне с исходным критерием эффективности, перейдя от однокритериальной задаче к двукритериальной. Так проблематика естественным образом смещается в область многокритериальных задач при неопределенности (в дальнейшем - МЗН), то есть, принимая решения в МЗН ЛПР должен учитывать:

1. то, что оценка качества функционирования управляемой системы проводится по нескольким критериям,

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

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

Принятие решения в задаче многокритериальной оптимизации сводится к выбору лицом, принимающим решение (ЛПР) одной альтернативы из некоторого множества допустимых. Последствия такого выбора оцениваются не непосредственно, а за счет набора значений числовых функций (в дальнейшем - критериев), определенных на множестве допустимых альтернатив: чем больше значение каждой из функций, тем «лучше» выбранная альтернатива. Основная проблема (и отличие от классических задач оптимизации) состоит в том, что критериев несколько, следовательно, обычного понятия максимума недостаточно и нужно вводить специальное понятие «векторного максимума». Основные варианты такого понятия были предложены в работах Парето [78], Борвейна [72], Джоффриона [75], Гурвица [10] (максимум по Слейтеру), Жуковского и Салуквадзе [83] (А-максимум). Общепринятый термин «эффективное решение» был введен Т. Купмансом [77]. Современное состояние классической теории принятия решения в многокритериальных задачах отражено в монографии В. В. Подиновского и В. Г. Ногина [54].

Отметим, что и в многокритериальных задачах, и в задачах при неопределенности отсутствует единый подход к понятию решения, когда же рассматриваются МЗН, то единства в определении «хорошего» решения нет тем более — дадим краткий обзор различных подходов к решению таких задач.

Впервые, по-видимому, на МЗН обратили внимание Р. Ауманн и Б. Пе-лег в [71] при определении се- и /^-оптимальности. На основе этих понятий в [76] было предложено обобщение понятия минимакса на случай антагонистической игры с векторной функцией выигрыша (векторный минимакс). Указанные построения использовались в [11] при исследовании многошаговых и иерархических игр, в [2] — для дифференциальных игр, а в [60, 61] — для игр с упорядоченными исходами. Ряд отличных от [76] подходов к определению векторного минимакса — в [44, 69]. Негативной стороной этих исследований были либо несимметричность в определениях (или условиях существования) векторных максимина и минимакса, либо отсутствие связи данных понятий с соответствующим образом определенной седловой точкой. Указанных недостатков лишены понятия векторных минимакса и максимина из [50, 51, 52]. Однако реализация предлагаемых там подходов связана с достаточно сложным построением специальных множеств (в критериальном пространстве) и наиболее эффективна, пожалуй, в случае конечных множеств альтернатив и неопределенностей. Более общее понятие минимакса (операторного минимакса) было предложено в [29, 30, 31], где построены также необходимые, а для выпуклой задачи и достаточные условия существования в функциональных пространствах. Аналогичный подход использован в [3, 74]. Отметим, что в [38, 39, 52] выявлена связь понятий векторных минимакса и седловой точки (что отсутствует в [29, 30, 31]. Наконец, в [3, 31, 60, 61] минимакс и седловая точка вводятся на основе различных бинарных отношений между подмножествами критериального пространства.

В данной работе, следуя подходу, развитому в [17, 18, 20], используется векторный аналог (по Слейтеру или Парето, см. раздел 1.2) седловой точки. И, если МЗН образована за счет расширения однокритериальной задачи, то понятия векторной седловой точки по Слейтеру, векторной седловой точки по

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

Принцип минимаксного сожаления рассматривался применительно к МЗН в монографиях [16, 21]; отметим что в данных работах термины «риск» и «сожаление» принимаются синонимами.

При построении векторного аналога седловой точки существенную роль играет метод свертки критериев, который обеспечивает достаточные условия, а при определенных предположениях еще и критерий для поиска такого решения. Наиболее значимы для данной работы свертки Карлина (линейная) [26] и Гермейера [8] (много других вариантов сверток приведено в [54]); основная их идея в том, что ЛПР фиксирует набор коэффициентов свертки и по этому набору формируется единый критерий, при максимизации которого и находится соответствующий (по Слейтеру или по Парето) векторный оптимум. При дополнительных предположениях, перебирая всевозможные наборы коэффициентов можно найти все множество оптимальных по Слейтеру или по Парето точек. Тут естественным образом возникает вопрос о связи коэффициентов свертки и результирующих значений критериев, например, могут ли значения коэффициентов свертки соответствовать «важности» критериев.

Задача о сужении множества всех максимальных по Слейтеру (или Паре-то) значений критериев эффективности на основании информации о «важности» критериев рассматривалась неоднократно (см., например, работы [9, 45, 53] и библиографию к ним), однако обычно используется информация об относительной важности критериев (например, «первый критерий важнее второго в 2 раза»), тогда как вопрос о соотношении коэффициентов сверток и результирующих значений критериев остается в стороне. А его решение позволило бы выбирать соответствующий предпочтениям ЛПР элемент из множества векторных оптимумов без предварительного построения всего этого множества. Исследованию этого вопроса посвящен раздел 1.6.

В главе 2 рассматриваются динамические многокритериальные задачи при неопределенности (ДМЗН). В отличие от обычных (статических), МЗН здесь предполагается, что управляемая система изменяется во времени и ЛПР может получать ту или иную информацию об этом функционировании, например, в виде обратной связи. Математическая формализация этой постановки задачи основывается на теориях оптимального управления и дифференциальных игр. Обращаясь к теории дифференциальных игр, будем считать первым игроком ЛПР, а вторым — лицо, «руководящее» выбором реализации неопределенного фактора.

В разделе 2.1 обсуждаются типы альтернатив ЛПР в зависимости от характера информации, получаемой ЛПР в процессе функционирования системы. Если никакой информации не поступает, то как ЛПР, так и неопределенный фактор формируется как функции от времени, тогда будем говорить, что ЛПР использует программные альтернативы, или просто программы. Формализация таких задач и методика их решения основывается на теории оптимального управления, созданной Л. С. Понтрягиным [36] и его сотрудниками, и получившей в дальнейшем широчайшее развитие. Из всего множества работ упомянем лишь [5], [34], содержащие обширные библиографии. Принцип максимума используется для построения решения МДЗН в классе программных альтернатив и неопределенностей в разделе 2.3.

Игровые постановки таких задач активно изучались Л. А. Петросяном в [79] (в классе кусочно-программных стратегий), где к требованиям оптимальности добавились требования динамической устойчивости принципов оптимальности. Эту идею развивали Н. Н. Данилов, В. В. Захаров, В. А. Ульянов, В. Д. Ширяев, результаты объединены в монографиях [46, 47, 48, 49].

Если же ЛПР в процессе функционировании динамической системы получает информацию о текущем состоянии системы — позиции,то будем говорить, что ЛПР выбирает свою альтернативу из класса позиционных стратегий. По-видимому, впервые такие задачи были рассмотрены в работе Айзекса [1]. В дальнейшем позиционные дифференциальные игры получили развитие и теоретическое обосование в работах Н. Н. Красовского, А. И. Субботина и их учеников [33, 32, 68]. В данном случае по аналогии предполагаем, что неопределенный фактор формируется в том же классе позиционных стратегий, что использует ЛПР, то есть пет информационной дискриминации неопределенного фактора. Формулировка МДЗН, основывающаяся на классе позиционных альтернатив и неопределенностей (в формализации В. И. Жуковского [19]) рассматривается в разделе 2.2.

В случае, когда предполагается неравнозначность в информированности ЛПР и неопределенного фактора, а именно, когда ЛПР в каждый момент времени знает не только текущую позицию, но и текущее значение неопределенного фактора, будем говорить, что ЛПР использует в качестве альтернатив класс контрстратегий. При этом возможен как вариант, при котором неопределенность использует программу, так и в вариант позиционной реализации неопределенности. Такой подход развит в работах Л. С. Понтрягина и его учеников [56, 57, 58, 37, 42, 43], ими была построена строгая теория и разработаны конструктивные методы решения линейных дифференциальных игр.

Класс контрстратегии в дифференциальных играх общего вида подробно рассматривается и в работах Б. Н. Пшеничного (например, в [59]); не обошла вниманием эту проблематику и школа Н. Н. Красовского, см., например, [68, с. 179]. В настоящей работе (в разделе 2.4) активно используется пара позиционная контрстратегия - программная неопределенность.

Линейно-квадратичные ДМЗН (в том виде, в котором они приводятся в разделах 2.2 и 2.4) подробно рассматривались (как в многокритериальной, так и в игровой постановках) в работах В. И. Жуковского и его учеников, начиная с пионерской работы Э. М. Вайсборда и В. И. Жуковского [4] и далее [15, 24, 17, 25, 12, 13]. Принцип минимаксного сожаления применительно к ДМЗН — в монографии [21]; отметим что в [21] термины «риск» и «сожаление» также отождествляются.

Краткое содержание работы

T=(X,Y,F(x,y)), (1) здесь F(x,y) = {Fi(x,y)}i(zN, N = {1, .,n}, n G N. С данной МЗН соотносятся две (чисто оптимизационные) многокритериальные задачи:

Г (y*) = (X,F(x,y*)).

В разделе 1.2 для этих задач имеется определения максимума (минимума) по Слейтеру и Парето. Приведем лишь одно из этих понятий.

Определение. Неопределенность у$ G У называется минимальной по Слейтеру для задачи Г(а;*), если при любых у € У несовместна система неравенств

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

Ф(х, у) = F(x: у)-max F(z, у); (3) zGX

Ф(ж, у) численно оценивает потери ЛПР от того, что он выбрал данную конкретную альтернативу, а не наилучшую при заданной неопределенности.

Определение. Гарантированным по сожалению решением задачи (1) при п = 1 назовем пару (х°, Ф°) Е X х К, определяемую цепочкой равенств

Ф° = maxmin Ф(£, у) — ттФ(ж°, у). хеХ yeY yeY

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

Г = (X, У, {F(a:, у),Ф(х, у)}}. (4)

Приводится определение гарантированного по исходу и сожалению решения в виде слейтеровской седловой точки. Далее F^ >s F^ 4Ф- Fj1^ > F^2\ i G N- FW F® ^ >5 F(2).

Определение. Пара (xo,yo) называется слейтеровской седловой точкой в задаче (4), если V(rc, у) G X xY выполнено

F(x,y0),<S>{x,yQ)) {F(xQly0),${xQ,yo)) {F(x0, у), Ф(ж0, у))

Доказываются следующие утверждения.

Утверждение. Если (хо,уо) G X х Y — слейтеровская седловая точка в задаче (4), то Ф(жо,уо) = 0.

Утверждение. Если (гсо, уо) G X х Y — седловая точка в задаче (1) при п = 1, то она же будет слейтеровской седловой точкой в двукритериальной задаче (4).

Приводятся примеры, подтверждающие строгость данного включения.

Аналогично вводится следующее (F^ >р F^ F^ ^ F^2\ г G N, 3j G N if} > ifF^ -iF^ >p F&)

Определение. Пара (a?o, уо) G X х Y называется паретовской седловой точкой в задаче (4), если \/(х,у) G X х Y выполнено

Ф(ггз2/о)) Ур ^{х0,уо),Ф{х0,у0)) ?Р (F(x0, у), Ф(я0, у)), и доказываются:

Утверждение. Любая паретовская седловая точка в задаче (4) будет одновременно и слейтеровской.

Утверждение. Если (жо, уо) G X х У — паретовская седловая точка в двукритериальной задаче (4), то Ф(жо,2/о) = 0.

Утверждение. Если (жо, Уо) £ X х Y — паретовская седловая точка в двукритериальной задаче (4), то (жо, у о) — седловая точка в исходной задаче (!)•

Пусть (при п — 1) W — множество всех седловых точек в исходной задаче (1), a Ws и WP — множество всех слейтеровских и паретовских точек соответственно в двухкритериальной задаче (4). Обозначим х*(у) = Argmaxi?(a;, у), а у*(х) = ArgminF(rr, у). хеХ уех

Теорема. Если в задаче (1) функция сожаления существует, то выполнена цепочка включений:

WP С W С Ws.

Теорема. Если в задаче (1) \/х е X у*(х) содержит ровно один элемент, а также Vt/i, у2 G У х*{у\) П х*(у2) = 0, то

WP = W = Ws.

T=(X,Y){Fl(x }у),Г2(х,у),Ф1(х,у),Ф2(х,у)}). (5)

Для нее доказывается эквивалентность следующих двух понятий:

Определение. Пара (жо, уо) G X х Y называется слейтеровской седловой точкой в задаче (5), если у) 6 X х Y выполнено: ж,г/0),Ф(я,2/о)) (F(x0,yo),<S>{x0,yo)) Уs (F{x0,y)^(x0,y)).

Определение. Пара (жо, уо) £ X х Y называется слейтеровской седловой точкой в задаче (5), если V(x,y) 6 X х Y выполнено:

F(x,y0) F(x0,yo),

F(x0,y0):<5>{x0}y0)) (F(x0,y)^(x0,y)).

Аналогичные определения и утверждение приводится и для сравнения векторов по Парето.

В следующем пункте рассматривается пример — скалярная линейно-квадратичная задача при неопределенности (с ограничениями).

-lA],{-l,ll{F1(x,y),F2(x,y)}), (6) здесь

Fi(x, у) = - jr2 + 2ху + |у2 + 2ж - 2у,

3 3

F2(ar, у) = --.т2 + А.ху + -у2 -2х + 2у.

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

После чего рассматривается фактически та же задача, только в общем виде и без ограничений

М, R, {АгХ2 + BiXy + Сгу2 + 2щх + 2ay}i=U2). (7)

В этой формуле Ai,Bi,Ci, щ, q — постоянные, причем будем предполагать, что Ai < 0, Bi Ф 0, a Q > 0.

ФДж, у) = A~l{AiX + BiV + ai)2 {г = 1, 2).

Таким образом, приходим к расширенной задаче

R, R, {А{х2 + Bixy + Qy2 + 2(цх + 2ay, Ai\AiX + В{у + сц)2}^). (8)

Отметим, что функция сожаления строго вогнута и по х и по у (так как А < < 0 и А-1 В2 < 0). Это значит, что отдельно по каждой функции сожаления минимума по у не существует. Тем не менее, удается доказать следующее утверждение.

Утверждение. Пара (гсо, уо) является слейтеровской седловой точкой в задаче (8) тогда и только тогда, когда выполнено:

1. За е [0,1]: aiAiXo + Biy0 + oi) + (1 - а){А2х0 + В2у0 + а2) = 0,

2. 3/3 е [0,1], 37G [0,1], ЗуеШ:

7(Ai.t0 + Biy + ai) + (1 - 7)(А2х0 + В2у + а2) = 0, р(Вцг0 + Cry + ci) + (1 - /3)(В2х0 + С2у + с2) = 0.

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

• n G N, n ^ 2 — количество критериев в задаче, будем также применять множество N — {1,., п},

• множество коэффициентов важности: Лп = {ск = (a?i,., ап)т\ оц £ е [MLELi ai = i},

• множество значений критериев: X С Mn, X ^ 0, предполагается, что X компактно, тогда, если сотр Мп — множество всех компактных подмножеств R71, то X £ comp Rn.

Вводится функция свертки (обшего вида):

F : compKn х Лп ^ Мп, эта функция по компактному множеству X С Мп и вектору коэффициентов важности а «возвращает» точку ха £ X.

Задача формулируется следующим образом: необходимо построить такую функцию F, что для нее выполнены следующие три условия.

1. УХ £ compR", Усе £ Лп, 3xa £ S{X) : = F(X,a) (достаточность)

2. УХ £ comp Mn, Mx £ S(X), 3ax £ An : x = F(X, ax) (необходимость)

3. VX £ compMn, \fi £ N,i < n, Var,/? £ An : оц ^ A F{(X,a) ^ ^ Fi(X,P) (монотонность)

На содержательном уровне первое и второе условия означают, что перебирая все возможные а £ Лп можно найти все максимальные по Слейтеру точки из X и только их, а третья задает соответствие между набором коэффициентов важности а и тем ха £ X, что этому набору соответствует, фактически обосновывая само название «коэффициенты важности» — если ЛПР при переходе от одного набора коэффициентов к другому не уменьшает коэффициент важности, то соответствующее значение критерия не может уменьшиться.

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

Теорема. Если п = 2, то существует функция F, удовлетворяющая условиям 1-3. Если п^З, то такой функции не существует.

Сначала устанавливается утверждение о несуществовании, потом показывается что при определенных предположениях и п = 2 свертки Карлина и Гермейера удовлетворяют условиям теоремы, а затем конструируется свертка, доказывающая утверждение теоремы при п — 2 для любого X е еотр Шп.

В главе 2 рассматриваются многокритериальные динамические задачи при неопределенности; в разделе 2.1 приводится общая постановка задачи. Предполагается, что динамика управляемой системы описывается обыкновенным дифференциальным уравнением

X = f(t,x,u,z), to ^ t < tf, где U -S-u(') € 21 и Z-i-z(-) £ Z — альтернатива ЛПР и реализация неопределенного фактора соответственно, а эффективность выбора ЛПР оценивается векторным критерием в

Ji{tQ,х(-)М-),г{-)) = дМ'в)) + J f?(t,x{t),u[t\,z[t))dt, i е Nto

Далее обсуждаются различные классы альтернатив ЛПР и реализаций неопределенностей. Снова приводится определение функции сожаления:

Ф(и,г) = J(U,Z)-mMiJ(V,Z), то есть, при построении функции сожаления ЛПР исходит из наилучшего действия при том раскладе, что ему известна вся функция г(-), а не только текущая позиция или текущее значение функции Откуда следует, что стандартные классы позиционных и контрстратегий, несмотря на то, что в них используется информации о реализации неопределенного фактора, не могут обеспечить нулевое сожаление при всех возможных реализациях неопределенного фактора, что показывается на конкретных примерах.

Ниже приводится основное понятие главы 2.

Определение. Тройка (£/*, 7*,Ф*) £21хМ2п называется слейтеро вским гарантированным по исходу и сожалению решением ДМЗН, если существует Z* б Z такое, что

2. U* является максимальной по Слейтеру в динамической многокритериальной задаче, которая получается из исходной при Z = Z*\

3. Z* является минимальной по Слейтеру в динамической многокритериальной задаче, которая получается из исходной при U = U*.

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

В разделе 2.2 рассматривается классическая [21] задача, с которой фактически и началось исследование принципа минимаксного сожаления в динамическом случае. Под линейно-квадратичной многокритериальной позиционной динамической задачей при неопределенности (ДМЗН) понимается упорядоченный набор

1. J* = J(U*,Z*), Ф* = <f>(U*,Z*)-}

J(U,Z,tо,х0)>, где динамика системы ]§) описывается уравнением х = Ах + u-\-z-\- a(t), x(tо) = xq,

10)

21 есть множество позиционных стратегий U ЛПР:

21 = {U + u(t, х) | u(t, х) = P{t)x + p(t)

VP(OeCmxm[o,tf],p(OeCm[o,0]}

И)

Z — множество позиционных неопределенностей Z \

Z = {Z + z{t, x) | z{t, x) = Q(t)x + q(t) VQ(-) G Cmxm[0,tf], g(-) G Cm[O,0]}.

Критерий эффективности задается векторным функционалом

J — (Jh Jn)i г-ая компонента которого имеет вид:

Ji{U, Z,to, х0) = x'^Qxi'd) + 2с'гх{'в)+ д J {u'[t][Diu[t] + 2KiZ[t] + 2Mix{t)] + z'[t]{Liz[t\ + 2 NiX{t)]+ to x\t)Gix(t) + 2d!iu{t]+2l'iz{t)+2g'ix{t)}dt (i G N), (13) выше использованы заданные априори постоянные т х га-матрицы A, Ci, Di, Mi, Gi, Ki, Ni, U, ш-вектора c^, di, git k, причем Д, L{, и Q симметричны, предполагается, что компоненты га-вектора a(t) непрерывны по t G [0, г?]; штрих сверху означает операцию транспонирования; множество порядковых номеров критериев N = {1, .,п}.

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

В разделе 2.3 рассматривается динамическая задача в классе программных альтернатив и неопределенностей. Рассматривается общая задача. х = f(t,x,u, z), х(0) — х0, х G Rm, u(t) G Р С z(t) G Q С Rh, u(-) G Ll[0,$], z(-) G , п.в. п.в. l-L^J

Jf(rc, u, z) = дг(х($)) + / X, u, z)dt (i = 1,., та), n ^ 2. 0

Здесь ЛПР выбирает измеримую с квадратом функцию u(t), определенную на отрезке [0,79] и удовлетворяющую ограничению u(t) G Р почти всюду, независимо от его выбора реализуется неопределенность, тоже в виде измеримой с квадратом функции v(t), определенной на отрезке [0,$] и удовлетворяющую ограничению v(t) G Q почти всюду. Далее строится решение дифференциального уравнения (в смысле Каратеодори) х = f(t, х, u(t), v(t)), х(0) = а:0- На всех возможных тройках {x(t),u(t),v(t)) t 6 [to,определен векторный критерий J(x, и, v), который и оценивает эффективность выбранной ЛПР альтернативы.

Параллельно с общей формулировкой рассматривается конкретный пример. х — — х + и + z, ж(0) = 1, х G М, и е К, v G R, u(t) е Ь2[0,1], v(t) 6 L2[0,1], i i

Ji(:c, u, v) = x(l) + J'(-U2 + z2)dt, J2(x, u, v) = -ж(1) + J(-u2 + z2)dt. о о

15)

Все дальнейшие рассуждения этого раздела проводятся для данного примера, но постоянно делаются отсылки к общему случаю, подробно обсуждаются, какие изменения может претерпеть методика решения (при переходе к общему случаю). За счет применения принципа максимума Понтрягина удается построить функции сожаления и перейти к расширенной задаче, правда, ценой увеличения размерности: х = —х + и + z, гс(0) = 1,

У1 = -Vi + ^ + z, У1(0) = 1,

У2 = -У2~^г + z, г/2(0) = 1, 1

J\{x, и, v) = ж(1) + f (—и2 + z2)dt, is)

J2(x, и, v) = -ж(1) + f (-и2 + z2)dt, о 1

Ф1(яг, у, и, z) = ж(1) - У1{1) + J(-u2 + V)^' о 1

Ф2(ж, у, и, z) = -ж(1) + 2/2(1) + Д-^2 + о

Для решения этой задачи применяется свертка Карлина и принцип максимума Понтрягина (и то и другое дважды - для альтернатив и для неопределенностей). Таким образом, при коэффициентах сверток с = 0.3, (3i = 0.4, р2 = 0-3, /?3 = 0.2, Д* = 0.1, дифференциального уравнения (в смысле Каратеодори) х — f(t, х, u(t), v(t)), ж(0) = xq. На всех возможных тройках (x(t), u(t), v(t)) t E [to,$\ определен векторный критерий J(x, и, v), который и оценивает эффективность выбранной ЛПР альтернативы.

Параллельно с общей формулировкой рассматривается конкретный пример. х~— x + u + z, ж(0) = 1, х G R, и е м, u(t) е L2[о, 1], v(t) е L2[о, 1], i i

Ji(x, и, v) = ж(1) + f (-и2 + z2)dt, J2(x, щ v) = -х(1) + f (-и2 + z2)dt. о о

15)

У\ = ~У\ + ^ + 2/1 (0) = 1, т = -у2-^- + z, у2(о) = 1, 1

Ji(x, и, v) = ж(1) + f (-и2 + z2)dt, 1 о , ^

J2{x, и, v) = -х(1) + f (—и + z2)dt, о

Ф^ж, у, и, z) = х{1) - ш(1) + f(-u2 + о

Ф2(х, у, u, z) = -х(1) + у2{ 1) + }(-и2 + ^)dt. о

X = -X + y~7^1 + (P2 + (P3), Х(0) = 1, + 3/1 (0) = 1,

У2 = ~У2 - ^ - f(<Pl + <£2 + <£з), 2/2(0) = 1,

01 = 01, 01 ( 1) = -0.4,

02 -- 02, 0г(1) = о,

03 = 03 , 0з(1) = 0, ¥>1 = ¥>Ь Vi(l) = 0.2, ф2 = <Р2, Уг(1) = -0.2, Фз = (Рз, у?з(1) = 0-1. которую удается решить в явном виде: х^Н^-е^ + е-'-Ч + е-', !/!(*) = ё^-1-е-'"1) + е-',

0!(t) = — |et1, 02(t) = 0, 0з(*) - 0, ¥>i(t) = t) = —he1"1, p3(t) = -Ы-1 5

X iov и найти значения критериев

Jl«z*) = 0.2354445698 J2(u*,z*) = -0.2656196038 Ф1 {u*,z*) = -0.2118428556 Ф2(гЛг*) = -0.03890991224.

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

В разделе 2.4 рассматривается вариант линейно-квадратичной задачи (9) в классе контрстратегий с дополнительными предположениями относительно динамики реализации неопределенного фактора:

2 J(U,Z,t0:x0)): (17) где

-г- х — Ах + и + A\z + а(£), x(t0) = xq,

21, = {U -г u(t, х, 2:) | u(t, ж, г) = Р(£)ж + Q(t)z +

VP(-) 6 CmXm[0, $], VQ(-) G Cmxfc[0,^], p(-) G Cm[0, #]},

Zt = {Z + z[t] I i(i) = Bz + b(t), Vz[to] = z0e Rk}, (19)

J = (Л) «Л0

В (19) к x к матрица В постоянна, Ь(£) G Cfc[0,i9]. Заметим, что источником принятого в (19) описания множества неопределенности Zt послужила модель Эванса из [28]; все множество неопределенностей Zt получаем, когда начальное значение zq «пробегает» все евклидово пространство а множество контр астр атегий 21г, — когда матрицы P(t), Q(t) и вектор p(t) в (18) «пробегают» все множество непрерывных на [0, $] матриц (и векторов).

Оказывается, что в данном случае этого класса альтернатив достаточно для построения функции сожаления, в отличии от ситуаций, рассмотренных в разделе 2.1. Следуя традиции рассмотрения данного класса задач [21], функция сожаления понимается здесь как разность между наилучшим и реализовавшимся вариантом (то есть отличается от рассмотренного выше только знаком).

В целях построения функции сожаления для каждого критерия

Ji(U,Z,to,xo) (i G N) из (17) строится вспомогательная однокритериальная задача

20)

С помощью метода динамического программирования удается доказать, что если выполнены условия,

Di < 0, Сг < 0, Gi - M[DrlMi ^ 0 (г G N), то компоненты Ф;(£/, to, жо), г G N, векторной функции сожаления имеют вид

Ф{(и, Z, t0, х0) = Vj(t0) cc0, z0) - Ji{U, Z, t0, s0) = z0Xi(t0)z0 + 2£-(г0)жо+ 2г/4(*о) + Wi(to) - J<(tf, Z, t0, xq), (21) где матрицы ©*(£), векторы &(£), "Hiifi) и скалярная переменная w(t) удовлетворяют специальной системе обыкновенных дифференциальных уравнений (2.21) (явно выписанной в тексте диссертации).

Имея такое представление функции сожаления, можно перейти к детальному определению понятия решения.

Определение. Тройку (Us, Js, Ф5) £ 2lz х R2n назовем гарантированным по исходам и сожалениям решением задачи (17) в контр стратегиях, если при любом выборе начальной позиции (to,xo) G [0,i9) х Rm существует неопределенность G Zt, при которой Js — J(US, Zs,to,xo), Ф5 = Ф(С/5, Zs, to, XQ), и

1°) контрстратегия Us является максимальной по Слейтеру в п— критериальной динамической задаче

Kz,J(U,Z,t о,хо)>, (22) т.е. для каждой тройки (Z,to,xo) G Z х [0,$) х Rm несовместна система неравенств

Ji(U,Z,t0,x0) > Ji{Us,Z,tQ,xo) VU G 21z{ie N); (23)

2°) неопределенность Zs минимальна no Слейтеру в 2n—критериальной задаче g(lи = US),Z, {J(us, z, to, xo), -Ф(Us, Z, to, a*)}), (24) т.е. при каждых (to,xo) G [0, x Rm несовместна система неравенств

Ji(Us,Z,tQ,xo) < Ji(Us,Zs,tQ,xo), ^i{Us,Z,to,xo) > $i{Us,Zs,to,xo) (i e N).

При этом Js назовем гарантированным векторным исходом, а Ф5 — гарантированным векторным сожалением.

Утверждение. Если удалось найти постоянные а £ Лп такие, что Da < 0 и специальная система уравнений типа Риккати (2.51) имеет про-должимое на отрезок [О, Щ решение 0а, то контр стратегия

Us + us(t, X, z) = -D~l [(2^ + Ka)z + (©в + Ma)x + (fe + da)], (26) где SQ и — решение специальной системы (2.53) (см. в тексте диссертации).

Для построения значений критериев эффективности используется следу-щая теорема.

Теорема. Предположим, что удалось найти решение Vi(t,x,z) уравнения с частными производными (2.56) (см. диссертацию). Тогда при любом выборе (to,XQ,zo) £ [0,т?) х Mm х справедливо равенство

Vifo, ге0, zQ) = Ji(Us, Zs, tQ, x0).

Указанное уравнение в частных производных удается свести к системе линейных уравнений (2.60) и построить значения критериев эффективности как функций от начальной позиции (to,xo) и zq.

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

Xp(t) = J^[Xi(t)-PiXi(t)] . ieN положительно определена, получаем, что zs = -Хр1^W(i0, х0), (28)

24 где mp{t, х) -- Еp(t)x + 2r]p{t),

S/M = £ - A2iW] , ieN vp(t)= E [Ш ~ PMt)] ■ i<EN

Зная zs можно построить векторную гарантию по исходу и сожалению

Ji{Us, Zs, t0, х0) = x'0Qi(to)xo - 2m'pito, x0)xp1(to)=<i{to)xo+ + mp(t0, x0)\^l{to)Xi{tQ)xpl{tQ)rrip{t^ ж0)+ + 2(&(*0))'x0 - 2{fji(t0))/Xp1(t0)mp(t0, xQ)+Wi(to) (i в N),

Zs, tQ, x0) = max Ji(U, Zs, t0, x0) - Ji(Us, Zs, t0, xQ) = Vi(t0, x0, zs) - Vi(t0, xQ, zs) — = асо[в<(«о) - ©i(io)]xo - 2m'f3(t0)xp1(to)[^i(t) - Щь0)]х0+ mp(to, x0)/Хд1(^о)[Хг(^о) -+ 2Й(*о) - ~ 2[Tfc(«o) - rji{t0)}'xp1{tQ)mp(tQ,x0)+ -oJi(t0) (ii e N) при любых (to,XQ) 6 [0, x Rm; здесь i (t) , § (*) , % («), £z (t), Tji (t) , LJi (t) решение системы (2.60), (см. диссертацию), а

Qi(t), Ei(t), Xi(t), &(t), m(t), решение системы (2.21).

Тем самым результаты параграфов 2.2 и 2.4 дают ответы на поставленные в монографии [21, с. 345] вопросы относительно применения принципа минимаксного сожаления в линейно-квадратичных ДМЗН (в самой монографии рассматривался гибридный случай, сожаление оценивается при дополнительных предположениях относительно динамики неопределенного фактора, а при решении расширенной задачи авторы возвращаются к случаю равноправных альтернативы ЛПР и реализации неопределенности).

Основные результаты

1. Для однокритериальной задачи при иеопределености установлено соотношение между седловой точкой и векторными седловыми точками (по Слейтеру и Парето) в расширенной задаче (при учете двух критериев -исхода и сожаления).

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

3. Для линейно-квадратичных динамических многокритериальных задач при неопределенности в классе контрстратегия ЛПР — программная неопределенность построен явный вид гарантированного по исходу и сожалению решения, приведены достаточные условия его существования.

Основные результаты работы представлены в статьях [22, 63, 66, 67] и материалах конференций [62, 64, 23, 65]. Кроме того, автором были написаны раздел 3.8 в монографии [21] и раздел 3.6 в монографии [14], оба упомянутых раздела содержат результаты численного расчета модельных примеров, непосредственно перекликающихся с материалами настоящей работы.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

2.4.8 Основные результаты для МДЗН

Объединил полученные утверждения, приходим к следующему выводу:

Утверждение 2.4.7. Пусть для динамической п-критериальной задачи (2.10)-(2.Ц)

1°) Д < 0, С{ < 0, Gi - MiD^Mi О (г G N),

2°) существуют постоянное a G Ап, что система дифференциальных типа Риккати (2.51) имеет продолжимое на интервал [0,$] решение a(t),

3°) существуют постоянное (3 G Ап, такое, что х/з(£) > 0, t G [0,#].

Тогда при любом выборе начальной позиции позиции (to, ^о) Е [0,19) xMm в задаче (2.10)-(2.14) существует гарантированное по исходам и сожалению решение (Us, J(US, Zs,t0,x0), Ф(Us, Zs,tQ,x0)).

Кроме существования указанные утверждения позволяют предложить следующий конструктивный способ построения S— гарантированного решения: а) проверить выполнение требования (1°) утверждения 2.4.7; б) найти решение (0,(2), x*(t),&(t), rji(t), w;(t)|0 ^ t ^ ■&), г G N, системы (2.21); в) используя (б) найти функции (определенные при (to^th^o) £ [0, х Rm+A) max Ji(U, Z, to, жо) = x'oei(to)a:o + 2(&(*о))'яо + Wi(to) + 4xi(*o)zo+ 2zbZi(to)xo + 2(77i(to)),2o + Wi(to) (ieN); г) построить по формулам (2.41) матрицы Ca, Da, Ka, Ma, La, 7Va, Gn, векторы ca, da, 'q , 9 a] д) найти решение ©Q(t), £a(t), £a(£)> 0 ^ t < $) системы (2.51), (2.53); е) построить контрстратегию, используя (д), с/5 - -D-1 [(Sa(t) + Ka(t))z + (ea(t) + Ma(t))® + (ш + <ът; ж) найти решение (6;(t), S,(t), Xi(t), <*(*) 0 t ^ tf) (г G TV) системы (2.60); з) с помощью (ж) найти функции (определенные при (to, £0,2:0) ^ х Rm+k)

X(t) = Е \Ш - РгХгШ , ieN т = Е piW - , ieN ieN m(t, z) = Е(£)ж + ?7(£); к) выбрать числа Д Е такие, что матрица х(*о) > 0; л) наконец, построить гарантированный векторный исход

Ji{US, ZS, to, Xq) — x'0Gi(t0)x0 - 2m'(to)Xp1(to)E,i(to)xo+ m,p(to, xoYxp^tQ^Mx^Mmpito, + 2(&(*о))'жо+

- 2{^i(tQ)),x}1{to)rnp(t0:x0)-\-uJi(t0),

Js = (Л(С/5, Zs, <0,so), -Ш5, ^s, So)) и гарантированное векторное сожаление я4[в4(«ь) - Щк)]х0 - 2т'р(г0)хрНк)[Е^) - Щг0)}х0+ 2[6(to) - li(to)]'xo - 2[rH{t0) - r}i{h)]'x-pl{tQ)rnp{tQ, ж0)+ uJi(tQ) - Uji(tQ), фЗ = (ф 1(t/Sj t0j I0)J Zs, £0, xo)).

Найденная в результате тройка (Us, J5, Ф5) и образует гарантированное по исходам и сожалениям решение многокритериальной динамической задачи (2.10)-(2.14) с начальной позицией (to,£o)

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Сорокин, Константин Сергеевич, Москва

1. Айзеке Р. Дифференциальные игры. — М.: Мир, 1965.

2. Борисенко М. В. Некоторые задачи теории дифференциальных игр с векторным критерием качества: Автореф. дис. . канд. физ.-мат. наук / МГУ. 1984.

3. Бурштейн Ф. В., Корелов Э. С. Многокритериальные задачи принятия решения при неопределенности и риске // Теоретическая кибернетика (Сб. трудов). — Тбилиси: Мецниереба, 1980. — С. 143-148.

4. Вайсборд Э. М., Жуковский В. И. Введение в дифференциальные игры нескольких лиц и их приложения. — М.: Сов. радио, 1980.

5. Васильев Ф. П. Методы оптимизации. — М.: Факториал Пресс, 2002.

6. Вилкас Э. Й. Оптимальность в играх и решениях. — М.: Наука, 1990.

7. Воробьев Н. Н. Теория игр для экономистов- кибернетиков. — М.: Наука, 1985.

8. Гермейер Ю. Введение в исследование операций. — М.: Наука, 1971.

9. Горелик В. А., Фомина Т. П. Основы исследования операций.— М.: МПГУ, 2004.

10. Гурвиц Л. Программирование в линейных топологических пространствах // Исследования по линейному и нелинейному программированию.- М.: ИЛ, 1962.-С. 65-155.

11. Ерошов С. Исследование игр с векторной функцией выигрыша: Автореф. дис. . канд. физ.-мат. наук / МГУ. — 1982.

12. Жуковский В. И. Введение в дифференциальные игры при неопределенности. — М.: Международный НИИ проблем управления, 1997.

13. Жуковский В. И. Кооперативные игры при неопределенности и их приложения. — М.: Эдиториал УРСС, 1999.

14. Жуковский В. И. Конфликты и риски, — М.: РосЗИТЛП, 2007.

15. Жуковский В. ИДочев Д. Т. Векторная оптимизация динамических систем.— Болгария, Русе: Центр по Математике, 1981.

16. Жуковский В. И., Жуковская JI. В. Риск в многокритериальных и конфликтных системах при неопределенности.— М.: Эдиториал УРСС, 2004.

17. Жуковский В. И., Молоствов В. С. Многокритериальное принятие решений в условиях неопределенности. — М.: Международный НИИ проблем управления, 1988.

18. Жуковский В. И., Молоствов В. С. Многокритериальная оптимизация систем в условиях неполной информации. — М.: Международный НИИ проблем управления, 1990.

19. Жуковский В. И., Салуквадзе М. Е. Многокритериальные задачи управления в условиях неопределенности. — Тбилиси: Мецниереба, 1991.

20. Жуковский В. ИСалуквадзе М. Е. Оптимизация гарантий в многокритериальных задачах управления. — Тбилиси: Мецниереба, 1996.

21. Жуковский В. И., Салуквадзе М. Е. Риски и исходы в многокритериальных задачах управления. — Тбилиси: Интелекти, 2004.

22. Жуковский В. ИСорокин К. С. Риски и исходы в одной многокритериальной динамической задаче // Известия Института Математики и Информатики УдГУ. Вып. 2(30). Ижевск: УдГУ, 2004. - С. 53 - 64.

23. Жуковский В. И., Сорокин К. С. Риски в многокритериальных задачах // Нелинейный динамический анализ — 2007. Тезисы докладов международного конгресса. — Санкт-Петербург: СПбГУ, 2007.— С. 90.

24. Жуковский В. И., Тынянский Н. Т. Равновесные управления многокритериальных динамических систем. — М.: МГУ, 1984.

25. Жуковский В. И., Чикрий А. А. Линейно-квадратичные дифференциальные игры. — Киев: Наукова Думка, 1994.

26. Карлин С. Математические методы в теории игр, программировании и экономике. — М.: Мир, 1964.

27. Кларк Ф. Оптимизация и негладкий анализ. — М.: Наука, 1988.

28. Колемаев В. А. Математическая экономика, — М.: ЮНИТИ, 2002.

29. Корниенко И. А. О нескалярных минимаксных задачах // Исследование операций и аналитическое проектирование в технике (Сб. трудов КАИ). Казань, 1979. - С. 3-8.

30. Корниенко И. А. Бинарные отношения множеств и многокритериальные задачи оптимизации в условиях неопределенности // Модели и методы оптимизации (Сб. трудов ВНИИСИ). Вып. 19.- М.: ВНИИСИ, 1986.— С. 47-53.

31. Корниенко И. А. Достаточные условия операторного минимакса // Модели и методы оптимизации (Сб. трудов ВНИИСИ). Вып. 19. — М.: ВНИИСИ, 1986. С. 44-46.

32. Красовский Н. Н. Управление динамической системой,— М.: Наука, 1985.

33. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. — М.: Наука, 1974.

34. Ли Э. Б., Маркус Л. Основы теории оптимального управления. — М.: Наука, 1972.

35. Льюс РРайфа Г. Игры и решения. — М.: ИИЛ, 1960.

36. Математическая теория оптимальных процессов / Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко. — М.: Наука, 1976.

37. Методы решения дифференциальных игр. Математическое моделирование / Н. JI. Григоренко, Ю. Н. Киселев, Н. В. Лагунов, Д. Б. Силин. — М.: Изд-во Московского университета, 1993.

38. Морозов В. В. О смешанных стратегиях в игре с векторной функцией выигрыша // Тезисы докл. III Всесоюзной конференции по исследованию операций. Горький: 1978. — С. 210-211.

39. Морозов В. В. Смешанные стратегии в игре с векторными выигрышами // Вестник МГУ. Вычисл. матем. и кибернетика. — 1978. — № 4. — С. 44-49.

40. Морозов В. В. Основы теории игр, — М.: ВМиК МГУ, 2002.

41. Мушик Э., Мюллер П. Методы принятия технических решений. — М.: Мир, 1990.

42. Никольский М. С. О нижнем альтернированном интеграле Понтрягина в линейных дифференциальных играх преследования // Математический сборник. — 1985. Т. 128, № 1. — С. 35-49.

43. Никольский М. С. Краткий обзор работ Л. С. Понтрягина по дифференциальным играм // Вест. Моск. университета, сер. 15, вычисл. матем., киберн. — 1993. — № 3. — С. 3-8.

44. Ногин В. Д. Двойственность в многоцелевом программировании // Ж. вычисл. матем. и матем. физики. — 1977. — Т. 17, N2 1. — С. 254-258.

45. Ногин В. Д. Принятие решений в многокритериальной среде: количественный подход. М.: ФИЗМАТЛИТ, 2002.

46. Петросян Л. А., Данилов Н. Н. Кооперативные дифференциальные игры и их приложения. — Томск: Томский ун-тет, 1985.

47. Петросян Л. А., Захаров В. В. Математические модели в экологии. — Санкт-Петербург: СПбГУ, 1997.

48. Петросян Л. А., Кузютин Д. В. Игры в развернутой форме: оптимальность и устойчивость. — СПб.: Изд-во СПбГУ, 2000.

49. Петросян JI. А., Томский Г. В. Динамические игры и их приложения. — JL: Ленинградский ун-тет, 1982.

50. Подииовский В. В. Эффективные планы в многокритериальных задачах принятия решений в условиях неопределенности // Модели процессов принятия решений (Сб. трудов). — Владивосток: ДНЦ АН СССР, 1978. — С. 102-113.

51. Подиновский В. В. Принцип гарантированного результата для частичных отношений предпочтения // Ж. вычисл. матем. и матем. физики. 1979. - Т. 19, № 6. - С. 1436-1450.

52. Подиновский В. В. Общие антагонистические игры // Ж. вычисл. матем. и матем. физики. — 1981. — Т. 21, № 5. — С. 1140-1153.

53. Подиновский В. В. Количественная важность критериев // Автоматика и телемеханика. — 2000. — № 5. — С. 110 123.

54. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука, 1982.

55. Понтрягин Л. С. Обыкновенные дифференциальные уравнения. — М.: ГИФМЛ, 1961.

56. Понтрягин Л. С. О линейных дифференциальных играх. I // Докл. АН СССР. 1967. - Т. 174, № 6. - С. 1278-1280.

57. Понтрягин Л. С. О линейных дифференциальных играх. II // Докл. АН СССР. 1967. - Т. 175, № 4. - С. 764-766.

58. Понтрягин Л. С. Линейные дифференциальные игры преследования // Математический сборник. — 1980. — Т. 112, № 3. — С. 307-330.

59. Пшеничный Б. Н., Остапенко В. В. Дифференциальные игры. — Киев: Наукова думка, 1992.

60. Розен В. В. Свойства исходов в ситуациях равновесия // Математические модели поведения (Сб. трудов). Вып. 2.— Саратов: Саратовский ун-тет, 1975. С. 45-49.

61. Розен В. В. Ситуации равновесия в играх с упорядоченными исходами // Современные направления теории игр (Сб. трудов). — Вильнюс: Моклас, 1976.- С. 115-118.

62. Сорокин К. С. Гарантированное по исходам и рискам решение одной двухкритериальной задачи // Автоматика-2004: Материалы 11-ой международной конференции по автоматическому управлению. — Киев: Национальный университет пищевых технологий, 2004. — С. 39.

63. Сорокин К. С. Гарантированное по исходам и рискам решение одной двухкритериальной динамической задачи // Сборник статей молодых ученых факультета ВМиК МГУ, выпуск №2,— М.:МГУ, 2005.— С. 1 -11.

64. Сорокин К. С. Существование гарантированного по исходам и рискам решения одной многокритериальной задачи // Вест. Моск. университета, сер. 15, вычисл. матем., киберн. — 2008. — № 1. — С. 19-25.

65. Сорокин К. С. Гарантированное по исходам и рискам решение одной многокритериальной динамической задачи // Автоматика и телемеханика. 2009. - № 3. — С. 123 - 135.

66. Субботин А. И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. — Москва-Ижевск: Институт компьютерных исследований, 2003.

67. Яновская Е. Б. Ситуация равновесия в общих бескоалиционных играх и их смешанных расширениях // Теоретико-игровые вопросы принятия решений (Сб. трудов). — JI. Наука, 1978. — С. 43-65.

68. Arrow К. J. Alternative approaches to the theory of choice in risk- taking situations // Econometrica. — 1951. —Vol. 19.— Pp. 404-437.

69. Aumann R. J., Peleg B. Von Neumann-Morgenstern solutions to cooperative games without side payments // Bull. Amer. Math. Soc. — 1960. — Vol. 66. — Pp. 173-179.

70. Borwein J. Proper efficient points for maximization with respect to cones // SIAM J. Control and Optimiz. 1977. - Vol. 15, no. 1. - Pp. 57-63.

71. Chernoff H. Rational selection of decision function // J. Optimiz. Theory and Appl. 1954. - Vol. 22. - Pp. 422-443.

72. Dragustin C. Min-max pour des criteres multiples, rechrerche operationelle // Operations Research. — 1979. — Vol. 12, no. 2. — Pp. 169-180.

73. Geoffrion A. M. Proper efficiency and the theory of vector maximization // J. Math. Anal and Appl. — 1968. — Vol. 22, no. 3. Pp. 618-630.

74. Jentzsch G. Some thoughts on the theory of cooperative games // Advances in game theory. Ann. Math. Studies. — 1964. — Vol. 52. — Pp. 407-442.

75. Koopmans Т. C. Analysis of production as an efficient combination of activities // Activity Analysis of production and Allocation. — N.Y.: Wiley, 1951.-Pp. 33-97.

76. Pareto V. Manuel d'economie politique. — Paris: Geard, 1909.

77. Petrosian L. A. Differential Games of Pursuit. — London, Singapore: World Sci. Publ. Co. Pt. Ltd., 1993.

78. Savage L. Y. The theory of statistical decision //J. American Statistic Association. — 1951. — no. 46. — Pp. 55-67.

79. Wald A. Contribution to the theory of statistical estimation and testing hypothesis // Annuals Math. Statist. — 1939. —Vol. 10, — Pp. 299-326.

80. Wald A. Statistical Decision Functions. — N.Y.: Wiley, 1950.

81. Zhukovskiy V. I., Salukvadze M. E. The Vector-Valued Maximin.— N.Y. etc.: Academic Press, 1994.