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

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

факультет вычислительной математики и кибернетики

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

СЕМОВСКАЯ Анна Сергеевна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2006

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

Научный руководитель:

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

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

доктор физико-математических наук, проф. кафедры системного анализа ф-та ВМиК МГУ им М. В Ломоносова А.В.Лотов

кандидат физико-математических наук, старший научный сотрудник ВЦ РАН им. А.А.Дородницына А.И.Голиков

Ведущая организация:

факультет прикладной математики - процессов управления (ПМ-ГГУ) СПбГУ

Защита диссертации состоится 10 февраля 2006 г в 11 ч. на заседании диссертационного совета Д501.001 44 при Московском государственном университете по адресу 119992, Москва ГСП-2, Ленинские горы, МГУ, факультет ВМиК, ауд. 685

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан "......"............ 2006 г.

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

Н.П Трифонов

/йг/

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

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

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

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

Цель работы.

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

Основные задачи работы:

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

- обоснование применения обратной логической свертки для параметризации и аппроксимации решения;

- разработка способов аппроксимации решения в нерегулярном случае

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

многокритериальной оптимизации и исследования операций, математического анализа, теории экстремальных задач

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

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

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

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

Публикации.

По материалам диссертации опубликованы 3 печатные работы.

Апробация работы. Результаты работы докладывались на научно-исследовательских семинарах кафедры исследования операций ВМиК МГУ, ВЦ РАН, факультета прикладной математики-процессов управления (ПМ-ПУ) СПбГУ.

Структура и объем работы. Диссертация состоит из введения, трех глав (в первой главе 5 параграфов, во второй - 2 параграфа и в третьей главе 4 параграфа), заключения и списка литературы Общий объем работы составляет 113 страниц, включая список литературы из 83 наименований.

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

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

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

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

Ф* == Min Мах Min Мах ... Min Мах Ф (u-.w). (1)

Здесь Ф(и; w) - вектор-функция, определяющая векторный критерий ЛПР, w* -переменные, относящиеся к неопределенности, и' - переменные, отвечающие управляющим воздействиям ЛПР, t = 1,Т - номер этапа (время). Б §1,1 рассматривается постановка задачи определения значения кратного векторного минимакса и делаются

' В настоящей автореферате формулы пронумерованы по порядку, а нумерация определений, теорем и утверждений соответствует принятой в диссертация

необходимые предположения относительно рассматриваемых функций и множеств А именно предполагается, что Ф(u;w) = {<р\(щ w), <£г(и; w), . ,<pq(u;w)} > 0, где функции p,(u;w) = tfitiu1,... ,uT;wl,.. •, wT), i — 1,2,...,Q, непрерывны no совокупности аргументов, множества С Ж"1 Vu;' е и Wt(ut~i) с Ит' Vu'"1 е Ut~l(wt~1) — компактны, а отображения {/'(•), W*(-) — непрерывны по Хау-сдорфу Vi = 1,2 ,...,Т (полагаем W^u0) d= Wl и U°(w°) = 0).

Знаки неравенств ">","<",">", и "<" для векторов понимаем в смысле покомпонентных неравенств ">","<",">", и "<" соответственно.

В §1.2 представлен используемый математический аппарат. Здесь приводятся основные сведения из теории векторной оптимизации, необходимые для формального описания решения многокритериальной динамической задачи с неопределенностью' Определение 1.1 Вектор € D называется максимальным по отношению >(>)

в множестве D, если не существует такого вектора d, е D, d ф , что d> <fl(d> <f).

Определение 1.3 Вектор dP С D, максимальный по отношению >, называется эффективным, или оптимальным по Парето (Парето-оптимальным, паретовским) Определение 1.4 Вектор <Р € D, максимальный по отношению >, называется оптимальным по Слейтеру (слейтеровским).

Совокупность оптимальных по Парето (Слейтеру) векторов в множестве D будем обозначать как Max D. При необходимости уточнения будем использовать также обозначения Махд для максимума по Парето и MaxQ для максимума по Слейтеру.

Аналогично вводятся определения минимальных по Парето (Слейтеру) векторов и множество Mm D.

Если элементы множества D в определениях 1.1-1.4 имеют смысл исходов в многокритериальной задаче оптимизации на заданном множестве стратегий, то стратегии, соответствующие паретовским (слейтеровским) исходам, также называются паретов-скими (слейтеровскими)

Рассмотрим следующую задачу пусть оперирующая сторона выбирает свои стратегии из некоторого множества U Пусть Ф: U -> И4, Ф(и) = {ip\(и), . ,<р<¡(и)) -векторный критерий, в максимизации которого заинтересована оперирующая сторона И введем следующее

Определение Гарантированной оценкой снизу критерия Ф(-) называется произвольный вектор ф е для которого существует и* G U, такой что ф < Ф(и')

В §1.3 приводятся основные результаты теории векторной оптимизации в условиях неопределенности.

В §1 4 представлены основные результаты, полученные для задач поэтапного принятия решений в условиях неопределенности.

Применение описанных в §1.3 методов формализации значений векторных макси-мина и минимакса приводит в §1 5 к следующим определениям кратного векторного минимакса:

Ф*=11?ПМт U Мах U •■•Min (J Мах U {^<Ф(и;ш)}.

(2)

и

Ф* ='Мах р| U ... П U {Ф>0\ф<Ф(и;и1)} (3)

w1aw1 ^eu^w1) wTewT{uT-1) urz uT(wT)

В определениях (2), (3) максимумы и минимумы рассматриваются либо по Парето либо по Слейтеру.

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

Теорема 1.1. Для слейтеровской постановки множества (2) и (S) совпадают

Отметим, что в паретовском случае определения (2) и (3) существенно различаются, причем определение (3) представляется более соответствующим смыслу постанов-

ки задачи в гарантированных оценках. Таким образом, в данной работе предлагается использовать определение (3) в качестве основного.

Вторая глава посвящена вопросам параметризации значения кратного векторного минимакса В §2 1 приводится понятие обратной логической свертки и описывается ее применение в задачах параметризации множеств Парето и Слейтера.

Обратной логической сверткой (OJTC) векторного критерия Ф(-) — (^i('), .., называется функция

mm urWO. ßeM, (4)

i€/(ii)

Q

где M = {ц> 0| = 1} - стандартный симплекс в IR1®, 1=1

T(ß)^{t = l,2,...,Q\ßljtO}, /«{. = 1,2, ,Q}.

В §2.2 изучается вопрос параметризации кратного векторного минимакса с помощью OJIC.

Выберем в качестве основного определения кратного векторного минимакса определение (3) и обозначим за Ф максимизируемое множество. Напомним, что максимум в данном определении может рассматриваться как по Парето, так и по Слейтеру И будем использовать обратную логическую свертку, то есть функцию вида (4).

С помощью свертки (4) сведем многокритериальную задачу (1), (3) к параметрическому семейству задач поиска

в\и\ = min max . . min max min u~lwju;w) Vu G M. (5)

11 uiieW'u'et/1^1) wTeWT(uT-l)uT£UT(wT)i£l(n) '

Введем условие регулярности Ф как требование выполнения следующего равенства:

* = ~П U •■ П ~TJ {Ф>о\Ф<Ф(%ш)} (б)

miew1 u leul(wi) uTewTluT-1)uTeuT(wT)

Оказывается, в регулярном случае OJ1C позволяет параметризовать значение кратного векторного минимакса, а именно справедлива основная теорема главы 2

Теорема 2.1. Условие регулярности (6) выполнено тогда и только тогда, когда для слейтеровской постановки задачи (3) верно

ф- = и 9\ф. (7)

Доказано также следующее Замечание. В общем случае, то есть без предположения о регулярности (6), можно доказать только включение

(8)

где и Ф*£г обозначают паретовское и слейтеровское значенш (3)

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

Третья глава посвящена аппроксимационным свойствам свертки в задаче поиска кратного векторного минимакса.

В §3 1 изучаются аппроксимационные свойства ОЛС при выполнении условия регулярности (6).

Основным результатом этого параграфа является Теорема 3.1. Функция в\р\ ф 0 непрерывна тогда и только тогда, когда выполнено условие регулярности (6)

Данная теорема позволяет использовать для аппроксимации кратного векторного минимакса ¿-сеть, построенную на основе ОЛС, где под конечной ¿-сетью во множестве М понимается конечное число точек М6 С М таких, что У/л С М найдется вектор // € М1, для которого - //|| < <$.

Справедливо следующее

Утверждение 3.3. В условиях регулярности (6) для любого е > 0 существует 6" > О такое, что для любой конечной 5-сети Mf С М (О < 8 < 5") множество (J 9[ß]ß образует е-сеть в В §3 2 рассматриваются свойства функции 6\ß\ в случае, когда условие регулярности (6) не выполняется. Отметим, что проверить выполнение условия регулярности непросто, а потому и в предположительно регулярном случае имеет смысл пользоваться методами, разработанными для нерегулярных задач.

В параграфе 3 2 доказана справедливость следующей леммы, которая является основополагающей для понимания аппроксимационных свойств OJIC. Лемма 3.1. Функция в[ц], определенная согласно (5), обладает следующими свойствами.

1) Если существует ß' £ М, для которого в\р!] = 0, то 9[ß\ = 0 для любого ß € М, удовлетворяющего условию 1{р') С I(ß);

