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



Л

0%

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДШШЗ ШСТИТУТ МАТЕМАТИКИ

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

ВАТОЛИН Анатолий Анатольевич

НЕСОБСТВЕННЫЕ: ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРЛММИРОВА1Ш И МЕТОЛУ их КОРРЕКЦИИ

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

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

НОВОСИБИРСК - 1992

Работа выполнена в Институте математики и механики Ур() РАН.

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

профессор В.П.Булатов

доктор физ.-мат.наук профессор В:А.Васильев

доктор физ.-мат.наук профессор Вл.Д.Мазуров

Ведущий организация: Вичислителышй центр РАН

Защита состоится " " О к" 1992 г. в 1 6 ча-

сов на заседании сиациализ ировашюго совета Д 002.23.03 в Институте математики Сийирскрго отделения РАН по адресу: 630090, Новосибирск, Университетский проспект, 4, Институт математики СО РАН.

С двсс'фгадией ыокно ознакомиться в библиотоке Института математики СО РАН. '

Автореферат разослан

Учений секретарь оиимшлиэирошнпого совета

доктор физ.-».ат. наук

^.КОСТОЧКА

1 8т «дч ( ОЩ&Я Ха\РШТРЙ)Т1КА РАБОТЫ

,ность проблемы. Настоящая работа посвшцека исследо-

вании несобственных задач (НЗ) математического программирования

ладаодах свойством одновременной разрешимости прямой и двойственной задач и совпадения их оптимальных значений. Важнойашм проявлением несобственноста является несовместность (противоречивость) системы ограничений (прямой или двойственной) задачи, в связи с чем для названия таких задач используется также термин "противоречивая модель". В частности, несобствешость задачи линейного программирования (Ш) эквивалентна несовместности системы ограничений прямой или двойственной задачи аяи их обеих (несобственность, соответственно, 1-го, 2-го или 3-го рода).

О необходимости разработки теории и методов разенвя для несобственных моделеЗ свидетельствует как практика рзтони* разнообразных прикладах задач {экономических, технических и др.), так и причины, связанные о подробностями разпвтрл зорич (азпрскси-мация и решение несовместных свсг'вг! для пряложэгшй з ^за^йчша областях математики таких, как прабливзние фушщвй, зод'дчн ¡>:?с-познавания и идентвфгкацяи и у.д.). В чаовкопги, как пог.азтаавг ■ практика решения задач длаиировшигя и управления производством, возникновение нротяворочавнх моделей - обычная, а чаохо а хиагп-ная ситуация.

_ Среди причин, приводящих на практика к появлении НЗ - плохая формализуемость, неточность и неопределенность информации, (часто вынужденное^, чрезмерное упрощение действительных связей . и т.д. К другоЛ группе причин можно отнести ресурсный дефицит, предъявление к моделируемому объекту требований,, превосходящих его возможности или противоречивых требования, конфликтность це-

(МП), т.е. задач, но имещих решения, или, более строго, не об-

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

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

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

Изучение и использование противоречивых моделей имеет уже давнюо историю (достаточно вспомнить метод наименьших квадратов Гаусса). Систематические исследования несобственных задач, с йводенпо;,! соотгзтствущей терминология, были начаты в 1980 г.

4

И.И.Ерсмянш (и Вл. Д.Мазуровым) и его учениками (Н.Н.Астафьев, А.А.Ватолин, Л.Д.Попов, С.В.Плотииков, В.Д.Скарин, С.П.Трофи-сов, В.П.Фролов и др.). Это стимулировало исследовании в этой области другими авторами (В.А.БулавскиЙ, А.И.Верескоп, м.М.Ко-валов, П.Г.РоманиА, М.Е.Салуквадзв, А.Л.Топчишвили, Н.Б.Третьяков, к. ßcxuMgcvvt, К. , O.N. &илк* , Н. J. ОгигепЛя^ , О, L. Mangcisanian , I. Maxusciac л др.)

В настоящее время теме несобственных задач я и* приложений посвящен ряд монографий3^, обзоров, сборников статей, пять кандидатских диссертаций и две докторские - по экономическим {В.Н. ■Фролов) и техническим (П.Г.Ромаяий) наукам, Библиография работ, на эту тому насчитывает долее трехсот наименований.

В диссертации представлены важнейшие направления всслодо- • ваний по ИЗ: теория двойсгеошюсти (глава I), методы коррекции (глааы 2, 3).

Глава 4 гюсвявдпа исследованию модолоа с яеодноаиачно заданной (неопределенной, неточной, случайной, уярдйдяшзй) и^-ф«-мадией. Данное направления является акгусльиш как в связи ß приложениями, так и carso но codo, т.о. в чисто научном ллипо. Начатое в работах Ф.Вудфи, (обобкзшюе Ш) и Д.Сой-

ствр'» (неточное Ш), око в последнее врем* привлекает внимание многих отечественных и зарубежных квтороа (Б.Й.Бахкиян, Л.Г. Пли скин, В.А.Рощин, Н.В.Сеггепова, И.В.Саргиеп.'о, С.Г.Тимохин, А.В.ЫалкинДР. и др.} к

Вреыьн И,И., Мазуров Вл.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. IL: Наука,I9G3. Еремин И.И. Противоречивые модели оптимального планирования. И.: Наука, 1988.

