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

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

(.4 ."'О

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

СМИРНОВ Михаил Михайлович

УДК 519.8

МЕТОДЫ АППРОКСИМАЦИИ МНОЖЕСТВА ПАРЕТО, ОСНОВАННЫЕ НА ОБРАТНОЙ ЛОГИЧЕСКОЙ СВЕРТКЕ, И ИХ ИСПОЛЬЗОВАНИЕ В СЕТЕВОЙ ОПТИМИЗАЦИИ

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

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

Москва - 1996

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

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

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

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

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

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

Институт высокопроизводительных вычислительных систем РАН.

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

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

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

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

Защита диссертации состоится

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

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

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

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

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

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

Научная новизна. Для аппроксимации множества Парето используется обратная логическая свертка (OJIC):

= min{у,-/А,-}.

|:Л,->0

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

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

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

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

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

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

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

Введем основные определения и обозначения. Пусть задано непустое множество X С В." (множество решений или стратегий), на котором определена вектор-функция / : X —> Ш" (векторный критерий). Множество У = /(X) = {/(г)|г £ А*} будем называть множеством оценок. Будем считать, что каждое решение х Е X полностью характеризуется своей векторной оценкой /(х) и каждый частный критерий /,•(«) желательно максимизировать.

Определение. Оценка у0 6 У называется оптимальной по Паре-то (Парето-оптималъной, эффективной), если не существует оценки у £ У \ {у0} такой, что у,- > у? сразу для всех г = 1 ,...,т. Соответствующая точка х° 6 X, для которой /(ж°) = у0, называется оптимальным по Парето (Парегпо-оптимальным, эффективным) решением.

Множество всех оптимальных по Парето оценок будем обозначать P(Y) и называть множеством Парето или эффективным, множеством. Множество оптимальных по Парето решений будем обозначать Pf(X).

Будем предполагать, что множество У — компакт. Данное условие фигурирует в работе как условие (*) и гарантирует непустоту множеств P[Y) и Pj(X). Условие (*) заведомо выполнено, если X — компакт в Rn, a /¿ — непрерывные функции на X (i = 1,..., т), либо если X — полиэдр в R" (возможно неограниченный), а /,- — ограниченные на X линейные функции.

Потребуем, чтобы У П intR™ = У (условие (**))• Это условие будет выполнено, если все частные критерии строго положительны на X. Если X —выпуклое множество, а /,- — непрерывные вогнутые на X функции, то условие (**) эквивалентно требованию, чтобы среди функций fi не было тождественно равных нулю, что в свою очередь эквивалентно условию Слейтера: найдется такая точка i £ X, что fi(i) > 0 для любого i = 1,..., т.

В главе 1 исследуются вопросы параметризации и аппроксимации множества Парето при помощи обратной логической свертки (ОЛС):

т

Ф{у, А) = min {у,/Аi}, где А 6 Am = {А £ Rm|A,- > 0,У>,- = 1},

t=l

а у Е У. В тех случаях, когда размерность симплекса будет ясна, индекс m будем опускать и вместо Ат использовать обозначение Л.

В §1.2 исследуются свойства функции максимума OJIC

Г (А) =ГтахФ(у,А) = тахФ(Дх), А),

y£Y х£Х

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

т

Утверждение 1.1. max0*(A) = <г* =f max Y^/i(x).

дел v ' xíx f—'

i=i

Утверждение 1.2. Функция 9* (А) непрерывна на Л.

Обозначим 0* =f min0*(A). Если выполнено условие (**), то

А£Л

9, > 0. В выпуклом случае значение в« легко может быть вычислено.

Утверждение 1.3. Пусть X — выпуклое множество, — вогнуты на X (i = 1,..., т). Тогда 9» = тттах/;(ж).

Утверждение 1.4. Пусть У с int R+. Тогда 0*(А) удовлетворяет условию Липшица на Л с константой L$ = а*/d, где

В выпуклом случае в* (А) будет липшицевой и без предположения о строгой положительности /¡(ж).

Утверждение 1.5. Пусть X —■ выпуклое множество, /,(г) — вогнуты на X (i = l,...,m). Тогда 9*(Л) удовлетворяет условию

Липшица с константой Lj = er*||urnaxl|, где u!-nax =-, . ..

max/,(ж) xex 4 '