2) Если существует ß' е М, для которого 9[ß'\ > 0, то в\р\ > 0 при всех ß & М, для которых I(ß') О I(ß);

S) Функция 0{ß] ограничена на множестве {ß 6 М| I(ß) = 7} VJ С I.

В отсутствие условия регулярности (6) функция 9[ß], не будучи непрерывной на множестве М, будет непрерывной на множестве М° = {ß s M\ß > 0}. Это дает возможность использования для аппроксимации кратного векторного минимакса функции 0[ß\, определяемой следующим образом-

V ß° € М e[ß°] = lim в\р\.

И -» (i°, Ii > о

Доказано, что такой предел существует и функция 9[ß\ непрерывна на М. Множество, получившееся на основе аппроксимации с помощью функции 9[ß] вместо ОЛС в нерегулярном случае, не будет содержать слейтеровских решений, не являющихся паретовскими ни для какого подпространства критериального пространства

В §3 3 описан случай, в котором условие регулярности выполнено не на всем пространстве критериев размерности С}, но на каком-то его подпространстве Обозначим через ¡Iх г-й орт и введем множество .7 {г € 1\ > 0} Тогда Ф — {О/у} х Ф где О/у - вектор из нулевых компонент г € / \ .7, а

П и •■• П и > о| ^ < <Р3(щш) У] е >/}.

Для любого вектора £ 6 Ш® и любого индексного множества Г С I символ £// означает вектор, составленный из компонент £„ г 6 /'.

Предположим, что условие регулярности типа (6) выполняется в каком-либо подпространстве критериев размерности 1< <3, те для замыкания в Н./ справедливо

~П и ••• П О {^Ш^п^ТГ} = ъ (9)

ю> 6И" и1 «С?1 (ш') 1) итеит(тт)

Условие (9) назовем редуцированным условием регулярности и определим редуцированную ОЛС

вЛиА^ пнп тах . . тш тах тт и,~1ю.(и\ ю) = вЦцт, Ол г)1,

6 м} « > 0| ъ = 1}, /Ы « {г € АЧ ^ 0}

Заметим, что если J ф Q, то все векторы из множества Ф являются и максимальными и минимальными по Слейтеру, те. понятие слейтеровского решения в таком случае не информативно. Более информативную оценку дает множество Мах Ф^, аппроксимация которого возможна с помощью редуцированной ОЛС.

В редуцированном пространстве Е.^ свойства ОЛС остаются аналогичными полноразмерному случаю Так, доказана следующая

Теорема 3.2. Редуцированное условие регулярности (9) выполнено тогда и только тогда, когда для Мах по Слейтеру имеет место представление

Мах Ф.7 = Ф} = и 0-ЧНя/-

При выполнении редуцированного условия регулярности для аппроксимации значения Мах Ф J становится возможным использование ¿-сети, поскольку справедлива

Теорема 3.3. Если выполнено условие регулярности (9), то функция непрерывна Уц} е М).

