Целевая функция представляет собой функцию с некоторыми переменными, от которых непосредственно зависит достижение оптимальности. Также она может выступать в качестве нескольких переменных, которые характеризуют тот или иной объект. Можно сказать, что, по сути, она показывает, как мы продвинулись в достижении поставленной задачи.
Примером таких функций может выступать расчет прочности и массы конструкции, мощности установки, объема выпуска продукции, стоимости перевозок и другие.
Целевая функция позволяет ответить на несколько вопросов:
Выгодно или нет то или иное событие;
В правильном ли направлении идет движение;
Насколько верно сделан выбор и т.д.
Если мы не имеем возможности влиять на параметры функции, то, можно сказать, что и сделать мы ничего не можем, разве что только проанализировать и все. Но чтобы быть в состоянии что-то изменить, обычно существуют изменяемые параметры функции. Главная задача - это изменить значения на те, при которых функция станет оптимальной.
Целевые функции не всегда могут быть представлены в виде формулы. Это может быть таблица, например. Также условие может быть в виде нескольких целевых функций. Например, если требуется обеспечить максимальную надежность, минимальные затраты и минимальную материалоемкость.
Задачи на оптимизацию должны иметь важнейшее исходное условие - целевую функцию. Если мы ее то можно считать, что оптимизации не существует. Иными словами, если нет цели, то и нет путей ее достижения, а тем более выгодных условий.
Задачи на оптимизацию бывают условными и безусловными. Первый вид предполагает ограничения, то есть определенные условия при постановке задачи. Второй вид состоит в том, чтобы отыскать максимум или при существующих параметрах. Зачастую такие задачи предполагают поиск минимума.
В классическом понимании оптимизации подбираются такие значения параметров, при которых целевая функция удовлетворяет желаемым результатам. Также ее можно обозначить как процесс подбора самого лучшего варианта из возможных. Например, выбрать лучшее распределение ресурсов, вариант конструкции и т.д.
Существует такое понятие, как неполная оптимизация. Она может образоваться по нескольким причинам. Например:
Число попавших в максимальную точку систем ограничено (уже установлена монополия или олигополия);
Нет монополии, но отсутствуют ресурсы (недостаток квалификации на каком-либо конкурсе);
Отсутствие самой а точнее «незнание» ее (мужчина мечтает о некой красивой женщине, но неизвестно, существует ли такая в природе) и т.д.
В условиях рыночных отношений управления сбытовой и производственной деятельностью фирм и предприятий основой принятия решений является информация о рынке, а обоснованность этого решения проверяется уже при выходе на рынок с соответствующим товаром или услугой. В таком случае отправной точкой является изучение потребительского спроса. Для нахождения решений устанавливается целевая функция потребления. Она показывает количество потребляемых благ и степень удовлетворения потребностей потребителя, а также зависимость между ними.
При решении реальных задач оптимизации данный метод применяется редко, т.к. зачастую производную целевой функции определить сложно или невозможно.
Метод равномерного перебора
Пусть дана функция (см. рис 7.1).
Рис.7.1. Графическая иллюстрация метода равномерного перебора
В соответствии с данным методом алгоритм поиска заключается в следующем. Фиксируют величину шага . Вычисляют значения целевой функции в точках и 
и . Полученные значения сравнивают. Запоминают меньшее из этих двух значений. Далее выбирается точка и в ней вычисляется значения целевой функции . Сравнивается оставшееся на предыдущем шаге значение и значение . Наименьшее из них опять запоминают. Так поступают до тех пор, пока очередное значение не превысит . Последнее оставшееся значение является приближенным значением глобального минимума.
Трудности при использовании данного метода. Если целевая функция имеет узкую впадину, подобную приведенной на рисунке, то можно ее проскочить, и вместо точки глобального минимума определить точку локального минимума. Т.е. вместо можно найти . Эта проблема частично снимается, если выбрать очень маленький шаг, но при этом потребуется много времени (в том числе и машинного) для решения задачи.
Метод золотого сечения
Рассматриваемая в данном методе функция должна быть унимодальной . Функция является унимодальной на отрезке , если она на этом отрезке имеет единственную точку глобального минимума и слева от этой точки является строго убывающей, а справа строго возрастающей. Другимисловами, функция унимодальна, если выполняются следующие соотношения (рис.7.2):
Суть метода золотого сечения заключается в том, чтобы определить точку глобального минимума на отрезке за минимальное количество шагов, т.е. за минимальное количество вычислений целевой функции.
В соответствии с данным методом в каждый текущий момент времени рассматривается всегда две точки, например, в начальный момент точки и так, чтобы 
. При этом возможен один из двух случаев (рис.7.3):
Рис.7.3. Иллюстрация обоснования исключения отрезков
Согласно свойству унимодальной функции в первом случае искомая точка не может находиться на отрезке , во втором случае на отрезке (показаны штриховкой). Значит, область поиска сужается, и следующую точку необходимо брать на одном из укороченных отрезков: - случай 1 или - случай 2.
Теперь следует определиться, где на исходном отрезке необходимо выбирать точки и . Первоначально ничего не известно о положении точки (графиков нет, и они не строятся, здесь мы их приводим для наглядной иллюстрации сути метода, при реальной оптимизации есть только выражение для целевой функции). Поэтому любой из приведенных выше случаев возможен с одинаковой вероятностью. Это означает, что лишним может оказаться любой из отрезков: или . Отсюда ясно, что точки и следует выбирать симметрично относительно середины отрезка .
Далее для того, чтобы максимально сузить область поиска, эти точки должны быть поближе к середине исходного отрезка. Однако слишком близко к середине отрезка их тоже брать не следует, т.к. мы хотим построить алгоритм, для реализации которого необходимо общее минимальное количество вычислений целевой функции. Рассмотрим рис. 7.4.
Рис.7.4. Иллюстрация обоснования расположения точек на отрезке
Выбирая на первом шаге сравниваемые точки слишком близко к середине отрезка , мы исключим из рассмотрения большой отрезок для случая 1 или для случая 2. Но на втором шаге величина исключаемого отрезка значительно уменьшится (будет исключен отрезок для случая 1 или отрезок для случая 2).
Таким образом, с одной стороны, точки следует брать рядом с серединой отрезка, а, с другой стороны, слишком близко друг от друга их брать нельзя. Т.е. необходимо найти некую «золотую середину». Для этого рассмотрим для простоты вместо отрезка отрезок единичной длины – рис.7.5.
Рис.7.5. Обоснование «золотой середины» расположения точек на отрезке
На этом рисунке .
Для того, чтобы точка B была «выгодной» как на данном, так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB/AD = BC/AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD/AD = BC/BD. В обозначениях координаты x эти пропорции принимают вид: x /1 = (1 – 2x )/(1 – x ). Решим эту пропорцию:
Корни этого уравнения равны:
не приемлем, т.е. уравнение имеет один корень.
О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка.
Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.
Итак, алгоритм метода «золотого сечения» заключается в следующем (см. также рис.7.6). На исходном отрезке [a ,b ] выбираются две точки x 1 и x 2 , так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках – и . Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой функции (здесь отрезок [x 2 ,b ]). Т.е. исходный отрезок [a ,b ] «стягивается» до отрезка [a ,b 1 ]. Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x 1 ставится точка x 3 . Для нее рассчитывается значение целевой функции и сравнивается с . Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок [a ,x 3 ]. Текущий отрезок «стягивается» до нового отрезка, здесь это [a 1 ,b 1 ] и т.д.
Рис.7.6. Иллюстрация алгоритма метода «золотого сечения»
Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.
Численные методы решения задач нелинейного программирования (поиск экстремума функции n – переменных)
Метод линеаризации (приведения задачи нелинейного программирования к задаче линейного программирования)
Данный метод строго не относится к численным методам решения задач оптимизации. Но он эффективен и часто используется для решения практических задач. Рассмотрим суть данного метода на примере, который решался в лекции 5. Напомним формулировку задачи:
найти и . Целевая функция 
, ограничения:
1 этап . Приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:
После вычислений получим:
 | (8.1) |