Фролов B.II. Оптимизация плановых программ при слабо согласованных ограничениях. М.: Наука, 1986.

5

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

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

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

2. Разработка методов коррекции несовместных систем линейных уравнений и неравенств и минимаксных задач.

3. Разработка новых методов анализа и решения моделей с неоднозначно заданной информацией..

Методы исследования. Основным инструментом исследования служит аппарат выпуклого анализа и теории линейных неравенств.

Научная новизна работы состоит в следующем.

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

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

3. Осуществлено распространение схем симметрической аппроксимации и линейной коррекции НЗ на общий класс минимаксных за-

дач, зависящих от параметров.

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

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

Апробация работы. Основные результаты диссертации обсуждались на семинарах в Институте математики в 'механики УрО РАН, на научных конференциях "Методы математического программирования и программное обеспечение" (Екатеринбург, 1984, 1965, 1987, 1989 гг.), П Всесоюзной пкола-сешнаре по опттаязао,йа и ее причо-явнинм в экономике (Аииабад, 1984 г.), Каадународно»» кон^оренпли "Стохастическая оптимизация" (Кззв, 1984 г.), 19-9 Международной конференции "Математическая сяпчгглзация" (Зелдлн, ГДР, ¿967 г.), 14-й Международной конференции ¡Г[Р по сисгоуцсму моделировании и оптимизации" (Лейпциг, ГДР, 1189 г.), научной конференции "Иатематичоскоо программированию я приложения" (Екатеринбург, 1991 г.).

Публикации. По тот диссертации опубликовано 25 работ (из 1шх 7 - в соаьторство).

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

СОДЛ'ЛЕЛГЩтг РАБОТУ

До В1)с';1011и:| дастся ебяор подходов и результатов разных на-

торов ло исследованию НЗ и моделей с неоднозначно заданной информацией, излагается содержание работы по главам.

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

Основы исследований в этом направлении били зажжены И.И. .Ереминцм, а частности, юл бала предложена об-цая схема двойственности для НЗ. Смысл ее состоит в том, чгю несобственной задаче С Г1 двойственной к ной С* (^поставляются собственнее задачи X) , 23 , связанные соотношениями двойственности и выступающие в роли аппроксимирующих п отношению к С , С * :

С™-

М I М

с ——

В | I дается ткоторое развитие и конкретизация этой схемы, позволявшая выделить в явном виде моменты, связанные с аппроксимирующей ролью задач X) , X) по отношению к С , С* . Г.^я атом ашроксшация понимается в смысле одного из наиболее общих подходов, когда исходные несобственные задачи С и С* ногруиа-»лея в параметрическое семейство задач С(<?), С*(<?) , из которого осуществляется ви<5ор аппроксимирующих (собственных) задач 'сс?), еда , в силу того или иного критерия качества ад-

проке 1ШШ1ИИ tffC&y.

Lnflii(fi-): КЛ S (I) '

К = {^*. C(d) собственная ^ С (^собственна ij^) ,

- множество допустим« коррекций . (Здесь и ладьте тер мины "аппроксимация" и "коррекция" попользуйте ,-t как синони-мн.) Графически предлагаемая схема изображается сведущим образом: i i"

С(в)--с--»D

«Ч «Н

-С*-U)

t_:_f

Переход С О?") , В* в (2) символизирует тот факт,

что при построения JD учитывается аппроксимация в соответствии с погружением С (&) , C'CS) , а обратной перевод

Л*) - тот фжг, что в результате роаешы задач D, определяется оптимальная аппроксимирующая кара C(fi*)tC (Av). Задача D сгроигся как некоторый синтез моделей С и (I). А именно, целевая функция D агрегирует в езбэ их целив: ю функции, а ее ограничения - это ограничения (I) плво некоторая часть ограничений С (берутся каиболоо важные и згшэдоно совместима ограничения). Например, J) мозено получить и) несобственной 1-го рода задачи С , оставив ь последней часть (заведомо совместных) ограничений (плюс ограниченна

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

Аппроксимирующая роль задач D , D по отношению к С . ' С* выражается также и в том, что оптимальная коррекция $ ' должна соответствовать найденным оптимальным (компромиссным) решениям 5с и. , а именно, для любой тройки S , X. ,ÎL решений задач D , D* должно выполняться: Ab£ ,

и. € Alg СЧ<?) (через Aig... обозначается множество

решений выписанной вслед задачи). Дадим более строгое

Определение I.I. Тройка векторов Si , CL , 3е называет ся стационарной аппроксимацией несобственных задач С , С по схеме (g), если

1) х. ,ÎL , & - реыэния задач D ,Ъ \

2) задачи C(<Î"),C*(£) -собственные;

' 3) Атд С(£). ги'Атд .

Итак, каждое решение задач £ , D* должно представлять собой стационарную аппроксимацию несобственных задач С , С* , Заметим, что переменными задач J) , J) являются, соответствен но, ас , и , а также часть или все компоненты вектора & . Впрочем, может и не входить явнш образом в JD £# , а вычисляться по найденным X , Û. .

Исследованию двойственности для 113 • конечномерного ЛП по-cBtiiiioii 5 з. В качестве исходных задач С , С* берется двойственная пара

С'. тах{<с,х>: Азс<ё,ж-»о5 (3)