Непрерывность функции $■'[на некотором множестве позволяет построить 6-сеть, аппроксимирующую значение Мах Фу на этом множестве. А именно, верно Утверждение 3.6. В условиях регулярности (9) для произвольного е > 0 существует <5* > 0, такое, что для любой конечной 6-сети М' С М3 (0 < й < &") множество

и в'Ым

юелл'

образует е-сеть в Мах Ф].

В случае если не удается построить редукцию Ф в явном виде, для аппроксимации значения кратного векторного минимакса имеет смысл использовать усиленные 5-сети

Определение 3.2 Будем называть усиленной 5-сетью М* на множестве М конечную 5-сеть, такую, что

V МЕМ Э ¿ем*: = /(д{). Им - А\ <

Утверждение 3.7. Для любого е > 0 существует <5 > 0, такое, что для любой усиленной 8-сети С М множество У образует усиленную е-сеть в

Ф'\{0}.

В §3 4 рассматриваются реализации кратного векторного минимакса - гарантирующие стратегии оперирующей стороны и наихудшие для нее варианты реализации неопределенного фактора — стратегии противника

Введем следующие обозначения: и* = (и1, и2,.. ,м') и = {шх,и?, , -ш4)

Обозначим через и{ [/i](ut_1, w*), w'"1) произвольные реализации го-

ответствующих максимумов и минимумов в (5) и итеративно определим (для этих реализаций) следующие множества:

U aMut~1,wt), wt_1) = U w*"»), (10)

и ем /1бМ

t = 1,2,... ,2™. Доказано

Утверждение 3.8. В задаче (1), (S) верно

Ф* = Min Мах .. Min Мах Ф (u,,w,). (11)

n>ä6Wfui6i/i(i»i) wTewTtf-1,^-1) иТеиТыТ'1,*!)

для произвольных наборов (10), объединяющих какие-либо реализации скалярных кратных минимаксов (5).

Таким образом, множества (10) предлагается рассматривать в качестве максимизирующих и минимизирующих стратегий в задаче (1), (3).

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

Основные результаты, выносимые на защиту.

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

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

Автор выражает признательность своему научному руководителю Н.М. Новиковой и И.И. Поспеловой за постоянное внимание к работе

Основные результаты диссертации опубликованы в работах:

Список литературы

[1] Новикова Н.М., Поспелова ИИ, Семовская А С Кратный векторный минимакс // Ж. вычисл. матем. и матем. физ. 2000. Т.40. N.10. С. 1451-1463.

[2] Новикова Н.М, Семовская А. С Обратная логическая свертка в задаче поиска кратного векторного минимакса // Вестн Моек Ун-та. Сер 15, Вычисл матем и матем. физ. 2000. N.4. С. 27-30.

[3] Семовская A.C. Аппроксимация множества неулучшаемых оценок вектора критериев в задаче динамического принятия решений в условиях неопределенности // Известия РАН, ТИСУ. 2005. N. 3. С. 12-23.

В совместной работе [1] автору принадлежит доказательство утверждения 1 (теорема 1.1 диссертации), а также лемм 6 и 7 (леммы 2.6 и 2 7 диссертации).

В совместной работе [2] автору принадлежит доказательство утверждения 1 (теорема 3.1 диссертации).

•-5451

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

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

Введение.

Глава 1. Определение значения кратного векторного минимакса.

§1.1. Задача поэтапного принятия решений в условиях неопределенности. Постановка задачи.

§1.2. Необходимые сведения о векторной отимизации.

§1.3. Задачи векторной оптимизации с неопределенностью.

§1.4. Задачи многоэтапного принятия решений в условиях неопределенности.

§1.5. Определение значения кратного векторного минимакса.

Глава 2. Параметризация значения кратного векторного минимакса.

§2.1. Обратная логическая свертка и ее свойства.

§2.2. Обратная логическая свертка в задаче на кратный векторный минимакс.

Глава 3. Аппроксимационные свойства свертки в задаче на кратный векторный минимакс.

§3.1. Регулярный случай.

§3.2. Нерегулярный случай.

§3.3. Редуцированное пространство.

§3.4. Реализации оптимумов.

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

Для формализации задачи введем необходимые обозначения: обозначим через wl переменные, относящиеся к неопределенности, через и1 управления оперирующей стороны и будем считать, что при выборе каждого иг уже станут известны значения к;1,., wl, а значения wt+1 определятся позже. Здесь t - индекс этапа (время). Векторный критерий обозначим за Ф(u;w).

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

Формально распространяя данный подход на многоэтапную многокритериальную задачу, запишем:

Ф* = Min Max Min Мах . Min Мах Ф (u:w). (1) wle\vl u1eui(w1)w2ew2(u1)u2eu'i(w2) wTe\vT(uT-'l)uTeuT(wT)

Приведем пример интерпретации задачи (1) с Т — 2 в терминах многопродуктовых потоковых сетей, служащих структурной моделью ряда многопользовательских сетевых систем (см. в частности [41]). Рассмотрим задачу учета неопределенности при синтезе многопродуктовых сетей.

Качество функционирования многопользовательской сетевой системы определяется мультипотоком — вектором одновременно пропускаемых по сети потоков заявок пользователей (видов продуктов) / = (/i,.,/q). Для сети с заданной пропускной способностью ребер ставится задача векторной максимизации /. При исследовании живучести сетевой системы учитывается, что в процессе ее работы исходный вектор пропускной способности может изменяться — уменьшаться по некоторым компонентам. Обозначим соответствующие неопределенные факторы через и»1, w2 и укажем, что u;1, w2 могут иметь смысл отказов и износа оборудования либо еще какого-либо ухудшения функционирования сети.

Пусть у оперирующей стороны между "ударами" w1, w2 есть возможность применить корректирующее управление и1, ограничения на которое в общем случае зависят от реализации w1. Здесь и1 имеет смысл вложения в восстановление сети после удара некоторого ресурса.

Тогда гарантированная оценка качества функционирования сети дается гарантированным значением кратного векторного мшшмакса типа (1)

Min Max Min Мах /. (2)

