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

министерство народного образования

' азербайджанской республики бакинский государственный университет

ии. м. а. расулзаде

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

ГАСЬШОВ РАФАИЛ НАИБ оглы

"УДК 5 ¡3.8

ДВОЙСТВЕННОСТЬ В НЕВЫПУКЛЫХ ЗАДАЧАХ ОПТИМИЗАЦИИ

01.01. 09 — математическая кибернетика

автореферат

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

БАКУ - 1992

Работа выполнена в Бакинском Государственном Университете им. Л1. А. Расул-заде.

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

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

А. Я. АЗИМОВ

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

— д. ф. м. н., профессор Рубинов А. М.

— к. ф. м. н. Гусейнов X. Г.

Ведущая организация: Азербайджанская Государственная

Нефтяная Академия

Защита состоится « Х9 > ЪисаорА . 1992 г. в 14. 00 чесов на заседании Специализированного совета К 004.21.02 по присуждению ученой степени кандидата физико-математических наук при Институте Кибернетики АН Азербайджанской Республики по адресу: 370141, г. Баку, ул. Ф. Агаева, кв. 553, дом 9.

С диссертацией можно ознакомиться в библиотеке Института Кибернетики АН Азербайджанской Республики.

Автореферат разослан <Л>4 * . . . 1992 г.

Ученый сехретарь Специализированного совета, к. ф. м. и.

А. М. БАГИРОВ

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

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

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

т

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

Б работах Л.ГурЕИца, В.ДЛ!огила,В.В.Подиновс.1сого,А.Я.Азимова, Х.КаЕасаки,Т.Танино,Й.Яна развита теорлл двойствен; юсти .для выпуклых многокритериальных задач.

Однако,во многих моделях неизбеено возникают невыпуклостя,что делает со?!нительши пригодность стандартных подходов к изучению двойственности в таких задачах. 15 не случайно, что различные авторы при рассштрянии отдельных классов невотухлнх задач ислолъ-

зуэтг различные методы.

Б обоих работах Р.РокафелларД.Гонен.М.Авриел. М.Иину при исследовании незыпуклнх задач математического пвдграмг-мрок^т-^ддя изучения двойственности используют модифицированные функции Лаг-ранаа.

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

Изучению двойственности в выпуклых задачах оптимизации по конусу, с применением метода возмущений посвящены работы Азимош [1J, Кавасаки С2],Танино и Савараги СЗ], в которых различными путями вводятся понятия субдифференщшла и первого и второго сопряжен-них многозначных отображений. В настоящей диссертации при изучении ДЕОйстЕенности в невыпуклых задачах оптимизации по конусу использованы идеи работы И].

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

ГП Азимов А.Я. Двойственность многокритериальных задач.- Мате-м.-пт.ччский сборник. 1985,131,М2,с.Б1Э-535.

Сй] Kawa.-.-akl Н. Duality Theorem in Multlobjective Nonlinear F-ruiTraming.- Mathenatl со' Oper.Res. ¡9G2,V.7,S1, p.95-11.

ГЗ] Tonino T.,Sasaragi Y. Conjugate Maps and Duality in Multi-objective Optimisation.- JOTA, 1980,31,p.473-499.

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

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

Характеризадая свойств минимальных и 'максимальных - .элементов множеств в частично упорядоченных пространствах часто опираются на теоремы отделимости. Отсутствие соответствующих теорем отделимости для невкпуклых множеств, по-видимому является одной из

трудностей на пути развития теории двойственности'для невыпуклых

1 . .

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

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

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

1) введено новое определение субдифференциал;.!, являющееся расширением классического, определения этого понятия;

' 2) получены достаточные условия субдифференцируемосги как для скалярнозначннх функций,так и для многозначных отображений;

3) доказана корена -отделимости для ношгуклнх множеств,гда в

качестве отделяющей функция используется ■ выпуклая монотонная функция;

4} установлены необходимые и достаточные услокп для слабо и собственно минимальных точек невыпуклых подмножеств частично упорядоченных пространств;

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

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