С: trun Аа>с. uvoj

где с, х € Я* , (((Г, А- - матрица

т.» п. . Соотвэтсгвущиэ им' согласно йхеме (2) задачи Р ,

-строятся следующим образом.'Фиксируется произвольный "раз ; зз" матрицы А на подматрицы А^ (0,1',«.). а &• (.' •••»п«) по'горизонтали и вертикали, соответственно, а также отвечающий ему разрез векторов С , ,ас , ё , и. , соответственно, на с1 , Xе , и? • Через обоз-

начаотся вектор, полученный из вектора у путем замены ого отрицательных координат нулями. Пусть Я, А ^ , ^х л , £ ^ , > •■•» п» » - система фиксированных положи-

тельных параметров, Я5 , Ж - функции ) -мерного аргумента, где п.*т. - ^ - , ^ , ^ - размерности векторов

, . Задачи 3) , Д)*" имеют вид: Ъ\ 5ир{<с,*> - Д<Р(А13С'.....Ак.^'./'ЛЛ,*--^)'-.-

I)" ^ {- (с-8>Г,...,

.....9м.В1и*с\и»о$ (6)

где ^ = АГ1 С г- 1, п. , ,

ТОО- яЛ) (Ф*, 8- -

- сопряженная и индикаторная функции,

<Р , "V берутся из некоторого класса функций, называемых "допустимыми" (из допустимости Ф следует допустимость Ф и наоборот, (Ф®)® « Ф ). В пункте 3.1 доказывается теорема о двойственности, связывающей задачи 2) , 2) . •

Выписанная в (5), (6) общая форма задач 2) .,3) допускает большое число конкретных реализаций, соответствующих различным подходам к аппроксимации исходах НЗ С , С* . Если,

напркмчр, С - Iß 1-го рода, то ей можно сопоставить задачу J) ь £орш

sup { <Cjx>-R9 (/X, (А,*-«т. ...

Асос£ ё\ х. VO ] , (?)

полученную из (Б) при 1г, = О . Здесь Ф , согласно определении допустимой функции, является монотонно ноуйцваодей функцией навязок ( Ajrx: ~ , причем Ф (о) - О . Иодбира! пара-штри yu, ,... , можно ранлпроиать груи.ш ограничений ио

в.'.кнасач! их мшоднеииа. Параметр R отвечает за баланс целей онгамизации ио <с,ас} и штрафования навнзок. Однако, и форма (7) яшыетсл очень общей. Пункт 3.3 иосвящон разработке спаця-ал*, ной схема генерации частных реализация задач (5), (6).

Иариштричест.оо погружение С (<S), С*, отвечающее задача« С, С*, 3), Э* согласно схеме (2) имеет вид

с (Л): Ыах {<С.-,ЭС.*> + £ xv>:

А0х о ) ,

С (йУ. min [<€>•> * ZL

i^M. >-Ce, IS-UVC'-AC*, t = 1,...,а0 , и.>О ^

г,, у- (&с .«с) - лс'". д£\ ьг) . и м *• , u . $ рошенвЗ аздач 1) , I) шкюр 5

154(лС ) шчиошетсм ш> 5L , 2 ио правилам sC 6 л, (Й) , fttU (X) , ,вде

^ , ..I я>(А|Ж',л„/»д;

«Л

Я» /Ц тп. [Ф® (I, 5Г ....

ЕДесь минимизация идет по , и ,

• • •» ) »- ПРИЧ0М разбиение , 5 соответствует раэби-ениям <У,...,ск-)-

Теорема 3.3. Пусть задачи (5), (6) собственные. Тогда любая тройка сс , и. г их рогений представл зт собоП- стационарную аппроксимацию несобственных задач С , С по схеме (2).

Двойственность для НЗ ЛП в бесконечномерных пространствах исслодуогся в § 4. При этом в пунктах 4.1, 4.2 изучается пара 2) , 2) в форме, обобщающей соогвотсгвущую пару, рассмат- . ривавшуюся И.И.Ереминым для конечномерного ЛП. В пункте 4.3 исследуется следующее их дальнейшее обобщение. Пусть даны пространства

X, МХ7Г

в виде произведений:

х-пх,, и-пи.,х-их*,и"«па;

где X;., Х1 , IX), и} - рефлексивные банаховы пространства и (сльно) сопряженные им. Тогда, если положить ^ос*, ос} в

и.

= 21 <жГ,*1>, ада

« (ос*,... X , то X , X (и аналогично 1Л , IX ) •

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

и

мами ||зсв-£«*г| , |[эслА« тал йх* | . диалогично, ЦК,

1_ , Ьч являются произведениями выпуклых замкнутых конусов 1;СХ; , К^ С ТЛ- и сопряженных к ним и; с ^ К/С и}у I-. Пусть . О

=> - линэйниэ непрерывные операторы, действуе-

шь из Х^ в ZL-j , - сопряженные ям операторы. Исход-

кие задачи С , С* имеют вид

С: с>; А}х € К}

. (в)

