Введение к работе
Актуальность темы. Направление в теории условной оптимизации, ізучающее несобственные (не удовлетворяющие основным соотношениям двойственности) задачи математического программирования (МП), появи-юсь в начале 80-х годов и имеет своим истоком работы П.И.Еремина, Зл.Д.Мазурова. 1 В случае линейного программирования (ЛП) несоб-;твешюсть задачи означает несовместность системы ограничений у пря-лой, или двойственной, или у той и другой задачи одновременно (соответственно говорят о несобственности 1-го, 2-го или 3-го рода).
Оформление нового направления отвечало в первую очередь потреб-юстям развития теории (аппроксимация и решение несовместных систем У1Я приложений в различных областях математики таких, как прибли-кение функций, задачи распознавания и идентификации, углубленное изучение проблем двойственности и т.п.). Вместе с тем в становлении нового управления сыграли большую роль и потребности экономических приложений. Последние требовали уточнения и развития положения о том, что їсякая теоретическая модель должна быть непротиворечивой.
Использование противоречивых моделей позволяет обеспечить большую гибкость и адекватность моделирования, дает возможность улучшить ;го адаптацию к требованиям практики. При поиске адекватной модели чожет оказаться целесообразным идти от варианта собственной модели ї несобственной за счет включения в модель не учитывавшихся ранее эграничений, а также всевозможных внешних и внутренних требований, эбязательных или желательных в той или иной мере для выполнения, а эт последней - уже к собственной, но на основе объективных процедур коррекции.
Важнейшими направлениями в проблематике несобственных задач (113) МП стали исследования по теории двойственности и методам оптимальной
'Еремин И.П., Мазуров В.Д. Нестационарные процессы математического программирования. - М.: Наука, 1979.
Еремин И.П., Мазуров В.Д., Астафьев П.II. Несобственные задачи линейного и выпуклого программирования. - М.: Наука, 1983.
LpcMiui \\Л\. Двоіи- iik-muxib для tuv oCv шейных .идлч .iuvu-ihw ;о \\ v-x-пуклого программирования // ДАН СССР. -1981. -Т.256. №2. -С.272-276.
коррекции для таких задач. Основная идея новой двойственности состоит в том, что исходной несобственной паре двойственных задач С а С* ставятся в соответствие определенным образом формируемые собственные задачи D и ># , связанные соотношениями двойственности друг с другом и в то же время определенным образом связанные с некоторыми параметрическими задачами С(6) и С* (6), выступающими в роли задач, аппроксимирующих исходные. С этими идеями тесно связан и принцип оптимальной коррекции (аппроксимации) несобственной задачи С, который предполагает согласовывать выбор в параметрическом семействе С(6) собственных представителей с дополнительным условием минимизации (максимизации) некоторой функции от 6 , трактуемой как критерий качества коррекции (аппроксимации). Этот критерий, впрочем, может иметь и более сложную структуру.
В настоящее время по теории и методам для НЗМП и их приложениям опубликован ряд монографий, обзоров, сборников статей, защищено несколько кандидатских и докторских диссертаций (В.Н.Фролов, П.Г.Романий, А.А.Ватолин). Работы И.И.Еремина (и Вл.Д.Мазурова) и его учеников (Н.Н.Астафьев, А.А.Ватолин, Л.Д.Попов, С.В.Плотников, В.Д.Скарин, С.П.Трофимов, В.Н.Фролов и др.) послужили стимулом к интенсификации исследований в этой направлении других авторов (В.А.Бу-лавский, А.И.Вересков, М.М.Ковалев, П.Г.Романий, М.Е.Салуквадзе, А.Л.Топчишвили, Н.В.Третьяков), в том числе зарубежных (It.Baumgart, К.Beer, J.N.Burke, H.J.Greenberg, O.L.Mangasarian, I.Marusciac и др.). Библиография по этой теме насчитывает более трехсот пятидесяти работ.
Настоящая работа включает в себя результаты, полученные автором при исследовании аппроксимативных свойств общих схем двойственности для НЗМП, а также посвящена распространению обсуждаемой проблематики на такие широкие классы оптимизационных постановок, как абстрактные минимаксные задачи и неразрешимые (несобственные) вариационные неравенства (и как их частный случай -задачи о дополнительности и поиска равновесия). Разработанная теория, методы и программное обеспечение применены к различным сложным противоречивым задачам прогнозирования, управления и планирования в экономике и технике.
Исторически вариационные неравенства и задачи о дополнительности появились в работах Ф.Хартмана, Дж.Стампаччи, Р.Коттла, Дж.Хабетле-ра, С.Лемке. В настоящее время эта проблематика превратилась за рубежем в жизнеспособную и плодотворную область исследований. Это объ-
[сняется по крайней мере тремя крупными научно-прикладными собы-иями. Первое - это развитие PIES (Система независимой оценки проектов) энергетической модели, предпринятое Американским министер-:твом энергетики в конце 70-х гг. Второе - публикации М.Смита и по-:ледователей, в которых задача о равновесии транспортных потоков бы-ia сформулирована как конечномерное вариационное неравенство. Вслед їм открылся широкий поток публикаций по различным моделям равно->есия: прогнозирование межрегиональных товарных потоков, равновесие ю Нэшу, прогнозирование цен на транспортные услуги. Наконец, третье событие - попытка М.Матиенсена решить задачу об общем равновесии Зальраса при помощи методов, развитых для решения нелинейных задач > дополнительности. Его успех подтолкнул других исследователей к применению этих методов для нахождения состояний равновесия в больших містемах.
Известные условия разрешимости различных микро- и макро-эконо-
кшческих моделей о равновесии в теоретическом плане выглядят вполне
естественно, но на практике вступают в конфликт с реальностью экономи
ческой и социально-политической жизни (на что, по-видимому, указыва
ют процессы роста безработицы, инфляции и т.п.). Поэтому перенос про
блематики неразрешимости (несобствености) на соответствующие модели
представляется актуальным. . .
Цель настоящей работы состоит в разработке теории и методов анализа и оптимальной коррекции несобственных задач оптимизации различных классов. При этом решаются следующие задачи.
-
Разработка теории и методов линейной коррекции несобственных выпукло-вогнутых минимаксных задач.
-
Разработка теории и методов оптимальной (в том числе нелинейной) коррекции несобственных обобщенных уравнений и вариационных неравенств для общих критериев качества.
-
Разработка численных схем, алгоритмического и программного обеспечения для методов оптимальной коррекции несобственных оптимизационных задач перечисленных типов (с приложением к конкретным оптимизационным моделям).
Методы исследования. Основным инструментом исследования сложит аппарат выпуклого анализа и теории линейных неравенств. Научная новизна состоит в следующем. 1. Сформулированы и изучены задачи оптимальной линейной коррек-
ции несобственных выпукло-вогнутых минимаксных задач (задач о седло-вой точке) для классического и минимаксного критериев качества коррекции. Предложены асимптотические по параметру методы аппроксимации таких задач собственными (разрешимыми) задачами, в которых процесс коррекции идет параллельно с процессом отыскания решения скорректированных задач. Обоснованы аппроксимативные свойства известных ранее и новых схем двойственности для несобственных задач линейного и выпуклого программирования.
-
Сформулированы и изучены задачи оптимальной коррекции неразрешимых обобщенных уравнений и конечномерных вариационных неравенств. Исследована структура множеств разрешимости как при линейном, так и при нелинейном типе параметризации исходного отображения. Построены методы их оптимальной коррекции относительно общих критериев вариационного типа (включающих в себя в частности классический, минимаксный и игровой критерии). Предложены методы композитных отображений для нахождения аппроксимационных корней перечисленных задач. Представлен анализ двух классических моделей экономического равновесия в предположении их несобственности.
-
Разработаны численные схемы различных вариантов общего метода композитных отображений для коррекции неразрешимых задач оптимизации, обощенных уравнений и вариационных неравенств с применением приемов регуляризации и итеративной аппроксимации. Предложены новые схемы метода модифицированных функций Лагранжа для анализа и оптимальной коррекции несобственных задач выпуклого программирования (ВП) 1-го рода.
4. Дано описание диалогового пакета программ численного анализа
несобственных задач линейного программирования 1-го рода ДЕЛЬТА
ПЛАН-ЕС, созданного в 1IMM УрО РАН группой программистов под ру
ководством автора (которому принадлежит разработка общей структуры
и принципов функционирования пакета, его алгоритмическое наполнение,
схемы привязки к СПО МПР-2 и схемы интерфейса), а также описание ря
да прикладных результатов соискателя, полученные при моделировании
работы сложных космических систем с большим числом взаимодействую
щих элементов, каждый из которых имеет свои цели, ресурсы и задачи.
Практическая значимость. Полученные результаты открывают новые возможности предлагаемых моделей и методов как для рассматриваемых ранее традиционных приложений задач МП, так и для новых
приложений в задачах нахождения различного рода равновесных состояний в экономических и технических системах и ряде других. Разработанное программное обеспечение применялось для решения важных прикладных задач, в частности, для проведения расчетов по теме "Оптимальное объемно-календарное планирование производства" для НПО Урал-маш (ППП ДЕЛЬТА-ПЛАН-ЕС был передан на это предприятие).
Апробация работы. Результаты диссертации докладывались на конференциях: Методы математического программирования и программное обеспечение. Свердловск, 23 - 27 февраля 1987, Методы математического программирования и программное обеспечение. Свердловск, 27 февраля-3 марта 1989, Методы математического программирования и программное обеспечение. Екатеринбург 22-26 февраля 1993, Системы программного обеспечения решения задач оптимального планирования. X Всесоюз. сими. 20-27 марта 1988, г. Нарва, Системы программного обеспечения решения задач оптимального планирования. XI Всесоюз. симпоз. 21-29 мая 1990, г. Кострома, Методы оптимизации и их приложения. 10-ая Байкальская школа-семинар. Иркутск, 14-19 августа 1995г. и др.
Публикации. Основные результаты диссертации опубликованы в работах [1-26] и в отчетах о НИР "Раунд" Института математики и механики УрО РАН N279 от 18.06.1987, N339 от 29.07.1988, N407 от 16.11.1989, N458 от 23.11.1990, N485 от 12.11.1991.
Структура и объем работы. Диссертация изложена на 221 страницах машинописного текста и состоит из введения, трех глав, приложения, заключения и списка литературы, содержащего 185 названий.