7) в каждом ель-чае (т.е. в - однокритериальвом и многокритериальном случаях) .юстроена функция Лагранаа и получены необходимые и достаточнее условия для рещений(эффективных решений) основной тл двойственной задач-в форме существования седловой точки функции Лаг ранка. ' • - ■

Полученные результаты применены для построения двойственных задач и доказательства теорем двойственности для некоторых клас-ор. невжуклнх задач.Ковне двойственные соотношения получены также для классов выпуклых задач оптимизации по-конусу с ограничениями в в ад« включений к дискретных вшючениЛ, для линейных многокритериальных задач с ограничениями в форме равенств и нера-венстз.Ьняымка возмсхность применения теории двойственности для 1'.зу41!Н1я с-и^аиин равновесия в конкурентной якотшке.

1 ■С:'?, ме-точика исследования. В работе т оркя двойстезнности с-поотч-ь нг, основа. метода возмущений.Примвгшются теории функционального анализа,выпуклого анализа, негладкого анализа и много-

критериальной оптимизации.

Апробация рзбогн. Основные результата диссертации докладывались на семинарах кафедры исследования операция и математического моделирования БГУ им.М. А.Расулзаде,на международной школе-се-шгаре по методам оптимизации и их прилояенням (Иркутск,1989),но {VII школе-семинаре по математическому моделированию в проблемах национального природопользование Ростов-на-ДонуЛ 990).

Публикации.По теме диссертации опубликовано восемь работ,спи-;ок которых приведен в конце автореферата.

Структура и объем таботц.Диссертация состоит из введения,трех "•лав и списка .га .'ературн, включающего 79 наименований. Объем работа составляет 141 страниц машинописного текста.

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

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

В главе! развита теог«ш двойственности для невкпуклых сдио-сритериа льнах задач. ' ■

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

Пусть Х-кешественное нормированное пространство,Г- функция на ; со значениями в К,где К -Р. (!) {+<£.}.Обозначим через множество всех, вогнутых непрерившх на X функций g -гаки?.,что ¡¿\0)--0.

ОПРЕДЕЛЕНИЕ 1. Функцию 1*: определенную как

1*(г)=гл15> {г(х)-Г(х)> (1)

х>-:х

назовем сопряженной функцией к f:X-R\ Функцию определенную как

f**(x>= аир -Cg(x)-f*(g)> (2)

в€вх

назовем второй сопряженной: функцией к f:X-E.

ОПРЕДЕЛЕНИЕ 2. Элемент gtGx называется оубградиентом функции ,f:X-E в точке хеХ, если

g(x)-g(xKf(x)-i(x), VxfX. Ижжество всех субградиентов функции f в точка х называется ее субдафферегахиалом в х и обозначается di(:<). Функцию i назовем субдиффарснцируеиой в точке х€Х если <ЭГ(х)?0.

ЬРЕШЮНЕШЕ 1. а) Функция f*:G »F. - определенная соотношением (1) тап/кла и полунепрерывна снизу;

б) функция 1**:>"^Е-определенная. соотношением (2) полунепрерывна снизу;

в) f(x)>i**(x), дм любого х<Х;

г) ег.ли Of(x)i^0, то I(x)=i**(x);

д)gedt(x) тогда и только тогда,когда

f(x}+f*(g)=g<x). Следующая теорема дает достаточнее условия для субдифференци-руемости функции в смысле определений 2.