С: ¿и^ [<<,u>-. AVeii^O-»...,^^«^.

где но определению Aji, L -»

i. А;

с» ^ »i

С - Cc......c^ € Г 4 - (€„...,4^ s

Аналогично конечномерному случаю, зафиксировав номера Об О* ^И- , выделим подсистемы ограничений за-

дач (8): 4j-AjX€ Kj 0*<,...,1*о), A[u-Ci€L* ((* V-»»u) ,

а функцию

Ф

над пространством Ут'Хп ♦ «*.»* "-'^»и

' И функций V над пространство!.! ^ ^../Х^* ^м.м" ""

будем брать из некоторых классов "допустимых" функций. Зафикси-ровгш систему положительных параметров R. A; (//Uj , Oj , удов "а творящих условиям Aj ^i53/^ - ( , H ,

J = ,..., tw ) , выпишем задачи

>. sup ........

•••^ДА^-еО): «J-Ai^i К. ,jH,..,h<c, оссС 5 }

«Ч*.....I О- Аг«- с<* LJ ,£-V-.и*,«* К* j,

и которых Я-5 , - допустимые функции над соответствующими пространствами. Для "-"ач D , D доказывается теорема двой-ctbuuiiootb, угзерадащах, что если одна из функций Ф , допустима:, а вторил - ей соиря&енная, то они обе допустим««* за-

дачи 2) , 3) связа ни соотношениями двойственности {при выпол-нзния соответствующих условий регулярности). Кроме того,'для этих задач справедлива

Теорема 4.6. Пусть задачи 2) , D собственные. Тогда

д.

произвольная тройка 5с., й , о" их решений является стационарной аппроксимацией несобственных задач С , с по схеме (2) (погружение С (<?-) , C*(cf") и правила вычисления по ОС , и. определяются аналогично конечномерному случаю).

В § 5 результаты § 4 применяются для получения теоремы двойственности для ИЗ стохастического программировали. В § 2 дается реализация «схемы двойственности (2) для выпуклых программ весьма общего вида, охватывающих обычные задачи линейного и выпуклого программирования. Огметш, что двойственность для

задач, близких по форма к одной из частных реализаций задач D , ТУ4*

Л) из § 4, изучалась К.Бастионом, К.Дибовским и К.Таймером, рассштривавшими ее применение как к НЗ, так и к задачам приближения функций. Построении двойственности для несобственных и полусобственных задач, т.е. имеющих конечный разрыв двойственности (включая различные методы аппрок имации и ликвидации "разрыва двойственности") поовздени ша ряд работ Н.Н.Астафьева, С.П.Трофимова, Дж.Борвайна, Р.Г.Джерослоу, Д.<2.Карнея 4 др.

В главе 3 разрабатываются методы коррекции для несовмест-них систем линейных уравнений и неравенств'вида

Ах^Хс R? , («) ^A-Kikn.Vie^g^,,, Л

¿£\ г1 tu . Большинство известных методов коррекции

для систем» (9) могут бить представлены в виде следующей модели. Введем Викторы р"1« R*1, р^ё d^1 ' параметров, а тше*

/ * л 1и

множество S .С К. их допустимых значений. Системе (9) сопоставим систему

AА^-^-р*« ос «Л (Ю)

и мноквотво К[ Р ■ ( ( рЛГ, ( Р*")Т У* сг тема

(10) совместна]. 3 ша коррекции запишется в-виде

¿^{ycpv. ptK'ns}, m)

где ' ty ( р} - критерий качества коррекции. Основной отличительной чертой подхода главы 2 является то, что допускается коррекция не только правых частей, но и матрицы ограничений, т.е. всей информации о с"отеме. Л именно, вводится параметрическая матрица H = Ot-j) размерности m "К , которая аналогично А разбивается на подматрицы H, , H г . Вводя для- компонент вектора р обозначение р« ( k1jnVi ,-..•» é ^ • по~ лучим расширенную матрацу (Н^р")3 (и вектор

k (/г,.....ЙГ^. всех коррекции расширен-

ной ы-трицц (А/<) (где А-^.^^Т.^ГГ).

Тики.,1 образом, системе (9) сопоставляется система

(A/H^^V » u-îX . (12)

Задача коррекции рассматривается в виде

¿^{Ф(к)' к-nsi , (13)

1-до ф ( К) - критерий качэстаа коррекции, К е { К : система (12) сонмеогна J, S - мноаество допустимых значений (г . Лоно, что модель (13) содорлит (И). Заметим, что (II) является и сущности задачей минимиза.^ ивБлзки. Например, при bi~ О w^eht, - ¡^ сиа переписывается в виде

¿»^ {<*(-€-А*у. Х€Х]. С14).

Сравним идеи подходов (II), (13), (14). В (И), (14) ищется оптимальное компромиссное решение эг , соответствующею минимуму нарушений ограничений (минимуму корре1 ;ий цравых частей). Если (9) представляет собой модоль некоторого реального объекта, то может оказаться, что мы не мокем (или можем в недостаточной степени, или нам невыгодно) изменять правые части Обращаясь к общепринятым в ЛП интерпретациям, замечаем, что (II) соответствует, коррекции за счеч экстенсивных факторов (вектор ■» р соответствует увеличению потребления ресурсов, уменьшению производственных заданий, ослаблению нормативов и т.д.), а вариация матрицы А в (13) соответствует изменении внутренних свойств самого объекта.

Одна из причин того, что модоль (13) к настоящему времени исследовалась довольно малым числом авторов, заключается в том, что до начала систематических исследований НЗ несовместные системы рассматривались в основном в постановках, связанных в идейном плане с подходами теории обработки наблодений или приближения функций, где цель состоит не в оптимальном изменении модели, а в нахождении - ос. , макс шаль но "вписывающегося" в имеюцуюоя совокупность данных. Другая причина связана с тем, что задача (13) является более сложной по сравнении с (II). Дело в том, что система (10) линейна относительно переменных ос. , р , в то время кик (12) бшшяойна относительно ос , к. .

Основной результат главы 2 состоит в том, что удается выделять класс критериев ^ (К) и множеств & , для которых решение задачи (13) момт быть существенно упрощено.' Обозначим

Рек™

Упомянутый класс состоит из всех Ч> I s , представших в вида

S- РмП{к: <>(М,..., W], as)

аде y (.и),tf(uéCb^.scR^), PcRT\

V/ С RT* - произвольные функции в множества, удовлетворяющие условиш: а) Vue Р ; б) для воех £ >0 , S** £f > О ; в) ftfc, s4) € W для всех 5* V-S* ^О , О i € W' ; a техже при некотором ф С # {oj условиям:

1) сущэствует конечный набор точек J™^*- Q такой, что VtA'e 'Ж G X 3

DnA^ UtQ}* ÇT ;

2) вела m о , то Q ** - Q \

3) Q(X)=r\Q (VAX)), Обо)« [ci • X«éQ VA>oJ,

где [ue P: A $ . Очевидно, Q может

быть выпуклым полиэдральным мнокоством (или конечным объединением таких множеств), при эгом JD -подмножество его воршин. Например, в качестве Vf можно взять положительно однородную ку-сочно-линийнуо функцию, принимающую неотрицательные значения, а в качестве Р - конечное объединение выпуклых полиэдральных конусов. В частности, мы мокем фиксировать произвольное поданоке-ство сирябцов и строк расширенной матрицы ( А, •€ ) . Если тх» »О , то условия б), в) выполняются говдествеяно, т.е. ф , W -произвольные, l^uwepa.. функций Ф ( к*) , удовлетворяющих пере«-числешшм условиям, могут служить нормы ( k^j ), ZI

