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

5Ъ

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

ЗЫКИНА Анна Владимировна

ПАРАМЕТРИЗАЦИЯ И ОБРАТНАЯ ДОПОЛНИТЕЛЬНОСТЬ В МОДЕЛИРОВАНИИ И РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

05 13 18 - Математическое моделирование, численные методы и комплексы

программ

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

Омск - 2007

003158776

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

ЗЫКИНА Анна Владимировна

ПАРАМЕТРИЗАЦИЯ И ОБРАТНАЯ ДОПОЛНИТЕЛЬНОСТЬ В МОДЕЛИРОВАНИИ И РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

05 13 18 - Математическое моделирование, численные методы и комплексы

программ

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

Омск - 2007

Работа выполнена б Государственном образовательном учреждении высшего профессионального образования "Омский государственный технический университет"

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

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

Еремин Иван Иванович,

Институт математики и механики. УрО РАН

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

Вычислительный центр им А А Дородницина РАН

доктор физико-математических наук, профессор Соколинский Леонид Борисович,

ГОУ ВПО "Южно-Уральский государственный университет"

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

ГОУ ВПО "Казанский государственный университет"

Защита диссертации состоится 1 ноября 2007 г в 13 часов на заседании диссертационного совета Д 212 296 02 при ГОУ ВПО "Челябинский государственный университет" по адресу

454021, г Челябинск, ул Вр Кашириных, 129

С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета

Автореферат разослан 25 сентября 2007 г Ученый секретарь

диссертационного совета Д 212 296 02 доктор физ -мат наук, профессор

Общая характеристика работы

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

Особенно эффективно использование параметризации для решения несобственных задач математического программирования (НЗ МП), активное исследование которых ведется в Уральском отделении РАН под руководством академика И И Еремина Несобственные задачи в общем случае-это задачи, не обладающие решением в силу каких-либо причин Для задач математического программирования (МП) понятие несобственных задач можно сформулировать более точно это задачи, не обладающие свойством одновременной разрешимости прямой и двойственной задач и совпадения их оптимальных значений

Параметризация и соответствующая коррекция несобственных задач

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

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

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

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

и предложения, выбор портфеля ценных бумаг) Исследованием и решением задач дополнительности занимались многие известные российские и зарубежные ученые ( В А Булавский, Я М Берщанский, В Г Жадан, И В Коннов, MB Мееров, ЛД Попов, В И Шмырев, S Agmon, RW Cottle, G В Dantzig, W S Dorn, P T Harker, I Kaneko, J S Pang и другие) При этом несмотря на то, что задачи дополнительности с их приложениями образуют большой самостоятельный раздел, задачи обратной дополнительности до сих пор еще не рассматривались

Обратная дополнительность, предложенная в диссертации, с одной стороны, представляет интерес как новая математическая конструкция, с другой стороны, большое значение имеет практическое применение обратных задач для моделирования, решения и исследования сложных содержательных задач С точки зрения математического моделирования обратные задачи - это чрезвычайно важный класс задач, поскольку модели сложных систем, содержащие внутренние и внешние параметры, как правило, приводят к конструированию обратных задач для известных классов задач С содержательной точки зрения в обратных задачах задаются дополнительные условия, позволяющие стабилизировать моделируемую ситуацию Исследованием обратных задач математического программирования занимались А С Антипин, Я М Берщанский, В П Булатов, В В Васин, Е Г Гольштейн, Л А Истомин, И В Коннов, Е С Левитин и другие

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

Объектом исследования в диссертации являются как разрешимые, так и противоречивые (несобственные) задачи математического программирования, а также системы неравенств, задачи стохастического программирования и задачи векторной оптимизации

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

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

Научная новизна работы характеризуется перечисленными ниже основными результатами - защищаемыми положениями (более подробно защищаемые положения рассмотрены в разделе "Заключение")

1 Выделен новый класс обратных задач - задачи обратной дополнительности

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

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

Теоретическая ценность работы состоит в следующем

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

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

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

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

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

при решении задач, выполнявшихся в рамках госбюджетных научно-исследовательских работ Омского государственного технического университета (регистрационные номера НИР 1 4 01 Ф, 7 04 Ф)

Апробация работы. Результаты работы представлялись на следующих международных, межрегиональных и региональных научных конференциях Международные "Проблемы оптимизации и экономические приложе-ния"(Омск, 1997), "Динамика систем, механизмов и машин"(Омск, 1997, 1999, 2002), ИНПРИМ-1998 (Новосибирск, 1998), конференция по исследованию операций (Новосибирск, 1998), конференция по анализу и геометрии, посвященная 70-летию академика Ю Г Решетняка (Новосибирск, 1999), "Методы оптимизации и их приложения" (Иркутск-Слюдянка, 2001, Иркутск-Северобайкальск, 2005)

Межрегиональные и региональные Всероссийская научная конференция "Математическое программирование и приложения" (Екатеринбург, 1999, 2003, 2007), Всероссийская научная конференция "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2001), Российская конференция "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), Всероссийская конференция "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006), 37-я Региональная молодежная конференция "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006), Седьмой Всероссийский симпозиум "Стратегическое планирование и развитие предприятий" (Москва, 2006)

В целом материалы диссертации докладывались на научных семинарах кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета под председательством профессора Ф П Васильева (Москва, 2007), отделения информатики и прикладной математики механико-математического факультета ЮжноУральского государственного университета под председательством профессора Л Б Соколинского (Челябинск, 2007), отделения математического моделирования НИИ математики и механики им Н Г Чеботарева Казанского государственного университета под председательством профессора А В Лапина (Казань, 2004, 2006), отдела прикладных проблем оптимизации Вычислительного центра им А А Дородницына РАН под председательством академика Ю Г Евтушенко (Москва, 2006), а также неоднократно в Омском государственном техническом университете (Омск, 2003-2007)

Публикации. По теме диссертационной работы опубликовано 47 научных работ Основные результаты представлены в публикациях [1-21] В их число входят 9 статей из перечня ведущих рецензируемых научных журна-

лов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук [1-9]

Личный вклад автора Все основные результаты получены автором лично В совместной работе [17] аспиранткой ОмГТУ Каневой О Н разработан алгоритм решения задачи МП с нечеткими исходными данными, в работе [20] аспиранткой ОмГТУ Шамрай Н Б разработан проективный метод решения систем неравенств Указанные результаты соавторов в диссертационную работу не включены

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

Содержание диссертационной работы

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

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

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

В разделе 1 1 приводятся постановки обратных задач для задач дополнительности и обсуждаются схемы методов их решения Для заданного нелинейного отображения Р Нт —»■ Ет рассматривается параметрическая нелинейная задача дополнительности

ы = Р(у)-д, ш>0, у> 0, уТш = 0 (1)

с вектором параметров д е <5, <5 С Кт. Для параметрического семейства задач дополнительности (1) строится отображение (возможно многозначное)

q t-—> У (я), сопоставляющее каждому q 6 Q множество решений Y(q) нелинейной задачи дополнительности Возникает задача об оптимальном выборе параметра q G Q для семейства параметрических задач (1), что приводит к постановке обратной задачи Для оценки оптимальности вводится критерий оптимальности (функция затрат) ip(q, у) Тогда обратная задача принимает вид

найти параметр q* £ Q, такой что

3»*€ Г (<f), q* € Агдтгп{ <p(q,y*) 1 g € Q} (2)

Таким образом, обратная задача (2) состоит в выборе из параметрического семейства задач дополнительности (1) задачи с таким значением внешнего параметра q = q*, решение у* £ Y(<j*) которой выступает в качестве внешнего параметра обратной задачи, при этом соответствующий внешний параметр q* задачи дополнительности (1) является решением обратной задачи (2)

В более общем случае, когда параметр q, в свою очередь, имеет некоторую параметрическую зависимость q = F(x), где F(x) = (fi(x), ,fm(x))y fi{x), г = 1, ,т,- скалярные функции на множестве X, X С Rn, получаем параметрическое по параметру ж семейство задач дополнительности

u = P(y)-F(x), w>Q, у> 0, уТш = 0 (3)

В этом случае строится отображение х i—Y(x), сопоставляющее каждому х € X множество решений Y(x) нелинейной задачи дополнительности (3), вводится функция затрат ip(x,y) и рассматривается задача обратной дополнительности

найти параметр х* £ X, такой что

Э у* <Е Y(x*), х* € Argmm{ tp(x, у*) | х € X}, (4)

или в эквивалентной форме записи

найти параметры х* 6 X и у* € У (ж*), такие что

<р(х,у*)-<р(х*,у*)> о VxeX (5)

В диссертации рассматриваются задачи обратной дополнительности (3), (4) (или (3), (5)) с различными классами функций ip(x,y) Выбор предложенных конструкций задач обратной дополнительности обусловлен проблемами решения задач векторной оптимизации, а также противоречивых задач математического и стохастического программирования, в том числе несовместных

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

В разделе 1 2 проводится теоретическое обоснование существования решений и определяется структура множества решений задач обратной дополнительности

Теорема 1 1. Пусть отображение Р непрерывно, множество Q непусто, выпукло и компактно, функции семейства ¡р(, у), у > О непрерывны и строго выпуклы Если выполняется Р(у) —> оо при )|г/|| —> оо, тогда задача обратной дополнительности, задаваемая соотношениями (1), (2), разрешима

Теорема 1.2 Пусть отображение Р непрерывно, множество X непусто, выпукло и компактно, функции семейства ip( , у), у > 0 непрерывны и строго выпуклы, Функции /г(ж), г — 1,. , т, непрерывны и существует константа F такая, что для любого х € X |/г(а;)| < F, г — 1, ,т. Если выполняется Р(у) —>■ оо при ||j/|| —> оо, тогда задача обратной дополнительности, задаваемая соотношениями (3), (4), разрешима

Специфика задачи (3), (4) с функцией ip{x,y) — yTF(x) позволила получить ее разрешимость без условий компактности множества X

Теорема 1.3 Пусть отображение Р непрерывно, множество X непусто и выпукло, функции /,(ж), г — 1, ,т, непрерывны, строго выпуклы, их лебеговы множества компактны и существует константа F такая, что для любого х б X |/г(ж)| < F, г — 1, ,га Если выполняется Р(у) —оо при ||«/|| —> оо и -Р(О) = 0, тогда задача-обратной дополнительности, задаваемая соотношениями (3), (4) с целевой функцией <р{х,у) — yTF(x), разрешима

Структура решений задачи обратной дополнительности задается следующей теоремой

Теорема 1 4 Пусть непрерывное отображение Р удовлетворяет условию сильной монотонности и функции /г(ж), г = 1, ,т, выпуклы Тогда решение обратной задачи (4) является выпуклым замкнутым множеством, а соответствующее решение нелинейной задачи дополнительности (3) существует и единственно

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

Общепринятая экономическая интерпретация задачи МП

min {/о(х) I fi(x) < 6Ь , fm{x) <Ьт, х € X} (6)

- это модель производства, в которой требуется выбрать интенсивности работы предприятия а: = (жх,. ,а;„) такие, чтобы обеспечить выпуск производимой продукции в соответствии с заданным технологическим процессом F(x) = (fi{x),. ,fm(x)) из ресурсов Ь = (6i, ,Ьт) с минимальными издержками fo(x) Здесь /¡(ж), г — 0, , m, - скалярные функции, X -замкнутое множество

В случае противоречивости исходной модели, например, при недостатке запасов ресурсов Ь для планируемого производства, соответствующая задача оптимизации (6) становится несобственной Очевидно, что если объемы ресурсов (компоненты вектора Ь) увеличивать, то их дефицитность будет уменьшаться и на каком-то этапе система ограничений станет совместной, соответственно увеличению объемов ресурсов Ь = (61, , bm) будут уменьшаться объективно обусловленные оценки и = (uj, , ит) и издержки предприятия /о(х) по выпуску продукции Но чем больше расходуется ресурсов для производства, тем больше спрос на эти ресурсы и тем больше их рыночная стоимость В связи с этим возникает проблема согласования дефицитности ресурсов с их внешней рыночной стоимостью Решение этой проблемы приводит к различного рода равновесным конструкциям, хаким как задачи о вычислении неподвижных точек, обратные задачи оптимизации и другие ( см , например, работы А С Антипина, В А Булавского, Е Г Голь-штейна, И В Коннова) В построенной нелинейной модели дефицита ресурсов рассматривается одно из возможных обобщений таких постановок Для этого в задачу (6) вводятся параметры - внешние управляющие воздействия У — (vi, , ут), характеризующие рыночную стоимость ресурсов В этом случае объемы запасов ресурсов b и издержки производства /о(ж) естественно рассматривать как функции от у В результате получаем задачу параметрического нелинейного программирования

