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

московский государственный университет

имени М.В.Ломоносова

РГ8 ОД 2 2 СЕН 1938

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

ВОРОБЕЙЧИКОВА Ольга Александрова

удк 519.85

векторный минимакс со связанными ограничениями

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

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

Москва - 1998

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

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

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

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

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

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

Защита диссертации состоится -^££1998 г. в.-Д&л.

на заседании диссертационного совета Д053.05.038 при Московском государственном университете по адресу:

119899, Москва ГСП-3, Воробьевы горы, МГУ, факультет ВМиК, ауд. 685.

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

Автореферат разослан ".V?!.." 998 г.

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

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

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

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

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

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

Цель работы. Формализовать понятие решения задачи поиска минимакса со связанными ограничениями для векторной функции общего вида и разработать методы его параметризации и аппроксимации.

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на 1-й Московской международной конференции по исследованию операций (Москва, 10-13 апреля 1996 г.), на 4-й международной конференции по многокритериальным и игровым задачам, учитывающим неопределенность, в Орехово-Зуево (Орехово-Зуево, 8-14 сентября 1996 г.) и на научно-исследовательских семинарах факультета ВМиК МГУ, ВЦ РАН и ИПУ РАН.

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

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

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

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

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

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

метрике Хаусдорфа слейтеровского значения векторного мини-макса.

5. Разработана техника сокращения перебора значений параметра при аппроксимации векторного минимакса с помощью обратной логической свертки.

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

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

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

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

В §1 излагаются основные сведения из теории векторной оптимизации.

Пусть задано непустое множество альтернатив X, на котором определена вектор-функция ц> : X (векторный критерий). Обозначим через У — ф(Х) множество всевозможных значений векторного критерия (р на множестве альтернатив X. Будем понимать ">" и "<" для векторов в смысле покомпонентного ">" и "<" соответственно.

Определение 1.1. Вектор у0 € У называется оптимальным по Парето, если не существует вектора у 6 У такого, что у > у0 (у < у0), у ф у0. Множество всех таких векторов Р(У) называется множеством Эджворта-Парето. Решение х° € X называется оптимальным по Парето, если вектор оптимален по Парето.

Определение 1.2. Вектор у0 е У называется оптимальным по Слейтеру, если не существует вектора у & У такого, что у > у° (у < у0)- Множество всех таких векторов Б (У) на-

зывается множеством Слейтера. Решение х° £ Л' называется оптимальным по Слейтеру, если вектор <р(х°) оптимален по Слейтеру.

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

Определение 1.3. Конечной ¿-сетью в множестве Л называется конечное множество точек из Л, от которого все точки Л удалены не дальше, чем на ¿. Конечную 5-сеть в множестве Л будем обозначать .

Свертывание критериев заключается в следующем. Вводится параметр А и множество его значений Л. Также вводится свертка / : У х Л —» К1. Множество Парето Р(У) аппроксимируется множеством (у>(ж*(А))}, где Лй — ко-

лел*

нечная 6-сеть в Л, а х*{\) — произвольная точка максимума (минимума) свертки f(^p(x)íX) на множестве X.

В качестве А будем использовать

о

М = {цеК<* |#>0,5>,- = 1} (1.1)

¡=1

— стандартный симплекс в й.9.

В работе рассматриваются, в основном, линейная свертка

Я

1=1

и обратная логическая свертка (для случая максимизации)

/(У,/0 = ц 6 М.

>0

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

функции общего вида

Мт Мах Ф(г,ш), (2.1)

где Ф(£, V)) - {<£>1(2, *»)>■••>¥»<?(*»Функции уф, к?),

г = 1, <5, будем предполагать непрерывными по совокупности переменных и ограниченными снизу. Для определенности будем считать, что > 0. Множества С Л" будем предполагать непустыми и компактными Уш & \¥, отображение Z{•) — непрерывным но Хаусдорфу на непустом компакте ТУ в евклидовом пространстве. Эти условия далее будем обозначать (*).

В сделанных предположениях Мах^Ф(.г,№) достигается и,

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

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

Следующие утверждения показывают способ формализации множеств Ф и Ф для случая связанных ограничений. Утверждения 2.1. Ф= Р) и {ф > 0| Ф(г,ш) > ф).

Утверждение 2.2. Ф= р] у {ф > 0| Ф(г,и>) ^ ф}.

«ей' гег(ш}

Утверждение 2.3. Ф = f] [J > Oj ф{< шах у,(z,го)}.

W£w izhQ ^ez(w)

Диссертационная работа посвящена изучению концепции гарантированности значения (2.1). Этой концепции соответствует в качестве значения (2.1) множество Ф*, далее обозначаемое Ф*, максимальных по отношению ">, но не =" (или ">") элементов множества Ф:

Ф*={Махр) (J {ф>0\Цг,т)>ф}. (2.2)

wew zez(w)

Векторный максимум в (2.2) достигается, так как в силу условий (*) Vw £ W множество (J {ф > 0[ Ф(г,го) > ф}

zez(w)

является компактом, а пересечение компактов также является компактом.

В работах Жуковского В.И. и Салуквадзе М.Е. введено определение векторного максимина, которое, если переформулировать его для задачи поиска векторного мшшмакса со связанными ограничениями, приводит к следующей записи значения (2.1):

Ф; = Min 11 Мах {ф > О) = ф}. (2.5)

В утверждении 6.4 доказано, что при выполнении ряда условий Ф* совпадает с замыканием Ф*.

В определении (2.2) участвует все множество W, вообще говоря, континуальное. Естественно, представляет интерес найти более узкое множество W' С W, для которого тоже

Ф* = Max fj \J {ф > 0| $(z,w) > ф}, (3.1)

v!tw> zez(vi)

т.е. множество наихудших для оперирующей стороны стратегий противника — соответствующее реализации Min в (2.1).

Как правило, нельзя выбрать одно w' £ W, так чтобы Ф* = Max [J {ф > 0| Ф(2,го') > ф}, поэтому имеет смысл гег(ш')

говорить о минимальном по включении таком множестве W'. Однако в общем случае поиск требуемого множества является самостоятельной сложной задачей. В §3 изучаются возможности использования линейной и обратной логической сверток для рассматриваемой задачи.

Введем следующие определения и обозначения:

УГС^Ф<[Г]= Г) U {^>0|Ф(z,w)>1>}, wew zez(w)

