Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Применение линий первого и второго порядков в задачах на экстремум функций

Применение линий первого и второго порядков в задачах на экстремум функций


Рассмотрим задачу поиска минимума функции двух переменных.


Пусть заданы:


а) функция f(x)=f(x_1,y_2) двух переменных (x\in\mathbb{R}^2);

б) множество допустимых решений M~(M\subset\mathbb{R}^2).


Требуется найти такую точку x^{\ast} из множества допустимых решений, которой соответствует минимальное значение функции f(x) на этом множестве:


f(x^{\ast})=\min_{x\in M}f(x).

Аналогично формулируется задача поиска максимума. Задача поиска минимума и максимума называется задачей поиска экстремума. Множество допустимых решений M задается условиями (ограничениями) на x, как правило, уравнениями или неравенствами. В этом случае поставленная задача называется задачей поиска условного экстремума. Если множество допустимых решений совпадает со всей плоскостью (M=\mathbb{R}^2), т.е. ограничения отсутствуют, решается задача поиска безусловного экстремума.


Постановки задач поиска экстремума функции принято записывать в сокращенной форме, например:


\begin{cases}f(x)\to\min,\\g_1(x)=0,\end{cases} \begin{cases}f(x)\to\max,\\g_1(x)=0,\\g_2(x)\leqslant0,\end{cases} \begin{cases}f(x)\to\operatorname{extr},\\x\in\mathbb{R}^2,\end{cases} \Leftrightarrow \quad f(x)\to\operatorname{extr}.

Последние две записи относятся к одной и той же задаче поиска безусловного экстремума, а первые две — к задаче поиска условного экстремума с ограничениями, задаваемыми функциями g_1(x),\,g_2(x).


Напомним, что линией уровня функции f(x)=f(x_1,x_2) называется геометрическое место точек плоскости, в которых функция принимает постоянное значение, т.е. f(x_1,x_2)=\operatorname{const}.


Графический метод решения задачи поиска условного экстремума

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


В основе графического метода решения задачи поиска условного экстремума лежит следующее соображение. Если линия уровня f(x)=\operatorname{const} имеете множеством допустимых решений M хотя бы одну общую точку, то это значение постоянной (const) является допустимым, так как функция достигает его на множестве M. Если же линия уровня f(x)=\operatorname{const} не имеет общих точек с множеством M, то это значение постоянной (\operatorname{const}) является недопустимым, поскольку функция не достигает его на множестве M. В частности, функция f(x), линии уровня которой изображены на рис.3.64, на множестве M принимает, например, значения c_{\ast},c_2,c^{\ast} (они являются допустимыми) и не принимает значений c_1 и c_3 (они являются недопустимыми).




Алгоритм графического решения задачи поиска условного экстремума


1. Построить на координатной плоскости \mathbb{R}^2 множество допустимых решений M.


2. Построить семейство линий уровня f(x)=\operatorname{const}.


3. По линиям уровня определить все допустимые на множестве M значения функции: c_{\ast}\leqslant f(x)\leqslant c^{\ast}.


4. Для наименьшего значения c_{\ast}=\min_{x\in M}f(x) найти координаты общих точек линии уровня f(x)=c_{\ast} и множества допустимых решений M. В результате получим точки условного минимума функции. Для наибольшего значения c^{\ast}=\max_{x\in M}f(x) аналогичным образом найти точки условного максимума функции. Например, на рис.3.64: точка A_{\ast} — точка условного минимума, а точки B_1^{\ast},\,B_2^{\ast} — точки условного максимума.




Замечания 3.17.


1. Возможны случаи, когда на множестве M функция f(x) не ограничена сверху (c^{\ast}=+\infty) или снизу (c_{\ast}=-\infty), тогда точек условного максимума или минимума нет.