теор5ма 1. Пусть задана функция i:X-R u {-kd>. Предположим,-что Inf l(x)>-m и Т.- Липшицева в окрестности.точки хсйош i. Тогда

х€Х

функция 1 субдифференцируема в точке ¡с.

В §1.2 для осноеной задачи конструируется двойственная задача и доказывается теорема двойственности.

Пусть 1:Х«3. Рассмотрим задачу (?: Ш f(х) . <

хсх

Зга з.здача называется основной. Няшга грань в этой задаче будем обдатять Inf '? . Каждый элекент х«Х,для которого f(x)=ini. Р

ííyo.-ь ï-rfp-.T(.e ио j.-í г. í рэ гi ; i-ro s пространство,

^ссютрга <4x,0)-f<x). ^унчц/я •!> ип-

аи&гегся вояиуг^н::»?.;. cíor^yjMpoism. ¿сюйстБзякую задачу к

? в::о;1чтсг1 сцункц;:.- ^G -R:

cup íC,(x)+s2(y)-'Kx,y) IxíX.yeYK

Рпдчча

{?") sup í-í>"(0,g)}

-leo,.

гстрквгится део?срх:-«кной к ? ш otjíoejsicío к заданному гозмуцевил О (w> эдзконт укелаваег Ф^жщот.гондоатгажо равную ну.®). Бзрхшя грань в задг-'з будь?. оЗппШ'дагьоз sup У*, 2 лобоЯ элемент ясбу,длл которого -2>*(0,g)=süp 5>* будет иэзякзться рзшииен

ПРЕ;1'С::йЖД 2. • sup ?*<inf -

С^орчу.тлру^: олад^ста'условие /¡¿я фуккдя шзкуцзнкя уоловкь 1. -<& < mí im ф(х,у) < тш .

yíY

УСЛОВИЕ 2. Cy;:ec?sver окрестность ¡гудя V в Y такая.что Функ-

iru: y-ï'(i.,yï ¿йьшшега S STC;Í ОКРЕСТНОСТИ Прй ЯЕгООН фИЛ'.СИХОГЛЫ-НОМ ХСл.

ТЕОРЕМА 2. Пуст;, .jjhkí.íis гозмувдедаЗ удовлетворяет условиям í и ?.. Тогда inf?=sup?V. задяча ?* чмэйт. по кеиыкЛ мерэ одаз potra газ.

Далее в §1.2 дотжтаегся теореиз»усгяшзшчзвдзя связь к-зк-ду рзгеккяга основне'; и даойственюй sann в зид» зкогрешл?-кого соотназш'ия.С! кон: ¡.s лауэгезфа Е№;.лтся .глгтгш::;ин для ьадзчи ? доказывается кесбходетше к дисг&дашие для кгю-нЛ зэд*!ч

и ? в суде содд-заой точки лзг^гк^зча.

3. --F, определения

Ь(х,е)=-зир [б(у)-ф(х,у)3 (3)

называется лагранжианом задали Р.

ОПРЕДЕЛЕНИИ 4. Пара (х,1НХхОу называется седловой точкой Ь, если

Их,е)< Ь(х,й)< Ь(х^), Ухех,

ПРЕДЛОЖЕНИИ 3. Пусть.функция Ф удовлетворяет условиям 1 и 2. Тогда следующие условия равносильна:

а) (х.,1) есть седловая точка Ь ;

б) х есхь решение ?,1 есть ,тешение Р* и 1пГ ?=вир ?*£К.

ПР'ЭДЛСШШ 4. Пусть выполнАэтся условия 1,2. Тогда х«Х является

реиькием задачи Р в том и только том случае,когда найдется такая гсйу,что (*,£)- седловбя точка Ь,определенного соотношением (3).

12 §1.3 применятся предшествующие результата к одному важному случаю,доказываются теоремн"двойственности в невыпуклом программировании (теоремы типа Куна-Таккерэ).

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

Введенная в настоящей диссертации теория двойственности для невнпут.лнх многозначных отображений основывается на скалярных свойствах 01"гималькнх по, конузу , точек , которые з свою очередь опирьятся на теоремы отделимости невипуклых множеств.В 52.1 до-кчзнвд.'тгя теорема отделимости 'для чэвыпуюа.х множеств , которая приминается при получении необходимых и достаточных условий для '•"•ч;" .! г. ссбс/цванно эффективных точек.

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

