Каждый класс прикладных задач, пройдя этап математического моделирования, характеризуется специфическим классом описывающих его функций и специальной структурой множества параметров. Многие из возникших подобным образом классов задач линейного и нелинейного программирования [1, 2] имеют в настоящее время детально разработанную теорию и всесторонне проверенные методы решения. Классический пример – задачи транспортного типа, рассмотренные во второй части данной книги [3]. Многие интересные классы задач изучены в [4, 5]. Процесс выделения специальных задач интенсивно развивался в последние пятнадцать – двадцать лет и будет, по всей вероятности, основным направлением развития методов оптимизации в будущем. Это объясняется тем, что стандартные (общие) методы оптимизации, в которых не учтена специфика задач, удается реализовать даже на современных ЭВМ лишь для задач небольшого размера по сравнению с размерами тех прикладных задач, которые актуальны сейчас в экономике и технике. Прогресс вычислительной техники наряду с расширением круга задач, доступных численному решению известными методами, остро ставит вопрос об эффективном ее использовании. В этой ситуации особое значение приобретают исследования по математическим методам, которые учитывают, с одной стороны, специфику решаемых задач, а с другой – возможности и тенденции развития ЭВМ. В данной, третьей, части книги для решения ряда важных специальных задач математического программирования применяются методы, обоснованные в первых двух частях. Однако теперь эти методы не выступают как единственное средство решения задач, а используются в сочетании с другими методами, учитывающими специфику рассматриваемых задач. Кроме того, в отличие от ч. 2 здесь в основу берется, как правило, только один прямой опорный метод из ч. 1. Несколько слов о содержании третьей части. Введение посвящено построению модификаций опорного метода, впервые опубликованного авторами в [28] и развитого в предыдущих частях книги. Нигде специально не подчеркивается, что в схему опорных методов при соответствующей нормировке укладываются многие известные методы (методы проекции градиента, условного градиента и др.). Изложение основного материала начинается с методов решения больших задач линейного программирования. Как известно, размер задачи определяется числом п переменных и числом т основных ограничений. Большие задачи (п, т>>1) типичны для всех современных приложений, и разработка эффективных методов их решения – одна из самых актуальных проблем методов оптимизации. Систематическое изучение больших задач началось после создания в 1960 г. метода декомпозиции Данцига – Вулфа. В главе I излагается модификация этого метода и приводится ряд других методов решения больших задач. В главе II предложенные методы применяются для решения некоторых типичных задач линейного оптимального управления. Материал главы III связан с экстремальными задачами на сетях. Рассматриваются разнообразные задачи в сетевой постановке. В каждой задаче имеется особенность, ради которой проводится модификация (реализация) общего метода. В совокупности задачи, исследованные в главе, позволяют составить сетевую модель любой задачи линейного программирования. Однако такая общая ситуация в книге не изучается и будет предметом нашей будущей работы. Глава IV посвящена нескольким обобщениям классической задачи линейного программирования. Суть этих обобщений состоит в том, что параметры задач не считаются фиксированными, а могут принимать конечное множество значений, и выбором этих параметров распоряжается участник, который в классической модели не рассматривался. Отдельно изучаются случаи, когда интересы участника 1) совпадают с интересами исследователя, выбирающего планы; 2) противоположны и 3) участник безразличен к действиям исследователя. В связи с большим вниманием, которое в последние годы уделяется вычислительным методам с ускоренной сходимостью, актуальной стала проблема разработки эффективных методов решения задач квадратичного программирования. Эта проблема с позиций методов данной книги рассматривается в главе V. В главе VI изложены первые результаты по распространению предложенных в книге методов на задачи линейного дискретного программирования. Книга завершается (глава VII) изучением нескольких проблем нелинейного программирования. Затронуты лишь те аспекты проблем, которые непосредственно связаны с основными методами книги. Третья часть книги рассчитана на читателя, уже владеющего материалом предыдущих частей. Предполагается, что для него не составит особого труда самостоятельное решение небольших иллюстративных примеров. Авторы считают, что книга может быть использована в качестве учебного пособия: материал прорабатывался на занятиях со студентами. В книгу включены результаты О.И.Костюковой (введение, гл.I, II; \S2, 4–6, 9 гл.III; \S1, 3 гл.IV; \S3 гл.VI); В.М.Ракецкого (гл.V); Л.В.Командиной (\S3 гл.III); С.В.Маркова (\S6–8 гл.III); Нгуен Дык Хиеу (\S9 гл.III); M.П.Дымкова (\S4 гл.IV); Е.И.Шилкиной (\S5 гл.IV, \S1 гл.VII); Л.Ф.Дежурко (\S4 гл.VII). Эти же сотрудники участвовали в подготовке данной части к печати. Пользуясь случаем, выражаем им нашу глубокую благодарность. АВТОРЫ
Габасов Рафаил Федорович
Доктор физико-математических наук, профессор. Окончил Уральский политехнический институт. С 1968 г. работал в Белорусском государственном университете (с 1970 по 2000 гг. — заведующий кафедрой, с 2000 г. — профессор кафедры методов оптимального управления). Заслуженный деятель науки БССР (1982). Почетный доктор Иркутского государственного университета. Лауреат премии Академии наук Беларуси за цикл работ по конструктивной теории экстремальных задач (1995). Автор более 500 научных работ, в том числе 8 монографий, посвященных качественной и конструктивной теории оптимального управления и ее приложениям.
Кириллова Фаина Михайловна Доктор физико-математических наук, профессор, член-корреспондент Национальной академии наук Беларуси. Окончила Уральский государственный университет. С 1967 г. работает в Институте математики Национальной академии наук Беларуси (с 1969 по 2007 гг. — заведующая лабораторией теории процессов управления, с 2008 г. — главный научный сотрудник Института математики). Почетный доктор Иркутского государственного университета. Лауреат премии Совета Министров СССР (1986) и премии Академии наук Беларуси (1995). Заслуженный деятель науки Республики Беларусь (2001). Автор 8 монографий и свыше 300 работ по качественным и конструктивным методам оптимизации и их приложениям.
|