mm {h{x,y) I F{x) < P(y), x G X}, y G Я?, (7)

содержательно состоящую в минимизации издержек /0 Rn x R™ R производства х € X из запасов ресурсов Р(у) = (Pi{y), , Рт(у)) при меняющейся рыночной стоимости у 6 R™' ресурсов и заданном технологическом процессе F(x) — (fi(x), , fm(x))

Для решения проблемы выбора оптимальной рыночной стоимости ресурсов у* строится отображение у i—> Х(у), сопоставляющее каждому

у € R™ множество решений Х(у) задачи нелинейного программирования (7), и вводятся дополнительные условия в виде параметрической нелинейной задачи дополнительности

Р(у) > F(x), у > 0, ут(Р(у) - F(x)) = 0, (8)

или, что эквивалентно, в виде вариационного неравенства

(P(tT) - F(x*), у - у*} > 0 Уу > 0, (9)

где

ж* 6 Arg mm {/0(®,»*) | F(x) < Р{у*), х € X} (10)

Введенные дополнительные условия (8) (или (9)) задают следующую обратную задачу оптимизации

в параметрическом по параметру у > 0 семействе задач нелинейного программирования (7) найти такое значение параметра у* и отвечающее ему решение х* € Х(у*), для которых параметр у* является решением нелинейной задачи дополнительности (8) (вариационного неравенства (9)) с внешним параметром х = х*

Замечание Если в паре задач (7), (8) исходной считать задачу (8), то оптимизационная задача (7) будет обратной к задаче дополнительности (8), и пара задач (7), (8) (или (9), (10)) задает задачу обратной дополнительности

Во введенном дополнительном условии (8) (или (9)) для задачи (7) основным является условие ут(Р(у) — F{x'j) = 0, которое означает выполнение условий дополняющей нежесткости для ограничений исходной задачи F(x) < Р(у) и внешних управляющих воздействий у > 0 Эти условия придают внешним параметрам задачи (7) свойства ее двойственных переменных, что позволило получить следующее свойство решений поставленных обратных задач

Теорема 1 5. Если задача (7) для каждого значения параметра у > 0 удовлетворяет некоторым условиям регулярности и существовует неподвижная точка точечно-множественного отображения у \—> U(y), которое каждому внешнему параметру у > 0 задачи (7) ставит в соответствие выпуклое замкнутое множество множителей Лагранжа этой задачи, то седловая точка (.х(у), и(у)) задачи (7), для которой и(у)=у, является решением обратной задачи (7), (8) (или (7), (9))

В случае линейного отображения Р для задачи обратной дополнительности (7), (8) рассматривается следующее параметрическое по параметру у > 0

семейство седловых функций

1{х, и, у) = /о(ж, у) + uT(F(х) - ipu), X 6 X, и 6 Я?, (11)

и ставится задача отыскания точки равновесия семейства функций (11) в следующем виде

в параметрическом по параметру у > 0 семействе седловых функций (11) найти функцию, седловая точка (х(у),и(у)) которой удовлетворяет равенству и{у)~ у

Аналитически эта задача записывается в виде

mmL(x,u*,y) = max ¿(а:*, и, у), у = и* (12)

При каждом фиксированном параметре у е R™ седловая функция L(x,u,y) выпукла по первой переменной х для выпуклых по ж отображений fo{x,y) и F(x) и вогнута (сильно вогнута) по второй переменной и при неотрицательно определенной (положительно определенной) матрице Р Такая седловая функция при каждом фиксированном параметре у 6 Rr", как правило, всегда имеет седловую точку (ж*, и*) = (х(у), и(у))

Доказано следующее утверждение

Теорема 1.6 Решение задачи отыскания точки равновесия (12) является решением задачи обратной дополнительности

mm {fo(x,y) | F(x) < Py, x e X}, у 6 R™, (13)

Py > F{x), у > 0, yT(Py - F(x)) = 0. (14)

Bn 15 первой главы строится обратная задача оптимизации в постановке для параметрического по параметру у 6 Y семейства задач математического программирования

mm{ yTF{x) I F(x) - Р(у) <0, хеХ}, yeY (15)

X

найти такое значение параметра у € Y и отвечающее ему оптимальное решение задачи (15), которые удовлетворяют условию

yT(F(x) - Р(у)) = 0 (16)

Специфика рассматриваемой задачи (15) позволяет учесть условия обратной задачи (16) как условия дополняющей нежесткости из условий оптимальности Куна-Таккера Выбор же внешних параметров для прямой задачи, равных ее множителям Лагранжа, приводит к тому, что образовавшаяся математическая конструкция содержит параметрическую по параметру х 6 X

нелинейную задачу дополнительности

Р(у) - F(x) > О, у > 0, ут(Р{у) - F(x)) = 0, (17)

что позволяет рассмотреть пару задач (15), (16), с одной стороны, как условия оптимальности Куна-Таккера для задачи (15), с другой стороны, как задачу обратной дополнительности

найти параметры х* € X и у* 6 Y(x*), такие что

{у*, F{x) - F(x*)) >0 VxeX (18)

Для обратной задачи (18) естественным образом выписывается нормализованная функция Ф(г*, х) = sup (у*, F(x) — F{x*)} и в случае достижи-

уеУ(х')

мости точной верхней грани (например, при компактности множеств Y(x*)) задача обратной дополнительности (18) сводится к задаче равновесия найти параметр х* € X, такой что

Ф(ж", ж) > 0 УхеХ (19)

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

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

Один из подходов, предложенных И И Ереминым для коррекции несобственных задач, состоит в замене пары двойственных задач

L = ст<; шах, А? < Ь, я > 0, . .

L' = 6ГС -»• mm, АТС > с, С > 0

системой неравенств (< имметрической задачей)

ст? > Ьт£ , А<; < Ь , АТС > с , ? > 0 , С > 0 ,

или в векторной форме

Их - д < 0 , (21)

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

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

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

2 этап Решается аппроксимирующая задача, решение которой х* принимается в качестве решения исходной задачи

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

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

Л(®)<0, , fm(x)<0, хех, XCRn, (22)

или, в векторном виде,

F(x) <0, х£Х, X С Rn, (23)

используется для введения понятия решения несовместной системы неравенств Это понятие является обобщением предложенного В А Булавским способа задания решений несовместных систем неравенств F(x) < 0, х £ Rn Пусть задано отображение Р Rm —Кгп Используя отображение Р и оценки у > 0 неравенств системы (22) (или (23)), введем параметризацию системы в виде

F(x)<P(y), у> 0, жеХ

Если оценки у содержательно интерпретировать как штрафные санкции за нарушение неравенств в (22), то отображение Р моделирует реакцию системы (23) на соответствующие штрафы у

При некоторых условиях на непрерывное отображение Р (например, условие сильной монотонности) можно определить однозначное отображение х I—> у(х), сопоставляющее каждому х 6 X решение у(х) нелинейной задачи дополнительности

и = Р(у) - F(x), w > 0, у> 0, утш = О,

и коррекцию несовместной системы (23) находить как решение задачи равновесия

найти параметр х* € X, такой что

Ф(а;\ж)>0 УхеХ, (24)

где Ф(ж*, х) = (у(х*), F(x) — F(x*)) - нормализованная функция

Поскольку задача коррекции (24) решается по параметру х € X, то получаем, что первый и второй этапы классической схемы коррекции сводятся к одновременному решению задачи оптимальной коррекции (решению нелинейной задачи дополнительности с параметром х = х*) и решению аппроксимирующей задачи со значением оптимального параметра коррекции У* = У{х*)

F(x)<P(y*), х<=Х (25)

Решение х* системы (25) принимается в качестве обобщенного решения несовмес1ной системы (23)

Существование обобщенного решения несовместной системы (23) гарантирует следующая теорема

Теорема 2.1 Пусть непрерывное отображение Р удовлетворяет условию сильной монотонности, функции /,(ж), г = \, ,т, непрерывны, квазивы-пуклы и отображение F — удовлетворяет условию Липшица на непустом выпуклом множестве X Обобщенное решение несовместной системы (23) существует, если выполнено одно из следуютцих условий

1) множество X ограничено,

2) найдется непустое ограниченное подмножество Z С X такое, что для каждого х £ X \ Z существует гг 6 Z, для которого выполняется неравенство F(z) < F{x)

Для коррекции несобственных задач линейного программирования (20) построена обратная задача

найти параметры х* £ Rn и у* = у(х*), такие что

(у*)Т(Нх - Нх*) >0 V I € йп, (26)

где у* = у{х*) - решение линейной задачи дополнительности

ш = Ру - Нх + д, ш > О, у > 0, шту = О

при х = х*, и доказано следующее утверждение

Теорема 2.2. Пусть матрица Р удовлетворяет условию положительной определенности и найдется непустое ограниченное подмножество X С Rn такое, что для каждого х € Rn \ X существует z € X, для которого выполняется неравенство Hz < Нх, тогда существует решение задачи коррекции (26) для решения пары несобственных задач ЛП (20)

Для несобственных задач линейного программирования в разделе 2 4 рассматриваются содержательные интерпретации решения задачи обратной дополнительности при различных выборах матрицы параметризации Р Так для несобственной задачи второго рода (20) полученное решение трактуется как введение подправки к ценам реализации с Эта подправка пропорциональна отклонению от заданного уровня в функции цели и имеет прогрессивный характер по отношению к объему производства ? (типа прогрессивного налога с деятельности) Ат(* > с - (ЬТС - в)Ря

Аналогичные исследования проведены и для других случаев несобственности

В разделе 2 5 для использования обратной дополнительности в задаче коррекции несобственной задачи квадратичного программирования

хтСх тгп, Ах < Ь, х е X, X С Rn (27)

вводится параметризация с помощью вектора параметров у £ Rf и заданной матрицы параметризации Р следующим способом

хТСх -»■ mm, Ах <b + Ру, х е X, у > 0 (28)

Если исходная задача (27) интерпретируется в терминах планирования производства, то Р - это матрица аварийных технологических способов производства, определяющих возможные пути компенсации обнаруженных невязок ресурсов Ь , у — это вектор оценок, задающих мероприятия по ликвидации как недостатков, так и избытков ресурсов

Задача оптимальной коррекции для несобственной задачи квадратичного программирования (27), являющаяся одновременно для (27) аппроксимирующей задачей, является задачей обратной дополнительности вида найти параметры х* € X и у* = у{х*), такие что

я* 6 Arg mm {хтСх + (y*f(Ax - b) | x € X}, (29)

где у* = у{х*) - решение параметрической линейной задачи дополнительности Ру > Ах — Ь, у > 0, утРу = ут(Ах — Ь) при х — х*

Теорема 2 3. Пусть матрица Р положительно определена и матрица С неотрицательно определена Задача обратной дополнительности (29) имеет решение, если выполнено одно из следующих условий

1) множество X ограничено,

2) найдется непустое ограниченное подмножество Z С X такое, что для каждого I 6 существует г & Z, для которого выполняются неравенства гтСг < хтСх, Ая < Ах

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

тш {/„(*) | /1 (ж) < 0 , , /т(ж) < 0, х<ЕХ, X С В"} (30)

Для заданной положительно определенной матрицы Р со строками Р°> Р1) >Рт € (размерность матрицы равна ш +1) разработан алго-

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

Л(®) - 7я < 0, Ь(х) < 0, , /т(х) < 0, х € X, к = 0,1,2, (31)

Связь между решением задачи обратной дополнительности для системы (31) и оптимальным решением задачи МП (30) устанавливает теорема

Теорема 3.1 Пусть получено решение х* задачи обратной дополнительности для системы (31), оценки у* ф 0 которого удовлетворяют условиям

1) {Р\У*)Ф О,

2) (рг,У*) = 0 для всех номеров г е {1, ,та}

Тогда вектор х* является оптимальным решением задачи МП (30)

В следующих теоремах приводятся условия неразрешимости задачи МП