ОПРЕДЕЛЕНИЕ 5. Функция г0:У0-К называется К -монотонной,если для всех уо,уоеУо таких,что У0>У0 выполняется яо(уо)>го(уо)• Функция go:Y0-R называется строго Ко-монотошой если соотношение ео(уо)>6осуо) выполняется для элементов- уо,уоеУо, которые удовлетворяют условию У0>У0. .,'. ',

Обозначим через 5о мнояество" всех выпуклых,Ко-конотонных и непрерывных на Всем пространстве функций ¿о, действующих из Уо на Я и таких,что 5о(0>0-. ; ' ■,

Через Со1 • будем обозначать;подмножество" штозгества Со .элементы которого являются строго К -моиотонкыми.

ОПРЕДЕЛЕНИЕ 6."Пусть А. и В произвольные непустые лодмнохестга " пространства Уо.Будем говорить,что 'функция е0:У0->В. отделяет множества А и В,если (Ь),для люби аеЛ/ЬсВ.'.'

ТЕОРЕМ 5. Пусть АсУо,ВсУо- непустйэ мнозоства такие,"что' А-К выпукло и Ш(А--Со)п Б=0. Тогда существует Функция е0"€бо отделя-кнцая множества А-Ко'и В. .•

ОПРЕДЕЛЕНИЕ 7. Пусть задано" цяоаестро Мнокества

ш1п( Ао, К0), т?-гп1п( А0, я р-т1п<А0, Ко) определенные как

п1п(Ло,Ко)={уоеАо|(А-^)п<-^М0}>,

«•-я1г.(Ло,Ко) = Суо€Ао|(Ло-уо)П (-1** Ко)=0>,

р-гп1п(Ло,Ко).={уо€Ло|сопё (Ао-уо+Ио)л (~Ко>-«)}},

где сопэ указывает замыкание конической оболочки множг :тва,называются мнокества«и,соотЕзтсавенно, га:ни!,мльнш;,слябо минимальных и'собственно минимальных точек мнонесгва '^относительно конуса К . Аналогично мохно ввести множества гаах(А0,К0), я-.тлх<ло,Ко) и р-шх(А Д )-мч:оияаль!Ш,гдабо мадс^мядьтг: я собственно какси-

К2ДЬК!!>: точек ккэкества А отноодтельно конусе К .

О О

Ti-'OPKI" 6. Пусть ГрОМЗЪОДЬПОО Hcir/C'tite MrluVOC'iEO.

:) V-'iilri у -{V ~!,Ч;!(|\ ,i. } У- TOJ.bV.O "1

* о о' с

б) ц»!нса у €jbiiin{A тогда »{ тшсс. тор-;;:, ог/л сулссг^у-вт Фунгчяп К е<; , так;::;,что г^у У,,):'",0(yJ . лхоого y„<i.„. • ft УУ.2 i;TO/ij:TOit iiOHii'iiiy суб:аг]<>о^енц'.5.'1.;и i; пую.Ч'-г'о;; до'.-га-

TCiHrio услошз cy6#'.<№iix.tiiU!pye«tocTM шот'.Пп'и"«

!iyc"b У-ижсгъенное иоркирсвшшои иро^'гр^ьс ?r:.., JH'h ¡.-.адяч.чого

МНО!\;Г;.(,аЧ!;иГО ОТ.^ГСеМЖа Ul.O. ! П: Y - У doia 1! -- {yeYiil(y)/0!-,

Ib H - U ¡Ну)

yCY

наркео«отся.соотясягтвешно,бффькгдаож мнойвстюм к образо:; ч.с.Н. СГРШШШВ 7. й.о. К: У - Y шгаеаогся «шшцешк г* икшст-

КССТК ТОЧКИ у€\'.вСЖ СУЦ^СТВУОГ OKJ.eCTHOC'1 г> К(у) ТОЧКа у Я твнса с>0 (липсщояа константа) такие,что дм fccsx у,,уг«Н(у)»;: любсго у01€Жу-,) «айдегся такой элемент уь.^Е(у?) >что

Biivvitw од'.-жцга a,: Y*G -> Ti, О*: G..*G '—.К и il**; Y*G - li

П О Н 1 О V. о

