Метод множителей Лагранжа

Форум для обсуждения вопросов математики

Модератор: Admin

Михалыч
Сообщения: 3
Зарегистрирован: Вт июн 09, 2009 4:57 pm

Метод множителей Лагранжа

Сообщение Михалыч » Вт июн 09, 2009 4:59 pm

Здравствуйте.
Мне необходимо найти минимум функции
F = 0.5 (3x*x + 6*x*y + 4*y*y) - x + 2*y
при ограничениях:
3*x - 2*y <=15
-x + 2*y <=12
4*x + 5*y <=43
-x <= 0
-y <=0

Составляю ф-ю Лагранжа:
L = F + 3*l1*x - 2*l1*y - 15*l1 - 4*l2*x + 5*l2*y - 43*l2 + 4*l3*x + 5*l3*y - 43*l3
Дифференцирую по Х и по Y.
dL/dx = 3*x + 3*y - 1 + 3*l1 - l2 + 4*l3 - l4
dL/dy = 3*x + 4*y + 2 - 2*l1 + 2*l2 + 5*l3 - l5

Неравенства преобразую в равенства:
3*x - 2*y + (S1)*(S1) =15
-x + 2*y + (S2)*(S2) =12
4*x + 5*y + (S3)*(S3) =43

Составляю из всего этого матрицу:

3 3 3 -1 4 -1 0 0 0 0 1
-3 -4 2 -2 -5 0 1 0 0 0 2
3 -2 0 0 0 0 0 1 0 0 15
-1 2 0 0 0 0 0 0 1 0 12
4 5 0 0 0 0 0 0 0 1 43
-6 -4 -5 3 1 1 -1 -1 -1 -1 -73

Решая систему методом Гаусса, получаю x = 7, y = 3. Но это далеко не минимум. Подскажите,пожалуйста,может что я не так делаю?
Заранее всем спасибо!

nn910
Сообщения: 55
Зарегистрирован: Чт май 21, 2009 1:20 pm

Re: Метод множителей Лагранжа

Сообщение nn910 » Ср июн 10, 2009 12:06 pm

Михалыч писал(а):Здравствуйте.
Мне необходимо найти минимум функции
F = 0.5 (3x*x + 6*x*y + 4*y*y) - x + 2*y
при ограничениях:
3*x - 2*y <=15
-x + 2*y <=12
4*x + 5*y <=43
-x <= 0
-y <=0

Метод множителей Лагранжа формально применим только если там где у Вас неравенства стоят равенства. Если там неравенства, гарантию на правильный результат не даст и страховой полис. Фактически вы искали решение задачи где везде равенства.У этой задачи даже область определения пуста но метод дал одну интересную точку, случайно.
Люди по-разному решают в случае неравенств, но некоторым преподают так(ограничусь Вашим случаям 2х переменных):1.Найти все безусловные локальные экстремумы (здесь 1 точка,мин)2.Найти экстремумы на границе не в вершинах: для каждого условия отдельно обратить его в равенство а остальные отбросить.Применить один множитель Лагранжа.Найти все точки. И так столько раз сколько условий (у Вас 5 точек, некоторые даже могут не удовлетворять условиям и их сразу отбросить)3.Вычислить значения функции во всех вершинах,-где 2 неравенства обращаются в равенство,а остальные удовлетворяются(у Вас я вижу 4 если неврет чертеж); Среди конечного числа точек найденных в пп 1)2)3) выбирать свой экстремум.Способ можно обосновать теоремой.

Михалыч
Сообщения: 3
Зарегистрирован: Вт июн 09, 2009 4:57 pm

Сообщение Михалыч » Ср июн 10, 2009 12:37 pm

Спасибо за ответ.
Для того,чтобы применить метод Лагранжа, я неравенства преобразую в равенства:
3*x - 2*y + (S1)*(S1) =15
-x + 2*y + (S2)*(S2) =12
4*x + 5*y + (S3)*(S3) =43