2. Для решения задачи поиска безусловного экстремума допустимые значения постоянной (\text{const}) в пункте 3 алгоритма определяются так: если линия уровня f(x)=\operatorname{const} имеет хотя бы одну точку (вещественную) на плоскости \mathbb{R}^2 то это значение постоянной (\text{const}) является допустимым, в противном случае — недопустимым.


3. За исключением простых задач, графическое решение требует проверки аналитическими методами теории оптимизации.




Пример 3.28. Графическим методом найти экстремумы:


\begin{gathered} \mathsf{1)}\,f(x)=\frac{x_1^2}{4}+x_2^2\to\operatorname{extr};\!\! \quad \mathsf{2)}\begin{cases}f(x)=x_1^2+x_2^2\to\operatorname{extr},\\ g_1(x)=x_1+x_2-1=0;\end{cases}\!\! \mathsf{3)}\begin{cases}f(x)=x_1^2+x_2^2\to\operatorname{extr},\\ g_1(x)=x_1^2-x_2^2-1=0;\end{cases}\\[3pt] \mathsf{4)}\begin{cases}f(x)=(x_1-3)^2+x_2^2\to\operatorname{extr},\\[3pt] g_1(x)=\dfrac{x_1^2}{4}+x_2^2-1\leqslant0;\end{cases}\!\!\! \mathsf{5)}\begin{cases} f(x)=x_2\to\operatorname{extr},\\ g_1(x)=-x_1-x_2\geqslant-5,\\ g_2(x)=x_1-x_2\geqslant-1,\\ g_3(x)=2x_1+5x_2\geqslant11,\\ g_4(x)=-x_1+2x_2\geqslant-1; \end{cases}\!\!\! \mathsf{6)}\begin{cases}f(x)=4x_1-x_2^2\to\operatorname{extr},\\g_1(x)=x_1-x_2+1=0.\end{cases} \end{gathered}

Решение.


1) 1. Множество M допустимых решений строить не нужно, так как оно совпадает со всей плоскостью: M=\mathbb{R}^2.


2. Линия уровня \frac{x_1^2}{4}+x_2^2=\text{const} при \text{const}>0 представляет собой эллипс (см. рис.3.65,а), при \text{const}=0 — пару мнимых прямых, пересекающихся в вещественной точке O(0;0), при \text{const}<0 — мнимый эллипс. При увеличении постоянной полуоси эллипса пропорционально увеличиваются. На рис.3.65,а изображены эллипсы \frac{x_1^2}{4}+x_2^2=1 (a=2,\,b=1) и \frac{x_1^2}{4}+x_2^2=\frac{9}{4} или \frac{x_1^2}{9}+\frac{x_2^2}{9/4}=1 (a=3,\,b=3/2). Стрелками указаны направления наискорейшего возрастания функции (градиента).


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством 0\leqslant f(x)\leqslant+\infty


4. В точке O(0;0) достигается безусловный минимум функции, так как в этой точке функция принимает наименьшее значение по сравнению со значениями в других точках плоскости, а наибольшего значения функция не достигает.




2) Решается задача поиска условного экстремума с ограничением типа равенств.


1. Строим множество M допустимых решений — прямую x_1+x_2-1=0 (см. рис.3.65,6).


2. Линии уровня x_1^2+x_2^2=\text{const} представляют собой семейство концентрических окружностей (при \text{const}>0). При \text{const}>\frac{1}{2} окружность x_1^2+x_2^2=\text{const} пересекает прямую x_1+x_2-1=0, при \text{const}=\frac{1}{2} — касается этой прямой в точке A\!\left(\frac{1}{2};\frac{1}{2}\right)\,, при 0<\text{const}<\frac{1}{2} — не пересекает прямую.


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством \frac{1}{2}\leqslant f(x)\leqslant+\infty.


4. Наименьшее значение на множестве M, равное \frac{1}{2}, функция достигает в точке A\!\left(\frac{1}{2};\frac{1}{2}\right)\,. Наибольшего значения на множестве M функция не достигает.