слеиу)ж»1 обрззсм:

J ini igjyj i у €К(У), если vedcaa Н, • Щу.е J = о . о _ (6)

!. т-я 5. т, протезном случае .

- sup cg(y) - yen. (?)

- cup ffriy) - it*(G,£c) i G£Gy). (35

KybFr(lUy),+K ),гд;з Pr означает гц&нииу мшксслы. о. Пусть у cIV у>: С-.-бд^ск.н^л.'ом Л: Y - Y

О о

'■'-•«s- (у,ус>) н%ысайтся иао^стет определяемое IUJK

гоъоллгъ,^о д.o.h: y - "r з точка

}r'ícüill,«сдля .:;có.-.¡ro :/г/Г(у) ^'^илал пуст.

'ГлО'РРМЛ /. íJ':'tT. л.о. ■:(: Y V чллллллго ■>■ OKÍ,':C¡::,VC'ÍÍÍ ".-yi ;7ь ¡í и ■ 'Ьл 1/c.'i'ov;'-'- " ry5,v.<. /^¡члй&фуи'3 :<• хлил y.

o

v.-Tr,LÍA,:< ) --- л ),

О О О

i'nfí л,К ' - .1' ¡,

О' ■•)- о

D-ínf(A,K ) - Р-Г-Ш-ЯВ ,К ),

о о о

нгг»КРГ.«;ГЗЯ ССОГЕ0':'СгГ.;;НИО,СЛ?0О IWÎr.'C? ЛКГ.В:,шфслл-

■и/л Л собственно иг^чмадьии ТОЛОЛ: лЛЛЛЙгС'ГЙ; À . СТЛО^ПЗЛЬКО

голу о л К .

лгл yj.e^eh'ïa упсг(у) поло-тел:

«Ujr,y0) - L«ßTi Д20«301 :S<V)-50(7C)<(S,S0)> • UO;

т.юргм s. пузаъ м.о. ii: y - ï лктгкагео з о.<гзстксоти тоте*. /•¿dorn й и "кзю я«ется условие p-vlnCIm Н,2 )?#.7огдз .ггя .'"кого p-'Ir;¿<Н( ;;) ) ллслкостго С'Н>(у,у ) опредохешгсз ссозкочзтн ;îOÎ не пусто.

3 52.3 вводятся г.сняг?я солта^эгннх геэгозю'ксг: олсЛралллши í джагкваетея теорема даойотвекност!;.

dPïïiSara^g 9. M.о. riGy-Yo íi^: GV»Y0), олрэделенкоо rsx

<*;<*)) = (yjyj 3^f.3o(G01>: го(уо>-ф,вс»

;аз;:рлетел солрл^йьгъгм отобт-лгзккеы к м.о. ?..

,г.о. а'А: Y - Y0 (H**: Y - Y }, опредзлешюо как

•aPriKïsrca влсрлд сопрл:конкач олс5рл:::слз'ем :: у. о. К.

Сл'-луллая ллос-згч гокапнгагзт/^то оллллнлл ¡i'^ív) л

■:-v.0'?'v»r.cM слкеле оцсильепт ciscy злонлнлу чн^ьест?-?. níy). л^ШО' Пусть Я: Y - Yn - т.о. л у,, do?» й. Тогза

а) у^уо для любых yodi**(y) и уо€Н(у),

б) 704у0 для любых уоеН**(у) и уо€Н(у).

Сформулируем основную теорему §2.3 - теорему двойственности шогзначных отображений.

ТЕОРЕМ 10. Пусть м.о. Б: Y - Yq субдифференцируёмо в точке уе dorn Н,тогда

тз-пш(й**(у)До) = «-Ш(Н(у),Ко), (11)

Если для любого уо€ p-Inf(H<y) ,К ) мнокество 6H>(y,yQ) определенное соотношением (10) не пусто,то. справедливы также следующие утверадения:

■ .. ' тах(Н**(у).,Ко) = p-Ini<Hiy),Ko), • . ,,{12)

