Задача по нелинейному программированию

[Ray1783]

Доброе время суток, уважаемые форумчане!
Помогите, пожайлуста, разобраться с решением задачи по нелинейному программированию!
Ее необходимо решить двумя способами: методом множителей Лагранжа и графически. Но ограничения представляют собой неравенства. При введении дополнительных искусственных переменных не могу разобраться, каковы условия условного экстремума.Графически - вообще понять не могу((

-- Пн июн 08, 2009 15:26:25 --

Нужно найти экстремум функции $x_1 + 3x_2 $
при ограничениях
$ x_1^2+x_2^2 \ge 25 $
$ x_1 x_2\ge 4$

[Yu_K]

Графически. Начните с того, что нарисуйте область допустимых значений и линии уровня целевой функции.
А с множителями Лагранжа придется добавить переменные $x_3$, $x_4$ в неравенства и превратить их в равенства - и составить функцию Лагранжа добавив полученные равенства в целевую функцию с двумя множителями Лагранжа - здесь на форуме поищите.

[AKM]

А что, так трудно и непонятно --- набрать $x_1 + 3x_2 $? Или $ x_1^2+x_2^2 \ge 25 $ ($ x_1^2+x_2^2 \ge 25 $)?
Да, будет эта самая c'est la vie, делать исключения нет оснований.

Используйте кнопку для редактирования своего сообщения. И в карантине тоже.

[Ray1783]

Спасибо, Yu_K
По области допустимых значений еще вопрос - следует рассмотреть ограничения как внешнюю область гиперболы и окружности? Или эти условия задают линии уровня поверхностей второго порядка? Потому как на плоскости область ограничений получается неограниченной...

-- Пн июн 08, 2009 15:46:33 --

Прошу прощения, уважаемый AKM! Но решить задачу мне надо было еще вчера((

[AKM]

В выходные форум работал. Переезжаем в карантин.
Бытовуха в данной ветке --- оффтопик.

В теме Что такое карантин и что нужно делать, чтобы там оказаться так же описано, как исправлять ситуацию.

Возвращено.

Возможно, Вам мешает флажок "Отключить в этом сообщении BBCode". Его не должно быть (проверьте свои настройки).
Достаточно окружить формулу долларами. [mаth]...[/mаth] вставится автоматически.

[Ray1783]

AKM, спасибо!

[AKM]

Yu_K в сообщении #220682 писал(а):

Графически. Начните с того, что нарисуйте область допустимых значений и линии уровня целевой функции.

Т.е. нарисуйте линии

$$\begin{array}{l} \ldots\\ x_1+3x_2=-1\\ x_1+3x_2=0\\ x_1+3x_2=1\\ x_1+3x_2=2\\ x_1+3x_2=3\\ \ldots \end{array} $$

Какие из них (может, и не перечисленные здесь) попадают в рабочую область?
Какие попадают "экстремально"?

[Ray1783]

линии-то я рассмотрела. А как быть с неограниченностью рабочей области? Для задач нелинейного программирования неограниченность не требуется?

[AKM]

Yu_K в сообщении #220682 писал(а):

А с множителями Лагранжа придется добавить переменные $x_3$, $x_4$ в неравенства и превратить их в равенства - и составить функцию Лагранжа добавив полученные равенства в целевую функцию с двумя множителями Лагранжа - здесь на форуме поищите.

Обычно в описаниях метода эти доп. переменные обозначают $\lambda_1,\lambda_2$.
Думаю, из линейности целевой функции следует возможность работать только на границах области "превратить неравенства в равенства". Ну и задачка требует аккуратности рассуждений, как мне кажется напоследок.

-- Пн июн 08, 2009 17:14:43 --

Ray1783 в сообщении #220708 писал(а):

А как быть с неограниченностью рабочей области?

Извините, я её не заметил. Подумал наоборот. Но на первый взгляд, это ничего не меняет.
Ну и вообще, по теме я как бы ничего не советовал.

[Ray1783]

$\lambda_1,\lambda_2$ - это коэффициенты при уравнениях-ограничениях (уравнениях связи). $x_3,x_4$ добавляются, чтобы из неравенств получить равенства. Но, в этом случае, частные производные по этим дополнительным переменным приводят к уравнениям $\lambda_1=0,\lambda_2=0$. Что-то тут не так... Если ввести вместо $x_3,x_4$ квадраты:$x_3^2,x_4^2$, получается система из 6 уравнений, но, опять-таки, надо что-то делать с условиями $\lambda_1*x_3=0,\lambda_2*x_4=0$

[AKM]

Или $x_{3,4}$, как Yu_K советовал, или $\lambda_{1,2}$, как обычно их называют в учебниках. Но не обе пары вместе!
Удаляюсь, ибо термин "нелинейное программирование" мне не знаком!

[Ray1783]

а как быть с условием в учебниках, что метод множителей Лагранжа применяют в тех случаях, когда система ограничений предстваляет собой систему равенств?
http://floyd-sweet.on.ufanet.ru/1.htm#_Toc186683239
в рассмотренном примере добавлены и $\lambda$, и $x_3$ (их там u назвали), но откуда взялись в том примере некоторые из условий, понять не могу. Если второе уравнение - частная производная по $x_2$, то как появилось первое?

-- Пн июн 08, 2009 17:38:28 --

извините, AKM! Я тоже пришла за советом поэтому - я знаю функцию Лагранжа из матанализа, там такие неопределенности не появлялись((

[мат-ламер]

Интересно попробовать решить задачу без введения дополнительных переменных. Дело осложняет то, что допустимая область не выпукла и воспользоваться теоремой Куна-Таккера не удастся. Локальные эстремумы скорее всего находятся в точках пересечения гиперболы и окружности. Найдите в этих точках конус допустимых направлений и посмотрите, принадлежит ли ему градиент (антиградиент). То что область не ограничена, ведёт к тому, что глобальных экстремумов нет, а только локальные. А сколько их - два или четыре - попробуйте разобраться сами.

[Ray1783]

без введения дополнительных переменных получаются точки пересечения окружности и гиперболы, только для проверки на экстремум нужны вторые производные, а для этого нужно еще и $\lambda$ искать. Там уж очень несимпатичные числа, почему у меня и возникли сомнения в правильности решения. А с конусами допустимых направлений я сто лет не пересекалась, и литературы под рукой нет((

[мат-ламер]

Решайте без конусов. Рассмотрите 4 подозрительные точки (пересечение гиперболы и окружности). Примените теорему Куна-Таккера (хотя её тут вроде из-за невыпуклости применять нельзя). Знаки множителей Лагранжа дадут ответ, будет ли в точке локальный экстремум. Вторую производную находить не надо. А вот, если вводить дополнительные переменные, то, наверное, надо. А, вообще, если этого будет достаточно, решайте графически.