Эллипсы и семейство концентрических окружностей как линии уровня



3) Решается задача поиска условного экстремума с ограничением типа равенств.


1. Строим множество M допустимых решений — гиперболу x_1^2-x_2^2=1 (см. рис.3.65,в).


2. Линии уровня x_1^2+x_2^2=\text{const} представляют собой семейство концентрических окружностей (при \text{const}>0). При \text{const}>1 окружность x_1^2+x_2^2=\text{const} пересекает гиперболу в четырех точках, при \text{const}=1 — касается гиперболы в точках A(1;0), B(-1;0) при 0<\text{const}<1 — не пересекает гиперболу.


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством 1\leqslant f(x)\leqslant+\infty.


4. Наименьшее значение на множестве M, равное 1, функция достигает в точках A(1;0) и B(-1,0) Наибольшего значения на множестве M функция не достигает.




4) Решается задача поиска условного экстремума с ограничением типа неравенств.


1. Строим множество M допустимых решений: множество, ограниченное эллипсом \frac{x_1^2}{4}+x_2^2=1, включая внутренние точки эллипса (см. рис.3.65,2).


2. Линии уровня (x_1-3)^2+x_2^2=\text{const} представляют собой семейство концентрических окружностей (при \text{const}>0) с центром в точке Q(3;0). При 1<\text{const}<25 окружность x_1^2+x_2^2=\text{const} пересекает множество M при \text{const}=1 — касается эллипса в точке A(2;0) при \text{const}=25 — касается эллипса в точке B(-2;0), при 0<\text{const}<1 или \text{const}>25 окружность не имеет общих точек с множеством M.


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством 1\leqslant f(x)\leqslant25.


4. Наименьшее значение на множестве M, равное 1, функция достигает в точке A(2;0). Наибольшее значение на множестве M, равное 25, функция достигает в точке B(-2;0).


Гипербола и семейство концентрических окружностей



5) Решается задача поиска условного экстремума с ограничениями типа неравенств. Данная задача относится к классу задач линейного программирования (функция f(x) и все функции, задающие ограничения, линейные).


1. Строим множество M допустимых решений: в данном случае выпуклый четырехугольник (см. рис.3.65,д и рис.3.35,г к примеру 3.18).


2. Линии уровня x_2=\text{const} представляют собой семейство параллельных прямых. При 1<\text{const}<3 прямая x_2=\text{const} пересекает множество M, при \text{const}=1 прямая проходит через вершину A(3;1) четырехугольника, при \text{const}=3 прямая проходит через вершину B(2;3) четырехугольника, при \text{const}<1 или \text{const}>3 прямая не пересекает четырехугольник M.


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством 1\leqslant f(x)\leqslant3.


4. Наименьшее значение на множестве M, равное 1, функция достигает в точке A(3;1). Наибольшее значение на множестве M, равное 3, функция достигает в точке B(2;3.)




6) Решается задача поиска условного экстремума с ограничением типа равенств.


1. Строим множество M допустимых решений — прямую x_1-x_2+1=0 (см. рис.3.65,е).


2. Линии уровня 4x_1-x^2=\text{const} представляют собой семейство парабол, симметричных относительно оси Ox_1. При увеличении постоянной (\text{const}) параболы перемещаются вдоль оси Ox_1 в сторону ее положительного направления. При \text{const}<0 парабола 4x_1-x^2=\text{const} пересекает прямую M в двух точках, при \text{const}=0 парабола касается прямой в точке A(1;2), при \text{const}>0 парабола не имеет общих точек с M.


3. Из пункта 2 следует, что допустимые значения функции определяются неравенством -\infty<f(x)\leqslant0.


4. Наибольшее значение на множестве M, равное 0, функция достигает в точке A(1;2). Наименьшего значения на множестве M функция не достигает.


Множество допустимых решений и параболы как линии уровня
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved