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

[AKM]

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

а как быть с условием в учебниках, что метод множителей Лагранжа применяют в тех случаях, когда система ограничений предстваляет собой систему равенств?

Думаю, так быть: поскольку целевая функция линейна ($f=x_1+3x_2$ кажется), то экстремумы могут быть только на границе области, стало быть, "на равенствах".

-- Пн июн 08, 2009 18:31:20 --

И ещё:
ежели бы там не было этих незнакомых (мне) слов "по нелинейному программированию", то я решал бы ОТДЕЛЬНО задачу с ограничением на окружности и ОТДЕЛЬНО задачу с ограничением на гиперболе. С единственной лямбдой в каждом случае!
А учёт обоих ограничений СРАЗУ означает, что мы просто на 4-х точках экстремум ищем. Не от того ли там где-то ерунда получалась?

-- Пн июн 08, 2009 18:34:52 --

1. $x_1 + 3x_2 + \lambda( x_1^2+x_2^2 -25) $.
2. $x_1 + 3x_2 + \lambda( x_1 x_2-4)$.

[Ray1783]

Такой момент - если двигаем линии уровня, локальный экстремум достигается в точках, в которых касательная к окружности параллельна прямой $x_1+3*x_2=0$, то есть угловой коэффициент касательной к окружности равен -1/3. И полученные точки не имеют отношения к точкам пересечения гиперболы с окружностью...

-- Пн июн 08, 2009 18:41:32 --

Спасибо, AKM, сейчас попробую в этом направлении поработать. Потому что, как уже сказала, касательные дают совсем другие точки, чем то, что получается при решении через функцию Лагранжа с двумя условиями

[AKM]

Согласен.
Графически Вы решили. Осталось поточнее подобрать (или найти) эти прямые. И, наверное, сами экстремальные значения.

-- Пн июн 08, 2009 18:45:34 --

А ведь Ray1783 в сообщении #220677 писал(а):

Графически - вообще понять не могу((

[Ray1783]

думала, что графически надо рассмотреть не просто гиперболу и окружность, а их как сечения поверхностей второго порядка... В общем, ожидала, что все сложнее.

[AKM]

Это к Лагранжу:
Предположим, Вы ищете максимум-минимум ф-ции $y=x^2$ на ограниченном отрезке $-2\le x \le 1$. Тогда, найдя экстремум(ы), Вы обязаны проверить значения ф-ции на границах отрезка.
Что-то подобное может потребоваться и в этой задаче --- проверка тех самых точек пересечения. Советы мои слегка неуверены. В частности, лень лезть уточнять-проверять термины "экстремум" vs "максимум-минимум" и постановку задач нелинейного программирования.

[Ray1783]

ура! При решении графическим способом получился ответ, совпадающий с решением методом множителей Лагранжа, когда $\lambda$ умножаем на уравнение окружности. НО! При решении методом множителей Лагранжа через умножение $\lambda$ на уравнение гиперболы тоже получаются точки условного экстремума. А их там быть не должно, поскольку в рабочую область они не входят... В принципе, графический способ и метод множителей Лагранжа решаются отдельно, то есть я не имею права эти точки отбросить, пользуясь графиком. Как бы мне избавиться от посторонних решений?

-- Пн июн 08, 2009 19:55:00 --

Кажется, я поняла))) Надо проверить, удовлетворяют ли полученные точки другому условию!

-- Пн июн 08, 2009 19:56:00 --

Всем большое-пребольшое спасибо за помощь!

[Ray1783]

Добрый день, уважаемые форумчане!
С предыдущей задачей разобралась, спасибо!
Возникла проблема с аналогичной. Целевая функция та же самая: $x_1+3x_2$, ограничения $x_1*x_2\ge 4$ и $x_2+(x_1-4)^2\leqslant 5$
При решении графическим способом оказывается, что рабочая область разбивается на две части. Верхняя - ограниченная область (внутренняя часть параболы и внешняя - гиперболы), но плюс внизу - неограниченная. Найти нижнюю точку как пересечение гиперболы и параболы пыталась, но до конца не довела - уж очень несимпатичные числа лезут. И, самая большая неприятность - при решении методом множителя Лагранжа обе точки из верхней области совпадают с графическим подходом (правда, нижняя при графическом решении - точка локального минимума, а при решении через Лагранжиан - максимум, тоже что-то не то..), но вот точка пересечения параболы и гиперболы никак не всплывает.