ф[ТГ]=Г П (J Ф(г,я>), Ф*[]¥'} = МахФ<[И"];

_ Q

W = {u?(A) = arg mn{mut У^Л.-^г, w)}| Л G М};

^ ' ¿=1

W* ~f {w*(fi) = arg mini max min w)}l И € M}>

(3.2)

где

= (3.3)

Данные обозначения корректны, так как при условиях (*) min достигается.

Утверждение 3.1. Если множества Ф<[{«>}] выпуклы Vi» G W, то Ф* = МахФ<[1?], т.е. Ф*[1У] = Ф*[Щ.

В общем (не обязательно выпуклом) случае множество наихудших стратегий противника может быть параметризовано с помощью (3.2), где использована обратная логическая свертка. Утверждение 3.3. Справедливо равенство

Ф* = МахФ<[УГ], или Ф*[И7] = Ф*[ЖФ].

Тем самым подтвердились гипотезы, высказанные ранее в работах Малашенко Ю.Е. и Новиковой ILM.

Множества W и W*, вообще говоря, различны. В выпуклом случае множество W* является подмножеством множества W (утверждение 5.2.). Обратное включение, вообще говоря, неверно. Поэтому для параметризации и аппроксимации Ф* используется обратная логическая свертка и множество W*. Утверждение 3.5. Пусть

1) <pi(z,w) = z{, 1 < i < Q (Q = n),

2) Vw 6 W Z(w) образовано линейными ограничениями-неравенствами "<" с неотрицательными коэффициентами и ограничением z > 0, причем в любой точке z G Р| Z(w) ак-

tuew

тивньши являются не более п ограничений,

3) Z(w) — тг-мерный многогранник. wefv

Тогда, если Мах в (3.1) понимается в смысле ">", то Vw* € W* выполнено Ф* ф Мах Ф[№* \ {то*}].

Условия утверждения 3.5 выполняются, например, для задачи анализа уязвимости сетей связи, исследуемой в §7.

В §4 рассматривается линейная задача поиска векторного минимакса. Будем предполагать, что:

1) множество W является многогранником;

2) Vw 6 W множество Z(w) является многогранником, т.е.

Vw е W Z{w) = {z6 Rft| A{w)zT < b(w)}, где A{w) G Rfc('">xn, b(w) £ R*(»>xl;

3) вектор критериев линеен по z: $T(z,w) — C(w)zr -f d(w), где C(w) G RQxn, d(w) £ R«xl.

