Математическое программирование (МП) является в настоящее время одним из наиболее развивающихся разделов прикладной математики. Объектом изучения в этой дисциплине служит задача оптимизации некоторого показателя качества принимаемого решения при ограничениях на это решение в виде функциональных неравенств и (или) уравнений. Подобные задачи возникают как в самой математике (аппроксимация, решение систем уравнений, регрессия, оптимальное управление системами, распознавание образов (РО), теория игр), так и во многочисленных приложениях по оптимизации технико-экономических систем, транспортных и информационных сетей, по управлению производством и другими сферами человеческой деятельности, в робототехнике и т.п.
У истоков уральской школы по МП стоял выдающийся математик С.Н.Черников (1912-1987), известный своими классическими работами по теории групп и теории линейных неравенств. В 1961 году в Свердловском отделении Математического института им. В.А.Стеклова (ныне Институт математики и механики УрО РАН) при отделе алгебры, возглавляемом профессором С.Н.Черниковым, была создана лаборатория линейного программирования. Ее возглавил ученик С.Н.Черникова молодой кандидат наук И.И.Еремин. После успешной защиты докторской диссертации в 1967 году на базе данной лаборатории И.И.Ереминым был организован отдел МП, ставший в дальнейшем ядром научной школы по оптимизации.
От других российских научных центров по МП, среди которых прежде всего следует упомянуть коллективы, возглавляемые чл.-корр. РАН Ю.Г.Евтушенко (Москва, ВЦ РАН), акад. П.С.Краснощековым (Москва, МГУ), д.ф.-м.н. В.А.Бересневым (Новосибирск, ИМ СО РАН), д.ф.-м.н. В.П.Булатовым (Иркутск, ИСЭМ-ИДСТУ СО РАН), д.ф.-м.н. А.А.Колоколовым (Омск, ОФИМ СО РАН), уральскую школу отличают и предмет и методология исследований. В первую очередь, это интерес к глубинным вопросам теории классического МП таким, как двойственность, устойчивость, регуляризация, нестационарность, несобственность. Далее, это проблема построения общих методов решения линейных и выпуклых задач оптимизации (фейеровского типа, штрафных функций, модифицированных функций Лагранжа).
Сразу следует заметить, что ряд этих вопросов: теория двойственности для определенных классов задач МП (многокритериальных, противоречивых, дизъюнктивных), нестационарные задачи МП, несобственные (в частности, противоречивые) задачи МП, некоторые виды регуляризации задач МП, комитетные конструкции в задачах РО, были инициированы работами представителей данной школы и получили широкую известность и признание как в нашей стране, так и за рубежом.
Специфику методологии в области теории составляет прежде всего алгебраический подход к доказательству математических результатов, опирающийся преимущественно на теорию линейных неравенств. В области алгоритмического обеспечения основное внимание уделяется оценочному подходу, связанному с получением оценок скорости сходимости методов, точности приближений, вычислительной сложности.
Отметим ряд результатов, полученных в рамках данной школы. Большое значение имеют исследования по методам штрафных функций. В 1966 году И.И.Еремин предложил метод точных штрафных функций, позволяющий в принципе свести решение исходной задачи на условный экстремум к однократной минимизации без ограничений подходящим образом выбранной вспомогательной функции. Результаты по методу, основанному на предложенной точной штрафной функции, именуемой в мировой специальной литературе “функцией Еремина-Зангвилла”, в значительной мере опередили зарубежные исследования в этой области. На самом деле был открыт конструктивный класс точных штрафных функций для задач линейного и выпуклого программирования (Еремин-Зангвилл) и дана исчерпывающая идентификация оптимальных штрафных констант (И.И.Еремин), совпадающих с объективно-обусловленными оценками Канторовича. Был развит оценочный подход в методе штрафных функций и получены соответствующие оценки уклонений (см. И.И.Еремин, Н.Н.Астафьев. Введение в теорию линейного и выпуклого программирования. –М.: Наука, 1976).
Был исследован широкий класс методов фейеровского типа для решения систем выпуклых неравенств и задач выпуклого программирования. Разработана методология нестационарных процессов МП как средства моделирования эволюционирующих сложных систем (экономических, биологических и др.). Первым итогом этого нового направления стала монография И.И.Еремина, Вл.Д.Мазурова “Нестационарные процессы математического программирования” (М.: Наука, 1979).
Базовой идеей теории МП является двойственность, позволяющая осуществлять конструктивный анализ моделей оптимизации. В работах И.И.Еремина и его учеников построена каноническая теория двойственности для несобственных (противоречивых, не имеющих решения в обычном смысле) задач МП, а также многокритериальных, дизъюнктивных задач, разработаны методы оптимальной коррекции несобственных задач. Решение этих вопросов можно найти в монографиях: И.И.Еремин, Вл.Д.Мазуров, Н.Н.Астафьев “Несобственные задачи линейного и выпуклого программирования” (М.: Наука, 1983), I.I.Eremin “Theory of Linear Optimization” (Inverse and Ill-Posed Problems, VSP, Utrecht, Boston, Köln, Tokyo, 2002).
Теория линейных неравенств, развитая С.Н.Черниковым, послужила фундаментом для развития исследований по оптимизационным задачам РО — дисциплины, актуальной своими богатыми приложениями (разнообразные задачи классификации, диагностика технико-экономических систем, медицинская диагностика и т.д.). В работах Вл.Д.Мазурова и его учеников системы линейных неравенств и комитеты большинства применялись для решения задач дискриминантного анализа, таксономии и выбора информативных признаков в условиях неформализованности, противоречивости и нестационарности постановок. Теория комитетов определяет оригинальную методику решения задачи обучения РО, которая тесно связана как с работами по алгебраическому подходу в РО (школа акад. Ю.И.Журавлева), так и с работами по исследованию несобственных задач оптимизации в рамках нестационарных процессов в МП и РО. Соответствующие результаты нашли отражение в монографии Вл.Д.Мазурова “Метод комитетов в задачах оптимизации и классификации” (М.: Наука, 1990). В последнее десятилетие были получены оценки числа членов минимального комитета, обоснованы соотношения двойственности для различных задач РО, предложена комбинаторная классификация минимальных комитетов несовместных систем ограничений на основе изоморфизма подходящих гиперграфов, доказана NP-полнота задачи о минимальном комитете (см., например, обзор Vl.D. Mazurov, M.Yu. Khachai, A.I. Rybin. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceedings of Steklov Inst. of Math. Suppl. 1, 2002).
Для данной школы характерно устойчивое внимание к созданию программного обеспечения для задач МП и РО и к решению прикладных задач. В числе созданных пакетов прикладных программ выделяются ППП ОПТИМА, ДЕЛЬТА-ПЛАН, ЛАМБДА, реализующие методы линейного, квадратичного и нелинейного программирования для задач большой размерности, ППП КВАЗАР и КВАЗАР-плюс для решения задач РО (последний пакет имеет вариант для работы через Интернет). Полигоном проверки эффективности программных средств выступали такие задачи как объемно-календарное планирование производства Уральского завода тяжелого машиностроения, задачи из области энергетики и черной металлургии, медицинские задачи, задачи управления сложными техническими системами.
В настоящее время основными направлениями научных исследований школы И.И.Еремина являются такие фундаментальные разделы МП и РО как теория двойственности для многокритериальных, кусочно-линейных, нелинейных, противоречивых и дизъюнктивных задач МП и РО; обоснование нестационарных процессов оптимизации и РО с исследованием сложности и скорости сходимости алгоритмов; развитие метода штрафных функций; построение методов оптимальной коррекции противоречивых и плохо формализуемых задач оптимизации и РО; анализ бесконечномерных задач математического программирования с применением аппарата теории бесконечных систем линейных алгебраических неравенств; исследование методов аппроксимации неразрешимых вариационных неравенств; применение комитетных конструкций в несобственных задачах оптимизации и РО; построение параллельных версий алгоритмов МП для реализации на высокопроизводительных многопроцессорных вычислительных системах типа МВС-1000.
Уральская школа МП поддерживает тесные научные контакты с отечественными и зарубежными коллегами. Широкой известностью пользуется регулярно проводимая с 1973 года в Екатеринбурге (с интервалом 2-3 года) Всероссийская конференция “Математическое программирование и приложения”. Школа долгое время вела плодотворное сотрудничество с научными центрами по оптимизации в Германии (университет им. Гумбольдта в Берлине, Технический институт в Ильменау), Чехии (Карлов университет в Праге), Испании (университет г. Аликанте), выпуская совместные труды и проводя научные конференции.
Членами Уральской научной школы по математическому программированию с полным правом считают себя более девяноста человек. Среди них академик И.И.Еремин, член-корреспондент РАН Х.Н.Гизатуллин, доктора наук Вл.Д.Мазуров, Н.Н.Астафьев, Л.Д.Попов, В.Н.Фролов, А.А.Ватолин, М.Ю.Хачай, Ю.В.Перевалов, кандидаты наук В.М.Кисляк, С.В.Плотников, В.Д.Скарин, А.И.Смирнов и др. В основном, это сотрудники Института математики и механики УрО РАН (отдел математического программирования, зав.отд. М.Ю.Хачай) и преподаватели Уральского государственного университета (кафедры математической экономики, зав. кафедрой — к.ф.-м.н. М.О.Асанов, экономического моделирования и информатики, зав. кафедрой — д.ф.-м.н. Вл.Д.Мазуров). В коллективе четко прослеживается наличие нескольких научных поколений. В качестве примера можно привести следующие цепочки “учитель-ученик”: акад. И.И.Еремин — д.ф.-м.н. Вл.Д.Мазуров — к.ф.-м.н. Л.И.Тягунов — к.ф.-м.н. Д.Н.Гайнанов — к.ф.-м.н. А.О.Матвеев; акад. И.И.Еремин — д.ф.-м.н. Вл.Д.Мазуров — д.ф.-м.н. М.Ю.Хачай — к.ф.м.н. А.В.Качалков; акад. И.И.Еремин — чл.-корр. РАН Х.Н.Гизатуллин — к.э.н. И.Э.Гимади — к.э.н. Д.А.Березин.
Коллектив школы возглавляет академик И.И.Еремин — общепризнанный авторитет в области математической оптимизации, математического моделирования, исследования операций и разработки программного обеспечения, автор и соавтор более 190 научных статей, 6 монографий, 5 учебных пособий. Он возглавляет национальную Ассоциацию математического программирования, является председателем оргкомитета Всероссийской конференции “Математическое программирование и приложения”, председателем специализированного совета по защите диссертаций в Институте математики и механики УрО РАН, входит в состав редколлегий ряда отечественных и зарубежных журналов. В числе учеников И.И.Еремина — 7 докторов и 12 кандидатов наук.
И.И.Еремину принадлежат глубокие результаты по нестационарным процессам МП и оптимизации иерархических систем, он разработал и исследовал широкий класс методов фейеровского типа для систем линейных и выпуклых неравенств, для задач МП. Он ввел и глубоко изучил ставший классическим метод точных штрафных функций, а также развил оценочный подход для общего метода штрафов. И.И.Еремин открыл новое принципиально важное в МП направление — теорию несобственных (в том числе противоречивых) задач оптимизации. Он построил каноническую теорию двойственности для несобственных задач оптимизации, а также разработал и обосновал методы аппроксимации для этих задач. Ему принадлежат все основные конструкции для кусочно-линейной оптимизации, в том числе базовые конструкции для формирования двойственности для этих задач.
Вопросам преемственности поколений в школе уделяется постоянное внимание. Работа с перспективной молодежью начинается уже на младших курсах вузов. Большинство сотрудников школы совмещают научную работу с педагогической деятельностью в ведущих вузах г. Екатеринбурга, прежде всего в УрГУ и УГТУ-УПИ. В целях повышения качества подготовки научного резерва в 1996 году И.И.Ереминым на математико-механическом факультете УрГУ была организована кафедра математической экономики. Аспиранты и молодые сотрудники привлекаются к активной работе в рамках постоянного семинара отдела математического программирования в ИММ УрО РАН. На ежегодной школе-семинаре молодых ученых-математиков, организуемой ИММ УрО РАН, как правило, работает секция МП. На Всероссийской конференции "Математическое программирование и приложения" практикуются молодежные заседания секций специально для выработки у молодых ученых навыков ведения научной дискуссии.