[мат-ламер]

Попробовал почитать решение первой задачи, но ничего не понял.

Цитата:

Такой момент - если двигаем линии уровня, локальный экстремум достигается в точках, в которых касательная к окружности параллельна прямой , то есть угловой коэффициент касательной к окружности равен -1/3. И полученные точки не имеют отношения к точкам пересечения гиперболы с окружностью...

. Но это не так. Точка, где линия уровня касается окружности, не является локальным экстремумом.
Касательно второй задачи. Что касается верхней области, то тут, наверное, можно действовать, как Вы решали первую задачу. Точки экстремума совпадают с точками касания линии уровня и областью. Одна из них будет локальным экстремумом, а вторая глобальным (максимумом). Что касается нижней области, то локальный экстремум будет в точке пересечения гиперболы и параболы, а гобальный минимум не достигается.

[Ray1783]

Была на консультации у специалиста по нелинейному программированию. Сказал, что нельзя разбивать на две задачи. Решать надо c двумя $\lambda$, причем вводить дополнительно $x_3,x_4$ не надо. Причем в экономических задачах подразумевается, что переменные неотрицательны, то есть работаем в первой координатной четверти. Первую задачу, где окружность пересекается с гиперболой, решила. Действительно, получается, что экстремум - не касательная к окружности, а пересечение окружности и гиперболы. Но вот при решении второй задачи надо найти точки пересечения параболы с гиперболой, а там всплывает кубическое уравнение $x_1^3-8*x_1^2+11*x_1+4=0$, и решить его не получается(((. Подстановка $x=x+8/3$ приводит к уравнению $x^3-(31/3)*x-124/27=0$

[мат-ламер]

Вопрос. А как в первой эадаче Вы доказали, что, действительно, четыре точки пересечения являются локальными экстремумами? (Что это гарантирует?) Найдите для них множители Лагранжа, и если они одного знака, то точки являются локальными экстремумами. А почему это так, разберём завтра (ухожу в offline). Во второй задаче точку пересечения найдите с помощью к-нибудь мат.пакета. И, подумайте, почему остальные две точки (из верхней области) действительно являются точками экстремума.

[Ray1783]

в первой задаче - через знак второго дифференциала функции Лагранжа

[мат-ламер]

Это как раз подойдёт для второй задачи. Для первой это не причём.

[мат-ламер]

Насчёт первой задачи. На первом этапе нужно найти точки подозрительные на экстремум. Сделать это можно либо графически, либо последовательно перебирая все граничные дуги множества (их три в в верхнем квадрате) (и далее - всё только в верхнем квадрате) и все угловые точки (их две). Для каждой дуги можно решать задачу с одним ограничением типа равенства и с одним множителем Лагранжа. Точки, не принадлежащие дуге, нужно отбросить. Получаем три подозрительные точки - две точки пересечения окружности и гиперболы и одна точка касания линии уровня и окружности. На втором этапе надо проверить подозрительные точки на экстремальность. Вот если эта задача была бы задачей с оганичениеями типа равенств, тогда разумно было рассматривать вторую производную функции Лагранжа. Здесь надо воспользоваться достаточными условиями для задач с ограничениями типа неравенств. Графический их смысл состоит в том, что если мы рассмотрим линию уровня миним. функции, которая касается подозрительной точки, то в окрестности подозрительной точки все точки множества должны находится с одной стороны от линии уровня. Формально - если мы найдём множители Лагранжа для данной точки, то они должны быть одного знака. Это так для двух точек пересечения. Что касается третьей точки (точки касания), то то, что она не экстремум видно графически. Итак имеем один гобальный минимум и один локальный. Максимум не достигается. Решать задачу введением дополнительных переменных можно, но расчёты усложняются, так как размерность задачи увеличивается.

-- Ср июн 10, 2009 11:00:53 --

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