иах(Н**(у),К0)_с 1пГШу),Ео) с пш(Н**(у) До) (13)

В 52.4 рассшгриЕазтся общая, невыпуклая задача-оптимизации ло. .конусу,Задача погружается в семейства Еозмущенша задач и возникающее при'этом м.о. сводит изучение-двойствености.в'задачах оп-«изадашд вопросу деойстванностк. для жогозначных отображений. Так появляется возможность примешть теорию деойстваннобти развитой в §2.3. ' '.-,/' с. " '.••."•''

Пусть X -вещественное-нормированное пространство.Задано многозначное отобракениэ Р:Х-»Уо. Рассмотрим задачу (Р) найти инфикальные,слабо инфимальше и собственно инфи-

мальше элемент инояества U F(x) .

' ' ' ■ , '

Полоим W-Inf Р =W-Inf(U Е(х),К ), Inf Р =Inf(U F(x),K ),

XÜ- ° X« • .

p-Inf Р=p-Ini(U F(x),KJ. ' •.••'-.'■

Элемент xeX,удовлетворяющий соотношению P(x)n w-Ini ■

(P(x)n Inf P/0, Jix)n i>-Inf называется слабо эффективным (эффективным;собственно эффективным)решением задачи Р.

Пусть Y- другое щдесгвенное нормированное пространство. Рас-

смотрим отображение $:Xxl-Yo такое,что $(x,0)=F(:<) для любого хеХ. Отображение Ф назовем возмущением. Введем' функции Пф:ХхУхСо-Н и fiJ-.G^G^G^R:

flniig (у)\у„€®(х,у)>, если (x,y)€dom It ® , в остальных случаях.

n®(g1,S,S0)=sup ig1(x)+g(y)-%(x,ylgo) |х€Х ,уШ (15)

Определим многозначные отобракения ff:Gy~Yo и W>:Gr~Ya следующим образом:

Шв) (^(g))={yoiYoIBgofGo(Go1):go(yo)=-i4(0,g,go)} (16) Задачи

(Р*) w-rnx U av<g) |geGy>

(?*) . шах U i\7>(S)\g^Gr} назовем двойственными к основной задаче Р по отношению'к заданному возмущению Ф.Введем обозначения w-max P*=w-max U mg)|geGy}, max P*=wax U {'^(g) lg<eGy>. Элемент g€Gy называется слабо эффективны*i (эффективным)решением задачи Р* (Р*У,еели v-пвх Р*У0 ("^(gin max Р*М.

ТЕ0РРШ1 11. Пусть xedom Р.Тогда не существует элементов Уое.ф(х,0), yc.eU{!v(g) {W>(g)), |g€Gy>удовлетворящих неравенству yo<yo (У0<У0). ,

Сформулируем следующие условия для возмущения Ф:

УСЛОВИЙ I.Существует окрестность нуля V в Y такая,что отображение у-U Ф(х,у)-лилшдгаво на V.

х€Х

УСЛОВИЕ II. Мнонество s-mln(U { U Ф(х,у)},К ) не пусто. •

уОГ хО( °

УСЛОВИЕ IJI. Множество p-mlri(U { и Ф(х,у)3,К ) не пусто.

у€Г r€X °

Введем многозначное отображение H:Y-*Yo как

К(у)~ U Ф(х,у) С7)

Тог™ с--1оз;1дно,чхо ?,

V-!::' - П' с;.' ь 1". ;-у- Тл^ ?.

^асмо слейтг/.->- утгзр.^зк;;:.:,которая гг.-.}:;

энашшак дюйстьекноП зедячк и етора» сощ№;:еш;ь::л отобрж^вв? шзгозначного отображения Н (17).

ЛТО1 1»Пусзь гашсдашгся условия I-II.Тогда

ъ~тх Р*-у -заахСВ**<0), К >, (18)

если вместо }/с.юв:ъ II шпожнязтоя более сильное услок.^ III го спрашдушо такте; следуйте соогноовназ:

ках Р*чгш(Н^{0),Ко). (19)

В § 2.4 доказана,чхо есдя о удовлетворяет условигм 1-11,то со-

ответствукцее ¡гыогозкачЕое отображение из (17) суб,о;4"слрзн»др¥- ■

■

еж з нуле,если Ф теоздэтьоряет уеловиян 1 а III, то р-ШР.-'С! и для любого у €р-1п£Р иякшшегся более склькза услодав еубдвф- , фзрешщруемости: :следовательно ш гакем щгдкенить •

'гоорзму 10 к- поучить осеошу» теорзку даойох&зтюс.ти $ 2.4... Т'Е0Р5?,:А 1?. Пусть кюкуауядаз С> удовлетворяет условиям I и II.

Тогда ' • , *

а) \р-1п£Р ч «маахР*; . . (20)

