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

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

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

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

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


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

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


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


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


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

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


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


[math]f(x^{\ast})=\min_{x\in M}f(x).[/math]

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


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


[math]\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}.[/math]

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


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


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

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


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




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


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


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


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


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




Замечания 3.17.


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


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


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




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


[math]\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}[/math]

Решение.


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


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


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


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




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


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


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


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


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


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



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


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


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


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


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




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


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


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


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


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


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



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


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


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


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


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




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


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


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


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


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


Множество допустимых решений и параболы как линии уровня



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

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


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

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