Целевая функция в (2) для сетевых систем линейна (по крайней мере во внутренней задаче максимизации), причем целевая функция зависит лишь от последнего управления и2 = f. Рассматривая общий случай, приходим к задаче (1). Допустима также зависимость ограничений Ul, \\rt и от всей предыстории w4 (w1,., wl), ut-i ^ u(~l), t = 1,2,., T, но для упрощения изложения ограничимся данной постановкой, поскольку обобщение проводится автоматически (требует лишь более громоздких обозначений). В дальнейшем для иллюстративных целей будем рассматривать случай линейных ограничений в данной задаче.

Рассмотрим следующий иллюстративный пример: пусть дана сеть ABC с двумя ребрами АВ, АС. В данной сети заданы тяготеющие нары АВ, АС, ВС. Для сети заданы пропускные способности линий связи рдв " Рве- По сети дважды наносятся удары ги1, w2, причем известна их мощность А1, Л2. Здесь Л1, Л2, рлв, Рлс ~ некоторые константы. Между этими ударами у ЛПР есть возможность применить корректирующее управление и, то есть вложить некоторый ресурс в ремонт, на увеличение пропускной способности ребер. Поток обозначим, по тяготеющим парам, /ав, /лс> }вс

Таким образом, приходим к задаче:

Ф* = Min Max Min МахФ(и;го), w^ew1 ueu(w1)w2e\v2(u1) feF при этом Ф(щ w) = {Jab, /ас, Ibc}

На удары естественно вводится следующая система ограничений: wab + w\c = Д1> wab > °> wac > о, ав + ™2лс = л2> wab > о» wac > о-5

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

