Парадигма развития науки. Методологическое обеспечение (стр. 87 )

Аналогично решается задача на условный экстремум с ограничениями, в которой аргументы целевой функции свя­заны не только неравенствами, но и уравнениями. Отметим, что если область (V), определенная всеми этими неравенст­вами и уравнениями, неограниченная (простирается в бес­конечность), то задача на экстремум может и не иметь решения; обычно это свидетельствует о ее неправильной формулировке.

Некоторые классы задач на экстремум с ограничениями разработаны особенно далеко. Так, если целевая функция является линейной, равно как и все уравнения и неравенст­ва, связывающие ее аргументы, то мы имеем задачу линей­ного программирования. Имеются стандартные программы для ЭВМ, позволяющие решать такие задачи, даже если целевая функция имеет несколько сотен аргументов. Изве­стны также алгоритмы решения задач линейного целочис­ленного программирования, т. е. задач, для которых аргу­менты целевой функции по своему смыслу могут принимать только целочисленные значения.

Если целевая функция и левые части высвобождающих связей, записанных по образцу (3), являются выпуклыми функциями, а все невысвобождающие связи линейные, то перед нами — задача выпуклого программирования. При этом функция называется выпуклой, если для любых выполнено неравенство

(Для функции одного аргумента это означает, что ее график выпуклый книзу; если же функция имеет непрерывные производные второго порядка, то ее выпук­лость равносильна неотрицательности всех собственных зна­чений «матрицы Гессе» Задачи выпуклого про­граммирования обладают важным свойством: они не могут иметь более одного решения, и если решение есть, то метод спуска обязательно приводит к нему. Задача выпуклого программирования, для которой целевая функция квад­ратична, а высвобождающие связи линейны, называется задачей квадратичного программирования; для таких задач алгоритм решения особенно стандартизован.

Отметим, что задача на нахождение экстремального значения целевой функции несколько отличается от задачи на нахождение точки экстремума (т. е. значений аргумен­тов, при которых экстремум достигается). В самом деле, пусть, как это чаще всего бывает, все участвующие функции имеют непрерывные частные производные. Тогда точка без­условного экстремума задачи без ограничений является ста­ционарной для целевой функции f, т. е. в этой точке все производные первого порядка функции f равны нулю. От­сюда следует, что малая погрешность при определении точки экстремума влечет за собой погрешность второго поряд­ка малости для экстремального значения функции f. Та­ким образом, если цель исследования состоит только в том, чтобы придать функции f по возможности меньшее зна­чение, то для рассматриваемого класса задач не требуется слишком точно находить точку минимума, так как это практически не повлияет на значение функции.

То же относится к задаче на условный экстремум без ограничений, если только соблюдение уравнений связи обес­печено с достаточной точностью. (Что касается задач с ограничениями, то подобное «шатание» точки экстремума возможно только вдоль содержащей ее грани наименьшей размерности области (V).)

В заключение укажем на один специфический класс задач с дискретным временем, для решения которых приме­няется так называемый метод динамического програм­мирования, получивший разнообразные применения. Пусть состояние некоторого объекта харак­теризуется величиной х (непрерывной или дискретной) и этот объект надо перевести из заданного состояния х0 в момент t0 в заданное состояние xN в момент tN, подобрав для этого промежуточные состояния в моменты Пусть при этом известна стоимость перевода объекта из состояния х в момент t, в состояние у в момент Задача состоит в том, чтобы минимизировать общую сумму затрат:

В курсах динамического программирования приводятся ал­горитмы решения этой и родственных ей задач, в частности аналогичной задачи с непрерывным временем.

Все описанные в этом пункте задачи могут включать те или иные случайные компоненты. Тогда значение целевой функции становится случайной величиной и цель задачи состоит в минимизации математического ожидания этой величины.

3.6.14. Задачи на экстремум с искомой функцией

Одной из самых наглядных задач подобного рода является задача о кривой наибыстрейшего спуска, поставленная еще Галилеем: среди всех кривых, лежащих в плоскости х, у с вертикальной осью у и имеющих заданные концы , где найти такую, двигаясь по которой под дей­ствием только силы тяжести, материальная точка, отправ­ляясь из А без начальной скорости, достигнет В за минималь­но возможное время.

Для формулировки математической модели допустим, что некоторая кривая с концами А и В и с уравнением у = у(х) задана; тогда можно проверить (попробуйте!), что время спуска по ней равно

где g — ускорение земного тяготения. Этот интеграл при­нимает определенное значение, если функция у(х) задана. Подобного рода соотношение, когда каждой функции из некоторого класса отвечает определенное значение неко­торой величины, называется функционалом.

Таким образом, для функционала те функции, на кото­рых он определен, являются как бы значениями независимой переменной. Чтобы подчеркнуть это обстоятельство, будем в этом пункте, как это сейчас часто делают в математической литературе, различать обозначения у и у(х), понимая под у (пишут также. саму функцию как закон зависимости, а под у(х) — значение этой функции при значении х аргумента. Тогда сформулированную задачу можно, обоз­начив функционал буквой f, записать в виде

при заданных краевых условиях

Эта задача принадлежит к следующему общему классу: найти функцию у, для которой

(1)

при заданных краевых условиях

(2)

Такие задачи изучаются в курсах вариационного исчис­ления, где рассматриваются и разнообразные варианты: функционал f может включать и производные более высо­кого порядка функции у, функция у может принимать векторные значения (другими словами, искомыми будут не одна, а несколько функций) и зависеть от нескольких аргу­ментов, краевые условия могут быть заданы не на всей границе или даже вовсе не заданы и т. д. Рассматриваются также задачи на условный экстремум — например, если в задаче (1), (2) заданы одно или несколько добавочных условий вида

Такая вариационная задача называется изопериметрической; название происходит от следующей знаменитой задачи: среди всех линий заданной длины на плоскости найти такую, которая ограничивает фигуру наибольшей площади. Подобно задачам на экстремум с конечным числом сте­пеней свободы задача (1), (2) более проста, если функция F определена для всех значений своих аргументов и имеет непрерывные производные. В этих предположениях функция у, на которой функционал принимает экстремаль­ное значение, является стационарной точкой функционала f. (Это означает, что при малом варьировании функции у, т. е. при переходе к функции где и малы, с сохранением условий (2) значение функционала f изме­няется на величину высшего порядка малости.) А из условия стационарности легко выводится дифференциальное урав­нение — так называемое уравнение Эйлера,— которому должна удовлетворять искомая функция у. Так, для функ­ционала (1) уравнение Эйлера имеет вид

или, подробнее,

Таким образом, вместе с (2) мы получаем краевую задачу для дифференциального уравнения второго порядка. В некоторых довольно редких случаях эту задачу удается решить точно. Так, в задаче о кривой наибыстрейшего спуска (см. начало этого пункта) оказывается, что решением служит дуга циклоиды с точкой возврата в А, проходящая через В. Но гораздо чаще точное решение найти не удается и краевую задачу решают приближенно тем или иным способом.

Однако еще чаще применяются прямые методы, с по­мощью которых приближенное решение задачи на экстре­мум функционала сводится без обращения к уравнению Эйлера к аналогичной задаче с конечным числом степеней свободы. Один из таких методов, предложенный еще Эйле­ром, состоит в следующем. Разобьем интервална п равных частей длины и обозначим