В §1.3 задача построения множества Парето сведена к параметрической задаче однокритериальной оптимизации. Показано, что множество Парето может быть параметризовано как объединение множеств максимумов ОЛС.

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

def

вать сумму критериев на множестве Х*(А) = {х £ X \ Ф(/(х), А) = 0*(А)}. Обозначим

m т

Х?(А) = Arg max о"*(А) = max

i=i t=i

Утверждение 1.7. P3{X) = |J X0*(A); Р(У) = [j {f(x*0(X))},

дел дел

где Zq(A) — произвольная точка из Xq (А).

Отметим, что для определения нужно решить двухэтап-

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

Определение. Оценку у0 £ Р(У) будем называть регулярной с константой регулярности с > 0, если для любого у £ У справедливо

неравенство

m

min{t/i < -c£> - у?).

' 1=1

Множество Парето P(Y) будем называть равномерно регулярным с константой с > 0, если каждая оценка у £ Р(У) регулярна с константой с.

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

В регулярном случае вместо Х£ (А) для представления множества Парето можно использовать

Х;(А) d= Arg тахФ„(/(х), А), где

х£Л

т т

Vy € У ф«(у, А) = ф(у, А) + а у; т = min {Ш/\{} + а Y>.

1=1 t = l Максимальное значение Фа(/(а;), А) на X будем обозначать

0;(А)^тахФа(Я*),А).

Утверждение 1.8. Пусть множество P(Y) равномерно регулярно с константой с > 0. Тогда для любого а £ (0, с) справедливы представления: Pj{X) = (J Х*(Х), P(Y) = |J {f(x'a(А))}, где ж* (А)

лел дел

— произвольная точка из X* (А).

Итак, решив задачу максимизации OJIC для всех значений параметра А £ Л, можно найти все множество Парето. IIa практике приходится ограничиваться лишь конечным числом точек из некоторой ¿-сети As С Л. Более того, в нелинейном случае точное решение задачи максимизации свертки, как правило, найти не удается.

Будем говорить, что задача максимизации свертки Фа(у, А) решена с точностью Д > 0, если получена точка из множества

' = {* е х I ф„(/(г), А) > ^(Л) - Д}.

Аналогично, точки множества

ХД(А) = {х е X I ф(/(х), А) > 0*(А) - Д}

будем называть Д-решениями задачи максимизации Ф(у, А). В §1.4 приведены условия, при которых множество точек решений (или Д-решений) задач максимизации ОЛС для набора параметров из некоторой 6-ссти Аб С А аппроксимирует множество Р(У) с заданной точностью.

Центральным результатом главы 1 может считаться Теорема 1.11. Пусть функция О" (А) удовлетворяет условию Липшица на А с константой Ь$, а множество Р(У) равномерно регулярно с константой с > О, А{ — произвольная ¿-сеть в А (5 > 0), 0 < а < с, а — произвольная точка из Х„(Х). И пусть выпол-

нены неравенства

Д/а<е и + (1 + а)Хе)5 + Д) < е.

с — а

Тогда расстояние по Хаусдорфу к(Р(У), (А))}) < е.

абл«

Для, вообще говоря, нерегулярного случая справедлива Теорема 1.12. Для любого е > 0 найдутся такие числа 6 > 0, а > 0 и Д > 0, что для любой 5-сети Л8сЛи любых точек х£(А) £ Х£(Л) справедливо неравенство Л(Р(У), (А))}) < е.

ЛбЛ

Таким образом, используя ОЛС, можно аппроксимировать множество Парето в метрике Хаусдорфа с любой наперед заданной точностью, если только величины а, 6 и А/а достаточно малы. В регулярном случае можно оценить зависимость между указанными параметрами и точностью аппроксимации е. Отметим, что если функция О* (А) удовлетворяет условию Липшица (для чего достаточно строгой

положительности всех критериев), множество Р(У) равномерно регулярно, а задача максимизации свертки решается точно, то между ей 8 есть линейная связь.

Теоремы 1.11 и 1.12 останутся справедливы если множество Лд С Л будет ¿-сетью не для всего симплекса А, а лишь для множества

л* = {А = у/Ею1»еР(У)}.