UAB + UAC = (5(1 + Uad > 0j Члс > Q

Из свойств сети вытекают следующие ограничения на вектор мультипотока: sab + sbc < Рлв - w\d + uab ~ ы2лв, iас + sbc < Рас ~ ™\с + иас ~ w2ac, sab > 0, sac > 0, sbc > 0.

В качестве примера для рисунков рассмотрен случай, Л1 = 2, Л2 = 3, 5 = 1, рдц = б) Рас — 7- Для наглядности в иллюстративном примере рассмотрен дискретный случай, в котором стратегии выбираются из конечного множества векторов.

Формализация значения кратного векторного минимакса (1) не очевидна. В данной работе предложено использовать определение, являющееся обобщением определения векторного минимакса из [59]. Для удобства описания решений предлагается также использовать множество иеулучшаемых оценок. А именно предлагается принять за основное определение кратного векторного минимакса следующее:

Ф* =f Мах П (J . П (J {ф>0\ф <Ф(щю)}. (3) w'etK1 u'et/^uj1) wTe\vT(uT~l) иTeuT(wT) Отметим, что данное множество оказывается заданным неявно, так что возникает необходимость в его параметризации. В данной работе для параметризации и аппроксимации значения кратного векторного минимакса предложено использовать обратную логическую свертку (OJ1C). Исследованы свойства OJIC в данной задаче, предложен и обоснован метод аппроксимации значения кратного векторного минимакса на основе OJIC. .

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

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

Многокритериальная оптимизация.

Проблемы формализации принятия решений человеком не являются еще полностью разработанной теорией ([83]). В качестве одной из основных концепций следует рассматривать задачи принятия решения при нескольких критериях.

Смысл многокритериальной постановки заключается в том, что зачастую лицо, принимающее решение (ЛПР) не в состоянии описать свои предпочтения при помощи одной функции, поскольку это противоречит многогранности, "нелинейности" его интересов. Практически в любой реальной задаче принятия решения, в любой рассматриваемой области, будь то распределение финансирования научных проектов либо проблема покупки нового телевизора, для выяснения предпочтений недостаточно одного критерия (см. [20], [52], [36], [4]).

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

Построение эффективного мноэ/сесгпва. Одним из классических определений "эффективного" множества является определение эффективности по Парето. Эффективное множество (или векторный максимум) по Парето - это множество всех педо-мшшрусмых (максимальных по отношению >) векторов.

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

Однако множество Парето неудобно для аппроксимации, а потому вместо множества Парето часто рассматривается некоторое его расширение - множество Слейтера. Множество Слейтера (или максимум по Слейтеру) - множество всех максимальных по отношению > векторов. Подробно о множествах Парето и Слейтера см. §1.3. Также точки максимума по Слейтеру часто называют иолуэффективными. Множество Слейтера в общем случае обладает лучшей структурой, чем множество Парето, потому в данной работе рассматривается почти исключительно именно это определение оптимальности вектора критериев.

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

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

Подробно о различных подходах к построению эффективного множества, а также о вопросах топологических свойств, параметризации и устойчивости множества Парето можно прочесть в монографии [57].

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

Прежде всего несколько слов об областях человеческой деятельности, в которых успешно применяется многокритериальный подход:

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

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

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

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

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

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

Аппроксимация. Связь аппроксимации функций и векторной оптимизации см., например в [80].

См. также сборник [82], посвященный вопросам многокритериальной оптимизации в науке и технике.

Построение эффективного множества:

Численные методы аппроксимации множеств Парето и Слейтера предлагаются в большом числе работ.

Подробный обзор методов аппроксимации множества Парето можно найти в работе [67], а здесь приведем только краткий обзор основных идей. Отметим вначале, что методы аппроксимации множества Парето делятся на три основные группы:

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

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

Методы свертки - подмножество методов скаляризации. Суть всех методов свертки состоит в том, что задача аппроксимации множества Парето заменяется на задачу оптимизации параметрического семейства скалярных функций, что позволяет ввести сетку но параметрам свертки и получить аппроксимацию множества Парето с необходимой точностью. Видов свертки уже разработано достаточно много, см. [13]. Видимо, наиболее известной и часто применяемой является линейная свертка критериев. Так, например, в работе [26] для линейной модели экономического взаимодействия регионов предложено использовать линейную свертку для параметризации множества Парето. Аналогичное применение линейной свертки см., например, в [СЗ].

Логическая свертка, введенная в [13], а также модифицированная логическая свертка, позволяющая получить множество Парето, а не Слейтера, также хорошо изучена и применяется для выпуклых задач.

Обоснованию предпочтительности использования нелинейной свертки по сравнению с линейной посвящена работа [54].

Отметим также ассортиментные свертки (см. [78]) и популярный в экономических работах метод идеальной точки (см., например [76]).

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

Существуют и иные методы аппроксимации множества Парето, например, в работе [79] предлагаются вычислительные методы поиска компромиссных решений, основанные на методе "центра тяжести".

Читателю, желающему получить подробное представление о постановках и методах решения многокритериальных задач можно рекомендовать книгу [77]. В этой работе подробно и иллюстративно обсуждаются вопросы построения эффективных точек, рассматривается применение в многокритериальной оптимизации целевого программирования, метода метрик Чебышева, методов наискорейшего подъема и Фрэнка-Вулфа и т.д. Также в этой работе рассматриваются такие частные случаи задач многокритериальной оптимизации как дробно-линейные многокритериальные задачи, задачи с невогнутой функцией полезности и т.д.

Многокритериальные задачи оптимального управления рассматриваются, в частности, в работе [39]. В данной работе рассматриваются и игровые задачи с векторными доходами, решать которые предлагается при помощи А-свертки.

В центре нашего внимания в данном исследовании будет обратная логическая свертка критериев (см. §2.1).

Многокритериальный выбор

Напомним, что кроме задачи многокритериальной оптимизации мы упоминали и задачу многокритериального выбора.

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

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

Разработано большое количество методов подбора экспертной группы и правил голосования внутри нее. Так, правила формирования группы экспертов и методы ее работы подробно описаны в работе [б].

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

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

В качестве примера интерактивной экспертной системы многокритериального выбора можно отметить Yandex Гуру (www.guru.yandcx.ru - популярный онлайн-сервис, помогающий принять решение о выборе той или иной модели в данной группе товаров).

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

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

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

Проблеме относительной важности критериев посвящены и работы [55], [53]. О нормализации критериев см. также [42].

Проблема количественной оценки важности критериев является актуальной. Так, отметим продолжающую данную тему статью [75].

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

В работе [18] также исследуются проблемы визуализации многокритериальных задач для помощи ЛПР в принятии решений. Исследуется функция полезности ЛПР и предлагаются методы аппроксимации данной функции при помощи квазивогнутых функций и Чебышевских функций.

Отметим также уже упоминавшуюся работу [15], в которой представляется экспертная система для принятия решений о разработке и разведке нефтяных месторождений.

Динамические задачи и задачи с неопределенностью

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

В работе [3] проведено исследование методологии принятия решения в условиях неопределенности, дана классификация видов неопределенности и формулируются различные подходы к принятию решений при неопределенности. Для выбора решения при неопределенности возможно использование следующих критериев: средних затрат, критерий минимаксных затрат, критерий минимаксного риска (критерий Сэ-виджа), критерий пессимизма-оптимизма (критерий Гурвица), обобщенный критерий. У каждого из этих критериев есть как достоинства, так и недостатки. Так, критерий средних затрат предполагает равновероятность всех исходов неопределенности, что не всегда соответствует действительности. Критерий Гурвица и обобщенный критерий опираются на субъективные показатели. Недостаток критерия минимаксных затрат и критерия Сэвиджа заключаются в ориентации на самые худшие из осуществимых условий, однако именно они предохраняют ЛПР от наибольших потерь. Таким образом, минимаксный критерий часто используется в математических моделях.

Например, в [19] рассматриваются задачи распределения ресурсов на транспортных сетях при наличии неопределенных факторов, задачи минимизации времени либо стоимости выполнения работ при наличии неопределенных факторов.

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

В [3] рассматривается задача потребления электроэнергии и, в частности, применение максимшшого критерия в задаче вычисления тарифов электроэнергии.

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

Любопытная динамическая модель рассматривается в работах [44], [45]. Приведена многошаговая или бесконечная игра, связанная с процессами перебора и пополнения. Суть игры в следующем: в исходный момент имеется некоторая не более чем счетная совокупность перебираемых предметов. Стратегия минимизирующего игрока - забирать не более чем счетное количество предметов из набора. Стратегия максимизирующего игрока состоит в добавлении не более чем счетного набора предметов. Цель игрока, отвечающего за перебор - минимизировать, а цель игрока, отвечающего за пополнение, максимизировать количество предметов, которые останутся незабрапиыми при самом неблагоприятном поведении другой стороны. Характерной чертой этой игры является зависимость результата от полноты информации о предыдущих состояниях игры. Показана связь такой модели с дифференциальными играми, а также описано применение модели перебора-пополнения для задачи сортировки деталей.

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

Один из основных источников динамических и теоретико-игровых задач с наличием противника - модели военных действий. Так, в работе [73] приведена модель минирования, легко распространяемая на случай кратного векторного минимакса. Игра заключается в следующем: защищающаяся сторона размещает мины в проливе. Нападающая сторона использует минный тральщик для того, чтобы обезвредить мины. Однако на случай прохода тральщика каждая мина имеет устройство, называемое счетчиком судов. Счетчик судов предотвращает взрыв мины до того момента, пока мимо нее не пройдет заданное заранее количество судов. Итак, управлениями "минирующей" стороны являются количество мин и значения, выставляемые на счетчиках судов, управлениями "прорывающейся" стороны будет количество тральщиков, направляемых по минируемому фарватеру. Критериями в данной задаче могут являться как количество прорвавшихся судов, так и стоимость минирования и противоминных работ.

Аналитические и численные методы поиска минимакса

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

В работе [43] проведены исследования транспортных задач с минимаксным критерием. Рассматриваются транспортные задачи с нетрадиционным критерием. В классических моделях транспортная задача ставится как задача максимизации или минимизации, в зависимости от постановки (подробно о транспортных задачах см., например, [48], [30]). В работе [43] критерий рассматривается как минимакс, разработан алгоритм нахождения минимаксного значения и соответствующей ему минимаксной транспортной матрицы, проведен анализ и для случая целочисленных переменных.

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

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

В работе [25] рассмотрена задача поиска мипимакса со связанными переменными. В основе исследования лежит идея сведения задачи на связанный максимин к предельной задаче математического программирования при помощи метода штрафов. Установлена связь между градиентами штрафных функций и множеством стационарных точек задачи и на основе этой связи предложен стохастический градиентный алгоритм для поиска стационарных точек задачи на связанный максимин.

Дифференциальные игры. Отдельной строкой стоит упомянуть активно развивающееся направление на стыке теории игр и оптимального управления, а именно дифференциальные игры. Отметим здесь такие работы как [21], [22], [23], в которых предложена концепции векторного мипимакса и максимина (подробнее см. §1.3) а также [47], [2], [71] в которых проведены исследования некоторых динамических минимаксных задач на основе аппарата дифференциальных игр. Обратим также внимание на статью [70j, в которой рассматриваются дифференциальные игры двух коалиций в условиях неопределенности. В этой работе рассматривается случай, когда каждая коалиция состоит из двух игроков, отношения между которыми считаются доброжелательными и строятся па основе максимума но Парето.

Динамическая многокритериальная задача с неопределенностью.

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

Отметим, например, статью [35], в которой, в частности, поднимаются вопросы о многокритериальных динамических задачах и предложено решение такой задачи па основе теории управления в условиях неопределенности.

В работе [47] в рамках концепции из [21] для формализации многокритериальной динамической задачи принятия решений при неопределенности рассматриваются методы решения обратных задач динамики и задач сближения объекта с заданными точками. В качестве оптимального решения многокритериальной позиционной задачи при неопределенности предложена седловая точка по Парето, доставляющая гарантированный результат векторному критерию (см [22]). Устанавливается динамическая устойчивость данного решения, выясняется его структура. Рассматриваются свойства максимина по Парето в позиционных дифференциальных играх и играх сближения.

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

Данная работа продолжает исследования, начатые в работах [7, 9, 10, 40, 58, 59, 60]. Здесь отметим, что в этих работах разрабатывалась формализация векторных максимина, мшшмакса и максиминимакса, с использованием понятия о гарантированных оценках. В этих работах также рассматривались вопросы аппроксимации векторных максимина, мшшмакса и максиминимакса. Подробнее о данном подходе см. в §1.3.

Структура диссертации.

В первой главе рассматривается вопрос определения значения кратного векторного мшшмакса. Для формализации задачи динамического принятия решения с неопределенностью используются классические определения векторного максимума по Парето или Слейтеру и определения векторных минимакса и максимина, предложенные в [9, 10, 59].

Параграф 1.1 посвящен постановке задачи на кратный векторный мшшмакс.

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

Параграф 1.3 посвящен обзору задач векторной оптимизации с неопределенностью. В применении к этим задачам обсуждаются различные определения кратного векторного минимакса и максимина, различия и связь между этими определениями. В работах [9, 10, 59] проведен подробный анализ различных подходов к определению векторного минимакса и доказано, что все имеющиеся определения для векторного минимакса и максимина за максимизирующего игрока для задачи с неопределенностью сводятся всего к двум различным подходам:

MinМахФ(а;, у) = F<= Max fj (J {ф\ф < Ф(ж,у)}, (4) yeY хеА' yeYxex

МахМтФ(я,1/) = /< = Мах N П Шф < Ф{х,у)\. (5)

1£Л' " хехуег

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

Параграф 1.4 дает представление о задаче поэтапного принятия решений в условиях неопределенности. Здесь приводится определение векторного максимшшмакса. Векторный максиминимакс исследуется в [49, 60]. В этих работах обосновано следующее определение:

Max Min Мах Ф(г,ги,и) — Мах N П II {-ф еШ9\ф < Ф(г,ю,и)}. (б) иеи wgw(u) zeziw) . Уг, . v ' v ' иеи u>e\v(u) zez(w)

В параграфе 1.5 вводится формализация кратного векторного минимакса. В работе [50] рассматриваются следующие обобщения определения минимакса (4):

Ф* =f IR+ pi Min [J Max [J .Min [j Max (J {ф < Ф(г/; w)}. w^-ew1 u^eu^w1) и>те\ут(ит-1) ureuT{ wT)

7)

Ф* =f Max П U ••• П U (u-w)}. (8) u^ew1 uiec/^w1) wT€\vT(uT-1) uTeuT(wT)

Доказано, что определения (7) и (8) в слейтеровском случае совпадают.

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

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

Эта свертка предполагает замену вектора Ф = (</?!,.,^q) (в задаче на Мах) параметрическим семейством скалярных критериев min/i~l(Pi, /i е А/, i£7(A0 Q где М = {// > 0| Y^l^i = 1} " стандартный симплекс в IR^, i=i 1,2,.,Q| тфЪ), jM{t = 1,2.Q}.

Применение OJIC для параметризации максимума Парето и Слейтера было изучено в работах [66, G5, 67].

Параграф 2.2 посвящен параметризации значений кратного векторного минимак-са при помощи обратной логической свертки.

Параметризация значения кратного векторного минимакса рассмотрена автором в работах [50, 51, 04]. На основе ОЛС введена функция свертки в\и) '= min шах . min max rriin u~lwAu\ w) Vu E M.

Основным результатом второй главы является теорема 2.1, в которой доказано, что при предположениях регулярности задачи = ~П и ■•• П и {Ф>0\4><<ЦЩ10)} (9) wKw* u*eul(wi) wTe\vT(uT~1) uTeuT(wT) для слейтеровских значений максимума справедливо представление

Ф* - и нем

Таким образом, обосновано применение обратной логической свертки для параметризации оценок векторного критерия.

Третья глава посвящена вопросам аппроксимациоппых свойств ОЛС в задачах на кратный векторный минимакс.

В параграфе 3.1 проведено исследование аппроксимациоппых свойств свертки для регулярной задачи. Доказано, что в предположениях регулярности (9) функция свертки непрерывна на рассматриваемом множестве. На основе непрерывности обоснован алгоритм построения 5-сети, позволяющей аппроксимировать значения кратного векторного минимакса для регулярного случая.

В параграфе 3.2 рассмотрены свойства функции свертки в случае, если условие регулярности (9) не выполнено. В частности, доказана ограниченность функции свертки. Предложен и обоснован способ построения непрерывного продолжения функции свертки, как предела 0[/j] — lim доказана корректность построения пенред -> /Л

1 > о рывиого продолжения и рассмотрены свойства функции 0[ц\. Показано применение непрерывного продолжения для аппроксимации значения кратного векторного минимакса.

Параграф 3.3 описывает аппроксимационные свойства OJIC в случае, если условие регулярности (9) выполнено не па всем пространстве критериев, по на некотором его подпространстве. Показано, что и при редуцированном условии регулярности возможно построение 5-сети, только на более узком множестве. В этом параграфе обосновано также построение усиленной $-сети.

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

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

В заключении приведены основные результаты диссертации.

Основные результаты, выносимые на защиту.

1. Обоснование применения OJIC для параметризации и аппроксимации решения динамической многокритериальной задачи оптимизации в условиях неопределенности;

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

Указанные результаты опубликованы в работах [50, 51, 64].

Заключение

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

1. Айзерман М.А., Ллескеров Ф.Т. Выбор вариантов. Основы теории. М.: Наука, 1990.

2. Баранов В.Н., Гавриков В.Г. Динамические минимаксные задачи исследования операций JIA и систем. М.: Изд-во МАИ, 1989.

3. Барыкин Е.Е., Воропаева Ю.А., Долгов П.П., Косматое Э.М., Ногин В.Д. Мно-гокритериальность и неопределенность в задачах планирования экономической деятельности предприятий. СПб.: Изд-во СПбГТУ, 1998.

4. Березовский Б.А., Барышников 10.М., Борзенко В.И., Кеминер JI.M. Многокритериальная оптимизация. Математические аспекты. М.: Наука, 1989.

5. Берзин Е.А. Оптимальное распределение ресурсов и теория игр. М.: Радио и связь, 1983.

6. Бешелев С.Д., Гурвич Ф.Т. Математико-статистические методы экспертных оценок. М.: Статистика, 1980.

7. Воробейчикова О.А. Векторный минимакс со связанными ограничениями: Авто-реф. дис. канд. физ.-матем. наук. М.: МГУ, ф.ВМиК, 1998.

8. Воробейчикова О.А., Новикова Н.М. Векторный минимакс со связанными ограничениями // Вести. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 199G. N. 4.

9. Воробейашкова О.А., Новикова H.M. Параметризация значения векторного минимакса со связанными ограничениями // Ж. вычисл. матем. и матем. физ., 1997. Т.37. N.12. С. 1467-1477.

10. Гараев Я.Г., Киселев В.Г. Многокритериальное ранжирование объектов. //Исследование операции (модели, системы, решения). М.: ВЦ РАН, 2000. С. 9-20.

11. Гараев Я.Г., Киселев В.Г. Оперативное распределение бюджетных средств между научными организациями. //Исследование операции (модели, системы, решения). М.: ВЦ РАН, 1999. С. 14-25.

12. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

13. Гермейер Ю.Б. Игры с ^противоположными интересами. М.:Наука, 1976.

14. Глова В.И., Аникии И.В., Шагиагметов М.Р. Методы многокритериального принятия решений в условиях неопределенности в задачах нефтедобычи. Казань: Изд-во Казан, гос. техн. ун-та, 2004.

15. Глотов В.А., Павелъев В.В. Векторная стратификация. М.: Наука, 1984.

16. Гурии Л.Г. О задачах многокритериальной оптимизации в условиях неопределенности. // Ж. вычисл. матем. и матем. физ., 2001. Т.44. N.8. С. 1356-1363.

17. Гусев Д.В., Лотов А.В. Методы поддержки принятия решений в конечной задаче выбора. //Исследование операций (модели, системы, решения). М.: ВЦ РАН, 1994. С. 15-43.

18. Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.

19. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985.

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

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

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

23. Завриев С.К. Стохастические градиентные алгоритмы решения минимаксных задач. // Автореф. дис. канд. физ.-матем. наук. М.:МГУ, 1981.

24. Завриева М.К. Метод штрафов в задаче на максимин со связанными переменными. // Автореф. дис. канд. физ.-матем. наук. М.:ВЦ АН СССР, 1988.

25. Злобин А.С. Параметрические методы решения линейных минимаксных и многокритериальных задач. // Автореф. дис. канд. физ.-матем, наук. М.:ВЦ АН СССР, 1983.

26. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. М: Наука, 1979.

27. Иозайтис B.C., Львов Ю.А. Экономико-математическое моделирование производственных систем. М.: Высшая школа, 1991.

28. Коноиенко А.Ф., Халезов А.Д., Чумаков В.В. Принятие решений и условиях неопределенности. М.: ВЦ АН СССР, 1991.

29. Кремер Н.Ш., Путко Б.А., Тритии И.М., Фридман М.Н. Исследование операций в экономике. М.: Банки и биржи, ЮНИТИ, 1997

30. Краснощекой П.С., Морозов В.В., Федоров В.В. Декомпозиция в задачах проектирования.! // Изв. АН СССР. Техн.кибернетика 1979. N 2. с.7—17. .

31. Краснощекое П.С., Петров А. А. Принципы построения моделей. М.: МГУ, 1983.

32. Крейиес Е.М., Новикова Н.М., Поспелова И.И. Многокритериальные игры двух лиц с противоположными интересами.

33. Куркгш О.М., Коробочкип Ю.Б., Шаталов С.А. Минимаксная обработка информации. М.: Энергоатомиздат, 1990.

34. Куржапский А.Б. Динамические задачи принятия решений в условиях неопределенности. // Современное состояние теории исследования операций. Под ред. Н.Н.Моисеева. М.:Наука 1979. с.197-235.

35. Ларичев О.И. Наука и искусство принятия решений. М.: Наука, 1979.

36. Лотов А.В., Бушенков В.А., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

37. Лыос Р.Д., Райфа X. Игры и решения. М.: Изд-во иностранной литературы, 1961.

38. Макаров И.М., Випоградская Т.М., Рубчинский А.А., Соколов В.Б. Теория выбора и принятия решений. М.: Наука, 1982.

39. Малаиленко Ю.Е., Новикова II.М., Поспелова И.И. Многокритериальный синтез потоковых сетей с гарантией живучести. // Известия РАН, ТИСУ. 2001. N. 2.

40. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. М.: УРСС, 1999.

41. Машунин Ю.К. Теоретические основы и методы векторной оптимизации в управлении экономическими системами. М.: Логос, 2001.

42. Миронов А.А., Цурков В.И. Минимакс в транспортных задачах. М.: Наука. Физ-матлит, 1997

43. Модель Б.И. Многошаговые процессы перебора с пополнением. М.: Наука, 1990

44. Модель Б. И. Элементы теории многошаговых процессов последовательного выбора решений. М.: Наука, 1985

45. Морозов Б.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986.

46. Мухин В.В. Парето-оптимальные гарантии в динамических системах. // Авто-реф. дис. канд. физ.-матем. наук. М.: Ун-т дружбы народов, 1991.

47. Нийл В., Кэтепис Э., Хайндс Д. Транспорт //Исследование операций. Модели и применения. Под ред. Дж.Моудера, С. Элмеграби, М.: Мир, 1981

48. Новикова Н.М., Поспелова И.И. Векторный максиминимакс // Вестн. Моск. унта. Сер.15, Вычисл. матем. и киберн. 1999. N. 4.

49. Новикова Н.М., Поспелова И.И., Семовская А.С. Кратный векторный минимакс // Ж. вычисл. матем. и матем. физ. 2000. Т.40. N.10. С. 1451-1463.

50. Новикова Н.М., Семовская А.С. Обратная логическая свертка в задаче поиска кратного векторного минимакса j j Вестн. Моск. Ун-та. Сер. 15, Вычисл. матем. и матем. физ. 2000. N.4.

51. Ногин В.Д. Принятие решений в многокритериальной среде. Количественный подход. М.: Физматлит, 2002.

52. Ногин В.Д. Относительная важность критериев и ее применение в многокритериальной оптимизации. // Автореф. док. канд. физ.-матем. наук. СпБ: 1995.

53. Ногин В.Д. Упрощенный вариант метода анализа иерархий на основе нелинейной свертки критериев. // Ж. вычисл. матем. и матем. физ. 2004. Т.44. N. 7. С. 1261-1270.

54. Подиновский В.В. Аксиоматическое решение проблемы оценки важности критериев в многокритериальных задачах. // Современное состояние теории исследования операции. Под ред. Н.Н.Моисеева. М.:Наука 1979. с.117—149.

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

56. Полищук Л.И. Анализ многокритериальных экономических моделей. Новосибирск: Наука, 1989.

57. Поспелова И.И. Теоретические вопросы двухэтаппой векторной оптимизации: Автореф. дис. канд. физ.-матем. наук. М.: МГУ, ф.ВМиК, 2000.

58. Поспелова И.И. Классификация задач векторной оптимизации с неопределенными факторами // Ж. вычисл. матем. и матем. физ., 2000. Т.40. N. С. .

59. Поспелова И.И. Аппроксимационные свойства обратной логической свертки в задаче поиска векторного максиминимакса // Ж. вычисл. матем. и матем. физ., 2002. Т.42. N. 2.

60. Пресман Э.Л., С опии И.М. Последовательное управление по неполным данным. Байесовский подход. М.: Наука, 1982.

61. Рабинович Я.И. Об отыскании слабо эффективных решений. // Ж. вычисл. матем. и матем. физ. 2004. Т.44. N.4. С. 013-022.

62. Ресин В.П., Дарховский Б. С., Попков Ю.С. Вероятностные технологии в управлении развитием города. М.: УРСС, 2004.

63. Семовская А.С. Аппроксимация множества неулучшаемых оценок вектора критериев в задаче динамического принятия решений в условиях неопределенности. // Известия РАН, ТИСУ. 2005. N. 3.

64. Смирнов М.М. О логической свертке вектора критериев в задаче аппроксимации множества Парето // Ж. вычисл. матем. и матем. физ., 1996. Т.36. N.3.

65. Смирнов М.М. Методы аппроксимации граней множества Парето в линейной многокритериальной задаче // Вести. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 1996. N. 3.

66. Смирнов М.М. Методы аппроксимации множества Парето, основанные на обратной логической свертке, и их использование в сетевой оптимизации: Автореф. дис. канд. физ.-матем. наук. М.: МГУ, ф.ВМиК, 1996.

67. Смирнов М.М. Метод обратной логической свертки в задачах векторной оптимизации. М: ВЦ РАН, 1996.

68. Соболь И.М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981.

69. Тараканов А.Ф. Дифференциальная игра двух коалиций в условиях неопределенности. //Изв. РАН. Теория и системы управления. 2003. N.2. С.53-61.

70. Томский Г.В. Игровые задачи в динамических системах. Иркутск: Изд-во Иркутского университета, 1982.

71. Федоров В.Б. Численные методы максимина. М.: Наука, 1979.

72. Хилл У. Военное приложение теории игр. // Математическое моделирование. Под ред. Дж. Эндрюса и Р. Мак-Лоуна. М.: Мир, 1979

73. Цхай А.А., Нахгпнебел Х.-П. (рсд). Многокритериальное принятие решений в природопользовании. Барнаул: Алтайский гос. техи. ун-т, 2000.

74. Шахнов И.Ф. Количественная оценка важности целей. //Изв. РАН. Теория и системы управления. 2003. N.1. С.78-86.

75. Шикип Е.В., Чхартпишвили А.Г. Математические методы и модели и управле-нии.М.: Дело, 2000.

76. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992.

77. Элъстер К.-Х., Гепферт А., Полищук Л.И. и др. Методы оптимизации в экономико-математическом моделировании. М.: Наука, 1991.

78. Юдин Д.Б. Вычислительные методы теории принятия решения. М.: Наука, 1989.

79. Jahn J., Krabs W. Applications of Multicriteria Optimization in Approximation Theory. //Multicriteria Optimization in Engineering and in the Sciences (ed. by Stadler W.). New York: Plenum Press, 1988

80. Lawrence Kenneth D., Reeves Gary K., Klimberg Ronald K. (editors) Multi-criteria applications. Amsterdam: JAI An Imprint of Elsevier Science 2002

81. Stadler Wolfram (editor). Multicriteria Optimization in Engineering and in the Sciences. New York: Plenum Press, 1988.

82. Yu P.L. Forming winning strategics. An integrated theory of habitual domains. Berlin: Springer-Verlag, 1990.