Не ограничивая общности, считаем, что для всех

Х> 1 и всех ненулевых С^еТ) .Пустг X* { ос *. А.ос* С $ . Обозначим I. - (*,...,€.} ,

К,.», ¿и.), /-С^ч, ^м), </-(</,*,♦•. у»,)-

Пусть - С-тая строка (. Вектор к составлен из подвекторов ,

—, »* . Полохим

К (О- { «Н«,*,

с« вм.«0, о, -£>0-,

Пусть С , К ~ оптимальное значение и оптимальное множество задача (13), - шгояество оптимальных векторов •( ¿, 5, у, и.) задач

полоким .

Связь между задачами (I.) и (16) устанавливав^

Теорема 8.1. Пусть для каждого. ^6 ¿- система ч

А^Х « несовместна. Тогда

= , К* для всех ¿"б ,, • .

Таким образом, для описанного вышЗ. класса гг и о решение задачи (13) мояег быть сведено к решение конечного набора задач (16), в частности, задач Ш, если У , V/ полиэдральны. Алгоритм решения задачи (13). для последчаго случая дается в § 9. Отметим, что описанный в главе 2 метод-не требует, в отли-

19 .

чне от других 'предлагавшихся методов решения задачи (13), чтобы $ содержалось в многообразии малой (по сравнении о mln+l)) размерности.

В главе 3 изучается следующее обобщение задач симметрической аппроксимации НЗ JJH в линейной коррекции 113, исследовавшихся 11. И. Ершиным, А.^.Бакушвским и А.В.Гончарским, А.А.Ватоли-ным, А.И.Вересковым, Л.Д.Поповш, В.Д.Скариным, Н.В.Третьяковим и др. Будем считать, как это принято л теории седловых функций, что вогнутая по (м,^ и выпуклая по

(ос, р4) <£ f^***1* собственная замкнутая функция F^,*:,(»п^тд-м.п«'п.") отображает в

U{-*o}U{«m) Сопоставим ей задачи на макримин и минимакс

Sup inf F(u,*,p,<ft, tn| sup Г(и>х,р,<х) (17)

и. at x. u

( p , <\, - параметры) и их множества разрешимости:

К 1' ИЫ8£,Г садловув то--у^ ,

С 1 зтацапкаш (I?) свяжем задачу коррекции вида

' ¿"M^Cp.O-. ЧмЛ«КП$1, . (19)

где ~ произвольная выпуклая, собственна)!, „амкнутаа

функция, s выпукло, (в дальнейшем считаем S» сЛогиЯ"* ). в (1а) вместо К кокно брать такие К* . К* . Задачи симметрической ашцюксимаеди и линейной коррекции получается из i l'j) при ^

£ F(u,jc) соответствует функции Лагранжа задачи МП).

Решение задачи (19) требует предварительного исследования структуры мнокеств (18). Этому посвящен § II. С со,адовой функцией

sup in? {<"»

ж М

свяжем множества (ниже рг% (/") обозначает проекции на подпространство координат вектора ж ; с£ - замыкание; ГС - относительную внутренность):

{(fM-V С^о.р,^«. с^ Jowt F"1} ,

" ( Р^ ОмгИЧ f>\ (} <- О) ,

( Р^рО^П^ (К ¿om.F1)) • "{Я,- (o.^tc^cU^F'NcUi^y

Пусть ct F сл. r - замыкания F no U. и ОС

.read F*

= £ (Wjao.p.c^y. . Введем условия на F :

Аг: РЧ (ree* ¿и F)c РЯ < '

Ap : prp {rtal d^F) С prp (cWF^

В § II получены, в частности, следующие результаты о структуре К , К\ К\ дащие условия их близости к выпуклому замкнутому множеству D . Заметим, что в общем случае эти множества ие обладают свойствами выпуклости или связности.

Теорема II.I. Если выполнено Д^ ,то K^C-DUQ^ , Если выполнено , то К*С 3)1/ Qa . При вйнолиенил обоих условий К с К1 Л К4 сХ> !

Показывается, что незначительное ослабление условий А^ » Ар приводит к невыполнении теоремы ПЛ. Рассматривая конкретно примеры, можно убедиться, что для Р , удовлетворяющей Ар ши условию А0: (геа£Г(сЬг,)Г) , как правило, выполняется К*С I) , К* С- 3) , в частности, так будет для всех F при т^ - я "/ . Однако, мокко

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

Пример 11.3. Пусть и» (и1гил)€ к ,

р|и.,{* и<- рхэ,

где для краткости для индикаторной функции использовано

^и^иншо: 5 (А(г)):= ( [г: АСь)^ , А (г) - некоторое ус.ч^ако на а . Тогда Р удовлетворяет , /Ц ^ А0 > Мсгдг- Рч ^ > 1>° } Й в то ко ьре.эд ОС К* Кг4 V. Г) данной примерь Р удовлетворяет но только А« , А (1 , Аа, н_> и учловили:

•1рйы>Д|«!и.» ише тооршиа 11.2 л-жазивиот, что достаточно усили ь ш.1'> .>и на & Iих услоьиЛ до гр<;бозаты

А( (.„ (геа/ с^Г) с Лоы.,

Ч!'.. )., Г.фШШ^ОбаТ!. 1ИС.;ПЧ(ЦПМ К*С Ъ , КаС 3)

а;

Теорема II.2. Если выполнено А., , Ар , то Если выполнено Аг , А<^ , то К* С D .

Теорема II.3. Пусть выполнено А^ , Ар (или К*А

ЛК1СЪ) , Ой P>"Cu.>2C.) СrL F1 • Тогда riDС КС

с К^Л Kz с D .

Разработке методов решения задгли (Iw посвящен § 12. Пусть ( МчН1"1 К, В, > <£ € Ва . где

Конкретно, р* , соответствуют субградиенты в точках:

(о,0,-Pi К р ., «

^«.x.^fo^Pi.li Обозначим С«-<р?,р«> + F(«„Kft/>t,0. са'<ЧГЛ1> 4 Pai^z) • Множество

JowH^ -{(M^at.p^V- (P^eJom.^,

,p>4i) e Г» У. рг € d«* F 3 -

возьмем в качестве эффективно! области вогнутой по («></) и выпуклой по (и-.х.р,«^) функции •» определяемой следующим образом:

И^ ^ » + во , ,

Hrf(/J - - оо f (U,tj)4.Jом, Hv .

23

Суюсь cL , р -произвольные положительные параметры. Пусть

. - множество седловых точек H«, а , С - оптималь-<*i р if*

нос значение задачи (19),

(р.«й - ^(p^^CCp.OI^ К), <„>(Г рг(р><^ ,

0'(*.Р> sup i*4 И,, JCA,ß>Ä«p i4 ' М,у Ä.i^p.H. «е А

В следующей теорема роЕение задачи (19) сведено к нахождению се-

дловых точек вспомогательной функции Н^ р .

Теорема 12.1. Пусть К CD, ß, , € В4 ,

РГСи* х•) ^ ^» Г£ ^ Л Г i К ^ pf ,

-со < о*< + «э . Тогда при любых oi>0, ^/3>С>

1) функция собственна и замкнута;

2) конечно, на изменяется при перестановке операций Sbtp , tnft в его определении, монотонно возрастает по ÜL >Ог fi > о t

О'« &М- - "4 trc*,}*)

ач+о а>о,р>о

3) S' с cL.n Р'^о.-^ЛсиФЫ К П¿ожФ;

Но л и, кроме того, О £ К dorn р ГЧ ß f, t rt ß4 , то

5) S, 0 , öo; )в того, Oer с dorn H*^ (VoOo ys>o);

6) Агд тЬгФв , d , .

При выполнении условий теороьш II.

з с£К® {ср.чУ* P<f\ '

Q ] , .де Р . Q выпуклы и замкнуты. Пусть Ч^рд)-

вогнутая по р и выпуклая по с^ собственная замкнутая функция. В § 13 получены методы решения задача (коррекции по макси-ми иному критерию)

sap 14 VCp.ü

р«jt-Q

впервые исследовавшейся Я.Д.Поповым для случая линейной коррекции. В § 14 строятея методы решения задачи (19) для случая, являющегося непосредственным обобщением подхода линейной коррекции', когда линейным является вхождение в функцию лишь параметров р , с^ .

Глава 4 посвящена исследовании мод-лей с неоднозначно заданной информацией. Как отмечалось выше, неточность, неопределенность задания информации является одной из причин возникновения ИЗ. Поэтому различные подходы к учету и "снятию" неопределенностей могут одновременно выступать в роли методов преодоления или предупреждения несобственности. В зависимости от конкретной ситуации в качестве допустимых векторов такого рода моделей можно рассматривать или все ас. , удовлетворяющие ограничениям модели при каких-либо значениях ее параметров, укладывающихся в заданные границы (обобщенное Ш.Дя.Данцига и Ф.Вулфь) или же вое ОС. , каждый из которых удовлетворяет ограничениям при любых, лекащих в заданных границах, значениях неопределенных параметров (неточное Ш Х.Сойстэра). Впоследствиэ оти подходи исследовались во многих работах оттчэс^енних и зарубежных авторов.

В случае несовместности ограничений модели первый из «тих подаодов соответствует цели преодоления ее аа ичет либо рассмотрении всех эквивалентных по точности реиииий системы, осли система задана приближенно (Л.И.Тихонов, В.А Морозов, З.И.Капма-

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

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

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

£ € .S . Будем считать, что £ - элемент векторного аростраи-отаа Т* и задано »S 'С Т* . Пусть предикат вида

ос* M (t) ш

означает, что надеется вектор £ такой, что i S С- &

к lé M Ci) для люоого £ £ £ * S . Вааа в качестве S

множество Ji S , получим, что предикат

ос £ M (I) , где X <■ 1, совпадает о условием

х £ M(i) При Л = О и с условием Vie S х € M(t) при

Далее, будем считать, что ^S^.-'S^ , X есть произведение пространств: , Sj С Tj , £ в •(£*...,£ £''6"7j , ja1t..,fC t и заданы множества iS/c cT4,...t , Тогда множеству воех ос é M (i) о ноодноанн-чзо заданным £ £ S иозно сошотаэигь множество всех х , удовлетворяющих условию

PJÏH^Ï... Р« К .зсс H60 (2D

В § 16 изучается реализация предложении* нодходоа ирймаив-гельно к моделям вида JC €

в которая

£, Q

X.* pr JC4 M ^ ,

где А=(а0)м,п tQ«(<liM« ' é"(4.....

. Б качестве "t берется лектор t - (£ t R*" , составленный из воех элементов

матриц А , Q и векторов , р , выписанных » произвольном пор-щке, т.е. m- (м'* *>i")h + ж/+ m" . Используя терминологию подхода <¡¿1), оуден считать, что £ рызОнт иа I подвектори»: I * (t\...}tf), V Л]. SjCTTj-V-/ ,

. В качестве ^ возьмем произвольные прямоугольные параллелепипеды: 5.» £ \ + ' < ■iJ ] }

^ = Н, ..., . Этим вводятся границы на каждый элемент ^ вектора Ь : , ¿» ,ьх .Поло-

жим Sj^=■)^jSj г

Зафиксировав произвольное I , т' , представим

с -тую строку система Аос«=--€ в виде

где { - перестановка элементов {от¿^ ,...

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

элементов «('п в последовательности

. Дри этом полагаем » , если е(к соответ-

ствует 0£у, ук , если ^ к соответствует — . Ана-

логичных образом произвольную строку системы фэс С р представим в виде

Пусть с/^ соответствует элементу I вектора £ . Обозначим

А'. = Ус/ '= •£ (если является 'элементом €к

' о* г ^ I ' _|»

вектора ь , т.е. с^ = --ь, то полагаем , а^ »-с^

в . О"- . Аналогично вводятоя /Л

Под проекцией (21) на строку (22) будем понимать выражение

ЧС^ЗсГсЗ,... РД?]

получеинов из (21) по правилу: для каждого ..., £ век-

тор ¿> составлен из влементов , соответствующих ^ , ^ -

соответствующий наргшизлашшвд с границами с] • , с! ; ,

-Лj £> • (ведя вектор V но содарниг элементов, соответствующих отроке (22), го операция ^ С^ 1 с! € считается "пустой"). Этем самым вектор («I<АИ*О разбивается на 5 + *1 непустых иодвектород- сГ*. ¿«(^ч.....»

с!К(Ч1.....¿к .-1 ^н»-.") • Аналогичный образом

определяется проекция (21) на строку (23).

Дня каадой строки системы , представленной в

виде (22), выпишем неравенства

а такйе систему 5+ \ неравенств вида •

+ ^ (2<ГИ4Г1)С, ^ < о ,

К« + - * О'кЛ, Ч*

Дня каждой отроки системы С« ос < р , представленной в виде (23), выпишем неравенство

.Пусть м - множество воех ОС , удовлегворницих (21) о

2У

введенными выше М (t) , Sj , . В следующем утверж-

дении дается представление М* в. в не пересечения М с множеством решений некоторой системы линейных неравенств.

Теорема 16.I. Множество М совпадает с множеством всех ж. е. М , удовлетворяющих системе, полученной объединением неравенств (25), (26) и (27) по воем строкам системы Аи ' Q ас р ; соответственно (связь »цементов эс^ , у^ для каждой строки указана выше).

ЁсЛи некоторый X из М уже виоран, то возникает вопро< каким образом выбирать значения векторов iJ на каждом шаге процесса принятия решений (21) так, чтобы осЬспечить в конечном счете выполнение условия эс е М (i) ? Этот'вопрос решается в следствии 16'I, где множества всех таких допустимых значений такте удается представить в виде множеств решений некоторых оис тем линейных неравенств.

В § 17 рассматривается случай бесконечных областей неоднозначности Sj , а в § 18 полученные результаты переносятся на ряд классов нелинейных моделей (задаваемых системами нелинейных уравнений и н равенств). В § 19 рассматриваются оптимизационные модели вида

¿в/'{¿С* ЛЬ хбМЮ),

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

3 а к hl ч е ii и к

Сформулируем осноркно результата, шнос»»*»о на зопиту.

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

2. Схемы симметрической аппооксимации и линейной коррекции

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

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

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

' список освовнш; работ по теме .диссертаций

I. Ватолин A.A. Об аппроксимации несобственных задач лвней-

наго программирования / Ред. Ж.вычисл.мат. и матем.физики. М., 1984. 30 с. Рукопись дай. в ВИНИТИ й 3501-84 Доп.

2. Ваголин A.A. Об аппроксимации несовмесгких систем лине, них уравнений и неравенств // Методы аппроксимации несобствен» задач математического программирования. Свердловск, 1984. С.39 54.

3. Еремин И.И., Вазолин A.A. Двойственность для несобстве! ных бесконечн-мерных задач линейного и выпуклого программирования // Методы аппроксимации несобственных задач математическое программирования. Свердловск. 1984. С.3-20.

4. Ватолин A.A. О задачах линейного программирования с интервальными коэффициентами // К.'вычисл.матем. и матем.физ., Ш Т.24, * II. C.I629-I637.

5. Ватолин A.A. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы // К.Вычисл. матем. и матем.физ. 1984. Т.24, Л 12. С. 19С'7-1908.

6. Ватолин A.A. Метод линейной корр кции выпукло-вогнутых минимаксных задач // Параметрическая оптимизация я методы аппроксимации несобственных задач математического программирования Свердловок: 1985. С.70-88.

7. Еремин И. И., Ватолин A. A. Двойственность дня несобствен ных задач математического программирования. Свердловок. 1985. 52 с. (Препринт / АН СССР, УНЦ, ИММ).

8. Ваголин A.A. Об одной общей реализации схемы двойственности да. несобственных задач линейного программирования // Противоречивые модели оптимизации. Свердловск, 1987. С.21-27.

9. Фролов В.Н,, Ватолин A.A. Анализ противоречивых ситуаций в задачах текущего планирования производства // Противоречивые модели оптимизации. Свердловск. 1987. С.79-92.

10. Ватолин A.A. Корроадая овлловои фуинцяи но минимаксному критерию // Исследования по несобственным задачам оптимизации. Свердловск, 1988/. С. 11-27.

XI. Ватолин A.A. О коррекции расширенной матриц!.. несовместной скстеми линейных неравенств и уравнений // Комбинатор.-алгебр, и вороятност.метода дискретного анализа. Горький, 1969. С. 40-54.

12. Ватолин A.A. Мяоаества рагреиимости я коррекция седло-пих функций и систем неравенств. Свердловск, 1989. 90 с. (Препринт / АН СССР, УрО, ИМ).

13. Ватолин A.A. О мноааствах разрешимости минимаксных задач, зависящих от параметров // Нерегулярная даоЗогалтосгь в маг.программировании. Свердловск, I9S0. С.8-23.

14. Ватолин A.A. Представление poaöimü s моделях с неточно задачкой информации;! / АЛ СССР. УрО. ИШ. Свердловск, IS9L 29 е.- Рукопись доп. в ЩНГИ 21.02.21, * 872-B9I.

15. Еремин И.И., Ватолин A.A., Лопов Л.Д. Шсойствошие задачи математического йрогра?даароваши // Метода зптниаэшш а экономико-математическом ^одадировачия. И,: Карта, ISÖI. G.2T9-255.

16. Krem in I.I., Va'oll.n A.A. Duality in improper ranilte-natloal programming problème urtder uncertainty // Lfot. Notes îontrol & Inform. Sei. 19ВС. Vol.81. P.326-333.

17. Vntolin A.A. Parraetric approximation of inoonsis-:ent systems of linear equat-'ona and inequalities //. Seminw-ier. Berlin: Humboldt-Univ., 1986. Î) 01. P. 145-15418. Vntolin A.A. Correction of inconsistent linear in-

qunlity syst era with record to restrictions or. ра-г-istor vari-tion // Seninarber. Derlin: Huubolitt-fniv., 1987. 90. P.

33

132-135.

19. Vatolin A. A. On the structure of solvability aeta of minima* probleraa // WIbû. Berlchte Techn. Hochach. leipzig. 1989. N 6. P.116-117.,

20. Ereminl.I., Vatollri A.Ai Improper mathematical programming problems // Publ. Control 8c Inform. Theqry. 1989. Vol.18, no.6. P.359-380.

QraoiataHO na poaanptmra Hiilf JpO PAH wpai 100 »ait.264 Otfteii 1,5 ne«.«. $opuaï 60x34 I/I6 r.EnârapHBffypr