Ваш метод проходит,но мне, к сожалению, необходимо решить эту задачу квадратичного программирования симплекс-методом с помощью метода множителей Лагранжа.

nn910
Сообщения: 55
Зарегистрирован: Чт май 21, 2009 1:20 pm

Сообщение nn910 » Ср июн 10, 2009 1:18 pm

Михалыч писал(а):Спасибо за ответ.
Для того,чтобы применить метод Лагранжа, я неравенства преобразую в равенства:
3*x - 2*y + (S1)*(S1) =15
-x + 2*y + (S2)*(S2) =12
4*x + 5*y + (S3)*(S3) =43

Ваш метод проходит,но мне, к сожалению, необходимо решить эту задачу квадратичного программирования симплекс-методом с помощью метода множителей Лагранжа.
Так это я Вам симплекс упрощенный длявашей задачи и излагал! И множители там применяются 5 раз по одному!

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Чт июн 11, 2009 9:27 am

Михалыч писал(а): к сожалению, необходимо решить эту задачу квадратичного программирования симплекс-методом с помощью метода множителей Лагранжа.

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

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Пт июн 12, 2009 8:23 pm

Множители Лагранжа имеют теоретическое обоснование, но по форме их записи всей глубины идеи не видно, если не познакомиться с теорией. Необходимость в множителях не возникла, если бы были известны способы выражения одних переменных через другие в уравнениях, задающих условия связи переменных. Число таких уравнений не может быть равно числу переменных, но только меньше него, иначе говорить об условном экстремуме целевой функции не имеет никакого смысла, потому что в таком случае она никак не влияет на решение системы из уравнений, задающие условия связи. Выражать одни переменные через другие человечество ещё не научилось, и все системы нелинейных уравнений решаются численно – не будем говорить об очень редких случаях и специально изготовленных олимпиадных примерах. Вот и была придумана новая функция, объединяющая с помощью множителей Лагранжа функцию цели и уравнения условий. После чего мы ищем уже безусловный экстремум новой функции, только число переменных возросло на число этих множителей. Геометрически получается, что в точке условного экстремума градиент функции цели выражается через сумму градиентов условных уравнений, умноженных на множители Лагранжа… Думается, сначала на практике применялись геометрические соображения и линейная алгебра, а потом практику соединили с теорией о неявных функциях, и получился полноценный метод множителей Лагранжа, но это только мои догадки… Конечно, интересно было бы узнать, как всё происходило на самом деле, но специально копаться лень…

volmike
Сообщения: 235
Зарегистрирован: Вс июн 05, 2005 2:42 pm
Контактная информация:

Сообщение volmike » Сб июн 13, 2009 11:24 pm

Ответ задачи
min= -1/6, {x=1/3,y=0}
Лысый пешему не конный...

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Вс июн 14, 2009 7:43 pm

volmike писал(а):Ответ задачи
min= -1/6, {x=1/3,y=0}

Ответ, похоже, верный, но заказчика он вряд ли удовлетворит без дополнительных объяснений. Если преподаватель велел решать именно так, как мы все тут читали, то что на это скажешь? Совет Михалычу: целевая функция в заданной области (по двум последним неравенствам) монотонно возрастающая, значит, её минимум будет находиться на какой-либо из этих двух границ; и мы по очереди выражаем одну из переменных через другую в каждом из двух уравнений (x=0 и y=0), что, понятно, очень легко и подставляем в уравнение целевой функции, рассматриваем получившиеся уравнения на безусловный экстремум и выбираем нужный ответ… Или, как советовали Михалычу выше, надо для каждого ограничения решать с помощью множителей Лагранжа, а потом тоже выбирать, но момент объяснения перехода от неравенств к равенствам не обойдёшь.
А задача должна звучать просто: найти минимум функции в такой-то области…

Михалыч
Сообщения: 3
Зарегистрирован: Вт июн 09, 2009 4:57 pm

Сообщение Михалыч » Пн июн 22, 2009 10:43 pm

СПАСИБО всем,тему можно закрывать