Теорема 3 3 Пусть получено решение х* задачи обратной дополнительности для системы (31), оценки у* ф 0 которого удовлетворяют равенствам Уо — 0, (р°, У*) = 0 Тогда допустимая область задачи МП (30) пустая

Теорема 3 4 Если для любого значения решение х* задачи обратной дополнительности для системы (31) имеет нулевую оценку у* = 0, то целевая функция задачи МП (30) неограничена на допустимом множестве

Доказана сходимость алгоритма

Теорема 3.5 Последовательность 7к, к — 0,1,2, , построенная по алгоритму, сходится к оптимальному значению 7* задачи МП (30)

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

fi(x) < 0 , , f,(x) < О, х 6 D, (32)

задаваемую выпуклыми функциями fi(x) , , fi(x) и выпуклым множеством D = { х е X, X С Rn | fM(x) < 0 , , fm(x) < 0> Условия

Л+i(x) < 0 , , fm(x) <0, хеХ, (33)

можно интерпретировать как директивные условия, или как максимальную совместную подсистему несовместной системы

/l(s) < 0 , , fl(x) < 0, fl+i (х) < 0 , , fm(x) <0,хеХ.

Такая задача может возникнуть, например, при интерпретации функций fi{x) , , fi(x) как целевых в многокритериальной задаче с ограничениями (33) и при последующем решении многокритериальной задачи как задачи целевого программирования

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

Л(*) - 7i < 0, , fi{x) - 7f < 0, f,+1(x) < 0, , fm(x) <0, х еХ (34)

Проводится теоретическое обоснование алгоритма Доказывается сходимость итеративного процесса решения задачи (32)

Теорема 3.8 Последовательность ук — (7* , , 7*), к — 0,1,2, , построенная по алгоритму, имеет предел

7* = (7i , , 7Г) = (bm Ti , . ,bm 7*),

К—>оо оо

где 7i , , 71 задают совместную систему (34)

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

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

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

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

/iO)<*i, ,fi(x)<ti, xeD, (35)

где , ti — недостижимые целевые уровни

В случае, когда D = Rn, доказана следующая теорема

Теорема 3 10. Пусть пороговые значения ii, . выбраны так, что для любого г€{1,- ., 1} выполняется строгое неравенство /г(ж)>t% для всех х € Rn. Тогда решение задачи обратной дополнительности для системы (35) совпадает с эффективным решением задачи целевого программирования

В случае множества вида D = {х £ Rfl\fi+i{x) < 0, , fm{x) < 0} ищется решение задачи обратной дополнительности для системы

h(x) - h < 0, , fi(x) - tt < 0, fl+1(x) < 0 , , fm(x) < 0 (36)

Доказана следующая теорема

Теорема 3.11. Пусть пороговые значения tlt ,ti выбраны так, что для любого г 6 {1,. , i} выполняется строгое неравенство /Дас) > t, для всех х € D. Тогда если оценки у* = [у\, >У*>Уш> ,Ут) найденного решения х* задачи обратной дополнительности для системы (36) удовлетворяют условиям

Ум = о, ,Ут = о, (р1+\у*) = 0, ,(гЛу•) = о, (37)

то решение задачи обратной дополнительности для системы (36) совпадает с эффективным решением задачи целевого программирования

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

Теорема 3.16. Последовательность = 1,2, , построенная на к-й итерации алгоритма, сходится к оптимальному значению (k)-is задачи из задач последовательной оптимизации к — 1,1 — 1, ,1

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

высоких приоритетов Для этого для каждой (к)-Ш задачи последовательной оптимизации, к = 1,1 — 1, ,1, проводится построение последовательностей

ЫУ'Ы+ih, , ÎTf}, J = 1,2, (38)

так, чтобы lim 7{ = jk, lim 7l+1 = , hm 7f = 7;, где

J—+oo j~>oo J~>00

7ь 7fc+i 1 i 7i уровни достижения целей для целевых функций fk(x), fk+i(x), , fi(x), обеспечивающие совместность системы ограничений для следующей (к — 1)-й задачи последовательной оптимизации Инструментом для построения последовательностей (38) выступают решения задач обратной дополнительности для несовместных систем вида

Л(*) - 7Î < 0, fM(x) - 71+1 < 0, , fi(x) — 7j < 0, . .

/;+i(s) < 0 , , fm(x) <0 К 1

Следующая теорема дает критерий завершения к-й итерации алгоритма

Теорема 3 19 Пусть получено решение задачи обратной дополнительности для системы неравенств (39), оценки у* ф 0 которого удовлетворяют условиям

1) (рг,у*) ф 0 для некоторых номеров г € {к, ,1},

2) (Рг,У*) — 0 для всех номеров г & {l+l, , то}

Toi да для (к — 1)-й задачи последовательной оптимизации сформировано допустимое множество (39) со следующими правыми частями

7* = il + (рк,У*),1к+1 = 7a+i + (Рк+\У*), ,11 = 7/ + (р',У1

Теорема 3.22 Предельные значения последовательностей (38), построенных на к -й итерации алгоритма, к = 1,1 — 1, ,2, сходятся к правым частям 7fc,7fc+i, ,7ь ограничений fk(x), fk+i(x), , fi(x) для {к - 1)-й задачи последовательной оптимизации

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

Теорема 3.23 Если последний по приоритету критерий задается строго выпуклой функцией fi(x), то решение задачи обратной дополнительности, полученное для (1)-й задачи последовательной оптимизации, является эффективным

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

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

В разделе 4 1 для задачи обратной дополнительности (18) строится непрерывная траектория решения обратной задачи как начинающаяся в ючке х° траектория решения х(1) автономной системы дифференциальных уравнений

~ = -(ЧР(х))ту{х), (40)

где у = у(х) — решение нелинейной задачи дополнительности (17) Пусть выполняются условия

сильная монотонность и обратная сильная монотонность отображения Р, сильная монотонность отображения (У^(г))г2/(х), дифференцируемость обратного отображения Р~г,

условие Липшица для якобиана \7-Р(ж) и условие ограниченности 1^1 < к, к > 0, « = 1, ,т, .7 = 1, ,п, хех,

ограниченность решения у{т) нелинейной задачи дополнительности (17)

№(аОИ ^62, 02 > 0, аг 6

выпуклость вторых часлных производных функций Д(а;), , /,п(ж) В этих условиях доказано следующее

Лемма 4 3. Для решения х = х(а), а € [0,+оо), системы дифференциальных уравнений (40) при любом начальном условии ж(0) = х° имеет место оценка

||®И-**||<||*°-**||, (41)

где х* - решение обратной задачи (18)

Лемма 4.4. Вдоль траекторий х(а) автономной системы дифференциальных уравнений (40) величина ||(У^,(а;)):гг/(а;)|| является непрерывной убывающей функцией параметра а, причем при аг > «1 > 0 выполняется неравенство

где 7 > 0 - константа, зависящая от параметров отображений Р и Р

Для задач обратной дополнительности с линейным отображением Р условия для отображения Р заменяются положительной определенностью матрицы Р В задачах с линейной параметризацией F(x) = Нх—д все условия для отображения F и его производных становятся лишними в силу аффинности входящих отображений Эти результаты доказаны в соответствующих леммах и следствиях Так аналогом леммы 4 4 являются следующие следствия

Следствие 4.4 (4 5). Вдоль траекторий х(а) автономной системы дифференциальных уравнений

|\ = ~Нту(х) (42)

величина ||Нту(х) || является непрерывной убывающей функцией параметра а, причем при аг > сх\ > 0 выполняется следующее неравенство

||Ягг/(ж(а2))|| < ИЯ^ОКс^Ие-^-^ ,

где 7 > 0 — константа, зависящая от параметров матрицы II и отображения (матрицы) Р

Итогом доказанных лемм и следствий является следующий результат

Теорема 4 1. Вдоль траектории системы дифференциальных уравнений (40) (в линейном случае (42)) существуют пределы

х* — lim х(а), у* = lim у(х(а)),

а-»+оо а-Я-оо

где х* — решение обратной задачи (18) (в линейном случае (26)), в, у* — решение соответствующей задачи дополнительности

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

хз+1 = хз - a}HTyJ,

где у1 — у{х3) - решение задачи дополнительности

w3 =Ру> - Нх3 +д, w3> 0, у3 > 0, {y3)Tw3 = 0 (43)

Для выбора величины шага а} используется следующая оценочная функция S(x) = ||ДгГ2/(х)||, где для данного х в качестве у(х) берется единственное решение линейной задачи дополнительности (43) При этом учитывается тот факт, что при движении в пределах одного базиса вектор у{х3 — аМ^у*)

линейно зависит от а, и, следовательно, за поведением величины 5(а) = = 3(х3 — аНту3) можно легко проследить и обеспечить ее максимальное (в пределах одного базиса) убывание Доказана теорема

Теорема 4.2. Существует константа С > 0, при которой для а > О справедлива оценка 5(0) — .У(а) > 5(0)(-уа — Со?), где 7 — константа из следствия 4 5 леммы 4 4

Исследовано строение системы дифференциальных уравнений и соответствующих траекторий х(Ь) и у(£) = у{х(€)) Показано, что в пределах фиксированного базиса правая часть системы дифференциальных уравнений (42) линейна Исследована проблема вырожденности при переходе от одного базиса к другому В общем случае справедлива следующая теорема

Теорема 4.3 Пусть точка у} — у(х3) является решением задачи дополнительности (43) Направление £3 изменения точки у[х3 +аг)3) = у3 +а£3, где г)1 = —Нту3 , определяется соотношениями