В главе 2 более подробно исследован линейный случай. Будем предполагать, что множество допустимых решений X — полиэдр: X — {г € К" | Ах < Ь), а все частные критерии — линейные функции: /(ж) = Сх. Отметим следующую особенность линейного случая. Известно, что при достаточно малом а > 0 справедливо равенство Х*(А) = А'о(А). Оказывается, что указанное равенство имеет место равномерно по А £ А (ТЕОРЕМА 2.3). Этот факт позволяет всюду в рассуждениях использовать множества Хд (А) (более удобные с теоретической точки зрения), а при практическом использовании изложенных методов заменять их на X* (А) (более удобные для вычислений) при достаточно малом а > 0.

В §2.1 предложен метод продолжения решения Хд(А) £ Ар (А) по параметру А 6 Л. Пусть А(г) = А0 где А0 £ Л, ||Л|| = 1, < £ Л, и Т > 0 таковы, что А(^) £ Л для любого t £ [0,Т].

ЛЕММА 2.1. Найдется такое число 70, что для всех достаточно малых 4 > 0 имеет место равенство 9*(А(<)) = 9* (А°)/(1 +

Пусть Ь > 0 — достаточно мало, а точки х° £ Ад (А0) и ж1 £ А5(А(4х)) достаточно близки друг к другу (все неактивные ограничения для х° остаются таковыми и для х1). Зная £?*(А°) и 0*(А(<1)), можно определить

70 ¿1

а значит, и функцию 9(1) = 0*(А°)/(1 + 70^) при всех Ь > 0, для которых 1 + 7о< > 0. Обозначим

Теорема 2.2. 1. Найдется такое число £* > <ь что а) х(г) в X для всех * £ [0,«*],

б) Ф(/(ж(4)), А(*)) = 6(1,) для всех < £ [О,Г].

2. Точка х(Ь) принадлежит множеству при всех t > О,

для которых а:(*) £ X и Ф(/(ж(г)), Д(¿)) = 0(*).

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

Пусть А* и А*+1 — соседние узлы ¿-сети Ас, и пусть хк £ Х^(Хк), хк+1 £ Х5(А*+1) — решения соответствующих задач. Обозначим вк = Ф(/(г*), А*), 0*+1 = Ф(1(хк+1),Хк+1). Положим

\к+1 _ \к

Если на прямой, соединяющей узлы А* и А*+1, имеются еще узлы А*+' = А* + £/Л,, то можно попытаться найти хк+1 £ Хц (А*+|) при <1 > ¿1, не решая задач максимизации свертки. Для этого нужно найти уо и в точках вычислить х(/;) и #(£/). Если оказалось так, что в(<|) £ X, а Ф(/(в(«|)), А*+') = 0(*,), то £ Х£(А*+|) и в узле А*+' решать задачу оптимизации не нужно.

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

1) Если шаг по сетке достаточно мал, то и полученные решения хк и хк+1 скорее всего окажутся близкими друг к другу. В методе §2.1 через эти две точки проводится прямая и в качестве решений подбираются точки, лежащие вне отрезка [хк, хк+1]. Следует ожидать, что данный метод окажется неустойчивым к ошибкам округления. Хотелось бы, чтобы продолжение решения осуществлялось вовнутрь.

2) Сокращение перебора достигается тем, что удается отбросить некоторые отрезки в симплексе Л. Хотелось бы уметь выбрасывать участки большей размерности.

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

Следующие два результата, полученные в §2.2, являются основой для построенных в работе методов.

Утверждение 2.4. Функция 1/9*(Х) — выпуклая и кусочно-линейная на Л.

Утверждение 2.5. На множестве функция <г*(А)/0*(А) —вогнутая кусочно-линейная.

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

В §2.4 предложен метод продолжения решения задачи максимизации OJIC внутрь многогранника произвольной размерности. Пусть в узлах А1,..., А* построены хк £ Хд(Ак) для к — 1,..., s. Обозначим Qk — в*(\к) и для любого ц Е Л" определим

(2.18) = Eg**-

к — 1 \к—1 / к.—1

Теорема 2.10. Если существует £ Л*, fi° > 0, для которого

(2.19) х(»°) £ Х0*(А(/)) и Г(А(М°)) = ^ &

то x(ji) £ Xq (A(/i)) для любого ¡i £ А".

Итак, зная хк £ Хд(А*), можно, при выполнении условий (2.19), получить х* £ Xq(A) при любом А £ cont^A1,..., А*}. Следующий результат дает ответ на вопрос, как часто может возникнуть такая благоприятная ситуация.