| (8.2) |
 | (8.3) |
После логарифмирования целевой функции:
Далее задача решается с применением симплекс - алгоритма или графо – аналитически (см. рис.8.1 и вычисления, сопровождающие построения). Для построения области допустимых решений (ОДР) в логарифмических координатах работаем с ограничениями (8.1) – (8.3). Ограничения (8.1) и (8.2) – это ограничения, графически представляющие собой прямые линии, параллельные соответственно осям и . Причем, левая ограничительная линия в ограничении (8.1) совпадает с осью . Ограничение (8.3) представляет собой прямую линию, наклонную под углом 45 градусов к осям, имеющая координаты пересечения осей «0-1». Для нахождения точки касания линии, соответствующей целевой функции, сначала строим «произвольную» линию для целевой функции, приравнивая ее выражение к произвольному числу в данном масштабе. Приравняем выражение для целевой функции к числу «1,2»:
| 0,3 | ||
| 1,2 | 1,5 |
Если целевая функция стремится к минимуму, т.е. , то прямая линия, соответствующая ей, коснется границы ОДР в точке с координатами:
Рис.8.1. Графическая иллюстрация графо - аналитического решения задачи оптимизации методом линеаризации
Метод покоординатного спуска в задачах без ограничений
Это задача безусловной минимизации
, т.е. задачи минимизации целевой функции
на всем пространстве переменных (на всем евклидовом пространстве). Если требуется решить задачу максимизации, то выражение целевой функции умножают на (-1) и снова решается задача минимизации.
Суть данного метода заключается в построении последовательности точек
, монотонно уменьшающих значение целевой функции .
Согласно этому методу направления спуска выбирается параллельно координатным осям, т.е. сначала спуск осуществляется вдоль первой оси ОХ 1 затем вдоль второй оси ОХ 2 и т.д. до последней оси ОХ n .
Пусть – начальная точка (см. рис. 8.2), a – некоторое положительное число. Вычисляют значение целевой функции в этой точке – . Далее вычисляют значение целевой функции при и проверяют выполнение неравенства
В случае выполнения этого неравенства полагают x (1) = x (0) - a. Если оба неравенства и (8.4), и (8.5) не выполняются, то x (1) = x (0) .
Рис.8.2. Графическая иллюстрация поиска точки минимума методом покоординатного спуска
Второй шаг производят вдоль координатной оси OX 2 . Вычисляют значение функции в точке (x (1) + a) и сравнивают его с предыдущим значением, т.е. проверяют выполнение неравенства
В случае выполнения неравенства (8.7) считают, что x (2) = x (1) – a. Если оба неравенства и (8.6), и (8.7) не выполняются, то принимают x (2) = x (1) .
Так перебирают все n – направлений координатных осей. На этом первая итерация закончена. На n - м шаге будет получена некоторая точка x (n) . Если , то аналогично, начиная с x (n) осуществляют вторую итерацию. Если же x (n) = x (0) (это имеет место, если на каждом шаге ни одно из пары неравенств не окажется выполненным), то величину шага нужно уменьшить, взяв, например, a n+1 = a n /2, и в следующей итерации использовать новое значение величины шага.
Последующие итерации выполняют аналогично. На практике вычисления прекращают при выполнении какого – либо условия окончания счета, например
,
где f (x ) (k+1) – значение целевой функции на (к+1) итерации;
f (x ) (k) – значение целевой функции на к –ой итерации;
Некоторое положительное число, характеризующее точность решения исходной задачи
минимизации целевой функции.
Метод покоординатного спуска в задачах с ограничениями
Данный метод распространяется на задачи, с простыми ограничениями типа:
| (8.8) |
| (8.9) |
| (8.10) |
Основные процедуры данного метода аналогичны предыдущему методу. Различие заключается в том, что наряду с проверкой выполнения неравенств f (x (0) + a) < f (x (0)) (f (x (0) – a) < f (x (0))), f (x (1) + a) < f (x (1)) (f (x (1) – a) < f (x (1))) и т.д. осуществляют проверку выполнения неравенств (8.8) – (8.10). Выполнение или невыполнение этих неравенств приводит к тем же последствиям, что и выполнение или невыполнение неравенств, приведенных выше.
Методы решения многокритериальных задач оптимизации
Эта задачи проектирования (оптимизации), в которых используется не один, а несколько критериев. На практике такие задачи возникают, когда проектируемый объект не может быть описан однокритериальной зависимостью, или объединить отдельные критерии в единый критерий не представляется возможным. Такое объединение критериев в единый критерий применяется, и оно будет рассмотрено ниже. Но это объединение, как правило, бывает формальным, искусственным. С математической точки зрения не существует идеального способа, метода решения таких задач. Каждый из них имеет преимущества и недостатки. Рассмотрим некоторые методы решения многокритериальных задач оптимизации.
Метод поиска Парето – эффективных решений
Рассмотрим его суть на примере использования двух критериев. Критерии при использовании данного метода являются равнозначными.
Пусть имеется множество вариантов решения. По каждому из вариантов определены значения всех критериев. Представим множество оценок вариантов решения в пространстве критериев (рис.9.1).
Рис.9.1. Иллюстрация поиска Парето – эффективных решений
На рис.9.1 приняты следующие обозначения:
К 1 и К 2 – критерии оценки вариантов решения;
Y = {y 1 , y 2 , …, y m }- множество оценок альтернативных вариантов решения;
К 11 , К 12 , … , К 1m - значения первого критерия для 1, 2, … , m - го варианта решения;
К 21 , К 22 , … , К 2m – значения второго критерия для 1, 2, … , m - го варианта решения;
P(Y) – множество Парето – эффективных оценок решений.
Правило . Множество Парето – эффективных оценок P(Y’) представляет собой «северо – восточную» границу множества Y без тех его частей, которые параллельны одной из координатных осей или лежат в «глубоких» провалах.
Для случая, изображенного на рис.9.1, Парето – эффективные оценки состоят из точек кривой (bc), исключая точку (c), и линии (de).
Преимущества метода: 1) Критерии равнозначны; 2) Метод математически объективен.
Недостаток метода: 1) Одно окончательное решение получается только в частном случае, т.е. количество Парето – эффективных решений, как правило, более одного.
Пример . Имеется 10 вариантов металлорежущих станков, среди которых для проектируемого участка необходимо выбрать наилучший. Станки оценены экспертами по двум показателям (критериям): производительности и надежности. Оценивание производилось по 11 - бальной шкале от 0 до 10. Результаты оценки станков приведены в таблице 9.1.
Таблица 9.1 Экспертные оценки станков по критериям производительности и надежности
Представим множество оценок вариантов металлорежущих станков в пространстве критериев (рис.9.2):
Парето – эффективными решениями здесь являются варианты станков С 5 , С 7 и С 9 .
Рис.9.2. Пример поиска Парето – эффективных решений
Метод решения многокритериальных задач оптимизации с использованием обобщенного (интегрального) критерия
Суть данного метода заключается в том, что частные критерии каким - либо образом объединяются в один интегральный критерий , а затем находится максимум или минимум данного критерия.
Если объединение частных критериев производится, исходя из объектной взаимосвязи частных критериев и критерия обобщенного, то тогда оптимальное решение будет корректно. Но такое объединение осуществить крайне сложно или невозможно, поэтому, как правило, обобщенный критерий есть результат чисто формального объединения частных критериев.
В зависимости от того, каким образом частные критерии объединяются в обобщенный критерий различают следующие виды обобщенных критериев:
Частные критерии имеют различную физическую природу и поэтому различную размерность. А значит просто суммировать их некорректно. В связи с этим в предыдущей формуле числовые значения частных критериев делятся на некоторые нормирующие делители, которые назначается следующим образом:
1. В качестве нормирующих делителей принимаются директивные значения параметров или критериев, заданные заказчиком. Считается, что значения параметров, заложенные в техническом задании, являются оптимальными или наилучшими.
2. В качестве нормирующих делителей принимаются максимальные (минимальные) значения критериев, достигаемые в области допустимых решений.
Размерности самих частных критериев и соответствующих нормирующих делителей одинаковы, поэтому в итоге обобщенный аддитивный критерий получается безразмерной величиной.
Пример . Определить оптимальный вариант машины с использованием обобщенного (интегрального) аддитивного критерия. Частными критериями, с помощью которых оценены варианты машины, являются ее производительность и надежность (наработка на отказ). Оба критерия «работают» на максимум, т.е. наилучшими вариантами машины являются те из них, которые обеспечивают наибольшую ее производительность и надежность. Исходные данные для решения задачи приведены в таблице 9.2.
Таблица 9.2. Исходные данные для определения оптимального варианта исполнения машины
Целевая функция на основе аддитивного критерия запишется следующим образом:
В качестве нормирующих делителей в данной задаче примем наилучшие (максимальные) значения частных критериев:
Значения обобщенного аддитивного критерия рассчитываются для каждого варианта машины:
Вариант 1.
F (X ) = 0,6(1000/4000) + 0,4(1500/1500) = 0,55.
Вариант 2
F (X ) = 0,6(2000/4000) + 0,4(1000/1500) = 0,558.
Вариант 3
F (X ) = 0,6(4000/4000) + 0,4(500/1500) = 0,732.
Оптимальным является 3 вариант машины , т.к. ему соответствует максимальное значение обобщенного аддитивного критерия.
Один из недостатков этого метода заключается в том, что весовые коэффициенты назначает проектировщик. Разные проектировщики могут назначать разные весовые коэффициенты. Пусть, например, C 1 = 0,4; C 2 = 0,6. Определим теперь значения аддитивных критериев для вариантов машины:
Вариант 1.
Вариант 2.
Вариант 3.
Т.е. при таком изменении значений весовых коэффициентов оптимальным уже будет 1 вариант машины.
Преимущество данного метода: как правило, всегда удается определить единственный оптимальный вариант решения.
Трудность решения задач нелинейной оптимизации обусловлена рядом факторов. Во-первых, при нелинейных ограничениях область допустимых решений может не быть выпуклой или даже состоять из ряда несвязанных областей. Во-вторых, процедура решения обычно позволяет выделить экстремум, но не дает гарантии, что этот экстремум глобальный. Эти и ряд других обстоятельств приводят к тому, что нелинейную задачу удается решить не всегда или же довольствоваться приближенным решением.
Задача на безусловный экстремум
Пусть в некоторой области n-мерного пространства R n задана функция п переменных WQQ. Требуется найти точки X * =(*1 х„), в которых эта функция имеет максимальные
(минимальные значения). Формально это можно записать так:
Задача (13.1) относится к множеству задач, которые объединены термином «задача на безусловный экстремум». Решение такого рода задач целиком и полностью определяется свойствами функции W(X).
Введем некоторые определения. Говорят, что функция W(X) имеет в точке X* локальный максимум (нестрогий), если при любых малых АХ имеет место условие
При выполнении же условия
говорят, что вХ* функция W(X) имеет минимум (нестрогий).
Если неравенства строгие («>» или «максимум (минимум ) называют глобальным («самый большой максимум» и «самый маленький минимум»).
Все точки максимума и минимума функции имеют обобщенное название - экстремумы. Очевидно, что глобальный экстремум является в то же время и локальным экстремумом. Функция W(X) может иметь в области своего определения один, несколько или даже бесконечное количество экстремумов. Она может и не иметь экстремума. На рис. 13.1 представлен график функции одной переменной Дх), рассматриваемой на отрезке [а; Ь]. Внутри отрезка эта функция имеет экстремумы в точках х, х 2 , х 3 , х 4 , х 5 . Из них точка х 2 - глобальный минимум, х 3 - глобальный максимум, а в точках х г и х 5 функция имеет локальные максимумы, в точке х 4 - локальный минимум. Отметим, что граничные точки также могут являться точками экстремума.
Рис. 13.1.
Нахождение точек, в которых функция имеет экстремум, является одной из важных задач математики, поскольку к ней сводится множество других, имеющих большое практическое значение задач. Где и как искать точки экстремума, т.е. как решать задачи безусловной оптимизации?
Пусть Дх) - функция одной переменной заданная на отрезке [а; Ь]. Точками экстремума функции Дх) могут быть лишь те точки, в которых выполняется одно из следующих условий:
- 1) Дх) терпит разрыв (на рис. 13.2 - точка х 2);
- 2) Дх) непрерывна, но производная/"(х) не существует (точках^;
- 3) Д(х) = 0 (точки х 3 и х 4);
- 4) граничные точки (точки х = а и х = Ь).
Точки, в которых выполняется хотя бы одно из этих условий, называются подозрительными на экстремум. Таким образом, функция может иметь экстремум только в точках, подозрительных на экстремум.
Если в формуле (13.1) функция дифференцируемая, то возможность решения этой задачи определяет теорема Вейерштрасса.
Рис. 13.2.
Теорема 13.1 (Вейерштрасса). Непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (.минимума) по крайней мере в одной из точек этого множества.
Отметим, что эта теорема говорит лишь о возможности решения задачи (13.1), но не о методах ее решения.
В некоторых случаях могут быть сформулированы необходимые условия существования экстремума в точке. Так, для дифференцируемых функций имеет место следующее необходимое условие существования экстремума: если дифференцируемая функция f(x) имеет в точке х = х* экстремум, то ее производная обращается в этой точке в нуль, т.е. f"(x*) = 0.
Для функции нескольких переменных W(X) необходимое условие экстремума выполняется там, где все ее частные производные равны нулю, Например, для точки максимума имеем
Очевидно, что для точек, где достигается минимум, аналогичное условие также имеет место. Точки, в которых выполняется условие равенства нулю всех частных производных, называются стационарными.
Подчеркнем, что стационарность точки есть лишь необходимое условие существования в ней экстремума и далеко не во всех стационарных точках функция имеет экстремум. Однако выявление стационарных точек упрощает решение задачи.
Для дважды дифференцируемых функций сформулированы и достаточные условия существования экстремума, что обусловливает и соответствующий метод решения задачи (13.1). Имеет место следующая теорема.
Теорема 13.2 . Если в стационарной точке функция дважды дифференцируема и матрица ее вторых производных (матрица
Гессе ) положительно полуопределена, то функция в этой точке имеет минимум, если же матрица отрицательно полуопреде- ленна, то в этой точке функция имеет максимум.
Напомним, что симметрическая матрица называется положительно полуопределенной в точке, если все ее собственные значения неотрицательны или, что то же самое, все главные миноры матрицы Гессе неотрицательны. В этой точке функция имеет минимум. В случае отрицательно полуопределенной матрицы, когда все ее собственные значения неположительны или (что то же самое) главные миноры четной степени неположительны, матрица положительно полуопределена. В таких точках функция имеет максимум.
Пример 13.1
Найти экстремум функции Дх х, х 2) = х? + х| - 3xiX 2 .
Решение. Вначале вычислим первые частные производные и приравняем их к нулю:
Эта система имеет два решения - две стационарные точки: =
= (о, 0),Х 2 =(1, 1).
Составим матрицу Гессе:
Рассмотрим матрицу в каждой из найденных точек.
Для X, имеем
Диагональные члены матрицы нулевые, а определитель равен -9. Следовательно, в точке Х 1
= (0, 0) функция имеет максимум.
Для Х 2
имеем
. Диагональные члены положительны,
а определитель матрицы равен 27 > 0. Отсюда вывод: в точке Х 2 = (1,1) функция /(xj, х 2) = X] 3 +х| -ЗХ[Х 2 имеет минимум, т.е. min/(x x , х 2) = =/(1,1) =-1.
При поиске глобального экстремума необходимо, перебирая и сравнивая все точки локального экстремума, выбрать точки с наименьшим и наибольшим значениями функции. Процедуры поиска экстремумов аналитическими методами весьма сложны и не всегда работают. В связи с этим чаще используются алгоритмы, основанные на численных (приближенных) методах.
Метод дихотомии. Простейшим численным методом поиска экстремума функции одной переменной, не требующим вычисления производной, является метод деления отрезка пополам (методом дихотомии ). Этот метод позволяет уточнить расположение точки максимума (или минимума), когда предварительно найден отрезок, на котором эта точки непременно присутствует, и притом в единственном числе.
Пусть известная функция Дх) на отрезке [а; Ъ ] имеет один максимум, расположенный в неизвестной точке х*. Поскольку х* находится в неизвестной точке отрезка [а; Ь], то его называют отрезком неопределенности. Требуется с наперед заданной точностью г найти точку максимума функции Дх).
Идея метода дихотомии заключается в том, чтобы на каждом шаге сокращать отрезок неопределенности практически вдвое, до тех пор пока его длина не станет меньше заданной точности. Это делается следующим образом: отрезок неопределенности делится пополам, находится та половина, где лежит искомый максимум, затем этот отрезок вновь делится пополам и процедура продолжается.
Рассмотрим схему алгоритма этого метода немного детальнее. Пусть известно, что искомая точка х* находится на отрезке [а 0 ; Ь 0 ]. Выберем середину отрезка с 0 = (а 0 + Ь 0)/2. Далее анализируются два пересекающихся отрезка [а; с 0 + 5] и [с 0 -5; Ь], где 8 - малое число, много меньшее е, т.е. 8 «: е (иногда для удобства выбирают величину S/2). Очевидно, что если/(с 0 - б) >/(с 0 + б), то максимум находится на отрезке [а 0 ; с 0 + 5], иначе - на отрезке [с 0 - б; Ь 0 ]. Поэтому если выполнено условие/(с 0 - б) >/(с 0 + 5), то за новый интервал неопределенности принимается отрезок [а а; Ь х ], где а а = а 0 , Ь а = с 0 + 5, в противном случае - отрезок, где а 0 = с 0 - 8, Ь г = Ь 0 . Этот отрезок вновь делится пополам, и процедура продолжается до выполнения условия | fo fc - a fc |
Пример 13.2
Рассмотрим для примера следующую задачу: на отрезке найти точку минимума функции Дх) = 2х 2 - 4х + 4 с точностью до е = 0,5.
Решение. Выберем параметр 5 = 0,2. Исходный отрезок неопределенности - . Находим точки «середин» этого отрезка:
Вычислим в этих точках значения функции и сравним их:
В качестве нового отрезка неопределенности выбираем тот, где находится искомая точка минимума, т.е. = [а; х 2 ] = .
Вновь определим «средние» точки:
Поскольку ДО,95) е, поэтому продолжаем процесс:
Так как/(х 5) >/(х 6), то полагаем а 3 = х 5 , Ь 3 = Ь 2 . Новый отрезок неопределенности [а 3 ; Ь 3 ] = . Его длина 0,675 превышает заданную точность, поэтому продолжаем процесс дихотомии:
Поскольку Дх 7) =
2,1653, Дх 8) = 2,0153, то новым отрезком неопределенности будет [а 4 ; Ь 4 ] = . Этот отрезок имеет длину 0,4375, что меньше, чем 0,5. Следовательно, процесс дихотомии закончен. Из двух точек х 7
и х 8 в качестве искомого приближения х* выбираем точку х 8 , так как/(х 8)
Рис. 13.3.
Градиентные методы. Для функции многих переменных обычно применимы поисковые методы, основанные на свойстве градиента указывать в каждой данной точке направление наибольшего возрастания функции. Напомним, что градиентом скалярной функции W(x ь х 2 ,..., х„) называют вектор, состоящий из частных производных этой функции:
В основе любого градиентного метода лежит идея пошагового улучшения некоторого начального решения за счет движения к экстремуму исследуемой функции. Все многообразие методов заключается в различиях процедуры такого продвижения. Рассмотрим лишь одну из них.
Пусть найдено некоторое начальное решение задачи (13.1) Х° =(xJ) ,X2,...,x®) и выбран шаг h. Следующий и все последующие шаги выполняются последовательно согласно следующему рекуррентному соотношению:
Смысл формулы такой: из данной точки X й делается шаг длиной h в направлении, указанном градиентом. Знак «плюс» выбирается при поиске максимума, знак «минус» - в противоположном случае.
Таким образом, согласно формуле (13.4) на каждом шаге к каждая координата х, решения получает некоторое приращение в нужном направлении. Процесс продолжается до тех пор, пока не выполнится принятое условие завершения процесса. Условие завершения процесса определяется исследователем исходя из физической сущности задачи. Одной из форм условий может быть, например, такое:
где 8 - заранее назначенная малая величина - точность решения задачи. Возможно использование и такого условия завершения процесса:
Очевидно, что эффективность градиентного метода зависит от выбранного шага. Если шаг мал, то сходимость в общем случае будет медленной, если шаг большой, то может возникнуть эффект «перешагивания» точки экстремума и процесс не будет сходиться. В связи с этим в ходе решения задачи целесообразно сначала шаг взять достаточно большим, а затем постепенно его уменьшать. Можно, например, задаться изменением шага по формуле h k = h/k.
Пример 13.3
Найти минимум функции
Решение. Выберем начальную точку Х° =(3,1,1) и шаг h = 0,16. Значение функции в этой точке есть /(Х°) = 26, градиент - (4х х; 10х 2 ; 6х 3) = (12; 10; 6).
Проведем согласно формуле (13.4) первую итерацию:
Значение функции в новой точке/(X 1) =4,15.
Для второй итерации градиент равен (4,32; -6; 0,24), шаг h 2 = 0,08. Проведем вторую итерацию:
Значение функции в точке Х 2 следуюгцее: /(X 2) = 1,071. Налицо быстрая сходимость. Продолжая процесс по приведенной схеме, можно быстро приблизиться к точному решению задачи - (0, 0, 0).
Метод статистических испытаний (Монте-Карло). С развитием возможностей вычислительной техники широкое применение находят так называемые методы случайного поиска. Суть этих методов заключается в выборе величины и направления очередного шага случайным образом. Различают направленный и ненаправленный случайный поиск, случайный поиск с обучением и ряд других методов .
Схема простейшего метода случайного поиска максимума может быть такой. Определяется начальная (отправная) точка Х° и из этой точки в случайном направлении совершается перемещение на расстояние |й| в точку X 1 . При этом случайное направление формируется посредством генерации последовательности псевдослучайных чисел в количестве, равном числу переменных анализируемой функции, т.е. компонентами вектора h являются разыгранные значения случайной величины, равномерно распределенной на отрезке , где I - максимальное допустимое смещение по той или иной координате h е .
Если значение функции W (X 1) не увеличилось по сравнению с W(X°), то возвращаются в точку Х°. Разыгрывают новое направление и в этом направлении делают шаг. В том случае, если значение W(X*) > W(X°), точка X 1 принимается за отправную и процедура повторяется уже из этой точки. В противном случае попытка найти эффективное направление повторяется. В каждой очередной точке процедура поиска улучшающего направления повторяется не более заданного числа, например т раз. Та точка, из которой т раз подряд были совершены неудачные попытки увеличения значения анализируемой функции, принимается за точку максимума. В приложении 2 приведены пример и программа его решения на языке Visual Basic for Application.
Основное преимущество методов случайного поиска - в простоте их реализации и в том, что они не налагают никаких ограничений на вид функции W. Недостатки связаны с медленной сходимостью этих методов (для получения высокой точности требуется значительное число шагов). Однако в некоторых случаях они могут быть компенсированы посредством применением высокоскоростных компьютеров.
Введение
Теоретическая часть
Аналитический способ
Численные методы
Решение поставленной задачи в МCAD
Решение задачи с помощью табличного редактора Ms Excel
Решение задачи с помощью языка С++
Заключение
Введение
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Наиболее сложно обстоит дело с принятием решений, когда речь идет о мероприятиях, опыта в проведении которых еще не существует и, следовательно, здравому смыслу не на что опереться, а интуиция может обмануть. Пусть, например, составляется перспективный план развития вооружения на несколько лет вперед. Образцы вооружения, о которых может идти речь, еще не существуют, никакого опыта их применения нет. При планировании приходится опираться на большое количество данных, относящихся не столько к прошлому опыту, сколько к предвидимому будущему. Выбранное решение должно по возможности уберечь нас от ошибок, связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов.
Вообще, чем сложнее организуемое мероприятие, чем больше вкладывается в него материальных средств, чем шире спектр его возможных последствий, тем менее допустимы так называемые "волевые" решения, не опирающиеся на научный расчет, и тем большее значение получает совокупность научных методов, позволяющих заранее оценить последствия каждого решения, заранее отбросить недопустимые варианты и рекомендовать те, которые представляются наиболее удачными.
Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Цель курсовой работы:
·изучить необходимые программные конструкции языка программирования;
·освоить стандартные алгоритмы безусловной оптимизации;
·реализовать их средствами языка программирования С++;
·научиться использовать программы MCAD и MS Excel для решения поставленных задач и сверить полученные результаты.
Задачи данной курсовой работы: 1.Рассмотреть аналитические методы поиска одномерного и многомерного безусловного экстремума.
2.Изучить численные методы поиска одномерного и многомерного безусловного экстремума.
Теоретическая часть
Для оптимизационного решения задачи требуется: Сформулировать задачу; Построить математическую модель (определить множество переменных); Определить ограничения на возможные решения; ·Аналитический
·Численный
В аналитическом f (x) задается в виде формулы, в численном f (x) задается в виде черного ящика, на входе подается х, на выходе значение целевой функции в этой точке.
Аналитический способ
1.Для одной переменной
Определение 1: Говорят, что функция имеет в точке максимум (или минимум), если существует некоторая окрестность в промежутке, где функция определена, что для всех точек этой окрестности выполняется неравенство: ().
Определение 2: Если выполняется равенство , то точку будем называть стационарной точкой.
Достаточное условие существования экстремума: Пусть функция y=f(x) : 1.непрерывна в точке ;
2.дифференцируема в этой точке ;
3. - точка возможного экстремума;
.при переходе через точку производная меняет знак.
Тогда, если меняет знак с плюса на минус, то - точка максимума, а если с минуса на плюс, то - точка минимума.
) Найти производную функции .
) Найти стационарные точки (точки, подозрительные на экстремум), решив уравнение .
) Выяснить, меняет ли производная свой знак в точках, подозрительных на экстремум. Если она меняет знак с минуса на плюс, то в этой точке функция имеет свой минимум. Если с плюса на минус, то максимум, а если знак производной не меняется, то экстремума в этой точке нет. ) Найти значение функции в точках минимума (максимума). Для двух переменных Необходимое условие локального экстремума дифференцируемой функции Если - точка экстремума функции f, то
и или
Достаточные условия локального экстремума дважды дифференцируемой функции Обозначим
Если D > 0, A > 0, то - точка минимума.
Если D > 0, A < 0, то - точка максимума.
Если D < 0, экстремума в точке нет.
Если D = 0, необходимы дополнительные исследования.
Численные методы
Метод «золотого сечения»
Метод "золотого сечения" почти столь же эффективен, как и метод Фибоначчи, однако при этом не требуется знать n - количество вычислений функции, определяемое вначале. После того как выполнено j вычислений, записываем
Lj-1=Lj+Lj+1
Однако если n не известно, то мы не можем использовать условие Ln-1 =Ln - е. Если отношение последующих интервалов будет постоянным, т.е.
т. е. τ=1+1/ τ.
Таким образом, τ2-τ-1=0, откуда. Тогда
Т.е. .
В результате анализа двух рассмотренных значений функции будет определен тот интервал, который должен исследоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Первая точка находится на расстоянии Li/t от одного конца интервала, вторая - на таком же расстоянии от другого. Поскольку, то становится видно, что поиск методом "золотого сечения" является предельной формой поиска методом Фибоначчи. Название "золотое сечение" произошло от названия отношения в уравнении. Видно, что Lj-1 делится на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т.е. равно так называемому "золотому отношению". Таким образом, если ищется интервал (х0, х3) и имеются два значения функции f1 и f2 в точках x1 и x2, то следует рассмотреть два случая (рис. 1).
Рисунок 1
Метод гарантирует нахождение минимума в самых неблагоприятных условиях, однако он обладает медленной сходимостью. Схема алгоритма метода «золотого сечения» представлена на рис. 2.
Рисунок 2. Схема алгоритма метода «золотого сечения» Здесь С - константа, 1 (поиск минимума функции F(x)), 1 (поиск минимума функции F(x)), При выводе x - координата точки, в которой функция F(x) имеет минимум (или максимум), FM - значение функции F(x) в этой точке. Метод градиентного спуска с постоянным шагом.
Постановка задачи. Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные первого порядка во всех его точках.
Требуется найти локальный минимум функции f(x) на множестве допустимых решений , т.е. найти такую точку , что .
Стратегия поиска Стратегия решения задачи состоит в построении последовательности точек {xk}, k=0,1,…, таких, что . Точки последовательности {xk} вычисляются по правилу
,
где точка x0 задается пользователем; - градиент функции f(x), вычисленный в точке xk; величина шага tk задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия
Или Построение последовательности {xk} заканчивается в точке xk, для которой
где - заданное малое положительное число, или , где - предельное число итераций, или при двукратном одновременном выполнении двух неравенств
где - малое положительное число. Вопрос о том, может ли точка xk рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.
Геометрическая интерпретация метода Геометрическая интерпретация метода для функции двух переменных f(x1,x2):
Алгоритм Шаг 1. Задать - предельное число итераций. Найти градиент функции в произвольной точке
Шаг 2. Положить k=0. Шаг 3. Вычислить .
Шаг 4. Проверить выполнение критерия окончания :
·если критерий выполнен, расчет закончен: ;
·если критерий не выполнен, то перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства :
·если неравенство выполнено, то расчет окончен: ;
·если нет, то перейти к шагу 6.
Шаг 6. Задать величину шага tk.
Шаг 7. Вычислить .
Шаг 8. Проверить выполнение условия
(или ):
·если условие выполнено, то перейти к шагу 9;
·если условие не выполнено, положить и перейти к шагу 7.
Шаг 9. Проверить выполнение условий
·если оба условия выполнены при текущем значении k и k=k-1, то расчет окончен,
·если хотя бы одно из условий не выполнено, положить и перейти к шагу 3.
Процедура решения задачи 1.Используя алгоритм градиентного спуска с постоянным шагом, найти точку xk, в которой выполнен по крайней мере один из критериев окончания расчетов.
2.Провести анализ точки xk с целью установить, является ли точка xk найденным приближением решения задачи. Процедура анализа определяется наличием у функции f(x) непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных условий минимума: . Если , то точка есть найденное приближение искомой точки . Если , то следует провести проверку функции f(x) на выпуклость в Q-окрестности точки , используя критерий выпуклости для функций : функция f(x) выпукла (строго выпукла) в том и только в том случае, если . Если функция f(x) выпукла (строго выпукла), то есть найденное приближение точки .
Замечание: если требуется найти глобальный минимум функции f(x), то для строго выпуклой f(x) решение этой задачи аналогично поиску локального минимума функции. В случае, когда f(x) имеет несколько локальных минимумов, поиск глобального минимума осуществляется в результате перебора всех локальных минимумов.
Схема алгоритма метода градиентного спуска
Решение поставленной задачи в МCAD
задача
Минимизация функции с одной переменной. способ
задача
Определение какого рода функция и нахождение минимума(максимума) этой функции. способ
способ
Для исследования функции на максимум или минимум мы находим производные второго порядка и по ним составляем определитель. Если он не равен 0, то экстремумы функции существуют. Если вторая производная по t больше 0 и определитель больше 0, то существующий экстремум-это минимум, что и требовалось доказать.
Решение задачи с помощью табличного редактора Ms Excel
задача:
0,0001,0000,1001,3300,2001,5180,3001,5630,4001,4650,5001,2240,6000,8400,7000,3160,800-0,3480,900-1,1491,000-2,0831,100-3,1481,200-4,3381,300-5,6481,400-7,0741,500-8,6091,600-10,2471,700-11,9801,800-13,8001,900-15,6982,000-17,6672,100-19,6952,200-21,7732,300-23,8902,400-26,0342,500-28,1932,600-30,3542,700-32,5052,800-34,6312,900-36,7183,000-38,7503,100-40,7123,200-42,5883,300-44,3613,400-46,0133,500-47,5263,600-48,8823,700-50,0603,800-51,0423,900-51,8074,000-52,3334,100-52,6004,200-52,5844,300-52,2624,400-51,6124,500-50,6094,600-49,2294,700-47,4464,800-45,2344,900-42,5665,000-39,4175,100-35,7575,200-31,5595,300-26,7945,400-21,4325,500-15,4435,600-8,7965,700-1,4615,8006,5955,90015,4046,00025,0006,10035,4166,20046,6866,30058,8456,40071,9296,50085,9746,600101,0166,700117,0946,800134,2446,900152,5057,000171,917 Поиск решений4,145-52,629 Ход решения в Ms Excel
Итак, вначале в соответствии с поставленной задачей протабулируем функцию (найти минимум при х>0). Затем по полученным данным построим график, по которому находим примерное приближение значений минимума. Записываем приближенное значение в отдельную ячейку, в соседнюю ячейку записываем формулу зависящую от приближенного значения и воспользуемся инструментом «Поиск решения». В качестве целевой ячейки указываем функцию, ставим галочку «Минимальное значение», в поле «Изменяя ячейки» ставим ячейку с приближение. Жмем «Выполнить» и получаем искомое значение минимума.
2 задача:
00,10,20,30,40,50,60,70,80,91000,050,20,450,81,251,82,453,24,0550,1-0,28-0,26-0,140,080,40,821,341,962,683,54,420,2-0,52-0,53-0,44-0,250,040,430,921,512,22,993,880,3-0,72-0,76-0,7-0,54-0,280,080,541,11,762,523,380,4-0,88-0,95-0,92-0,79-0,56-0,230,20,731,362,092,920,5-1-1,1-1,1-1-0,8-0,5-0,10,411,72,50,6-1,08-1,21-1,24-1,17-1-0,73-0,360,110,681,352,120,7-1,12-1,28-1,34-1,3-1,16-0,92-0,58-0,140,41,041,780,8-1,12-1,31-1,4-1,39-1,28-1,07-0,76-0,350,160,771,480,9-1,08-1,3-1,42-1,44-1,36-1,18-0,9-0,52-0,040,541,221-1-1,25-1,4-1,45-1,4-1,25-1-0,65-0,20,3511,1-0,88-1,16-1,34-1,42-1,4-1,28-1,06-0,74-0,320,20,821,2-0,72-1,03-1,24-1,35-1,36-1,27-1,08-0,79-0,40,090,681,3-0,52-0,86-1,1-1,24-1,28-1,22-1,06-0,8-0,440,020,581,4-0,28-0,65-0,92-1,09-1,16-1,13-1-0,77-0,44-0,010,521,50-0,4-0,7-0,9-1-1-0,9-0,7-0,400,51,60,32-0,11-0,44-0,67-0,8-0,83-0,76-0,59-0,320,050,521,70,680,22-0,14-0,4-0,56-0,62-0,58-0,44-0,20,140,581,81,080,590,2-0,09-0,28-0,37-0,36-0,25-0,040,270,681,91,5210,580,260,04-0,08-0,1-0,020,160,440,82221,4510,650,40,250,20,250,40,651-1,12-1,31-1,42-1,45-1,4-1,28-1,08-0,8-0,44-0,010,5
Поиск решений0,9680,290-1,452 Ход решения в Ms Excel
Табулируем функцию. По полученным данным построим график поверхности, по которому видим, что нужно найти минимум этой функции. С помощью встроенной функции МИН() найдем наименьшее приближенное значение функции. Далее в отдельную ячейку скопируем значения х, у и z для полученного максимума, и воспользуемся инструментом «Поиск решения». В качестве целевой ячейки указываем скопированное выше значение z, ставим галочку «Минимальное значение», в поле «Изменяя ячейки» ставим ячейку со значением х и у. Жмем «Выполнить» и получаем искомое значение максимума.
Решение задачи с помощью языка С++
численный экстремум безусловный оптимизация 1 задача:
#include #include #include #include #include {pow(x,4)/4-pow(x,3)/3-7*pow(x,2)+4*x+1;//заданная функция //Метод золотого сеченияGoldenSection(double a, double b) {x1,x2;//объявляемy1, y2;//переменные= a + 0.382*(b-a);//два отрезка на которые= a + 0.618*(b-a);//делится промежуток= fun(x1);//вычисляется значение функции в точке х1= fun(x2);//вычисляется значение функции в точке х2((b-a) > epsilon) {= x1;//к началу отрезка присваевается значение первого отрезка= x2;//= fun(x1);//вычисляется значение функции в точке х1= a + 0.618*(b-a);= fun(x2);//вычисляется значение функции в точке х2 {= x2;//к концу отрезка присваивается значение х2= x1;= fun(x2);//вычисляется значение функции в х2= a + 0.382*(b-a);= fun(x1);//вычисляется значение функции в х1 }(a+b)/2;//отрезок делится на две части {(LC_CTYPE, "Russian");a, b, min, max;//объявление переменных<< "\t Вычисление минимума функции F(x) = x^4/4-x^3/3-7*x^2)+4*x+1 \n\t метадом золотого сечения " << endl << endl;<< "Входной интервал для поиска экстремальных функций (например 0 15):\n";>> a;//Ввод начала отрезка>> b;//ввод конца отрезка= GoldenSection(a, b);//Значение минимума в золотом сечении("\n Значение точки минимум MIN=%3.3f",min);//Вывод минимума("\n значение функции F(min)=%3.3f",fun(min));//Вывод функции от точки минимума Результат программы:
2 Задача:
#include #include #include #include {(2*pow(x,2) -3*x*x + 5*x*x-3*x); //функция }dy_dx0(double *x, int n) // первая частная производная по Х }dy_dx1(double *x, int n) // первая частная производная по Y }dy2_dx0(double *x, int n)// 2-я частная производная по X }dy2_dx1(double *x, int n)// 2-я частная производная по Y { setlocale(LC_CTYPE, "Russian");_k = 0.001;//шаг_k = 0;//начальное_k = 5;//приближение(1)//будет длится до конца интервала {_k_1 = x_k- lambda_k*dy_dx0(x_k, N) ;//последвательное_k_1 = x_k - lambda_k*dy_dx1(x_k, N);//приближение(fabs(dy_dx0(x_k_1, N)) }_k = x_k_1;_k = x_k_1;("\tГрадиентный метод:\n");("\tМинимум найден на x1 =%.3lf, x2 =%.3lf, Y(X1,X2) =%3.3f\n", x_k, x_k, y(x_k, N));//Вывод минимальных точек и значения функции в этой точке();0; Результат программы:
Заключение
Путем сложных вычислений курсовая работа выполнена в математическом редакторе Mathcad, табличном редакторе Excel и языке программирования С++. Все ответы сходятся, для проверки построены графики, на которых видна приблизительная цель вычислений. Всё выполнено согласно правилам. Таким образом, можно сделать вывод, что данная курсовая работа по теме «Решение задач безусловной оптимизации» выполнена.
Пусть решается задача поиска экстремума нелинейной функции f
на всем пространстве n
-мерных векторов . Обозначим Ñf
(x
) =
- градиент функции f
в точке х =
(х
1 ,…, х
n
). Он задает направление скорейшего роста функции в этой точке. Точка, в которой градиент функции f
равен нулю, т.е. для всех
,
называется стационарной
или критической
.
Необходимое условие экстремума в задаче без ограничений дает следующая теорема
Теорема 2 (необходимое условие локального экстремума). Пусть - точка локального экстремума дифференцируемой функции f . Тогда является ее стационарной точкой.
Однако стационарная точка не всегда является точкой экстремума функции. Например, х = 0 - стационарная точка функции z = х 3 , но в ней она не достигает ни минимума, ни максимума. Это точка перегиба функции.
Другим примером может служить функция z = . Точка (0, 0) является ее стационарной точкой, но в ней функция достигает минимума по переменной x и максимума по переменной y . Поэтому эта точка является не точкой экстремума, а седловой точкой этой функции.
Таким образом, стационарная точка будет точкой экстремума лишь при выполнении дополнительных условий, которые дает следующая теорема.
Теорема 3 (достаточные условия локального экстремума) . Пусть f - дважды непрерывно дифференцируемая функция и х * - ее стационарная точка, т.е. для всех . Тогда
1) если все главные миноры гессиана функции f в этой точке положительны, то х * - точка локального минимума;
2) если все главные миноры нечетного порядка гессиана функции f в этой точке отрицательны, а все главные миноры четного порядка положительны, то х
Для функции одной переменной (n = 1) условия теоремы 3 выглядят так.
Пусть х * - стационарная точка дважды непрерывно дифференцируемой функции f , т.е. = 0 . Тогда
1) если > 0, то х * - точка локального минимума функции f ;
2) если , то х * - точка локального максимума функции f .
Для случая n = 2 условия теоремы 3 приобретают такой вид.
Пусть х * = - стационарная точка дважды непрерывно дифференцируемой функции f , т.е. , , а также выполнено условие
.
Тогда х * - точка локального экстремума функции f , причем
1) если > 0, то х * - точка локального минимума,
2) если < 0, то х * - точка локального максимума.
Для выпуклой (вогнутой) функции необходимое условие оптимума является достаточным.
Если же нужно найти минимум выпуклой (максимум вогнутой) функции, то задача существенно упрощается. Достаточно найти любую стационарную точку этой функции. Она и будет точкой ее глобального оптимума.