[Р22 - Р21РГ1Р12] > [Н2 - РпРп'Нг] т?,?2> 0, (44)

[Рп - РпРГг'Рп] е2 = (еУ [Н3 - Р2гРГг1Н1] У

Здесь разбиение вектора и матриц Р и Н сделано согласно разбиению вырожденной точки у3 на базисные, вырожденные и небазисные компоненты При этом базис в точке у3 составляется из номеров положительных компонент вектора у3 + а£3 при некоторых малых положительных а

Важным для реализации численных методов является факт сохранения в задаче (44) специфики исходной задачи (43) при некоторых выборах матрицы Р А именно, справедлива следующая теорема

Теорема 4.4. Если матрица Р является треугольной или диагональной, то матрица Р22 — Р21Р11Р12 задачи (44) для нахождения направления £з2 изменения вырожденных компонент точки у3 сохраняет ту же специфику

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

о < (у>)г < е, 0 < (Ру3 -Нх3+д)г<е

Учет е-вырожденности интерпретируется как некоторое изменение вектора g в задаче дополнительности Этот результат доказан в следующей теореме Теорема 4.5 Направление f, которое вычисляется при учете g—вырожденности решения у3—у(х3) задачи (43), является направлением изменения точки у{х3 + ащ1) = у3 + aÇ>, где if — —HTyJ, а у3 = у(х3) — решение задачи дополнительности

Ру3>Нх3-д, ^>0, (tffPy3 = (у3)т(Нх3-д), (45)

для которой выполняются оценки ||<? — <7|| < е(1+ ||Р||)-\Дп, \\у3 — < е^/т

На основе теоретических результатов и проведенных исследований вырожденности строятся алгоритмы для решения обратной задачи (26)

Первый алгоритм основан на чистом понятии вырождения, и в нем величина шага выбирается из условия сохранения базиса (ав) или из условия достижения минимума оценочной функции S(x) в данном направлении (3°) Сходимость алгоритма доказана в следующих теоремах Теорема 4.6 Если множество решений X* обратной задачи ограничено, то для всякого е> 0 существует такое J(e), что при j > J(s) элементы последовательности {х3}, построенной по алгоритму, лежат в е—окрестности множества X*

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

Теорема 4 7 Последовательность {х3}, построенная по модифицированному алюритму, сходится к некоторому решению х* обратной задачи

Второй алгоритм основан на понятии е-вырожденности Для определения величины шага в этом алгоритме используется е-траектория, направление которой по существу есть направление приближенной траектории для линейной задачи дополнительности (45) с подправленным вектором g

Лемма 4 5 Существует D > 0, при котором для любого Д > О найдется такое а(Д) > DA, что при г = ЦЯ^ЦД вдоль е—траектории у{р), 0 < а < а(Д), и вдоль траектории у(х(а)), 0<а<а(Д), задачи дополнительности (45) базисы не меняются

Теорема 4.8 Для любых заданных параметров алгоритма d > 0 и а > 0 существует Д > 0, не зависящее от номера итерации j, такое, что скорость

сходимости оценочной функции 5(ж) вдоль приближения х(а) = х3 + аг)3, rf> = —HTyJ, при шаге а3 — mm{5^, ав} имеет вид

S(a3) < 5(0)(1 - dA1+a) . (46)

При необходимости параметр Д дробится, однако доказано, что таких дроблений может быть лишь конечное число Если величину шага а3 ограничить некоторой произвольно заданной константой Т > 0, то есть выбирать aj = mm{T, а°, «в}, то оценка скорости сходимости (46) сохранится

Теорема 4.9. Последовательность {я-7}, построенная по алгоритму, сходится к некоторому решению х* обратной задачи

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

Последние два раздела четвертой главы посвящены экстрапроксимальным и экстраградиентным методам, которые впервые были рассмотрены в работах Г М Корпелевич и А С Антипина для решения равновесных и седловых задач В диссертации экстрапроксимальные и экстраградиентные методы предлагается применять для решения задач обратной дополнительности

В разделе 4 5 решение задачи обратной дополнительности (18) на основе ее эквивалентного представления в виде (19) сводится к задаче о вычислении неподвижной точки х* 6 Argmin{{y(a:*), F(x) — Fix*)) | x £ X}, для которой необходимые и достаточные условия минимума вьшисьшаклся в терминах проксимального отображения

ж* € Argmm{i||r - х*\\2 + а(у(х*), F(x) - F(x*)) | х € X},

и для решения задачи (18) используется экстрапроксимальный процесс

я" € Argmm{i||a; - хп\\2 + <х(у(хп), F(x) - F(xn)) \ х е X}, . хп+1 е Argmm{i||a; - хп\\2 + a(y(sE"), F[x) - F(x")} \ х € X) { 4

Теорема 4 10 Если существует решение задачи обратной дополнительности (18), на выпуклом замкнутом множестве X функции fl(x), , fm(x) выпуклы и F(x) удовлетворяет условию Липшица с константой L, непрерывное отображение Р сильно монотонно с константой /3, то последовательность {х"} экстрапроксимального итеративного процесса (47) с выбором длины шага из условия а < 1/(s/2^-) сходится монотонно по норме к одному из решений х* задачи обратной дополнительности (18)

Экстрапроксимальный метод для задачи обратной дополнительности (13), (14) строится на основе теоремы 1 6 Решение задачи (13), (14) выписывается в виде эквивалентных задач оптимизации

и* € Argmax{uT(F(a;*) - Ь>и) | и > 0},

¿t

х* е Argmm{/0(х,и*) + (u")TF(x) | х € X},

для которых необходимые и достаточные условия максимума и минимума в терминах проксимальных операторов следующие

и* = argmax{-i||w - и*||2 + auT(F(х*) - ¡Pu) | и > 0}, , .

ж* = axgmm{i||x - х*||2 + a{h{x,u*) + (u*)TF{x)) | х £ X}, (48j

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

ж" б Argmin{i||a; - жп||2 + a{f0{x,un) + {иn)TF{x)) \ х 6 X},

ип+1 € Argmm{|||u - и"||2 - - \Ри) | и > 0}, (49)

жп+1 6 Argmm{||jx - ж,1||2 + a{f0(x,un+1) + (un+1)TF{x)) j г € X}

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

f0(x, и) - f0{x*, и) - f0(x, и•) + f0(x*, и*) > 0 (50)

для всех а; и и из некоторой окрестности решения (ж*, и*)

Теорема 4.11 Если существует решение задачи отыскания точки равновесия (12) и на выпуклом замкнутом множестве X функция /о(ж, и) удовлетворяет условию монотонности (50), функции fo(x, и) и F(x) выпуклые по параметру х и F(x) удовлетворяет условию Липшица с константой L, то последовательность {(х™, и")} экстрапроксимального итеративного процесса (49) с выбором длины шага из условия а < l/(%/2L) сходится монотонно по норме к одному из решений х* задачи обратной дополнительности (13), (14)

Для решения обратной задачи (13), (14), в которой fo(x,y) = yTF{x), получена сходимость экстрапроксимального процесса (49), не требующая выполнения условий монотонности (50), достаточно только липшицевости и выпуклости функций F(x) Этот результат доказан в теореме 4 12

В разделе 4 6 решение задачи обратной дополнительности (13), (14) сводится к поиску седловой точки (х*,и*) — (х(и*), и(и*)) функции Лагранжа

задачи ВП (13) при фиксированном параметре у = и* В случае дифферен-цируемости /о (ж, у) и Р(х) необходимые и достаточные условия минимума и максимума функции Лагранжа выписываются в виде операторных уравнений

и* = тг+(и* + а(Г(х*) - Ри*)), х* = 7гх{х* - а(УхМх*,и*) + (и*)тУР(х*)), для решения которых предлагается неявная схема проекции градиента с прогнозом по прямым и двойственным переменным

г?1 = тг+(ип + а(Р(хп) - РгГ1)), х» = пх(хп - а^,/о(®п,гГ») + (З»)^^®"))), , ,

хп+1 = тгх(хп - а(Х?х/о(хп,йп) + (г^У^ж"))), 1 ;

ип+1 = п+(ип + ог(Р(®") - РЯ1))

Теорема 4 13. Если решение задачи отыскания точки равновесия (12) существует и функция /о(х,и) удовлетворяет условию монотонности (50) на выпуклом замкнутом множестве X, функции /о(к, и) и F(a:) выпуклые и дифференцируемые по переменной х, матрицы \7х/0(х, и) и VР(х) удовлетворяют условиям Липшица по переменной х с константами Ьо и Ь\ соответственно, Г(х) удовлетворяет условию Липшица с константой Ь, кроме того, ||гб™|| < С, тогда последовательность {(хп, и")}, порожденная прогнозным методом проекции градиента (51) с выбором длины шага из условия а < 1/у/2(£о + С2Ь\)2 + £2, сходится монотонно по норме к одному из решений х* задачи обратной дополнительности (13), (14)

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

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

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

хтШх шш, Нх>г° хвХ (52)

Здесь

7П

X - множество вида {х | £ хг — 1, хъ > 0, г — 1, , га}, где хъ - доля

г=1

стоимости г-го актива в общей стоимости портфеля,

К - диагональная матрица размером т. х га, на диагонали которой стоят величины гг - ожидаемые доходности г-го актива (г, = Мр„ где рг - случайная величина, моделирующая доходность г-го актива, М - знак математического ожидания),

г° - вектор, элементами которого являются величины = г = 1, . ,га, где йг - желаемый доход г-го актива, Л - общая стоимость портфеля, IV - матрица, в которой элемент 'шг] является коэффициентом ковариации между доходностями г-го и ]-го активов, юг} = М-{рг—гг)(р2~г3) — соу(рг,р}) При завышенных требованиях на желаемый доход ограничения становятся несовместными, в этом случае задача (52) является несобственной Коррекция несобственной задачи проводится с помощью задачи дополнительности

Ру > (г° - Их), у > 0, уТРу = ут(г° - Их) (53)

и задачи обратной дополнительности

хтЦ?х + ут(г°-~Их) ->■ тш, х е X, (54)

Новизна использования обратной задачи (54) в задаче коррекции состоит в том, что вместе с задачей оптимальной коррекции решается задача, которая аппроксимирует исходную несобственную задачу (52)

В прототипе торговой системы были реализованы предложенный подход, классическая двухэтапная модель сюхасги ческою программирования и базовый портфель Результаты вычислительного эксперимента содержатся в приложении и позволяют сделать вывод об эффективности применения предложенной параметрической модели Исследования использованы в ОАО Банк "Соотечественники"(г Омск) при анализе процессов распределения инвестором определенной суммы денег по различным альтернативным вложениям и могут применяться в торговых предприятиях при разработке систем механической и автоматической торговли

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

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

Основные научные результаты

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

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

2 Предложен новый параметрический метод для исследования решений в задачах оптимизации Метод допускает отсутствие разрешимости в соответствующих моделях Основой метода являются решения задач обратной дополнительности для соответствующих параметрических систем неравенств

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

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

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

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

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

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

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

I Зыкина А В Параметрическое обобщенное решение в линейной векторной оптимизации // Кибернетика и системный анализ - 2001 - № 1 - С 177-181

2. Зыкина А В Алгоритм для задачи лексикографической оптимизации // Автоматика и телемеханика - 2004 - № 3 - С 10-16

3 Зыкина А В Обобщенное решение для интерактивной процедуры // Кибернетика и системный анализ - 2004 - № 2 - С 153-161

4 Зыкина А В Обратная задача оптимизации и задача Лагранжа // Омский научный вестник - 2005 - № 2(31) - С 81-84

5 Зыкина А В Обратная задача для линейной задачи дополнительности // Омский научный вестник - 2005 - № 3(32) - С 77-80

6 Зыкина А В Последовательная оптимизация для многокритериальной задачи // Экономика и математические методы - 2006 - Т 42, № 1 - С 110-118

7 Зыкина А В Многокритериальный подход к коррекции противоречивой задачи квадратичного программирования // Омский научный вестник -2006 - № 1(34) - С 75-79

8 Зыкина А В Обратная дополнительность постановки, методы, приложения // Научный вестник НГТУ - 2006 - № 2(23) - С 91-104

9 Зыкина А В Обобщенная двойственность для задачи математического программирования // Омский научный вес i ник -2006 -№8(44) -С 60-65

10 Зыкина А В Построение обобщенного решения линейной системы неравенств // Оптимизация Сб науч тр - Новосибирск ИМ СО АН СССР, 1988 -Вып 43(60) - С 11-25

II Зыкина А В Параметризация в несобственных задачах линейного программирования // Дискретная оптимизация и анализ сложных систем Сб науч тр - Новосибирск ВЦ СО АН СССР, 1989 - С 56-61

12. Зыкина ABO вариационном подходе к решению задачи математического программирования // Алгебра, геометрия, анализ и математическая физика Тр 12-й Сибирской школы - Новосибирск ИМ СО РАН, 1999 - С 68-73

13 Зыкина А В Обобщенный подход для решения линейных векторных задач /'/ Доклады СО АН ВШ - 2000 - № 2 - С 16-22

14 Зыкина А В Обобщенное решение при ограничениях / / Математическое программирование Труды XII Байкальской междунар конф "Методы

оптимизации и их приложения" - Иркутск ИСЭМ СО РАН, 2001 - Том 1 -С 324-329

15 Зыкина А В Анализ решений в противоречивых моделях оптимального планирования // Доклады СО АН ВШ - 2001 - № 1(3) - С 11-16

16 Зыкина А В Алгоритм последовательной оптимизации / / Доклады СО АН ВШ - 2003 - №2(8) - С 36-43

17 Зыкина А В , Канева О Н Обобщенное решение для задачи математического программирования с нечеткими исходными данными // Доклады АН ВШ РФ - 2004 -№2(3) - С 34-40

18 Зыкина А В Обратная задача для параметрической нелинейной задачи дополнительности // Прикладная математика и информационные технологии Сб науч и метод тр - Омск ОмГТУ, 2005 - С 27-35

19 Зыкина А В Решение обратной нелинейной задачи дополнительности // Математическое программирование Труды XIII Байкальской междунар школы-семинара "Методы оптимизации и их приложения" - Иркутск ИСЭМ СО РАН, 2005 - Том 1 - С 215-220

20 Зыкина А В , Шамрай Н Б Проективный метод для систем неравенств ,// Доклады АН ВШ РФ - 2005 - № 1(4) - С 36-43

21 Зыкина А В Обратная задача дополнительности для коррекции задачи математического программирования // Проблемы теоретической и прикладной математики Труды 37-й Региональной молодежной конференции -Екатеринбург УрО РАН, 2006 - С 372-376

I

Печатается в авторской редакции ИД №06039 от 12 10 2001

Подписано в печать 05 09 07 Формат 60 X 84 1/16 Отпечатано на дупликаторе Бумага офсетная Уел печ л 2 Уел -изд л 2 Тираж 100 экз Заказ 649

Издательство ОмГТУ, Омск, пр Мира, 11, т 23-02-13 Типография ОмГТУ

Предисловие

Введение

1. Задача обратной дополнительности

1.1. Обратная дополнительность для задачи оптимизации

1.2. Разрешимость задачи обратной дополнительности

1.3. Обратная дополнительность в модели дифицита ресурсов

1.4. Обратная дополнительность и условия Куна-Таккера

2. Обратная дополнительность в несобственных задачах

2.1. Общая схема коррекции несобственных задач МП

2.2. Задача коррекции для системы неравенств.

2.3. Коррекция несобственных задач ЛП

2.4. Частные случаи коррекции несобственных задач ЛП

2.5. Коррекция несобственных задач КП

3. Обратная дополнительность в векторной оптимизации

3.1. Обратная дополнительность для решения задачи МП

3.2. Обратная дополнительность с ограничениями

3.3. Задача целевого программирования.

3.4. Модель последовательной оптимизации.

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

4. Итеративные методы решения обратной задачи

4.1. Непрерывная траектория для обратной дополнительности

4.2. Метод оценочной функции

4.3. Градиентный метод для линейной дополнительности

4.4. Модифицирований градиентный метод.

4.5. Экстрапроксимальный метод.

4.6. Прогнозный метод проекции градиента.

5. Решение прикладных задач

5.1. Задача стохастического программирования.

5.2. Формирование портфеля ценных бумаг.

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

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

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

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

Цель работы

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

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

Методы исследования

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

Содержание диссертационной работы

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

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

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

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

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

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

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

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

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

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

Рассматриваются вопросы, связанные с вырожденностью решения линейной задачи дополнительности, предлагается прием преодоления вырожденности, вводится понятие е—вырожденности.

Доказаны сходимости алгоритмов, получены оценки скорости сходимости.

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

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

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

Научная новизна

Научную новизну работы образуют перечисленные ниже основные результаты (защищаемые положения), изложенные в соответствующих разделах диссертации (более подробно защищаемые положения рассмотрены в разделе "Заключение"):

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

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

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

Практическая значимость

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

Кроме того, построенные параметрические модели для задач принятия решений и разработанные алгоритмы для их решения используются в учебных процессах в Омском государственном техническом университете и в Омском государственном университете в дисциплинах "Теория принятия решений", "Методы оптимизации", "Несобственные задачи математического программирования", "Противоречивые модели оптимального планирования", в аспирантских диссертациях, в курсовых и дипломных проектах, а также при моделировании практических задач, выполняемых в рамках госбюджетных научно-исследовательских работ ОмГТУ (регистрационные номера НИР 1.4.01.Ф, 7.04.Ф).

Апробация

Результаты работы докладывались на международных, межрегиональных и региональных научных конференциях, среди которых:

Международные: "Проблемы оптимизации и экономические приложения" (Омск, 1997); "Динамика систем, механизмов и машин" (Омск, 1997, 1999, 2002); ИНПРИМ-1998 (Новосибирск, 1998); конференция по исследованию операций (Новосибирск, 1998); конференция по анализу и геометрии, посвященная 70-летию академика Ю.Г. Решет-няка (Новосибирск, 1999); "Методы оптимизации и их приложения" (Иркутск-Слюдянка, 2001, Иркутск-Северобайкальск, 2005 ).

Межрегиональные и региональные: Всероссийская научная конференция "Математическое программирование и приложения" (Екатеринбург, 1999, 2003, 2007); Всероссийская научная конференция "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2001); Российская конференция "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004); "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006); 37-я Региональная молодежная конференция "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006); Седьмой Всероссийский симпозиум "Стратегическое планирование и развитие предприятий" (Москва, 2006).

В целом материалы диссертации докладывались на научных семинарах кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета под председательством профессора Ф.П. Васильева (Москва, 2007), отделения информатики и прикладной математики механико-математического факультета Южно-Уральского государственного университета под председательством профессора Л. Б. Соколинского (Челябинск, 2007), отделения математического моделирования НИИ математики и механики им. Н.Г. Чеботарева Казанского государственного университета под председательством профессора А.В. Лапина (Казань, 2004, 2006), отдела прикладных проблем оптимизации Вычислительного центра им. А.А. Дородницына РАН под председательством академика Ю.Г. Евтушенко (Москва, 2006), а также неоднократно в Омском государственном техническом университете.

Публикации

По теме диссертационной работы опубликовано 47 работ, среди них:

- статьи из ведущих рецензируемых научных журналов и изданий перечня ВАК, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук - 9;

- статьи в периодических изданиях СО РАН, СО РАН и РАН ВШ - 9;

- статьи в сборниках СО РАН, в вузовских сборниках и в трудах конференций - 8;

- тезисы докладов в материалах конференций - 21.

Личный вклад автора. Все основные результаты получены автором лично. В совместной работе [93] аспиранткой ОмГТУ Каневой О.Н. разработан алгоритм решения задачи МП с нечеткими исходными данными, в работе [95] аспиранткой ОмГТУ Шамрай Н.Б. разработан проективный метод решения систем неравенств. Указанные результаты соавторов в диссертационную работу не включены.

Введение

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

Особенно эффективно использование параметризации для решения несобственных задач математического программирования (НЗ МП), активное исследование которых ведется в Уральском отделении РАН под руководством академика И.И. Еремина [13-18]. Несобственные задачи в общем случае — это задачи, не обладающие решением в силу тех или иных причин. Для задач МП понятие несобственных задач можно сформулировать более точно: это задачи, не обладающие свойством одновременной разрешимости прямой и двойственной задач и совпадения их оптимальных значений [13, 17]. Простейшим (и одновременно наиболее важным и часто возникающим в прикладных задачах) случаем несобственности задачи МП является несовместность системы ограничений прямой задачи при совместности системы ограничений двойственной задачи. Причем, как только при некотором приращении в правой части система ограничений становится совместной, задача становится разрешимой. Это так называемые несобственные задачи 1-го рода [13, 15, 16].

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

С : inf{/o(z) | Ш < 0,., fm(x) < 0, ж G Rn}. (0.1)

Здесь функции /о, /ь ., fm : Rn —> R в общем случае — выпуклые. Вводится класс параметрических задач

С[у] : inf{/oM(aO I fi[y]{x) < 0,., fm[y](x) < 0, х £ Rn}. (0.2) по параметру у Е U, где U — некоторое конечномерное пространство, причем для некоторого параметра у = уо G Y, Y С [/, выполняется равенство С [у о] = С. Это означает, что одна из задач (0.2) совпадает с исходной задачей (0.1). Пусть а — некоторое свойство задачи (0.2) (к примеру, разрешимость). Определяется множество параметров Ya СУ, для которых задача С [у] обладает свойством и. На множестве Ya определяется функция ф : Ya R1 называемая критерием или функцией качества аппроксимации (коррекции). В результате возникает задача оптимальной аппроксимации (коррекции):

К : min{ф(у) | у G Ya}. (0.3)

Формальный содержательный смысл задачи (0.3) состоит в выборе из множества параметров Ya наилучшего элемента у в смысле некоторого критерия ф{у). Для исходной задачи С (0.1) решение задачи оптимальной коррекции К (0.3) означает следующее: пусть у б АгдК, тогда задача С [у] аппроксимирует исходную задачу С по критерию ф(у).

Таким образом, общая схема использования параметризации для решения НЗ МП (0.1) может быть записана тремя этапами:

0 этап. Для исходной задачи С (0.1) вводится параметризация с параметром у G У. При этом образуется класс параметрических задач С [у] (0.2). Выделяется множество параметров Уа СУ, для которых задача С [у] обладает свойством разрешимости а.

1 этап. Решается задача оптимальной коррекции К (0.3) с критерием ф(у). В результате из класса задач (0.2) выделяется некоторая задача С [у], выступающая в роли аппроксимирующей для исходной задачи С (0.1).

2 этап. Решается аппроксимирующая задача С [у], оптимальное решение которой х* принимается в качестве решения несобственной задачи С (0.1).

В основе рассмотренной коррекции НЗ МП лежит метод штрафных функций, или более общо — метод последовательного программирования [70, 126, 127]. Недостатком такого подхода является то, что хотя несобственная задача С и сводится к разрешимой С [у], но последняя может оказаться некорректной [2, 35, 131]. В связи с этим возникает необходимость в регуляризации несобственных задач [5, 6, 56, 57, 63, 64, 128]. Метод регуляризации, предложенный впервые А.Н. Тихоновым [129], основан на стабилизации задачи при помощи вспомогательного параметрического функционала — регуляризиру-ющего оператора [5, 35]. К другим методам для решения НЗ МП относятся методы итеративной аппроксимации [125], когда коррекция осуществляется одновременно с оптимизацией целевой функции исходной задачи, и методы дискретной аппроксимации [123, 124], использующие комитетные конструкции для решения несобственных задач.

Использование методов коррекции при решении ИЗ МП — это один аспект в исследовании несобственных задач, другой состоит в использовании теории двойственности, разработанной И.И. Ереминым для НЗ МП [17, 71]. С одной стороны, двойственность важна как основа теории МП. С другой стороны, двойственность является источником построения конструктивных численных методов решения задач МП (в частности, решение пары двойственных разрешимых задач можно заменить решением эквивалентной системы неравенств).

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

Если задача МП — результат моделирования конкретной экономической (производственной) ситуации, то двойственность и порождаемая двойственностью информация позволяют провести глубокий анализ моделируемой ситуации, выявить узкие места, тенденции изменения модели, выразив эти факторы в количественной форме [14, 16].

Для противоречивых (и, как следствие, неразрешимых) задач роль двойственности возрастает, так как численный анализ таких задач усложняется. Но для неразрешимых задач классическая схема формирования двойственных задач в прежнем виде становится бессодержательной, поскольку оптимальное значение каждой из пары двойственных задач либо отсутствует, либо равно бесконечности. Возникла необходимость расширения понятия двойственности на несобственные задачи. И.И. Еремин предложил следующую схему формирования двойственности для несобственных задач [17, 71].

Несобственной задаче С (0.1) и построенной для нее по классической схеме двойственности несобственной задаче С* по некоторой единой схеме параметризации ставятся в соответствие собственные (разрешимые) задачи D и D& . При этом задачи D и D& выступают в роли аппроксимирующих (в некотором смысле) для задач С и С*. Задачи D и D* построены так, что они связаны между собой следующими свойствами: (D#)# = D, opt D = opt D*. Указанными свойствами обладают и пары двойственных задач в классической схеме двойственности для разрешимых задач.

Таким образом, работа с противоречивыми моделями и несобственными задачами приводит к различным конструкциям, которые связаны с теми или иными видами параметризации и соответствующей коррекцией, приводящими к непротиворечивым собственным моделям. Следует, однако, заметить, что если бы все дело сводилось к корректированию с помощью некоторой параметризации противоречивой модели, к преобразованию ее в непротиворечивую и дальнейшей работе уже с непротиворечивой моделью, то, по существу, не имелось бы никакого принципиально нового момента. Более того, чаще всего содержательный смысл и значение имеет именно исходное противоречивое описание объекта или ситуации, а не получаемые в результате коррекции непротиворечивые модели [12, 14]. С учетом этого в диссертации построена новая конструкция параметризации - обратная дополнительность -основанная на аппарате задач дополнительности. Предлагаемые в диссертации приемы параметризации построены так, что соответствующая коррекция осуществляется одновременно с оптимизацией исходной противоречивой (или несобственной) задачи. При этом вводимая параметризация пригодна и для решения непротиворечивых задач.

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

Одной из первых работ, посвященных теории линейных неравенств, является сборник статей [22]. В работах С.Н.Черникова теория линейных неравенств получила глубокое и всестороннее развитие [37]. В основу теории был заложен принцип граничных решений, который используется при решении вопросов о совместности конечных систем линейных неравенств и о существовании у них решений с теми или иными свойствами. Из принципа граничных решений выводятся все основные теоремы, относящиеся к конечным системам линейных неравенств, и наиболее важные теоремы теории линейного программирования.

Одним из первых методов решения систем линейных неравенств является релаксационный метод Моцкина-Агмона [134, 150], который позволяет находить хотя бы одно решение совместной системы линейных неравенств. В основе метода лежит практически легко реализуемая операция проектирования на полупространства, отвечающие неравенствам системы. Подход к решению систем линейных неравенств, состоящий в последовательном исключении переменных, детально разработан С.Н.

Черниковым [133]. И.И. Еремин распространил метод Моцкина-Агмона на случай системы выпуклых замкнутых множеств [66, 67, 68] и создал релаксационные методы нахождения решений систем линейных и нелинейных неравенств, в основе которых лежат исследования автора по М-фейеровским отображениям и итерационным процессам фейеровского типа [8, 69].

Естественным обобщением развитого А.Н. Тихоновым [130, 132] способа регуляризации для решения систем линейных алгебраических уравнений являются предложенные В.А. Булавским [4, 60, 61, 62] методы стационарной релаксации для решения систем неравенств (в общем случае несовместных). В методах В.А. Булавского параметрическая развязка для несовместности используется путем введения в правую часть подправки, зависящей от параметров. Введение параметрической подправки позволяет, с одной стороны, ввести понятие решения для случая несовместной системы, с другой стороны, разработать достаточно широкий класс методов типа метода последовательных приближений, пригодных для решения как несовместных, так и совместных систем неравенств. Методы стационарной релаксации основаны на использовании аппарата линейных задач дополнительности [137, 139].

Задачи дополнительности интересны прежде всего их приложениями. Это транспортные и экономические задачи, многочисленные задачи из физики. К примеру, равновесие транспортных потоков и модели экономического равновесия, баланса спроса и предложения, задача выбора портфеля ценных бумаг и задачи, возникающие при расчете механических нагрузок на упруго-пластичные конструкции, структурная механика, при исследовании задач которых возникли различные постановки как непараметрических, так и параметрических задач дополнительности [И, 23, 58].

Классическая задача дополнительности состоит в нахождении пары связанных некоторой определенной функциональной зависимостью точек со и у в пространстве Rm, у которых все координаты неотрицательны и в каждой паре соответствующих координат не более, чем одна величина отлична от нуля. Рассмотрим принятые постановки [1, 32, 59, 142, 154] линейных и нелинейных, параметрических и непараметрических, в том числе обобщенных задач дополнительности.

Произвольная нелинейная задача дополнительности NCP(P) состоит в следующем: = Р{у) , и > 0 , у > 0 , (0.4) утсо = 0 , (0.5) где Р : Rm —> Rm — заданное нелинейное отображение, а пара векторов со, у £ Rm определяет решение нелинейной задачи дополнительности (0.4), (0.5). При этом обычно для краткости решением называют вектор у, а нелинейную задачу дополнительности (0.4), (0.5) записывают в более компактной форме

Р(у)> 0, у> 0, (0.6) утР(у) = 0 . (0.7)

Геометрически нелинейная задача дополнительности (0.4), (0.5) (или задача (0.6), (0.7)) состоит в поиске неотрицательного вектора у € К171 такого, что образ Р{у) также неотрицателен и ортогонален вектору у. Содержательно условия (0.5) (или (0.7)) аналогичны условиям дополняющей нежесткости в теории двойственности. Действительно, если неравенства в (0.4) (или в (0.6)) принимать покординатно как сопряженные, то условия (0.5) (или (0.7)) означают, что в каждой паре сопряженных неравенств есть хотя бы одно равенство.

Обобщенная задача дополнительности возникает, когда неравенства в (0.4) рассматриваются в смысле частичной упорядоченности пространства Rm, задаваемой при помощи конуса К С Rm, то есть условие у > 0 заменяется на условие у £ К. Этот конус предполагается замкнутым и выпуклым, имеющим непустую внутренность. Тогда обобщенная задача дополнительности состоит в нахождении таких векторов у, со £ Rm, для которых выполняется ш = Р(у), уек, соеК\ утси = о, (0.8) где К* — сопряженный конус, К* — {си \ утсо >0, V у G К]. Результаты, справедливые для задачи (0.8), являются не слишком сложным обобщением соответствующих результатов для нелинейной задачи дополнительности (0.4), (0.5).

Более существенное обобщение нелинейной задачи дополнительности (0.4), (0.5) состоит в том, что Р : Rm —»■ Rm — многозначное отображение, сопоставляющее каждой точке у G Rm подмножества Р{у) С Rm. Тогда задача дополнительности состоит в нахождении векторов у, со £ Rm, таких что выполняется

W € Р{у) , У> о , w > 0 , утш = 0 . (0.9)

Параметрическое семейство задач по параметру х G Rn для нелинейной задачи дополнительности (0.9) задает параметрическую нелинейную задачу дополнительности вида: со G Р{у, х) , у > 0 , со > 0 , утсо = 0 . (0.10)

Здесь Р : Rm+n —» Rm — многозначное отображение, зависящее от внутренних параметров у G Rm и от внешних параметров х G Rn.

Для нелинейной задачи дополнительности (0.4), (0.5) соответствующая параметрическая нелинейная задача дополнительности будет иметь вид: со = Р{у, х) , ш > 0 , у > 0 , утсо = 0 . (0.11)

Еще одним важным обобщением нелинейной задачи дополнительности (0.4), (0.5) являются вариационные неравенства [21, 32, 42], которые служат удобной общей формой записи многих задач математической физики, а также ценового, транспортного и игрового равновесия и многих других задач [3, 142]. Кроме того, с задачей решения вариационного неравенства тесно связана задача о равновесии, которая является одной из основных задач в теории игр и ее приложениях [10, 24, 27, 112, 113]. Пусть У — непустое подмножество пространства Rm и отображение Р : У —> Rm — в общем случае многозначное. Задача решения вариационного неравенства VI(P, У) состоит в нахождении точек у* е У, таких что выполняется w* G Р(у*) , («Л у-у*)> 0 V у е у • (0.12)

Если отображение Р : У —» Rm — однозначное, то задача нахождения вариационного неравенства VI(P,Y) (0.12) запишется так:

Р{у*), У-У*)> о VyeY. (0.13)

Эквивалентность вариационных неравенств VI (Р: У) и задач дополнительности NCP(P) достигается в следующих случаях [32]:

1. Если У — выпуклый конус, то задача решения вариационного неравенства (0.13) эквивалентна обобщенной задаче дополнительности (0.8).

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

3. Если выпуклый конус У совпадает с неотрицательным ортантом пространства Rm, то задача решения вариационного неравенства (0.13) эквивалентна нелинейной задаче дополнительности (0.4), (0.5).

Линейная задача дополнительности LCP(P, q) состоит в отыскании векторов j/, ш G Rm таких, что выполняются следующие условия: ш = Py-q, ш > 0, у > 0, (0.14) у1 и = 0, (0.15) где Р — матрица размерности т xm, q Е Rm. Вектор q в аффинном отображении ш = и>(у) = Ру — q будем называть вектором правых частей задачи дополнительности (0.14), (0.15), это название связано с несколько другой эквивалентной постановкой LCP(P,q), состоящей в нахождении такого вектора у Е Rm, что выполняются следующие условия:

Ру>4, У> 0, (0.16) уТРу = yTq. (0.17)

В диссертации будем рассматривать линейную задачу дополнительности LCP(P,q) (0.14), (0.15) (или эквивалентную (0.16), (0.17)) и нелинейную задачу дополнительности NCP(P) (или NCP(P,q)), где Р(у) = Р{у) - q, в виде: cu = P(y)-q, у> 0, ути> = 0. (0.18)

Здесь Р : Rm —>• Rm — заданное отображение, вектор q G Rm — заданная правая часть нелинейной задачи дополнительности (0.18) (по аналогии с вектором q в линейной задаче дополнительности LCP(P, q) (0.14), (0.15). В частном случае, когда Р(у) = Ру, где Р — квадратная матрица соответствующего размера, получаем из нелинейной задачи NCP(P,q) (0.18) линейную задачу дополнительности LCP(P,q) (0.14), (0.15).

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

Первую теорему о существовании решений для нелинейной задачи дополнительности NCP(P) (0.4), (0.5) и первый вычислительный метод предложил Коттл [136]. При этом от отображения Р требуется дифференцируемость, и его якобиан VP (у) обладает следующим свойством положительной ограниченности: существует такое 5, 0 < 5 < 1, что для всех у £ Y, УС каждый главный минор матрицы VP (у) лежит между 5 и 1 — 5.

Для применимости метода Коттла делается предположение о невырожденности нелинейной задачи дополнительности NCP(P) (0.4), (0.5). Это означает, что в любом решении со, у Е К171 системы уравнений ш = Р(у) самое большее т из 2т компонентов могут обращаться в нуль. В соотношении со = Р{у) переменные со называются базисными, а переменные у — небазисными. Основной операцией в методе Коттла является обмен местами базисной и небазисной переменных сог, уг, который осуществляется следующим образом. Уравнение сог = Рг(у) (аналог ведущей строки в симплексном методе) разрешается относительно уг. Это всегда можно сделать, так как в силу положительной ограниченности якобиана VP (у) всегда выполняется дРг/дуг > 0 . Полученное выражение подставляется в уравнения coi = Pi(y), г ^ г. Новые базисные переменные для простоты снова обозначаются со, а небазисные у. Получается нелинейная задача дополнительности, в которой вместо Р{у) будет другая функция, скажем Р(у)- Если на очередной итерации получена функция Р(у) > 0, то получено решение задачи дополнительности. Доказано, если задача дополнительности (0.4), (0.5) невырожденная и отображение Р(у) имеет положительный ограниченный якобиан, то метод Коттла находит решение нелинейной задачи дополнительности NCP(P) (0.4), (0.5) за конечное число итераций [136].

Последующие работы в области нелинейных задач дополнительности посвящены выводу более общих теорем существования решения. Первый такой результат получил Карамардиан [144]: если непрерывное отображение Р сильно монотонно, то есть для любых двух точек у1 и у2 выполняются неравенства у2 - у1)т{р{у2) ~ р(у')) > р Из/2 - уЧ2, 0 > о, то существует единственное решение у* нелинейной задачи дополнительности NCP(P) (0.4), (0.5) (или задачи (0.6), (0.7)).

В доказательстве этого результата используется теорема Какутани о неподвижной точке [25].

В дальнейшем при установлении тесной связи решений нелинейной задачи дополнительности с существованием неподвижных точек и с вариационными неравенствами условие сильной монотонности было заменено на другие условия. Это оказалось возможным в силу того, что существование решений для вариационных неравенств (а значит, и для нелинейных задач дополнительности) опирается на факт существования неподвижной точки некоторого отображения, заданного в ограниченной области. Смысл условий состоит в том, чтобы найти такую ограниченную область и чтобы не дать неподвижной точке уйти в бесконечность при неограниченном расширении области (условия коэрцитив-ности) [149]. Несколько более общие условия существования решений нелинейной задачи дополнительности NCP(P) (0.4), (0.5) получил Кодзима [146], но эти условия недостаточно конструктивны. Тем же недостатком обладают полученные в работе [148] условия на функцию Р{у), при которых нелинейная задача дополнительности NCP(P) (0.4), (0.5) с отображением Р(у) = Р{у) — q имеет единственное решение у* = y(q) для любого q.

В диссертационной работе найдены условия для разрешимости нелинейной задачи дополнительности NCP(P), P(y) = P(y) — q, получены и исследованы свойства зависимости y(q), в частности, если q имеет, в свою очередь, некоторую функциональную зависимость q = F(x) [94, 97].

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

Функцию Р называют Р-функцией, если она обладает следующими двумя свойствами:

1) для любых у1, у2, у1 ^ у2 существует номер i = i(y1,y2), такой что выполняется неравенство uf-y}f(Pi(y2)-Pi(y1))>0]

2) для любого подмножества номеров J С {1,., п} и любого заданного вектора ш система уравнений i = Pi(y), Wi = yi, г E {1,. ,n} \ J, (0.19) разрешима относительно параметров у.

Следует заметить, что линейная "Р-функция — это Р-матрица, то есть матрица с положительными главными минорами. В [141] рассмотрен алгоритм, который обобщает алгоритм Мурти [153] для решения линейной задачи дополнительности на случай нелинейных "Р-функций.

Алгоритм состоит в следующем. Произвольным образом выбирается подмножество J0 С {1,. . •, п} . Пусть уже найдено подмножество Jk и ук — решение системы нелинейных уравнений (0.19) при и = 0 и J = Jk. Тогда определяется точка zk из условий: гк = Рг(ук), i Е {I,. ,n}\Jk, zk = yl г G Jk .

Если zk > 0, то решение найдено. В противном случае определяется наименьший индекс г, для которого zk < 0. Если при этом г е Jk, то полагают Jk+1 = Jk \ {г}, а при г ^ Jk полагают Jk+l = Jk U {г}. При практическом применении описанного метода на каждой итерации решается система нелинейных уравнений (0.19). Однако алгоритм использует лишь знаковую структуру решения, поэтому все решения, кроме последнего, могут находиться приближенно. Если Р(у) является ^-функцией, то нелинейная задача дополнительности NCP(P) (0.4), (0.5) имеет единственное решение (при этом непрерывность Р(у) не требуется), и алгоритм Мурти находит решение задачи дополнительности за конечное число итераций [141].

Рассмотрим еще один класс отображений — Л-функции [59].

Функция Р(у) называется Z-функцией, если для у2 > у1, и у2 = у] выполняется неравенство Рг(у2) < Р^у1)) .

Следует заметить, что линейная Л-функция — это Л-матрица, то есть квадратная матрица с неположительными внедиагональными элементами. При этом в случае непрерывности функции Р(у) и непустого множества У = {у\ у > 0, Р(у) > 0} методы решения линейной задачи дополнительности с Л-матрицей переносятся на нелинейный случай.

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

Основная теорема в теории линейных задач дополнительности утверждает [41, 143], что задача LCP{P,q) (0.14), (0.15) (или (0.16), (0.17)) имеет единственное решение у £ Rm для любого вектора правых частей q Е Rm тогда и только тогда, когда матрица Р является "Р-матрицей (имеет положительные главные миноры). Утверждение теоремы справедливо для матриц Р с положительно определенной симметризацией |(Р + РТ) [4,62].

Линейная задача дополнительности возникла изначально как задача выпуклого квадратичного программирования (КП) специального вида min{уТ{Ру -q) | Py>q, У > 0 } с нулевым оптимальным значением. Именно этот факт положил начало выделению задач дополнительности в самостоятельный класс [138].

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

Первым методом, предложенным для решения линейной задачи дополнительности, является алгоритм дополнительного ведущего преобразования Лемке [137], являющийся аналогом прямого симплекс-метода для системы уравнений со = Ру + dyo — q, взятой из расширенной задачи дополнительности вида со = Ру + dy0 - q , и> > 0 , 2/0 > о, у> 0, ум = 0, г = 1,. ., ш, где d — произвольный вектор соответствующей размерности (например, d = (1,., 1) ), уо — вспомогательная скалярная переменная, yi, coi — взаимно дополнительные переменные. На первой итерации алгоритма Уг = 0, i — 1,., т, а скалярная переменная > 0 выбирается из следующих условий: coi > 0, для г = 1,. ,т, и для одного номера г £ {1,. , га} выполняется равенство сог — 0. В результате получается начальное базисное решение, в котором базисными переменными являются уо и coi, г = 1,. ,т, кроме сог. На каждой следующей итерации алгоритма одна из небазисных переменных увеличивается (на первой итерации это переменная уг) или неограниченно (в этом случае алгоритм останавливается, не получив решения задачи), или до тех пор, пока одна (в предположении о невырожденности) из базисных переменных не обратится в нуль. В последнем случае на следующей итерации должна увеличиваться переменная, дополнительная к той, которая на предыдущей итерации вышла из базиса. Когда из базиса выводится переменная уо, получается решение задачи дополнительности. Что касается числа итераций в методе Лемке, то известно, что решение задачи линейного программирования с неотрицательной матрицей при помощи метода Лемке в 2-3 раза эффективнее обычного симплекс-метода [59].

Для ^-матриц (с неположительными внедиагональными элементами) метод Лемке работает как обычный симплекс-метод для следующей задачи линейного программирования [152] у0 -> min, Py + dy0-q> 0, у0 > 0, у > 0.

Для Z-матриц с множеством У = {у \ у > 0, Ру — q > 0} ф 0 разработаны достаточно эффективные итерационные методы [23, 58, 135]. Так метод, предложенный в работе [135], находит решение задачи дополнительности не более чем за т шагов. Алгоритм метода состоит в следующем. На первой итерации J1 — пустое подмножество номеров {1 ,.,т}. На к-й итерации находится решение системы уравнений Шг = 0, i е Jk, yi = 0, i ^ Jk, где сOi = (Ру — q)i, после чего образуется новое множество номеров Jh+l = Jk U {г\и>к < 0} и вычисления повторяются.

Для линейной задачи дополнительности LCP(P, q) с "Р-матрицей следует отметить два метода — метод Коттла-Данцига [137] и метод Мурти [153], которые в дальнейшем были обобщены на нелинейную задачу дополнительности. В методе Коттла-Данцига на каждой итерации находятся вектора у и и>, такие что ио = Ру — q, у > 0, и для всех г е {1,., т} выполняются равенства y^i = 0. На первой итерации алгоритма у% = 0, i = 1,. ,т. Вычисления проводятся таким образом, чтобы число отрицательных компонент вектора ио убывало, для этого отрицательная переменная заменяется в базисе ее дополнительной. В методе Мурти на каждой итерации проверяются только условия yiUJi = 0, г = 1,., т.

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

Рассмотрим особенности сведения задач ЛП и задач КП к LCP(P, q) и вытекающие из этих особенностей свойства решений и методов для соответствующих задач LCP(P, q) [32].

Первый класс задач - задача Л П. Пусть прямая задача ЛП состоит в нахождении вектора z и минимума L таких, что

Az>b, z > О, l = cTz. (0.20)

Тогда в двойственной задаче ЛП находится вектор £ и максимум L такие, что

Ат( < с, С > 0, L = ЪТС (0.21)

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

Az - v = b, v > 0, г > 0,

0.22)

АтС + и = с, и> 0, С > 0.

Если прямая и двойственная задачи непротиворечивы, то из теории двойственности ЛП имеем, что min L = maxL, и для оптимальных решений г и С прямой и двойственной задач выполняется bT( = cTz. (0.23)

Далее покажем, что равенство (0.23) эквивалентно условию zTu + (Tv = 0. (0.24)

Действительно, рассмотрим преобразования, используя условия (0.22): сTAz = (T(b+v) = CTb + CTv, CTAz = (с- u)Tz = cTz - uTz.

Тогда

QTb + CTv = cTz - uTz (0.25) и, учитывая (0.23), получаем равенство (0.24). Обратно, пусть справедливо равенство (0.24). Тогда, учитывая справедливость равенства (0.25), получаем условие (0.23). В результате задача ЛП эквивалентна задаче отыскания векторов и, v, z, £ таких, что и > 0, v > 0, > о, С > о, сь: р = ( ~ " I. у = (: I (°-26) устанавливают соответствие между LCP(P1 q) (0.14), (0.15) и задачей ЛП (0.20), (0.21).

Второй класс задач - задача КП. Рассмотрим задачу КП в следующей постановке. Найти вектор -г и минимум С такие, что

Az > b, z> 0, С = cTz + \zTDz . (0.27)

В выпуклой задаче КП (матрица D неотрицательно определена) достаточными условиями для минимума задачи (0.27) являются условия Куна-Таккера г > 0, и > 0, С > 0, v > 0, zTu = 0, C,Tv = 0, или эквивалентно z > 0, и > 0, ( > 0, v > 0, zTu + (Tv — 0, где v — вектор дополнительных переменных для ограничений Az > 6, С и и — вектора множителей Лагранжа для ограничений Az > b и z > 0 соответственно, следовательно, вектора z, и, ( и v связаны равенствами и = Dz — Ат(^ + с, v = Az — b. Таким образом, задача КП сводится к поиску решения системы v = Az-b, z > 0, v > 0, u = Dz-AT£ + c, и> 0, С > 0, (0.28) zTu + (Tv = 0.

Вводя обозначения, аналогичные обозначениям для задачи ЛП, получаем эквивалентность задач (0.28) и LCP (0.14), (0.15).

Обсудим теперь свойства решений и применимость алгоритма дополнительного ведущего преобразования Лемке для решения полученных линейных задач дополнительности LCP(P, q).

Рассмотрим задачу дополнительности для задачи ЛП. Матрица является сильно коположительной. Действительно, в силу структуры (бисимметричная матрица с нулевыми диагональными блоками) матрица Р является неотрицательно определенной, и следовательно, сильно коположительной. В предположении невырожденности алгоритм дополнительного ведущего преобразования Лемке останавливается за конечное число шагов. Если система уравнений и неравенств (0.22), составленная из ограничений прямой и двойственной задач ЛП (0.20), (0.21), является совместной, то алгоритм Лемке приводит к полному базисному допустимому решению LCP(P,q), и мы получаем в результате решение пары двойственных задач ЛП (0.20), (0.21). Если же система (0.22) несовместна, то получаем пустую допустимую область в прямой и двойственной задачах ЛП (0.20), (0.21), либо в одной из пары двойственных задач, и алгоритм Лемке в этом случае останавливается при нахождении луча.

Рассмотрим разрешимость задачи дополнительности для задачи КП. Матрица является сильно коположительной в силу бисимметричной структуры матрицы Р и неотрицательной определенности матрицы D (для выпуклой задачи КП). А значит, и в этом случае в предположении невырожденности алгоритм дополнительного ведущего преобразования Лемке останавливается за конечное число шагов. Если система неравенств v = Az-b, z > 0, v > О,

0.29) и = Dz- АтС + с, и > 0, С > 0, для задачи КП совместна, то по алгоритму Лемке получаем полное базисное допустимое решение для LCP(P, q) и одновременно решение задачи КП (0.27) и двойственной к ней задачи. В случае остановки алгоритма Лемке при нахождении луча в силу сильной коположительности матрицы Р система неравенств (0.29) для задачи КП несовместна. Если при этом допустимая область задачи КП непустая, то остановка при нахождении луча означает, что оптимальное решение задачи КП неограничено, иначе - допустимая область задачи КП пустая.

Еще один класс задач, исследуемых в диссертации — это обратные задачи. Важность этого класса задач обусловлена тем обстоятельством, что сложные содержательные задачи могут быть записаны как обратные задачи для известных, хорошо изученных классов задач. К примеру, модель экономического равновесия Эрроу-Дебре является обратной (векторной) задачей оптимизации [24, 33].

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

Из определения следует, что имеется некоторый произвол в том, какую из двух задач называть прямой, а какую — обратной. Обычно более простая или лучше изученная задача называется прямой [65]. Исследование и решение обратных задач можно встретить у многих авторов (А.С. Антипин, Я.М.Берщанский, В.П. Булатов, В.В. Васин, Е.Г. Голь-штейн, Л.А. Истомин, И.В. Коннов, Е.С. Левитин и др.).

В работе А.С. Антипина [45] обратная задача формулируется как система различных по природе задач. Так обратная задача выпуклого программирования определяется следующим образом: для заданных скалярной функции f(x,y) и векторной функции Go(x,y), выпуклых относительно переменных х G X, где X — выпуклое множество, и векторных функций G\(x,y) и G2(x,y) требуется определить пару векторов х*,у*, которая удовлетворяет системе, содержащей экстремальное включение, уравнения и (или) неравенства: х* G Argmin{f(x,y*)\G0(x,y*) < 0, я G X], у* G У, (0.30)

Gx(x\y*) = 0, G2{x\y*)< 0. (0.31)

Другими словами, в параметрическом относительно вектора у семействе задач выпуклого программирования (0.30) требуется выбрать параметр у — у* и отвечающий ему оптимум х = х* такие, чтобы выполнялась система уравнений и (или) неравенств (0.31).

У В.П. Булатова [28] в качестве обратной задачи (0.31) выступает параметрическая относительно параметра х оптимизационная задача, внутренним параметром которой является вектор у.

В работе JI.A. Истомина [107] приводится следующая формулировка обратной задачи. Для параметрической относительно вектора у задачи выпуклого математического программирования вида

С[у] : max{f{x,y)\G0(x,y) < 0}, у G У, (0.32) найти такие параметры у G У, для которых двойственные оценки и задачи С [у] (0.32) по некоторому выбранному критерию лучше всего отвечали бы условию у1 = и, где у1 - часть вектора параметров у.

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

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

Заключение

Основные научные результаты

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

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

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

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

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

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

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

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

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

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

1) результаты численных экспериментов для моделирования процесса формирования портфеля ценных бумаг;

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

Использование и дальнейшее развитие результатов исследований

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

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

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

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

- Исследование методов решения задач дополнительности.

- Задача МП для обобщенного решения при ограничениях.

- Алгоритм построения множества обобщенных решений.

- Метод штрафных функций в несобственных задачах МП.

- Задача векторной оптимизации с ограничениями.

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982. - 583 с.

2. Бакушинский А.Б., Гончарский А.В. Итеративные методы решения некорректных задач. М.: Наука, 1989. - 128 с.

3. Байокки К., Капело А. Вариационные и квазивариационные неравенства. Приложение к задачам со свободной границей. М.: Наука, 1988. - 448 с.

4. Булавский В.А. Методы релаксации для систем неравенств. Новосибирск: НГУ, 1981. - 82 с.

5. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002. - 824 с.

6. Васильев Ф.П. Численные методы решения экстремальных задач. -М.: Наука, 1988. 552 с.

7. Васильев Ф.П. Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998. - 176 с.

8. Васин В.В., Еремин И.И. Операторы и итерационные процессы фей-еровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. - 211 с.

9. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. - 320 с.

10. Голынтейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука, 1989 - 400 с.

11. Дюво Г., Лионе Ж.Л. Неравенства в механике и физике. М.: Наука, 1980. - 383 с.

12. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

13. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. - 336 с.

14. Еремин И.И. Противоречивые модели оптимального планирования.- М.: Наука, 1988. 160 с.

15. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. - 248 с.

16. Еремин И.И., Мазуров Вл.Д, Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрО РАН, 2000. -280 с.

17. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001. - 180 с.

18. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. -Новосибирск: ИМ СО РАН, 1999. 268 с.

19. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: АН СССР, 1959. - 344 с.

20. Карманов В.Г. Математическое программирование: учеб. пособие.- 4-е изд., перераб. и доп. М.: ФИЗМАТЛИТ, 2000. - 264 с.

21. Коннов И.В. Методы решения конечномерных вариационных неравенств: курс лекций. Казань: ДАС, 1998. - 101 с.

22. Линейные неравенства и смежные вопросы: сб. под ред. Куна и Таккера. М.: ИЛ, 1959. - 470 с.

23. Мееров М.В., Литвак Б.Л. Оптимизация систем многосвязного управления. М.: Наука, 1972. - 344 с.

24. Методы оптимизации в экономико-математическом моделировании: сб. под ред. Е.Г. Голыптейна. М.: Наука, 1991. - 448 с.

25. Никайдо X. Выпуклые структуры и математическая экономика. -М.: Мир, 1972. 517 с.

26. Нурминский Е.А. Математические основы теории финансовых рынков Владивосток: ДГУ, 2000. - 110 с.

27. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988. - 264 с.

28. Обратные задачи математического программирования. М.: ВЦ РАН, 1992. 155 с.

29. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: МГУ, 1984. - 296 с.

30. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Сов. радио, 1975. - 192 с.

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

32. Попов Л.Д. Введение в теорию, методы и экономические приложения задач о дополнительности. Екатеринбург: УрГУ, 2001 - 124 с.

33. Приоритетные результаты в области математического программирования. Информац. бюллетень АМП № 9. - Екатеринбург: УрО РАН, 2001. - 143 с.

34. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975. - 320 с.

35. Тихонов А.В., Арсенин В.Я. Методы решения некорректных задач.- 2-ое изд., перераб. и доп. М.: Наука, 1979. - 285 с.

36. Урясьев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. М.: Наука, 1990. - 184 с.

37. Черников С.Н. Линейные неравенства. М.: Наука, 1968. - 488 с.

38. Ширяев А.Н. Основы стохастической финансовой математики. В 2-х томах. - М.: ФАЗИС, 1998. - Т. 1 - 512 е., т. 2 - 1056 с.

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

40. Юдин Д. Б. Математические методы управления в условиях неполной информации. М.: Сов. радио, 1974. - 399 с.

41. Cottle R.W., Pang J.S., Stone R.T. The linear complementarity problem. Boston: Academic press, Inc., 1992.

42. Konnov I.V. Combined relaxation methods for variational inequalities.- Berlin etc.: Springer, 2001. 181 c.1. Статьи

43. Антипин А.С. Экстраполяционные методы вычисления седловой точки функции Лагранжа и их применение к задачам с блочно-сепарабельной структурой // Журнал вычислительной математики и математической физики. 1986. - T.l, № 1.-С. 150-151.

44. Антипин А.С. Методы решения систем задач выпуклого программирования // Журнал вычислительной математики и математической физики. 1987. - Т.27, № 3. - С. 368-376.

45. Антипин А.С. Обратная задача оптимизации: постановка задачи и подходы к ее решению // Обратные задачи математического программирования. М.:ВЦ РАН, 1992.

46. Антипин А.С. Управляемые проксимальные дифференциальные системы для решения седловых задач // Дифференциальные уравнения. 1992. - Т.28, № И. - С. 1846-1861.

47. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений // Журнал вычислительной математики и математической физики. 1995. - Т.35, № 5. - С. 688-704.

48. Антипин А.С. Вычисление неподвижных точек экстремальных отображений с помощью методов градиентного типа // Журнал вычислительной математики и математической физики. 1997. - Т.37, № 1. - С. 42-53.

49. Антипин А.С. Равновесное программирование: проксимальные методы // Журнал вычислительной математики и математической физики. 1997. - Т.37, № 11. - С. 1327-1339.

50. Антипин А.С. Равновесное программирование: методы градиентного типа // Автоматика и телемеханика. 1997. - № 8. - С. 125-137.

51. Антипин А.С. Решение вариационных неравенств со связанными ограничениями с помощью дифференциальных уравнений // Дифференциальные уравнения. 2000. - Т.36, № 11. - С. 1443-1451.

52. Антипин А.С. Методы решения вариационных неравенств со связанными ограничениями // Журнал вычислительной математики и математической физики. 2000. - Т.40, № 9. - С. 1291-1307.

53. Антипин А.С. О равновесной модели дефицита ресурсов // Нелинейная динамика и управление. 2005. - Вып. 5. - С. 1-9.

54. Антипин А.С. Экстрапроксимальный метод решения равновесных и игровых задач // Журнал вычислительной математики и математической физики. 2005. - Т.45, № 11,12. - С. 1969-1990, 2102-2111.

55. Антипин А.С. Экстрапроксимальный подход к вычислению равновесий в моделях чистого обмена // Журнал вычислительной математики и математической физики. 2006. - Т.46, J№ 10. - С. 17711787.

56. Астафьев Н.Н. Двойственная регуляризация задач линейного программирования, заданных последовательностью реализаций // Журнал вычислительной математики и математической физики. -1978. Т.18, № 5. - С. 1129-1138.

57. Астафьев Н.Н. Двойственная регуляризация задач линейного программирования (общий случай) // Методы оптимизации и распознавания образов в задачах планирования. Свердловск, 1980. - С. 3-12.

58. Беленький В.З. Некоторые модели оптимального планирования, основанные на схеме межотраслевого баланса // Экономика и математические методы. 1967. - Т.З, № 4 - С. 539-549.

59. Берщанский Я.М., Мееров М.В. Теория и методы решения задач дополнительности // Автоматика и телемеханика. 1983. - N2 6. -С. 5-31.

60. Булавский В. А. Релаксация в задачах с неравенствами // Оптимизация. 1979. - Вып. 23(40). - С. 32-40.

61. Булавский В.А. Квазилинейное программирование и векторная оптимизация // Доклады АН СССР. 1981. - Т. 257, № 4. - С. 788-791.

62. Булавский В.А. Обобщенные решения и регуляризация систем неравенств // Вычислительные методы линейной алгебры: труды Интитута математики. 1985. - Т.6. - С. 161-174.

63. Васильев Ф.П. О регуляризации некорректных экстремальных задач // ДАН СССР. 1978. - Т.241, № 5. - С. 1001-1004.

64. Васильев Ф.П. О регуляризации некорректных задач минимизации на множествах, заданных приближенно // ЖВМ и МФ 1980. -Т.20, № 1. - С. 38-50.

65. Голиков А.И. Об одной постановке обратной задачи нелинейного программирования // Обратные задачи математического программирования. М.: ВЦ РАН, 1992.

66. Еремин И.И. Итеративный метод для чебышевских приближений несовместных систем линейных неравенств // ДАН СССР. 1962. -Т. 143, № 6. - С. 1253-1256.

67. Еремин И.И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях // ДАН СССР. 1965. -Т.160, № 5. - С. 994-996.

68. Еремин И.И. Обобщение релаксационного метода Моцкина-Агмона // УМН. 1965. - Т.20, вып.2. - С. 183-187.

69. Еремин И.И. Методы фейеровских приближений в выпуклом программировании // Матем. заметки. 1968. - Т.З, № 2. - С. 217-234.

70. Еремин И.И. О задачах последовательного программирования // Сиб. мат. ж. 1973. - Т. 14, № 1. - С. 53-63.

71. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // ДАН СССР. 1981. - Т.256, № 2. - С. 272-276.

72. Зыкина А.В Построение обобщенного решения линейной системы неравенств // Оптимизация: сб. науч. трудов. Новосибирск: ИМ СО АН СССР, 1988. - Вып.43(60). - С. 11-25.

73. Зыкина А.В. Параметризация в несобственных задачах линейного программирования // Дискретная оптимизация и анализ сложныхсистем: сб. науч. трудов. Новосибирск: ВЦ СО АН СССР, 1989. -С. 56-61.

74. Зыкина А.В. Анализ решения в противоречивых моделях оптимального планирования // Динамика систем, механизмов и машин: материалы II Междунар. науч.-техн. конф. Омск: ОмГТУ, 1997. -Кн.З. - С. 33.

75. Зыкина А.В. Обобщенное решение в линейной векторной оптимизации // Междунар. Сибирская конф. по исследованию операций. -Новосибирск: ИМ СО РАН, 1998. С. 82.

76. Зыкина А.В. Обобщенный подход для решения линейных многокритериальных задач // Математическое программирование и приложения: информац. бюллетень АМП JV2 8. Екатеринбург: УрО РАН,1999. - С. 124-125.

77. Зыкина А.В., Пригнец О.Н. Несобственная задача стохастического программирования // Математическое программирование и приложения: информац. бюллетень АМП № 8. Екатеринбург: УрО РАН,1999. - С. 126.

78. Зыкина А.В. Об обобщенном решении в векторной оптимизации // Динамика систем, механизмов и машин: материалы III Междунар. науч.-техн. конф. Омск: ОмГТУ, 1999. - Кн. 2. - С. 344-345.

79. Зыкина А.В. О вариационном подходе к решению задачи математического программирования // Алгебра, геометрия, анализ и математическая физика: труды XII Сибирской школы. Новосибирск: ИМ СО РАН, 1999. - С. 68-73.

80. Зыкина А.В. Обобщенный подход для решения линейных векторных задач // Доклады СО АН ВШ. 2000. - № 2. - С. 16-22.

81. Зыкина А.В. О реализации метода взвешенных сумм // Моделирование неравновесных систем 2000: материалы III Всерос. семинара.- Красноярск: ИПЦ КГТУ, 2000. С. 98.

82. Зыкина А.В. Параметрическое обобщенное решение в линейной векторной оптимизации // Кибернетика и системный анализ. 2001.1. С. 177-181.

83. Зыкина А.В. Анализ решений в противоречивых моделях оптимального планирования // Доклады СО АН ВШ. 2001. - № 1(3). -С. 11-16.

84. Зыкина А.В. Обобщенное решение при ограничениях // Математическое программирование: труды XII Байкальской междунар. конф. "Методы оптимизации и их приложения". Иркутск: ИСЭМ СО РАН, 2001. - Том 1. - С. 324-329.

85. Зыкина А.В. Проблемы численной реализации алгоритма нахождения обобщенного решения // Дискретный анализ и исследование операций: материалы Росс. конф. Новосибирск: ИМ СО РАН, 2002.- С. 166.

86. Зыкина А.В. Обобщенное решение в методе последовательных уступок // Динамика систем, механизмов и машин: материалы IV Междунар. науч.-техн. конф., посвященной 60-летию ОмГТУ. -Омск: ОмГТУ, 2002. Кн. 2. - С. 165-166.

87. Зыкина А.В. О реализации метода последовательных уступок // Математическое программирование и приложения: информац. бюллетень АМП № 10. Екатеринбург: УрО РАН, 2003. - С. 119.

88. Зыкина А.В. Эффективность обобщенных решений в многокритериальной оптимизации // Проблемы оптимизации и экономические