Теорема 2.11. Существуют многогранники такие,

что

L

1)УЛГ=Лт;

2) dim Л,* = 771 — 1;

3) относительные внутренности многогранников попарно не пересекаются: rtAJ1, П riA.*v, = 0 для любых V ф I".

4) для любых {Afc}jb=1 С Л* и любых хк £ выполнены условия (2.19) при любом векторе /i° £ Л4,

ц° > 0.

Теоремы 2.10 и 2.11 позволяют сократить число решаемых оптимизационных задач при аппроксимации множества Парето. Действительно, пусть многогранники IJi,..., Рм покрывают симплекс Л™. Если многогранник Рг целиком лежит в одном из Л* при некотором I £ {1,..., L}, то для его вершин (согласно теореме 2.11) будут выполнены условия (2.19), что позволяет (по теореме 2.10) находить *5(А) Е Х*0(\) (при A G Рг), не решая соответствующей задачи. Обозначим через Q объединение всех таких многогранников. Если для вершин многогранника Рг не выполнены условия (2.19), то этот многогранник по крайней мере пересекается с границей одного из Л*. Пусть R — объединение всех таких многогранников. Так как (т — 1)-мера границы любого Af (I — 1,..., L) равна нулю, то при достаточно малых диаметрах множеств Рг малой окажется и мера R. А это, в свою очередь, означает, что при малом 6 > 0 лишь незначительная доля узлов ¿-сети на Ат (более или менее равномерной) попадет в R. Для остальных узлов ¿-сети А (принадлежащих Q) точки Xq(A) £ Хо(А) можно будет определить по формуле (2.18). В работе приводится алгоритм построения множеств Pi,..., Рлг-

Как следует из теоремы 2.11, целесообразно организовать дробление исходного симплекса Лт так, чтобы границы между участками линейности функций 1/0*(А) и <т*(А)/б*(А) оказывались бы и границами между получаемыми многранниками. В §2.5 описан алгоритм, позволяющий разбить многогранник определения выпуклой кусочно-линейной функции на многогранники ее линейности, используя лишь информацию о значениях функции в конечном числе точек. Этот алгоритм позволяет за конечное число шагов в точности построить множество Парето линейной многокритериальной задачи в виде объединения конечного числа многогранников.

В главе 3 рассмотрена следующая модель многопродуктовой сети. Пусть задан некоторый граф G = (N,A), где N — {ui,..., ип} — множество вершин, а А = {гх,..., га} — множество ребер. Граф G в дальнейшем будет называться графом сети. Также пусть имеется набор тяготеющих пар вершин М = {Pb---,Pm} С N х N, где pi = (vSi, vti). Вершины va; и vt% будем называть соответственно источником и стоком г-го продукта. Многопродуктовой сетью S будем называть пару (G, М).

Потоком г-го продукта по сети 5 от источника и5; к стоку г>4, будем называть множество неотрицательных чисел хц 0' = 1,..., 2а), удовлетворяющих следующим ограничениям

(3.1) £ хц - £ хц-*<„*,- = О Чье^

з^ь) ¿6т(»)

