Введение
Во многих областях наукии в практической деятельности часто приходится сталкиваться с задачами поискаэкстремума функции. Дело в том, что многие технические, экономические и т.д.процессы моделируются функцией или несколькими функциями, зависящими отпеременных – факторов, влияющих на состояние моделируемого явления. Требуетсянайти экстремумы таких функций для того, чтобы определить оптимальное(рациональное) состояние, управление процессом. Так в экономике, часто решаютсязадачи минимизации издержек или максимизации прибыли – микроэкономическаязадача фирмы. В этой работе мы не рассматриваем вопросы моделирования, арассматриваем только алгоритмы поиска экстремумов функций в простейшемварианте, когда на переменные не накладываются ограничения (безусловнаяоптимизация), и экстремум ищется только для одной целевой функции.
ЭКСТРЕМУМЫФУНКЦИИ
/>
Рассмотрим графикнепрерывной функции y=f(x), изображенной на рисунке. Значение функции вточке x1 будет больше значений функции во всех соседнихточках как слева, так и справа от x1. В этом случае говорят,что функция имеет в точке x1 максимум. В точке x3функция, очевидно, также имеет максимум. Если рассмотреть точку x2,то в ней значение функции меньше всех соседних значений. В этом случае говорят,что функция имеет в точке x2 минимум. Аналогично для точки x4.
Функция y=f(x) вточке x0имеет максимум, если значение функции в этойточке больше, чем ее значения во всех точках некоторого интервала, содержащеготочку x0, т.е. если существует такая окрестность точки x0,что для всех x≠x0, принадлежащих этойокрестности, имеет место неравенство f(x)f(x0).
Функция y=f(x) имеетминимум в точке x0, если существует такаяокрестность точки x0, что для всех x≠x0,принадлежащих этой окрестности, имеет место неравенство f(x)>f(x0.
Точки, в которых функциядостигает максимума и минимума, называются точками экстремума, а значенияфункции в этих точках экстремумами функции.
Обратим внимание на то,что функция, определенная на отрезке, может достигать максимума и минимуматолько в точках, заключенных внутри рассматриваемого отрезка.
Отмети, что если функцияимеет в точке максимум, то это не означает, что в этой точке функция имеетнаибольшее значение во всей области определения. На рисунке, рассмотренномвыше, функция в точке x1 имеет максимум, хотя есть точки, вкоторых значения функции больше, чем в точке x1. Вчастности, f(x1) f(x4)т.е. минимум функции больше максимума. Из определения максимума следует только,что это самое большое значение функции в точках, достаточно близких к точкемаксимума.
Теорема 1. (Необходимоеусловие существования экстремума.) Если дифференцируемая функция y=f(x) имеетв точке x= x0экстремум, то ее производная в этой точкеобращается в нуль.
Доказательство. Пусть для определенности в точке x0функция имеет максимум. Тогда при достаточно малых приращениях Δxимеем f(x0+ Δx)0), т.е. />Но тогда
/>
Переходя в этихнеравенствах к пределу при Δx→ 0 и учитывая, что производная f'(x0) существует, а следовательно предел, стоящий слева, независит от того как Δx → 0, получаем: при Δx →0 – 0 f'(x0) ≥ 0 а при Δx → 0+ 0 f'(x0) ≤ 0. Так как f '(x0)определяет число, то эти два неравенства совместны только в том случае, когда f'(x0) = 0.
Доказанная теоремаутверждает, что точки максимума и минимума могут находиться только среди техзначений аргумента, при которых производная обращается в нуль.
Мы рассмотрели случай,когда функция во всех точках некоторого отрезка имеет производную. Как жеобстоит дело в тех случаях, когда производная не существует? Рассмотримпримеры.
Примеры.
y=|x|.
Функция не имеетпроизводной в точке x=0 (в этой точке график функции не имеетопределенной касательной), но в этой точке функция имеет минимум, так как y(0)=0,а при всех x≠ 0y > 0.
/>
Функция />не имеет производной приx=0, так как />обращается в бесконечность приx=0.Но в этой точке функция имеет максимум.
/>
Функция />не имеет производной приx=0, так как />при x→0. В этой точкефункция не имеет ни максимума, ни минимума. Действительно, f(x)=0 и при xf(x)x>0f(x)>0.
/>
Таким образом, изприведенных примеров и сформулированной теоремы видно, что функция может иметьэкстремум лишь в двух случаях: 1) в точках, где производная существует и равнанулю; 2) в точке, где производная не существует.
/>
Однако, если в некоторойточке x0мы знаем, что f '(x0)=0, тоотсюда нельзя делать вывод, что в точке x0функция имеетэкстремум.
Например.
/>.
Но точка x=0 неявляется точкой экстремума, поскольку слева от этой точки значения функциирасположены ниже оси Ox, а справа выше.
Значения аргумента изобласти определения функции, при которых производная функции обращается в нульили не существует, называются критическими точками.
Из всего вышесказанногоследует, что точки экстремума функции находятся среди критических точек, и,однако, не всякая критическая точка является точкой экстремума. Поэтому, чтобынайти экстремум функции, нужно найти все критические точки функции, а затемкаждую из этих точек исследовать отдельно на максимум и минимум. Для этогослужит следующая теорема.
Теорема 2. (Достаточноеусловие существования экстремума.) Пусть функция непрерывна на некотороминтервале, содержащем критическую точку x0, и дифференцируемаво всех точках этого интервала (кроме, быть может, самой точки x0).Если при переходе слева направо через эту точку производная меняет знак с плюсана минус, то в точке x = x0функция имеет максимум.Если же при переходе через x0слева направо производнаяменяет знак с минуса на плюс, то функция имеет в этой точке минимум.
Таким образом, если
f '(x)>0 при xx0и f '(x)0 при x> x0, то x0–точка максимума;
/>при xx0и f '(x)>0 при x> x0, то x0–точка минимума.
/>
Доказательство. Предположим сначала, что припереходе через x0производная меняет знак с плюса на минус,т.е. при всех x, близких к точке x0f '(x)>0для x0, f '(x)0 для x> x0.Применим теорему Лагранжа к разности f(x) — f(x0) = f'(c)(x- x0), где c лежит между x и x0.
Пусть x 0.Тогда c0и f '(c)>0. Поэтомуf'(c)(x- x0)0и, следовательно,
f(x) — f(x0)0, т.е. f(x)0).
Пусть x > x0.Тогда c> x0и f '(c)0. Значитf'(c)(x- x0)0. Поэтому f(x) — f(x0)f(x)f(x0).
Таким образом, для всехзначений x достаточно близких к x0f(x) f(x0).А это значит, что в точке x0функция имеет максимум.
Аналогично доказываетсявторая часть теоремы о минимуме.
Проиллюстрируем смыслэтой теоремы на рисунке. Пусть f '(x1)=0 и для любых x,достаточно близких к x1, выполняются неравенства
f '(x)0 при x1, f'(x)>0 при x> x1.
Тогда слева от точки x1функция возрастает, а справа убывает, следовательно, при x = x1функция переходит от возрастания к убыванию, то есть имеет максимум.
Аналогично можнорассматривать точки x2 и x3.
/>
Схематически всевышесказанное можно изобразить на картинке:
Правило исследованияфункции y=f(x) на экстремум
Найти область определенияфункции f(x).
Найти первую производнуюфункции f '(x).
Определить критическиеточки, для этого:
найти действительныекорни уравнения f '(x)=0;
найти все значения xпри которых производная f '(x) не существует.
Определить знакпроизводной слева и справа от критической точки. Так как знак производнойостается постоянным между двумя критическими точками, то достаточно определитьзнак производной в какой-либо одной точке слева и в одной точке справа откритической точки.
Вычислить значениефункции в точках экстремума.
Примеры. Исследоватьфункции на минимум и максимум.
/>. Область определения функции D(y)=R.
Найдем производнуюзаданной функции
/>
Определим критическиеточки />.Производная не существует при х2= 0. Следовательно,критические точки: 0 и 2/5. Нанесем их на числовую ось и определим знакпроизводной на каждом из полученных промежутков.
/>
/>
/>
/>
/>
Критическая точка функцииx =3. Точка x= –1 не входит в область определения функции.
/>
/>
НАИБОЛЬШЕЕИ НАИМЕНЬШЕЕ ЗНАЧЕНИЯ ФУНКЦИИ НА ОТРЕЗКЕ
Наибольшим значением функции на отрезкеназывается самое большое из всех ее значений на этом отрезке, а наименьшим– самое маленькое из всех ее значений.
Рассмотрим функцию y=f(x)непрерывную на отрезке [a, b]. Как известно, такая функция достигаетсвоего наибольшего и наименьшего значений, либо на границе отрезка, либо внутринего. Если наибольшее или наименьшее значение функции достигается во внутреннейточке отрезка, то это значение является максимумом или минимумом функции, тоесть достигается в критических точках.
Таким образом, получаемследующее правило нахождения наибольшего и наименьшего значений функции наотрезке[a, b]:
Найти все критическиеточки функции в интервале (a, b) и вычислить значения функции в этихточках.
Вычислить значенияфункции на концах отрезка при x = a, x = b.
Из всех полученныхзначений выбрать наибольшее и наименьшее.
Примеры.
Найти наибольшее инаименьшее значения функции />на отрезке [–2; –0,5].
Найдем критические точкифункции. />
Вычислим значения функциив найденной точке и на концах заданного отрезка.
/>
Итак, />
Найти наибольшее инаименьшее значения функцииy=x-2·ln x на [1; e].
/>
/>
Чему равна наименьшаяплощадь боковой поверхности прямого кругового конуса объема 3π?
/>
По теореме Пифагора
/>.
/>
Следовательно, />.
/>.
Найдем критические точкифункции S: S' = 0, т.е. />
Покажем, что принайденном значении h функция Sбок достигает минимума.
/>.
/>
/>
Найти радиус основания ивысоту цилиндра наибольшего объема, который можно вписать в шар радиусом R.
Пусть r – радиусоснования цилиндра, h – высота.
Нам нужно максимизироватьобъем цилиндра />.
Используя условие задачи,найдем связь между r и h. По теореме Пифагора из треугольника ABCследует, что />. Отсюда
/>.
/>, по смыслу задачи 0≤h≤2R.
/>.
Покажем, что принайденном значении h функция V принимает наибольшее значение.
/>
Условный экстремумфункции нескольких переменных
Часто приходится решатьзадачу о нахождении экстремума функции нескольких переменных при наличиинекоторых дополнительных условий.
Примеры: 1) Найти длинысторон прямоугольника, имеющего наибольшую площадь S = ху при заданной величинеего периметра Р = 2х + 2у.
2) Решить ту же задачупри условии, что х — у > а, а = const.
Задача 1) имеетдополнительное условие в виде равенства, а задача 2) еще имеет условие в виденеравенства. Мы будем рассматривать задачи вида 1), которые называются задачамина условный экстремум. Задачи вида 2) называются задачами линейного(нелинейного, динамического) программирования и рассматриваются в специальныхкурсах.
Для функции двухпеременных имеем:
О: Пусть z =/>(х, у)определена на множестве D. Пусть также L/>D — подмножество, заданноеусловием F(x, у) = 0. Точка />называется точкой условногомаксимума (минимума) для/>(х, у), если/>> 0 такое, что в/>для />выполнено/>
Условные максимум иминимум называются условными экстремумами.
Для функции двухпеременных задачу о нахождении точек условного экстремума решают одним изследующих двух способов.
1. Если это возможно, изуравнения связи F(x, у) = 0 находят />и затем подставляют в функцию z=/>(x, у). Врезультате
/>становится функцией однойпеременной х, для которой задача решается известными методами.
В противном случае длянахождения точек экстремума применяется метод множителей Лагранжа, которыйзаключается в следующем.
2. Составляютфункцию Лагранжа
/>
где/>R — множитель Лагранжа.Очевидно, что на множестве L второе слагаемое обращается в нуль вследствиевыполнения условия F(x, у) = 0. Таким образом, на L выполнено/>/>и поэтому задача вслучае функции двух переменных, сводится к поиску экстремума функции однойпеременной х.
Формально процедурарешения такова. Приравниваем к нулю все частные производные функции Лагранжа:
/>
и отсюда находим решение/>
Пусть/>— любое из решений этойсистемы.
Подставляя в/>найденный из
уравнения связидифференциал/>и обозначая
/>(в опорном конспекте № 12/>записано в видеопределителя), получаем/>/>Тогда, если/>имеет в т./>
условный максимум, если/>> 0 — тоусловный минимум.
Пример: Найти точкиэкстремума функции/>/>если уравнение связи у — х = 0.Рассмотрим оба способа решения. 1. Из аналитической геометрии известно, чтолюбое уравнение 2-го порядка определяет в пространстве поверхность второгопорядка. Выделим в заданном уравнении полные квадраты х и у:/>/>— уравнение параболоидавращения с вершиной в т. N(1, 2, 9) (рис. 12.3); у = х — уравнение плоскости.Подставляя уравнение связи в исходную функцию, получаем
/>
/>
Исследуем на экстремум:
/>— максимум в т.М(1,5; 1,5).
Функция/>имеет условный экстремум
/>= 4-2 · 2,25 + 6 · 1,5 = 13 — 4,5= 8,5. 2. Составим/>/>
/>линейная система уравнений.
Используя метод Крамера,получим:/>и/>
/>/>— т. условного максимума
Для функции/>при наличии mуравнений связи />функция Лагранжа будет иметь вид
/>/>
Необходимые условияусловного экстремума выражаются системой (n + m) уравнений:
/>
Правилоисключения интервалов
Пусть функция f унимодальна на интервале a£x£b, а ее минимум достигается в точке x*.
Рассмотрим точки x1 и x2, расположенные в интервале такимобразом, что a
Если f(x1)>f(x2), то точка минимума f(x) не лежит винтервале (a,x1), т.е. x*Î(x1,b)
2. Если f(x1)
/>3. Если f(x1)=f(x2), то можно исключить оба крайних интервала (a,x1) и (x2,b), при этом x*Î(x1,x2).
Согласно правилуисключения интервалов можно реализовать процедуру поиска, позволяющую найтиточку оптимума путем последовательного исключения частей исходногоограниченного интервала.
Поиск завершается, когдаоставшийся интервал уменьшается до достаточно малых размеров.
Достоинства этих методов:
устраняется необходимостьполного перебора всех допустимых точек.
методы основаны лишь навычислении значений функции.
(при этом не требуется,чтобы исследуемые функции были дифференцируемы).
Методзолотого сечения
В методе же золотогосечения мы будем выбирать расположение точек х1 и х2,рассекающих интервал, таким образом, чтобы на каждом шаге уменьшения интервалаодна из этих точек совпадала с одной из аналогичных точек предыдущего шага,т.е. на каждом шагу уменьшения интервала фактически вводится только одна новаяточка, для которой требуется произвести только одно вычисление значения целевойфункции.
Такое рассечениеинтервала новой точкой может быть точно рассчитано. Забегая вперед, запишу этупропорцию:
Точки х1 и х2расположены симметрично относительно середины интервала (a, b).
b-x1 x2-a -1+/>
/>/> = = » 0.618
/>b-a b-a 2 .
Такое рассечениеинтервала и получило название золотого сечения.
Введем обозначения:
D1 = b-a – исходныйинтервал.
D2 – интервал, полученный после уменьшения интервала D1 отбрасыванием его левого или правого подинтервала.
DК+1 – интервал, полученный послеуменьшения интервала DК.
Рассмотрим теперь методзолотого сечения формально. Золотым сечением отрезка называется делениеотрезка на две неравные части так, чтобы отношение всего отрезка к большейчасти равнялось отношению большей части к меньшей.
Золотое сечение отрезка [a, b] производится двумя симметрично расположенными точками (х1и х2).
Т.е. (b-a)/(b-x1)=(b-x1)/(x1-a)=g и (b-a)/(x2-a)=(x2-a)/(b-x2)=g.
/>Можно показать, что g = (1+Ö5)/2»1.618.
Примечательно то, чтоточка х1 в свою очередь производит золотое сечение отрезка [a, x2], т.е. (x2-a)/(x1-a) = (x1-a)/(x2-x1) = g.
Аналогично, точка х2производит золотое сечение отрезка [x1, b].
Итак, метод золотогосечения состоит в том, что длины последовательных интервалов берутся вфиксированном отношении:
D1/D2 = D2/D3 = … =g.
Из соотношений DК/DK+1 = DK+1/DK+2 = g и DK = DK+1 + DK+2
Получаем: DK/DK+1 = (DK+1+DK+2)/DK+1=1+DK+2/DK+1
g = 1 + 1/g или g2 — g -1 = 0.
Корнем этого уравненияявляется золотое сечение.
g=(Ö5+1)/2 »1.618 /> t = 1/g = (Ö5-1)/2 » 0.618.
Можно записать формулыдля точек х1 и х2, производящих золотое сечение наинтервале [a, b]:
x1 = a+(1-t)(b-a) x2 = a+t(b-a)
Алгоритм метода золотогосечения.
Ввести a, b, e-точность вычисления, t=(Ö5-1)/2
Вычислить:
x1 =b– (b-a)t; x2 =a + (b-a)t
Вычислить: y1 = f(x1); y2 = f(x2)
если y1£y2, то для дальнейшего деления оставляют интервал [a, x2]
и выполняют следующее:
b: = x2; x2: = x1; y2: = y1; x1:= b-(b-a)t y1 := f(x1)
в противном случае (если y1 > y2), для дальнейшего деления оставляютинтервал [x1, b] ивыполняют следующее:
a := x1; x1 := x2; y1 := y2; x2:= a+(b-a)t; y2 :=f(x2);
Сравнение длины интерваланеопределенности с заданной точностью e:
Если (b-a)£e, то положить x* := (b-a)/2 (точка минимума), иначе (если (b-a)
Максимуми минимум функции нескольких переменных
Напомним, что подокрестностью точки плоскости понимается внутренность любого прямоугольника,окружающего эту точку, исключая саму точку (проколотая окрестность).
В пространстве это будетпроизвольный параллелепипед, содержащий эту точку за вычетом самой точки.
Определение 15.1. Максимумом (строгим) функции f (x,y) называется такое значение f(x1, y1) этойфункции, которое больше всех ее значений f(x, y), принимаемых данной функциейв точках некоторой окрестности точки О(х1, у1).(Окрестность может быть весьма малой по своим линейным размерам).
Определение 15.2. Минимумом (строгим) функции f (x, y) называется такое значение f (x2,y2), которое меньшевсех ее значений f (x,y), принимаемых данной функцией в точках некоторойокрестности О (х2, у2).
Максимум или минимумфункции f (x, y) называетсяэкстремумом этой функции. Точка, в которойдостигается экстремум, называется точкой экстремума (точка минимума,точка максимума).
Аналогично определяетсяэкстремум функции f (x, y, z) и т.д.
Теорема 15.1. (Необходимый признак экстремумафункции нескольких переменных). В точке экстремума функции несколькихпеременных каждая ее частная производная первого порядка либо равна нулю, либоне существует.
Доказательство. Пусть u= f (x, y) и f (xo, yo) — ее максимум (для минимума рассуждения аналогичны). Зафиксируем одну из переменных, например, у, полагая у = уо, тогда получим функцию одной переменной U1 =f (x, yo), которая, очевидно, будет иметь максимум при х = хо. Отсюда, на основании теории экстремума однойпеременной, получаем, что /> или /> несуществует.
Пусть теперь у=уо,а хо — фиксируем, тогда /> или не существует.
Следствие В точке экстремума Мо (хо,уо) дифференцируемой функции f (x, y) выполнены равенства />
Для U = f(x,y,z) в точке Мо (хо, уо, zо)будет выполнено условие />.
Замечание. Точку, в которой частные производныепервого порядка либо не существуют, либо равны нулю, называюткритической.
Т.е. экстремумы функциинескольких переменных могут достигаться лишь в критических точках.
Пример 15.1. Покажем, чтоуказанные выше условия не являются достаточными. Пусть z = f(x, y) = x × y тогда имеем />
Следовательно, /> Однакоточка 0(0,0) не является точкой экстремума, т.к. в любой окрестности точки 0 (о, о) имеются точки
A (e,e) и B(- e, e) " e > 0 :
f(A) = e2 > 0 = f(0) и f(B) = — e2
Абсолютныйэкстремум
Определение 15.3. Наименьшее или наибольшее значениефункции в данной области называется абсолютным экстремумом функции.(Соответственно, абсолютный минимум, абсолютный максимум).
Теорема 15.2. (Вайерштрасс) Функция,непрерывная в ограниченной и замкнутой области, достигает в этой области своегонаименьшего и своего наибольшего значения. (Без доказательства)
Теорема 15.3. Абсолютный экстремум функции вданной области достигается либо в критической точке функции, принадлежащей этойобласти, либо в граничной точке области. (Без доказательства)
Пример 15.2. Для функцииz = x × y найти абсолютный экстремум втреугольной области S с вершинами О(0,0), А(1,0), В(0,2).
Определим
/>
/>
Критическая точка O(0,0) Î S. На участке ОА имеем у = 0 (0 £ х £ 1) и тогда z = 0.
Аналогично ОВ: х = 0 (0 £ у £ 2) Þ z = 0.
Наконец, отрезок АВ имеет уравнение /> или у = 2 — 2х (0 £ х £ 1).
Отсюда
z = x × y = 2x — 2x2 .
Имеем />, т.е.при /> ит.к. />,то в точке /> функция Z достигает своегонаибольшего значения /> на отрезке АВ.
Итак, наименьшеезначение z в S есть m=0 и оно реализуется в точках отрезков ОВ и ОА,составляющих часть границы Г.
/> достигает в точке />
Заключение
В работе приведены ичисленные методы нахождения экстремума. Необходимость в них возникает, когдасистема из частных производных не имеет аналитического решения или содержитсложную нелинейность. Аналитически решается лишь малая часть задач оптимизации,поэтому рассматриваются и некоторые численные алгоритмы. Численные алгоритмызапрограммированы, как правило, в математических компьютерных пакетах, которыеобеспечивают высокую точность и скорость нахождения экстремума, но, ксожалению, не всегда находят глобальный экстремум. Среди таких пакетов следуетотметить математические программы Maple, MatLab, Mathematica. Но это не означает, что длянахождения экстремумов следует пользоваться ими, не имея понятия о математических алгоритмах.
В работе в видуограниченного объема не рассматривались задачи оптимизации функций сограничениями, и задачи многокритериальной оптимизации. Тем не менее, онисоставляют важный класс задач поиска экстремума, которые часто появляются внаучной и практической деятельности.
Литература
1. Акулич И.Л.Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
2. Алексеев В.М.,Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. — М.: Наука, 1984.
3. Банди Б. Методыоптимизации. Вводный курс. — М.: Радио и связь, 1988.
4. Васильев Ф.П.Численные методы решения экстремальных задач. — М.: Наука, 1980.
5. Гилл Ф., МюррейУ., Райт М. Практическая оптимизация. — М.: Мир, 1985.
6. Евтушенко Ю.Г.Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982.
7. Карманов В.Г.Математическое программирование. — М.: Наука, 1975.
8. Лесин В.В.,Лисовец Ю.П. Основы методов оптимизации. — М.: Изд-во МАИ, 1995.
9. Летова Т.А.,Пантелеев А.В. Экстремум функций в примерах и задачах. M.: Изд-во МАИ, 1998.
10. Пшеничный Б.И.,Данилин Ю.М. Численные методы в экстремальных задачах. — М.: Наука, 1975.
11. Федоров В.В.Численные методы максимина. — М.: Наука, 1979.