б) для .вдбого Р существует £ й такая,что

£е(0,е,6о)!; (21)

Воле ьхь^то услоийк II заполняется более- сильное уелоикь Ш, то гаргтду с ншешре'шслв1фвяай уЕБарадзнияии справедливы такке следувзю утверждения:

в) шах Р*=р~1п1 Р; (22)

г) шах РГ с ш Р с шх (?3) т.е. мшзгствэ пах Р* ьязду плотно во множестве Хш Р.

Далее,в этсь; параграфе црхсдат^я несб-ход&ше я достаточна условия дм &ФСвезли:: р&г.з»Ш: ►'З-о/.сагейг^х ¡задач Й докасйаштоя

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

В конце 5 2.4 вводится лагранжиан для задачи Р и приводятся {еобходише и достаточные условия для вффе^ившх решений задач • э и Р* в форме существования седловой точки лагранжиана при условия, что отображение ?:Х-У0, фигурирующее в постановке основной задачи Р,а такте возмущение Я: ХхУ-Уо-однозтачнне отображения.

ОПРЕДЕЛЕНИЕ 8. Функцию I:Х*От*йо-К, определяемую) соотносз-

■мем

¿и.г,г„)=-зир (г(у)-г (®(х,у))} (24)

чазовем лагранжианом задачи Р относительно заданного возмущения.

ОПРЕДЕЛЕНИЕ 9 Для заданного к.пара называется

зедловой точкой К •, • ,го) если

ь(х,г,йо)< их,ё,е0), Ухех, vg€Gy. (25)

ТЕОРЕМ 13. Пусть возмущение Ф удовлетворяет условиям I и II !1 и III).Элемент х«Х является слабо(собственно) эффективным решением задачи Р тогда и только тогда, когда существуют элементы г^бу» й0€б0 (го€Со1) такие,что пара 1.x,к) является седловой точкой функции 1(.-,-,ес) — определенной соотношением (24).При этом элемент в является слабо эффективнш решением задачи Р* (Р*) и выполняется соотношение

