Введение к работе
Актуальность темы Актуальность построения новых математических конструкций для моделирования, исследования и решения задач оптимизации обусловлена возрастающим количеством моделей и систем, имеющих различное описание и представление, что создает множество теоретических и алгоритмических проблем при использовании классических подходов для решения этих задач Математические модели сложных систем (и, как правило, противоречивых) наряду с внутренними параметрами содержат внешние параметры, отражающие влияние окружающей систему среды на процесс принятия решений В результате получаются параметрические модели, структура которых отличается от классических задач оптимизации Эффективное решение таких задач требует не только разработки новых методов для нахождения решений, но и принципиально новых подходов и новых математических конструкций для моделирования и для определения понятия решения таких задач В общем случае параметризация может использоваться двояким способом С одной стороны, параметры могут вводиться в решаемые задачи извне и служить для развязки их возможной несовместности В этом случае говорят о коррекции исходной задачи Для разрешимых задач такая параметризация позволяет также рассматривать само искомое решение как функцию от некоторых параметров, при этом с помощью параметризации можно задавать некоторые желаемые свойства для решения - это приводит к постановке обратной задачи С другой стороны, параметры могут использоваться в качестве вспомогательного средства для поиска итерационных точек, в том числе для поиска начальной точки В ряде случаев таким образом удается уменьшить количество вычислений или снизить размерность решаемой задачи, используя подходящие итерационные схемы для решения преобразованной задачи
Особенно эффективно использование параметризации для решения несобственных задач математического программирования (НЗ МП), активное исследование которых ведется в Уральском отделении РАН под руководством академика И И Еремина Несобственные задачи в общем случае-это задачи, не обладающие решением в силу каких-либо причин Для задач математического программирования (МП) понятие несобственных задач можно сформулировать более точно это задачи, не обладающие свойством одновременной разрешимости прямой и двойственной задач и совпадения их оптимальных значений
Параметризация и соответствующая коррекция несобственных задач
может осуществляться на основе разных подходов И И Еремин предлагает следующую схему коррекции НЗ МП Проводится параметризация исходной задачи и отыскивается параметр, обеспечивающий разрешимость задачи при найденном значении параметра При этом дополнительно можно оптимизировать (по некоторому критерию качества) получаемую в результате коррекцию задачи В основе предложенной коррекции НЗ МП лежит метод штрафных функций, или более общо - метод последовательного программирования
В методах стационарной релаксации В А Булавского для решения систем неравенств (в общем случае несовместных) параметрическая развязка для несовместности используется путем введения в правую часть подправки, зависящей от параметров Введение параметрической подправки позволило, с одной стороны, ввести понятие решения для случая несовместной системы, с другой стороны, разработать достаточно широкий класс методов типа метода последовательных приближений, пригодных для решения как несовместных, так и совместных систем неравенств
Основную трудность при решении противоречивых задач составляет тот факт, что чаще всего содержательный смысл и значение имеет именно исход-нос противоречивое описание рассматриваемой задачи, а не получаемые в результате коррекции непротиворечивые модели С учетом этого в диссертации построена новая конструкция параметризации - обратная дополнительность - основанная на аппарате задач дополнительности Предлагаемые в диссертации приемы параметризации построены так, что соответствующая коррекция осуществляется итеративно, одновременно с решением исходной противоречивой (или несобственной) задачи При этом вводимая в диссертации параметризация пригодна и для решения непротиворечивых (собственных) задач Такая параметризация используется, в частности, при решении систем неравенств (как совместных, так и несовместных) Интерес к этому классу задач связан с тем, что по своему предмету теория неравенств относится к самым основным и элементарным разделам математики, широко используемым в различных областях и приложениях В связи с этим разработка новых численных методов решения таких задач по-прежнему весьма актуальна
Актуальность использования обратной дополнительности как инструмента параметризации обусловлена также и тем, что задачи дополнительности являются обобщением классических постановок задач математического программирования Кроме того, задачи дополнительности представляют большой интерес благодаря их многочисленным приложениям (к примеру, равновесие транспортных потоков, вопросы ценового равновесия, баланса спроса
и предложения, выбор портфеля ценных бумаг) Исследованием и решением задач дополнительности занимались многие известные российские и зарубежные ученые ( В А Булавский, Я М Берщанский, В Г Жадан, И В Коннов, MB Мееров, ЛД Попов, ВИ Шмырев, S Agmon, RW Cottle, G В Dantzig, W S Dorn, P T Harker, I Kaneko, J S Pang и другие) При этом несмотря на то, что задачи дополнительности с их приложениями образуют большой самостоятельный раздел, задачи обратной дополнительности до сих пор еще не рассматривались
Обратная дополнительность, предложенная в диссертации, с одной стороны, представляет интерес как новая математическая конструкция, с другой стороны, большое значение имеет практическое применение обратных задач для моделирования, решения и исследования сложных содержательных задач С точки зрения математического моделирования обратные задачи - это чрезвычайно важный класс задач, поскольку модели сложных систем, содержащие внутренние и внешние параметры, как правило, приводят к конструированию обратных задач для известных классов задач С содержательной точки зрения в обратных задачах задаются дополнительные условия, позволяющие стабилизировать моделируемую ситуацию Исследованием обратных задач математического программирования занимались А С Антипин, Я М Берщанский, В П Булатов, В В Васин, Е Г Гольштейн, Л А Истомин, И В Коннов, Е С Левитин и другие
Критический обзор подходов к решению обратных задач математического программирования показывает невозможность, либо неэффективность прямого использования методов решения этого класса задач для решения задач обратной дополнительности В связи с этим представляется актуальной как адаптация известных, так и разработка новых численных методов для решения задач обратной дополнительности
Объектом исследования в диссертации являются как разрешимые, так и противоречивые (несобственные) задачи математического программирования, а также системы неравенств, задачи стохастического программирования и задачи векторной оптимизации
Цель работы Целью диссертационной работы является выделение нового класса обратных задач - задач обратной дополнительности, построение на этой основе новых параметрических моделей для несобственных задач математического программирования, систем неравенств, задач стохастического программирования, задач векторной оптимизации и разработка эффективных методов для решения содержательных задач исследования операций
Методы исследования В работе используется аппарат математического моделирования, выпуклого и нелинейного анализа, математического и стохастического программирования, векторной оптимизации, теории двойственности, теории задач дополнительности и вариационных неравенств, классической теории дифференциальных уравнений
Научная новизна работы характеризуется перечисленными ниже основными результатами - защищаемыми положениями (более подробно защищаемые положения рассмотрены в разделе "Заключение")
Выделен новый класс обратных задач - задачи обратной дополнительности
Построены новые параметрические модели для разрешимых и противоречивых задач, в том числе для систем неравенств, несобственных задач математического программирования, задач векторной оптимизации и некоторых специальных задач стохастического программирования
Для решения задач обратной дополнительности разработан градиентный метод с минимизацией оценочной функции, предложены экстраградиентные и экстрапроксимальные методы
Теоретическая ценность работы состоит в следующем
1 Найдены условия разрешимости задач обратной дополнительности,
определена структура множества решений
Разработаны новые схемы исследования и соответствующие методы для решения систем неравенств, несобственных задач математического программирования, задач векторной оптимизации и некоторых специальных задач стохастического программирования
Обоснована сходимость разработанных алгоритмов, получены оценки скорости сходимости, исследованы свойства решений содержательных задач исследования операций
Практическая значимость. Разработанный способ моделирования задач на основе параметризации использован при исследовании сложных задач принятия решений, в частности, в модели дефицита ресурсов, в стохастической задаче для формирования портфеля ценных бумаг Пакет программ для моделирования процесса формирования портфеля ценных бумаг использован в ОАО Банк "Соотечественники"(г Омск) при исследовании процессов распределения инвестором определенной суммы денег по различным альтернативным вложениям
Построенные параметрические модели и разработанные алгоритмы используются в учебных процессах Омского государственного технического университета и Омскою государственного университета, а также
при решении задач, выполнявшихся в рамках госбюджетных научно-исследовательских работ Омского государственного технического университета (регистрационные номера НИР 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 наименований
Похожие диссертации на Параметризация и обратная дополнительность в моделировании и решении оптимизационных задач