5(и) = {з I г, = (и, и') е А, V < и'} и {«+ 3 I г; = (и, и') £ А, V > у'}, Т(и) = {a + j | г,- = (у, ь') Е А, V < и'} | г,- = (ь,и') € А, V > V1}, а <5,-„ = 1, если V = V,., = —1, если V = vti, и ¡5а-„ = 0, если » £ {»и. "!.■}•

Первая сумма в (3.1) имеет смысл потока ¿-го продукта, выходящего из вершины V, а вторая — суммарного потока г-го продукта, входящего в и. Неотрицательное число г,-, фигурирующее в (3.1), будем называть величиной потока ¿-го продукта.

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

Будем предполагать, что пропускная способность каждого ребра г к € А ограничена неотрицательным числом (¡¡с. Это ограничение запишется в виде

Сеть 5 с ограничением на пропускную способность ребер будем обозначать Я((1). Если многопродуктовый поток х удовлетворяет ограничению (3.2), соответствующий вектор г(х) будем называть допустимым или достижимым в сети Множество всех векто-

ров 2, достижимых в сети будем обозначать

Естественным обобщением задачи о максимальном (однопродук-товом) потоке в сети является задача максимизации МП-потока 2 Е Я{<1). Очевидно, что задача о максимальном многопродуктовом потоке — линейная многокритериальная задача.

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

т

(3.2)

пар, причем поток величины / недостижим в сети S. Задачу оптимального (неизбыточного) синтеза МП-сети поставим как задачу многокритериальной минимизации вектора Д добавленной на ребрах графа сети пропускной способности при ограничениях / 6 Z(d + А).

Третьей многокритериальной сетевой задачей, рассмотренной в работе, является задача анализа живучести многопродуктовой сети. Предположим, что сеть 5(d) может быть подвергнута внешнему воздействию (удару), способному нанести частичные разрушения так, что в результате останется сеть S[y), где 0 < у < d. Пусть множество возможных воздействий У известно. Будем предполагать, что У — компакт. Обозначим Zr = Z(y) и поставим задачу много-

»6 Y

критериальной максимизации z £ Zt — задачу анализа живучести МП сети.

В параграфе §3.2 получены оценки констант регулярности для задачи о максимальном МП-потоке и задачи развития. Теорема 3.2.

1) В задаче о максимальном многопродуктовом потоке множество Парето равномерно регулярно с константой (т — 1) ■ 3 3

2) В задаче развития сети множество Иарето-минимальных оце-

— 1 _ n(w—1)

нок равномерно регулярно с константой (а — 1) • 3 3

Отметим одну важную особенность задачи максимизации многопродуктового потока. Легко видеть, что если поток 2° достижим в сети S, то и любой поток z € R!j?, меньший z°, также достижим в сети S. Для таких задач многогранникам Л* из главы 2 можно придать следующий наглядный смысл.

А именно, вернемся к линейной многокритериальной задаче

у — Сх > Мах, Ах <Ь

Дополнительно потребуем, чтобы для любого у0 £ У и у > 0, у < у0 выполнялось включение у £ У. В таком случае справедливы

Теорема 3.7. Многогранников линейности у функции 1/0*(А) на Л.ровно столько, сколько максимальных слейтеровских граней имеет множество S(Y).

Теорема 3.9. Пусть F — максимальная слейтеровская грань множества У. Тогда участок линейности 1/0*(А), отвечающий

грани F, содержит столько многогранников линейности функции а*(\)/9* (А), сколько максимальных паретовских граней имеет множество F.

Таким образом, число многогранников Лj для подобных задач зависит только от структуры множества P(Y). Чем проще устроено множество P(Y), тем меньше будет множеств Л, и тем выше будет эффективность предложенных в главе 2 алгоритмов.

В §2.4 более подробно исследована задача анализа живучести МП-сети. Для любого А £ Лт определим

0Г(А) =f max Ф(г, А) = max min {г,/А,}, а для любых А £ Лт и у £ У положим

0*(А;у) =f max Ф(.г,А) = max min {z,/A.).

Утверждение 3.10. Для любого А £ Л справедливо равенство 0г(А) = гшпГ(А;г/).

y€Y

Утверждение 3.11. Функция 1/0г(А) — выпуклая кусочно-линейная.

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

В главе 4 алгоритмы, построенные в главе 2 для линейного случая, перенесены на выпуклый (нелинейный) случай. Если множество X выпукло, а функции fi{x) вогнуты на X, то отдельные участки множества P(Y) могут оказаться весьма близкими к линейным. Этот факт позволяет надеяться на существенное сокращение числа решаемых задач максимизации OJIC. Попутно доказано, что функция 1/0*(А) выпукла на Л.

Теорема 4.2. Пусть А* £ Л, хк £ X, 9к = Ф(/(хк),\к) и при этом Ok > б*(А*)(1 — 6) > 0 для любого к — 1 ,...,s. И пусть при некотором /i° £ A', ft0 >0 выполнено

-1

Ol

(4-3) ХтЧ >*W))(1-*).

Тогда для любого /i g Л* справедливо

1)0*(Л(/х))(1-(7(/Лм)«)<

» о

шш W 0Е#

C(jt,ft) =-5-Ï-;

min -—7г > —

2) для величины C(ft°,n) верна оценка

m 0 / О

Обсудим те возможности сокращения числа решаемых задач оптимизации, которые предоставляет использование теоремы 4.2. Пусть в вершинах А1,...^* некоторого многогранника с относительной точностью S решена задача максимизации свертки Ф. Выберем произвольную "контрольную точку" А0 = A(/i°) G ri conv{Xï,А*} и проверим условие (4.3) теоремы. Если оно выполнено, то формула (4.2) дает решение задачи максимизации свертки во всех точках данного многогранника с относительной точностью 5C(/i°,/i) < <5Ci(/j°). Так как решение задачи максимизации OJIC с относительной точностью Д является решением этой задачи с абсолютной точностью <т* А, то построенные точки могут быть использованы для аппроксимации множества Парето в соответствии с результатами главы 1.

Выпишем Ci(/i°) для двух конкретных случаев выбора контрольной точки A(/î°).

Следствие 1. Пусть $ = 1 /s. Тогда

aof) - ayfc ç i S 1 + (. - S jéïé-

Следствие 2. Пусть fi0k = h/Y,; к- Тогда Ci(/i°) = s.

Отметим, что для любого /л0, удовлетворяющего условиям теоремы 4.2, > е. Поэтому выбор контрольной точки в соответствии со следствием 2 является, в известном смысле, оптимальным. С другой стороны, выбор контрольной точки по следствию 1 дает возможность решать задачу оптимизации исключительно в заранее намеченных точках симплекса Лт.

Как указывалось выше, для аппроксимации множества Парето Р(У) при помощи ОЛС достаточно решить задачу максимизации свертки лишь в узлах ¿-сети на множестве А*, которое заранее не известно, но которое обычно значительно уже чем стандартный симплекс Ат. В §4.2 эта идея применена для многокритериальных задач с сильно вогнутыми частными критериями.

Будем предполагать, что все критерии /¿(х) ограничены сверху константой Д сильно вогнуты на выпуклом компакте X с константой I и удовлетворяют на X условию Липшица с константой Ь.

Теорема 4.3. Пусть А* 6 А*, а А 6 А — произвольная точка из единичного симплекса, для которой ||А — А*|| < ¿ при некотором 5 > 0. И пусть точка хА Е X такова, что Ф(/(гд), А) > 0*(А)(1 - Д). Тогда для любого I = 1,... ,т справедливо неравенство

/,(а:д)<Ф(/(хл),А)А, +е + Хд/2^7/, где е = (<г* + Ьв)8 + ^дА.

При аппроксимации множества Парето теорема 4.3 может быть использована следующим образом. Пусть в некоторой точке А0 £ Л с относительной точностью Д решена задача максимизации ОЛС (т.е. построена соответствующая точка гл). Если шар радиуса г > 0 с центром в А0 содержит хотя бы одну точку множества А*, то по теореме 4.3 для любого £ = 1,..., т будет справедливо неравенство

Л(*Л) <

< Ф(/(*д), А°)Л? + («т*+Хв)'-+((«г* + ь9)г+ //.

Если же при некотором г имеет место обратное неравенство, то указанный шар не содержит точек множества Л*, и значит, все узлы ¿-сети, оказавшиеся в этом шаре, могут быть удалены: решать задачу максимизации ОЛС в них не нужно.

В §4.3 на основе теорем 4.2 и 4.3 описан метод ветвей и границ для решения параметрического семейства задач максимизации ОЛС.

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

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

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

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

4. Для многопродуктовых сетевых задач получена оценка константы регулярности эффективного множества, оценено количество многогранников линейности функции максимума ОЛС.

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

1. Давидсон М.Р., Малашенко Ю.Е., Новикова Н.М., Смирнов М.М., Строгая Г.В. Математические постановки задачи восстановления и обеспечения живучести для многопродуктовых сетей. М.: ВЦ РАН, 1993.

2. Смирнов М.М. О задаче "справедливого" развития многопродуктовых сетей // Ж. вычисл. матем. и матем. физики, 1995, т. 35, N 2, с. 211—222.

3. Смирнов М.М. Обратная логическая свертка в векторной оптимизации, Сборник трудов 1-й Московской международной конференции по исследованию операций, М.: ВЦ РАН, 1996, с.91—93.

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

5. Смирнов М.М. Методы аппроксимации граней множества Парето в линейной многокритериальной задаче // Вестник МГУ, сер. 15, вычислительная математика и кибернетика, 1996, N 3, с. 37—43.

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