|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Краткий очерк истории возникновения и развития теории экстремальных задач от античных времен до наших дней. Приводятся примеры экстремальных задач, которые характеризуют этапы развития теории. Бурное развитие теории экстремальных задач на современном этапе определяется практическими потребностями в различных сферах человеческой деятельности.
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИВ СОВРЕМЕННОЙ НАУКЕ
И ПРИЛОЖЕНИЯХ
Р. Ф. ГАБАСОВ
Белорусский государственный университет, Минск
Экстремальной задачей в математике называют задачу на максимум или минимум (экстремум) функции по переменным, удовлетворяющим, возможно, некоторым ограничениям. С простейшими экстремальными задачами знакомят в школе, в общем виде теория экстремальных задач изучается в университетах. Для того чтобы понять место экстремальных задач в современной науке и ее приложениях, целесообразно проследить историю их развития.
Экстремальными задачами человек интересуется с античных времен. В Древней Греции уже давно (во всяком случае до VI века до н.э.) знали об экстремальных свойствах круга и шара: среди плоских фигур с одинаковым периметром наибольшую площадь имеет круг (решение изопериметрической экстремальной задачи); шар имеет максимальный объем среди пространственных фигур с одинаковой площадью поверхности (решение изопифанной экстремальной задачи). История сохранила легенду о следующей самой древней экстремальной задаче, известной как задача Дидоны. Финикийская царевна Дидона (IX век до н.э.) решила организовать поселение на берегу понравившегося ей залива в Северной Африке. Она уговорила вождя местного племени отдать ей клочок земли, который можно охватить воловьей шкурой. Воины Дидоны разрезали шкуру на тонкие полоски, и Дидона охватила ремнем, составленным из этих полосок, участок земли на берегу залива. Так возник город Карфаген. Задача Дидоны состоит в указании формы границы участка, имеющей заданную длину, при которой площадь участка максимальна. Если знать экстремальное свойство круга, то решение получается немедленно: граница участка представляет часть окружности, имеющей заданную длину (рис. 1). Экстремальными задачами занимались многие античные ученые (Евклид, Архимед, Аристотель и др.). Известна следующая задача Евклида (IV век до н.э.): в заданный треугольник ABC (рис. 2) вписать параллелограмм ADEF наибольшей площади. Нетрудно доказать, что решением этой задачи является параллелограмм, вершины D, E, F которого делят соответствующие стороны треугольника пополам.
После гибели античной цивилизации научная жизнь в Европе стала возрождаться только в XV веке. Экстремальные задачи оказались среди тех, которыми интересовались лучшие умы того времени. Если в античные времена экстремальные задачи исследовались только геометрическими методами и каждая задача для своего решения требовала специфического приема, то в XVII веке появились общие методы изучения экстремальных задач, которые привели к созданию дифференциального и интегрального исчислений. Первые элементы математического анализа были созданы И. Кеплером (1615 год), который так описывает появление своего открытия: "Мне как хорошему хозяину следовало запастись вином. Я купил его несколько бочонков. Через некоторое время пришел продавец - измерить вместимость бочонков, чтоб назначить цену на вино. Для этого он опускал в каждый бочонок железный прут (рис. 3) и, не прибегая ни к какому вычислению, немедленно объявлял, сколько в бочке вина". После размышлений Кеплер открыл секрет такого простого способа измерения объема бочек. Оказалось, что бочары за долгую историю научились изготавливать бочки такой формы, при которой они имели наибольший объем при заданной длине мокрой части прута. А поскольку в окрестности максимума значения функции изменяются мало (в этом суть открытия И. Кеплера), то торговец вина почти не ошибался при объявлении объема бочки по одному измерению.
Открытое И. Кеплером основное свойство экстремумов было затем оформлено в виде теоремы сначала П. Ферма (для многочленов), потом И. Ньютоном и Г. В. Лейбницем для произвольных функций и носит теперь название теоремы Ферма, согласно которой в точке экстремума x0 непрерывной функции f (x) производная функции равна нулю:
С тех пор исследование функций с помощью анализа бесконечно малых величин стало одним из мощнейших математических методов и привело к созданию современного математического анализа.
С экстремальными задачами связано и зарождение основ другого раздела современной математики - функционального анализа. В 1696 году И. Бернулли опубликовал статью с приглашением ко всем математикам решить следующую задачу. В вертикальной плоскости заданы две точки, не лежащие на одной вертикали. Нужно соединить эти точки такой непрерывной линией, чтобы тяжелый шарик, скатываясь по ней без сопротивления, проходил путь от верхней точки до нижней за наименьшее время. Через год эту задачу, называемую теперь задачей о брахистохроне, решили И. Ньютон, Я. Бернулли, Г.В. Лейбниц и сам И. Бернулли.
Принципиальное отличие задачи И. Бернулли от задач на экстремум функций конечного числа переменных, для которых до этого была доказана теорема Ферма, состояло в том, что время движения шарика было функцией от линии, то есть функцией от бесконечного числа переменных. Такие функции называются теперь функционалами. К такому же классу экстремальных задач относится и задача Дидоны.
При решении задачи о брахистохроне упомянутые выше ученые и Ж.Л. Лагранж перенесли метод анализа бесконечно малых величин на исследование функционалов. Ж.Л. Лагранж назвал его методом вариаций, а Л. Эйлер предложил называть вариационным исчислением весь раздел математики, в котором исследуются экстремумы функционалов. Вариационное исчисление - первый раздел функционального анализа.
Теория экстремальных задач в XVIII-XIX веках играла большую роль и в других разделах науки, особенно в механике и физике.
Всем очевидно, что тяжелый шарик, помещенный в сосуд, занимает в состоянии равновесия самое нижнее положение. Это свойство в терминах механики означает, что потенциальная энергия шарика принимает наименьшее значение. Сформулированный экстремальный принцип широко используется в механике и физике для поиска состояний равновесия сложных систем. Для этого для систем с конечным числом степеней свободы достаточно по известным правилам составить функцию потенциальной энергии и решить задачу на минимум этой функции с учетом ограничений, наложенных на исследуемую систему.
С помощью теории экстремальных задач можно эффективно искать не только состояния равновесия, но и составлять математические модели и исследовать их поведение для различных сложных механических, физических процессов, протекающих во времени. В основе такого подхода лежит принцип Ферма, открытый в геометрической теории света. Физик В. Снеллиус экспериментально обнаружил известный теперь и школьникам закон преломления света
где a1 , a2 - углы между перпендикуляром к поверхности раздела и линиями лучей в первой и второй средах, u1 , u2 - скорости света в указанных средах. П. Ферма вывел этот закон из следующего принципа: при движении из одной точки в другую свет выбирает кратчайший путь, путь, который он может пройти за наименьшее время. Ученые, анализируя другие движения и процессы в механике и физике, обнаружили, что все они подчиняются следующему обобщению принципа Ферма, который называется вариационным принципом: всякое реальное (наблюдаемое в действительности) движение (или процесс) развивается (происходит) так, что при этом определенным образом составленный функционал (интеграл действия) достигает стационарного (чаще всего минимального) значения. Другими словами, реальные процессы среди множества всех возможных законов развития выбирают тот, на котором значение интеграла действия минимально. Например (рис. 4), если выброшенный в точке A камень достигает точки B по траектории, показанной сплошной красной линией, то эта траектория отличается от других (голубых штриховых) траекторий, которые также удовлетворяют всем геометрическим ограничениям, тем, что на сплошной траектории интеграл действия достигает наименьшего значения. Пользуясь вариационным принципом, можно достаточно просто составить уравнения движения (математические модели) для очень сложных процессов. При этом нужно для интеграла действия этого процесса найти точку минимума методами вариационного исчисления.
С конца XVII до середины XX века теория экстремальных задач прошла огромный путь. В ее развитии приняли участие почти все великие математики прошлого. Кроме упомянутых экстремальными задачами (точнее, вариационным исчислением) занимались Х. Гюйгенс, К.Ф. Гаусс, А.М. Лежандр, П.Г. Дирихле, Б. Риман, У.Р. Гамильтон, К.Г. Якоби, К.Т. Вейерштрасс, Д. Гильберт и др. К середине XX века создалось впечатление, что теория экстремальных задач достигла такого уровня, который позволяет решить любую экстремальную задачу, возникающую в науке и практике. Последнее утверждение больше относится к науке, чем к практическим приложениям, ибо до середины XX века математика мало использовалась для решения прикладных задач, а в основном находила разнообразные применения в других разделах естествознания. Ситуация стала заметно меняться накануне второй мировой войны. В экономике и технике стали возникать задачи, для решения которых практический опыт и здравый смысл оказывались уже недостаточными. Это было связано с увеличением возможных вариантов выбора, ужесточением требований к точности решения, с ограничениями на доступные ресурсы. Человечество стало все энергичнее переходить от использования только природных процессов к созданию искусственных материалов, систем, процессов. Резко повысилось влияние его деятельности на окружающую среду. Все эти и другие обстоятельства постепенно заставляли более научно подходить к решению практических задач. Научный подход предполагает составление математической модели изучаемого практического явления или процесса, исследование модели соответствующими математическими методами, составление алгоритмов решения и реализацию этих алгоритмов в виде программ для ЭВМ.
В теории экстремальных задач новые явления XX века впервые были замечены советским математиком Л.В. Канторовичем. В 30-е годы он консультировал экономистов некоторых ленинградских заводов и столкнулся с задачей о раскрое материалов. Экономистов интересовало, как наилучшим образом разрезать листы фанеры, чтобы отходы были минимальными. Л.В. Канторович показал, что эта задача и многие другие практические задачи могут быть сформулированы в виде следующей экстремальной задачи:
c1x1 + c2x2 + _ + cnxn max,
a11x1 + a12x2 + _ + a1nxn # b1 ,
a21x1 + a22x2 + _ + a2nxn # b2 ,
. . . . . . . . . . . . . . . . . . . . . . . .
am1x1 + am2x2 + _ + amnxn # bm ,
x1 $ 0, x2 $ 0, _, xn $ 0.
Главная особенность этой задачи состоит в том, что в ее условиях присутствуют нестрогие неравенства. Конечно, с неравенствами ученые встречались и раньше и находили для каждого случая специальные приемы их учета. Л.В. Канторович первым отчетливо заявил, что нестрогие неравенства типичны для большинства практических задач и для их учета в математике нет общих эффективных методов. Он же предложил несколько приемов решения нового класса экстремальных задач, но завершению работы помешала вторая мировая война. Заслуги Л.В. Канторовича по исследованию нового класса экстремальных задач были отмечены Нобелевской премией по экономике, в которой задачи (1) играют огромную роль.
После второй мировой войны независимо от Л.В. Канторовича задачи (1) обнаружил (1947 год) американский математик Д. Данциг и предложил эффективный метод их решения, известный теперь как симплекс-метод. С начала 50-х годов новый раздел экстремальных задач (1) стал называться линейным программированием и явился первым разделом современной теории экстремальных задач, которая отличается от классической теории экстремальных задач наличием в ней методов решения задач с нестрогими неравенствами и порождаемыми последними замкнутыми множествами.
Становлению линейного программирования, его обобщениям и приложениям огромную помощь оказало создание в середине 40-х годов XX века электронных вычислительных машин (ЭВМ). Дело в том, что экстремальные задачи, включающие в свои условия нестрогие неравенства, редко допускают решения в форме, которая до XX века была широко распространена в математике и широко используется теперь и в школьной математике. Речь идет о записи решений в виде формул, выражающих искомые переменные через параметры задачи. Простейшие примеры - формулы для площадей треугольника, круга, для корней квадратного уравнения, для точек минимума и максимума квадратного трехчлена и т.п. Такой "формульный тип решения" математических задач часто удобен для использования, а в простейших ситуациях его знание для математика обязательно как таблица умножения. Его достоинство состоит в глобальности: получив формулу один раз, ее можно использовать для получения численного ответа в любой конкретной ситуации.
Формульное решение обладает и существенным недостатком: чрезвычайно узок класс математических задач, для решения которых удается построить удобные формулы. В последние годы с помощью ЭВМ ученые существенно продвинулись в этой области и стали ненужными многочисленные таблицы формул. Теперь ЭВМ сама получает формулу для решения математической задачи, если задача допускает формульное решение. Однако уже давно известно, что проблема построения формул для решения большинства математических задач принципиально неразрешима. В связи с этим с появлением ЭВМ на первый план стал выходить другой тип решения математических задач. Этот тип решения был известен еще И. Ньютону, но использовался в математике не очень часто. В отличие от формульного новый тип решения предназначался для получения численного ответа с любой наперед заданной точностью для конкретных задач с заданными численными значениями параметров. Решение получалось путем последовательных уточнений по определенным правилам начального приближения (начальной догадки) к решению. Правила уточнения последовательных приближений называются алгоритмом, а сами приближения - итерациями. Теперь при решении задач целью математиков стало построение эффективных алгоритмов, которые за небольшое число итераций приводят к решению (к точному или приближенному с заданной точностью).
Итеративные методы решения сложных математических задач получили повсеместное распространение в силу того, что рутинную работу по их реализации (по уточнению приближений) могут с успехом выполнять ЭВМ. Использование итеративных методов может оказаться полезным и при решении не очень сложных задач на калькуляторах. В качестве примера решения на калькуляторах математической задачи итеративными методами приведем задачу вычисления корней кубического многочлена. Существует простой, легко реализуемый на калькуляторе итеративный метод Ньютона вычисления упомянутых корней. Многие предпочитают такой метод известной формуле. Подобная ситуация сейчас не является исключительной при решении математических задач. Достигнутый в последние годы фантастический прогресс в области ЭВМ позволяет получать решения таких задач, которые еще недавно казались недоступными. Симплекс-метод Д. Данцига решения задач (1) связан с новым понятием решения. Он позволяет с помощью ЭВМ за конечное число итераций найти точное решение задачи.
Вслед за линейным программированием, в котором изучается задача на экстремум линейной функции конечного числа переменных при учете конечного числа линейных неравенств и равенств, возник и новый раздел в теории задач вариационного типа. Снова источником послужили практические задачи, но теперь уже не в экономике, а в технике, связанной с управлением реактивным движением. Реактивные самолеты, ракеты в отличие от винтовых самолетов должны всегда снабжаться системой управления. Математические проблемы, возникшие при решении нового типа экстремальных задач, проиллюстрируем на примере управления простейшим механическим движением. На горизонтальном прямолинейном участке дороги заданы два пункта A и B (рис. 5). Нужно составить программу u(t), t $ 0, изменения во времени ограниченного управления (силы)
| u(t) | # 1, t $ 0,
при котором тележка перемещается из точки A в точку B за кратчайшее время. Эта задача похожа на упомянутую выше задачу о брахистохроне, но отличается принципиальным элементом - наличием ограничения (2) в виде нестрогого неравенства. По этой причине сформулированная на рубеже 40-50-х годов XX века задача не могла быть решена методами классического вариационного исчисления. Только после открытия в 1956 году группой советских ученых во главе с Л.С. Понтрягиным метода решения нового типа экстремальных задач, известного сейчас во всем мире под названием принципа максимума Понтрягина, начался современный этап развития вариационного исчисления, именуемый теорией оптимального управления. Большую роль в теории оптимального управления играет и второй фундаментальный метод - динамическое программирование Беллмана.
Как линейное программирование, так и теория оптимального управления привлекли внимание многих ученых, усилиями которых современная теория экстремальных задач получила мощное развитие. В конечномерном разделе были созданы квадратичное программирование, дискретное программирование, нелинейное программирование и много других специальных частей, в названия которых входит слово "программирование". Все эти части объединяют одним термином "математическое программирование", который пришел на смену классическому термину "задачи на максимум и минимум". В квадратичном программировании линейная целевая функция задачи (1) заменяется на квадратичную функцию
В дискретном программировании переменные (все или часть) задачи (1) могут принимать лишь конечное число значений, могут быть, например, лишь целыми числами. В нелинейном программировании вместо линейных функций задачи (1) используются произвольные нелинейные функции переменных x1 , x2 , _, xn .
Выделение из теории экстремальных задач специальных частей позволяет создавать для них эффективные методы, учитывающие специфику этих задач.
На базе теории оптимального управления в 60-е годы была создана теория дифференциальных игр. Экстремальные задачи называют игровыми, если в них учитываются несовпадающие интересы нескольких участников (игроков). Конечномерные игровые задачи появились еще в 20-е годы XX века, затем для них Дж. фон Нейманом была создана красивая теория с приложениями в экономике. Игры называют дифференциальными, если поведение объектов исследования описывается дифференциальными уравнениями. Яркий пример дифференциальной игры доставляет задача защиты истребителем объекта от бомбардировщика. Здесь рассматривается система из двух игроков (истребитель, бомбардировщик), интересы которых противоположны. Теория дифференциальных игр занимается исследованием оптимального поведения игроков.
Теория экстремальных задач продолжает развиваться и в наши дни. В последние годы возникли и сейчас находятся в центре внимания многих математиков три направления: 1) большие экстремальные задачи, 2) негладкие экстремальные задачи, 3) задачи оптимизации в условиях неопределенности.
Каждая конечномерная экстремальная задача имеет два размера: количество ограничений и количество переменных. Если эти размеры большие, то задача называется большой. Это условное (не очень четкое) определение меняется со временем, по мере развития средств для решения экстремальных задач. Для решения больших экстремальных задач используются два подхода: а) совершенствование общих методов решения, б) разработка реализаций общих методов для специальных подклассов задач, имеющих ярко выраженную особую структуру математических моделей. Подход а) в последние годы обогатился новыми методами, основанными как на идеях симплекс-метода, так и на других идеях. Типичным примером реализации подхода б) являются методы решения широко распространенных в приложениях транспортных задач. В неформальной постановке они представляют собой задачи о составлении планов перевозок грузов с минимальными транспортными расходами по заданной сети дорог от заданных поставщиков к заданным потребителям. Математические модели этих задач являются частным случаем задачи (1), и поэтому их можно решить симплекс-методом. Однако если реализовать симплекс-метод с учетом специфики новой модели, то получается метод, который намного эффективнее симплекс-метода. Успехи, достигнутые в решении больших задач, позволяют с помощью современных ЭВМ решать специальные задачи линейного программирования, имеющие миллионы переменных и сотни тысяч основных ограничений. Однако проблема решения больших экстремальных задач не может считаться закрытой, ибо практика постоянно поставляет все новые и новые задачи, которые пока не под силу современным методам и ЭВМ.
Математический анализ на протяжении веков занимается, по определению, исследованием гладких функций (непрерывных функций с непрерывными производными). Поэтому его можно назвать гладким анализом. С появлением современной теории экстремальных задач математикам приходится все чаще и чаще иметь дело с функциями, которые не обладают производными или даже разрывные. В связи с этим возник выпуклый анализ, в котором специальный класс функций, называемых выпуклыми (пример: f (x) = | x |), исследуется без использования классических производных. Поскольку выпуклый анализ не удовлетворяет всех потребностей теории экстремальных задач, то в последние годы прилагаются большие усилия к созданию общего (невыпуклого) негладкого анализа.
Третье направление современной теории экстремальных задач, к которому приковано внимание многих математиков, называется проблемой оптимизации систем в условиях неопределенности. Это направление в некотором смысле является развитием теории дифференциальных игр. Поэтому при постановке задач этого направления неявно предполагается, что наряду с основным участником оптимизации присутствуют еще другие участники, которые мешают (сознательно или несознательно) основному участнику. В 40-70-е годы неопределенность в основном моделировалась (описывалась) в терминах теории вероятностей. С конца 70-х годов для описания неопределенностей стали использовать невероятностные модели, ибо во многих прикладных задачах получение вероятностных характеристик или затруднено, или невозможно. Теперь при оптимизации систем стали говорить о получении гарантированного результата, то есть о построении таких управлений, которые для самых неблагоприятных ситуаций гарантируют получение результата (например, прибыли) не ниже некоторой величины. Последние задачи часто встречаются в экономике, где неопределенность порождается многими причинами.
В связи с задачами оптимизации в условиях неопределенности на первый план вышел новый тип решения динамических экстремальных задач. В теории оптимального управления различают программные управления и управления типа обратной связи. Программные управления представляют функции времени u(t), t $ 0, которые составляются в начале процесса управления на весь период управления, и их вид не изменяется в процессе управления. Управления типа обратной связи имеют вид функций от состояний системы u(x) и изменяются в зависимости от изменения состояния. Программные управления часто невозможно использовать в условиях неопределенности (при действии на систему неизвестных возмущений). Управления типа обратной связи успешно парируют действие многих возмущений и поэтому предпочтительнее в задачах оптимизации в условиях неопределенности.
На этом закончим краткий очерк об экстремальных задачах в современной науке и приложениях. Тема очерка очень обширна и постоянно развивается. Ниже приводится список трудов, которые сыграли выдающуюся роль в развитии современной теории экстремальных задач. Благодаря этим работам каждый учитель и школьник сможет познакомиться с оригинальными идеями классиков науки.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966.
2. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
3. Гюнтер Н.М. Курс вариационного исчисления. Л.; М.: ОГИЗ, 1941.
4. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Физматгиз, 1961.
5. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960.
6. Айзекс Р. Дифференциальные игры. М.: Мир, 1967.
7. Красовский Н.Н. Управление динамической системой: задача о минимуме гарантированного результата. М.: Наука, 1985.
* * *
Рафаил Федорович Габасов, доктор физико-математических наук, профессор, зав. кафедрой методов оптимального управления факультета прикладной математики и информатики Белорусского государственного университета, заслуженный деятель науки Республики Беларусь. Область научных интересов: качественная и конструктивная теории оптимального управления, методы оптимизации. Автор более 300 научных работ, среди них 13 книг, две из которых переизданы в США.