Утверждение 4.1. Если C(w) — обратимая матрица, то = {ф G RS| F(w)i>T < g{w)}, где

F(w) = A{w)C~\w), g{w) a=b{w) + A(w)C~1{w)d(w). (4.1)

Обозначим через Wext = {w1, w2,..., u?(} множество крайних точек многогранника W.

Утверждение 4.2. Пусть Vu; € W C(w) — обратимая матрица, F(w) и д(т) линейны по w. Тогда Ф[И7] =

Утверждение 4.3. Если A(w) = А и C(w) = С — не зависят от w, а b(w) и d(w) линейны по w, то = $[Weaet],

Таким образом, если выполнены условия утверждения 4.2 или утверждения 4.3, то при решении задачи поиска векторного минимакса мы можем рассматривать только множество Wext > которое является конечным множеством точек.

Далее в §4 предполагается, что множество W является конечным множеством точек W = {wl,w2, Введем следующие обозначения:

( ^(ш1) О

Л =

\

О

/

о

—C(w2) C(w2)

О

о

о

A(w<)

О О

-C(w<)

b(wx)

b(wi) diw^-diw1) d{w*) - d{w2)

¿(ю%) - d(wL) \ ¿(ад1) - d{wi)

(Через 0 обозначена матрица соответствующей размерности, состоящая из нулей.)

Ь

Рассмотрим множество {/ = {мё R'"|Аит < Ь}. Определим множество V = V(U) = {vT £ RQ| г>т = Cur + d, и 6 t/}.

Утверждение 4.4. Справедливо равенство V(?7) = $[W].

Из утверждения 4.4 следует, что Max$[W] = MaxF(i/). Отсюда если Ф* = МахФ[>У], то Ф* = MaxV(t/). При этом неважно в отношении строгого или нестрогого порядка понимается векторный максимум.

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

Min Max (C(w)zT + d(w))

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

Мах Сит + d.

Аит<Ь

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

Важным содержательным примером выполнения условий утверждения 4.4, в частности условий утверждения 4.3, является задача исследования уязвимости многопродуктовых потоковых сетей, которая рассмотрена в §7.

Глава 2 посвящена возможностям использования ОЛС для параметризации и аппроксимации значения векторного мини-макса и применению этих возможностей для анализа уязвимости многопродуктовых сетей.

В §5 предложена параметризация значения векторного ми-нимакса с помощью ОЛС. В случае если Мах в (2.2) понимается в смысле строгого отношения порядка (по Слейтеру), то

использование ОЛС позволяет получить следующую параметризацию множества Ф* — значения задачи (2.1). Утверждение 5.1. Пусть

Ф<[ИГ)Г|ЫВ.? = Ф<[1Р]. (5.1)

Тогда, если Мах в (2.2) понимается в смысле ">", то

Ф* - U Г, (5.2)

МбМ

где

^=f(mm max min iiY1^i(z,w))u. (5.3)

Тем самым, в условиях утверждения 5.1 получено обобщение на минимаксный случай формулы для параметризации множества Слейтера с помощью ОЛС. При этом для описания решения не надо искать все множество реализаций минимак-са свертки, а достаточно лишь найти значение минимакса для каждого /z £ М.

Если Ф< [W] — выпуклое множество, то условие (5.1) можно заменить следующим:

min max ф{> О, (5.5)

что в свою очередь эквивалентно условию Слейтера: З^еФ<[W\: ф> 0.

В §6 показано, как можно получить аппроксимацию множества Ф*, т.е. построить Ve > 0 конечную е-сеть в Ф*. Введем функции

ф(и) = arg max min а~1г/>; : = const Vi 6 I(ft), = 0 Vi ^ /(/i),

9(a) =f max min u¡ гф{. (6.1)

Доказаны следующие свойства функций ф(ц) и 0(р).

Утверждение 6.1. Справедливо равенство ф(рС) — фгде ф'' определяется по формуле (5.3).

Следствие. Если Мах в (2.2) понимается в смысле ">" и РФ\ ф2 6 Ф* : ф] < ф] Vi = ТД : Ф1 + Ф! > О, то

Ф* = U Ш-

Íi6 м

Утверждение 6.2. Справедливо равенство ф{ц) = B(fl)¡l.

Следствие. Справедливо равенство

в(ц) = min max min ц~1 ip¡(г, w). (6.2)

шеи' z£Z(w) te/(/j)

Таким образом, V/í 6 М в(ц) можно находить, решая од-нокритериальную задачу поиска минимакса

^ 512х 9 - ft'Pii2,™) Vi G I(n)}.

«ей7 ze^(tu)

Утверждение 6.3. Если выполнено условие (5.1), то отображение ф([1) непрерывно в любой точке множества М.

Использование 0J1C позволяет построить аппроксимацию множества Ф* конечными множествами в метрике Хаусдорфа.

Утверждение 6.5. Пусть выполнено условие (5.1) и Мах в (2.2) понимается в смысле ">". Тогда для любого е > 0 найдется такое положительное число S, что для любой ¿-сети Ме С М множество У ф** образует е-сеть в Ф*.

iteMs

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

Предположим теперь, что множество Ф<[ТУ] является многогранником. Это условие выполняется, в частности, при решении сетевых задач. Покажем как можно получить ряд точек ф(р), не решая соответствующей задачи оптимизации.

Пусть в узлах /л1,...,// найдены 9к = в(цк) и построены ф([1к) для к = Обозначим через А' — симплекс в Н/.

5

Для любого А € Л' определим /¿(Л) = ^ \кцк,

*=1

= (6.4)

к-1 к=1

При определенных условиях формула (6.4) определяет точки ф{ц{А)), т.е.

ф{ А) = ф(ц( А)) =

Утверждение 6.6. Пусть Ф<[Ж] — многогранник, /х* 6 М, фк = ф(^к), Ок = #0"*) (к = 1,...,з). Если существует А0 е Л", А0 > 0, для которого

ош°))=(±тг\ (6.5)

то ф(А) = ф(ц{А)) для любого А 6 Л4.

Итак, зная ф? , можно, при выполнении условия (6.5), получить ф* при любом ¡1 е СОПу{[1Х,

Утверждение 6.7. Существуют многогранники Л,, ...,А*Ь, такие что

1=1

2) (ИтА1 = - 1;

3) относительные внутренности многогранников попарно не пересекаются: гг'Л*, Г) Л*„ = 0 для любых V ^ I";

4) для любых С Л* выполнено условие (6.5) при всех векторах АЧ Л3 : А0 > 0.

Утверждения 6.6 и 6.7 позволяют сократить число решаемых оптимизационных задач при аппроксимации множества Ф* и применять алгоритмы, разработанные Смирновым М.М.

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

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

В §7 показано, как результаты, полученные в предыдущих параграфах, могут быть использованы для решения задачи анализа уязвимости МП-сети.

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

1. Воробейчикова O.A. Аппроксимация векторного мини-макса со связанными ограничениями // Вестн. МГУ. Вычисл. матем. и кибернетика, 1998. N 2. С. 29-31.

2. Воробейчикова O.A., Малашенко Ю.Е., Новикова Н.М. Одна игра типа Г\ с вектор-функцией выигрыша / Сборник трудов 1-й Московской международной конференции по исследованию операций. М.: ВЦ РАН, 1996. С. 26-32.

3. Воробейчикова O.A., Новикова H.Mi Векторный мини-макс со связанными ограничениями // Вестн. МГУ. Вычисл. матем. и кибернетика, 1996. N 4. С. 45-48.

4. Воробейчикова O.A., Новикова Н.М. Параметризация значения векторного минимакса со связанными ограничениями // ЖВМ и МФ, 1997. Т.37. N.12. С. 1467-1477.

5. Воробейчикова O.A., Новикова Н.М. Метод сверток в задаче поиска векторного максимина // Вестн. МГУ. Вычисл. матем. и кибернетика, 1998. N 1. С. 24-26.

6. Malashenko Y.E., Novikova N.M., Vorobeichikova O.A. A game Гг with vector-function of pay-off / Сборник трудов 1-й Московской международной конференции по исследованию операций. М.: ВЦ РАН, 1996. С. 139-145.

7. Malashenko Y.E., Novikova N.M., Vorobeichikova O.A. Game theory approach to multicommodity flow network vulnerability analysis / Causal Models and Intelligent Data Management. New York - London - Berlin: Springer-Verlag, 1998. P. 101-109.

8. Novikova N.M., Smirnov M.M., Vorobeichikova O.A. Approximation techniques for linear multicriterial optimization and games / Symposium über Operations Research (SOR97). Jena: Friedrich-Shiller-Universitat, 1997. P. 116.

9. Vorobeichikova O.A., Novikova N.M. Multicriterial minimax with dependent variables / Multiple Criteria and Game Problems under Uncertainty. Moscow - Orekhovo-Zuevo, 1996. P. 130.