го(Ф(х,0)>=ь(х,г,«о> (26)

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

Пусть X и У- вещественные нормированные пространства Предлогах™,что пространство У частично упорядочено с помощью выпуклого замкнутого и острого конуса К=У, имеющего непустую внутренность.

Сформулируем следушиз условия. 31. А-непустое замкнутое выпуклое ограниченное подмножество

£2. Ро:А-Уо- однозначное лшшкцево отображение. ВЗ. ?:А-У - выпуклое однозначное отображение, имеющее замкнутей надграфик.

В4. Существует точка хек такая,что Р(х)<0.

В5. и р (х),К >¡¿0.

° °

Вб. р-1пГ( и Ро(х),Ко)?!0.

Основная задача состоит.в следующем: (Р) найти инфимальные, слабо шфимальные к собственно

инфакалыше элементы инокества О (х)1хеА, Р(х)&0}.

о —

В этом случае возмущение Ф:Х*У~Уои {+ш> принимает вид:

{Р <х), если х€А, ?(хку, ■к» , в остальных случаях.

Двойственные задачи к задаче (27) - следующие:......

(Р*) «-пш£у0€Уо|Зв0бВо:во{у0)= ках 1п1Сго(Ро(х))-г(Кх))1 (29)

(Р*) пах{уоеУо1Эго€Со1:го(уо)= шах 1пГГя0(Р0(х))-е{Р{х))] (30)

где мноаество определено соотношением (4).

Для задач (27),(29) л (30) доказываются теоремы, подобные теоремам 12 и 13.

Глава 3 посвящена изучению двойственности для конкретных классов выпуклых задач оптимизации по конусу. Мы уш отметили, что выпуклый случай подробно исследован в работах А.Я.Азимова,чьи идеи были использована при получэнйй сдо'тноаений двсйсгпенностк для невыпуклых шогокритёрвльйй задач Ь йайей -Диссертации.

В §3.1 используя понятия сус>лйффе1егаийла и сопряженных Шбг*о-значных отображений (в адос определениях су6ди#ё-г«йцй2Л состоит только из линейных непрерывных функционалов) ¿веденные А-. Я. Азимовым, получена тоорекз двойственноетц .ша ¡вшптошх Ъшогезначных

(27)

(28)

отображений,подобна теорема 10.

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

Пусть Х- линейное пространство,АсХ-выпукяое множество.Y и Y* вещественные линейные пространства,двойственные относительно канонической билинейной формы <-,->,наделенные соответственно ела- • быми o(Y,Y*) я c(Y*,Y) топологиями.Пространство Y частично упорядочено с помощью телесного выпуклого вамкнутого и острого конуса K=Y. Заданы однозначное отобрааение и многозначнее отображение P:A-Y.Отображения Ро и Р удовлетворяет условию выпуклости. ■ Рассмотрим следующую задачу:

найти инфжальныз, слабо инфимальше и собственно

(31)

инфимальнне элементы мюаестга <Fq( х) |хеА,0е^(х)^К}. Пусть К* и К* сопряженные конусы к К и ^»соответственно.Пересечете К* (int к*) с единичной сферой сопряженного пространства У* обозначим К*. (К'",)..

о o1 od

Введем функций : :

г1(х,е*,у*)=<у*,Ро(х)>-&ир{<у*,у>|у€?(х)+К}. (32)

Двойственные задачи в отом случае приобретают следующий вид:

гпах U Cy0tYol<y*,yo>=Inf ^(х.у'.у*)}, (33)

А

где у* и у*~ всевозможные элекенты такие,что у'е-К^у^К^К*^.

В & 3.3 рассматривается Енпуклая многокритериальная задача, описываемая дискретными включения;,ж.

Пусть задана однозначное отображение f:RnxR-»Yo, «ногозначкке отсбрагения t=0,..,T-1, g^R"-'^, где Уг-конечномеркое

эгклидово пространстю.д^н^выпуклов множество, t=Q,...Т, Пространство У1 частично упорядочено с помощью выпуклого тч?кнутого и

острого конуса К*.Отсбрежения f..,Т-1) ag, (t-0,...,T>

удовлетворяюг следующим условиям:для любш-и Ы10,13

1=0,...,Т-1.

Рассмотри задачу: •

найти инфиыалъныэ, слабо икфиыалышв и собственно кн^ималыше

•т .

элементы множества { £ Кг. ,1)|г„5+,/г,

1=0 г . г г г г

«г+^Ц), 1=0,;..,Т-1). (34

Если ввести обозначения

У2={1'=Гу°,у1,... .У™ ) IуЧ^.Ы),...,Т-1),

Е ггг.д;, . . - -

• 4^=1 ... ,

то задачу (34) моано представить, также з следующем виде:

найти инфиыальные,слабо инфишльвде и собственно инфкмалькуе элемента множества -ОуяЛгеЛОу с^ГхМ^Оу (34';

где 0У и 0,, указывают нули пространств У. и У, соответственно

Введем функции £г: Х*У*хУ*хУ* :

-аир {<у*,у2>11'2е?г(гЛ. (35)

В этой случае двоЯствзнше задачи сформулируются следукннк образом: .