Б) Алгоритм метода множителей Лагранжа

Пусть задана задача нелинейного программирования:

найти max (min) Z (Х) = Б) Алгоритм метода множителей Лагранжа - student2.ru при ограничениях

Б) Алгоритм метода множителей Лагранжа - student2.ru

где Б) Алгоритм метода множителей Лагранжа - student2.ru - дважды непрерывно дифференцируемые функции. При этом m ≤ n, где n – число переменных, m – число независимых ограничений - равенств.

1. Составить функцию Лагранжа:

Б) Алгоритм метода множителей Лагранжа - student2.ru , где Б) Алгоритм метода множителей Лагранжа - student2.ru - множители Лагранжа. То есть функция Лагранжа равна сумме, причем в качестве первого слагаемого переписывается целевая функция без изменений, а каждое ограничение (правая часть ограничений равна нулю) умножается на множитель Лагранжа li (i=1¸m), и полученные выражения приписываются к целевой функции в виде слагаемых. Функция Лагранжа имеет n+m переменных: х1, х2, …, хn, l1, l2, … , lm .

2. Найти частные производные функции Лагранжа и приравнять их к нулю:

Б) Алгоритм метода множителей Лагранжа - student2.ru

3. Решить получившуюся систему из n+m уравнений, являющимися частными производными функции Лагранжа, и найти стационарные точки.

Искомый максимум (или минимум) выбирается среди стационарных точек сравнением значений целевой функции в них или при помощи неформальных дополнительных соображений.

Пример 11. Найти Б) Алгоритм метода множителей Лагранжа - student2.ru

Решение.

1. Преобразуем ограничение, перенеся все его члены в левую часть х2+4хy-12=0.

2. Составляем функцию Лагранжа: Б) Алгоритм метода множителей Лагранжа - student2.ru

3. Находим частные производные функции Лагранжа, приравниваем их к нулю и составляем систему уравнений:

Б) Алгоритм метода множителей Лагранжа - student2.ru

4. Решаем получившуюся систему из трех уравнений.

Находим l из уравнения Б) Алгоритм метода множителей Лагранжа - student2.ru . Б) Алгоритм метода множителей Лагранжа - student2.ru . Подставляя найденное значение l в первое уравнение системы, получаем Б) Алгоритм метода множителей Лагранжа - student2.ru или Б) Алгоритм метода множителей Лагранжа - student2.ru . Приписывая оставшееся уравнение, получаем следующую систему: Б) Алгоритм метода множителей Лагранжа - student2.ru . Вычитая из первого уравнения второе, получаем, что хy=2 или Б) Алгоритм метода множителей Лагранжа - student2.ru . Сделав подстановку найденного значения х в уравнение Б) Алгоритм метода множителей Лагранжа - student2.ru Умножим обе части уравнения на у и поделим на 4: Б) Алгоритм метода множителей Лагранжа - student2.ru . Б) Алгоритм метода множителей Лагранжа - student2.ru

Ранее нашли, что Б) Алгоритм метода множителей Лагранжа - student2.ru и Б) Алгоритм метода множителей Лагранжа - student2.ru . Отсюда Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru Так как хy=2, то х1,2 = Б) Алгоритм метода множителей Лагранжа - student2.ru , а Б) Алгоритм метода множителей Лагранжа - student2.ru .

Таким образом, найдены стационарные точки:

Б) Алгоритм метода множителей Лагранжа - student2.ru

Вычисляем значение Z для стационарных точек: Б) Алгоритм метода множителей Лагранжа - student2.ru Следовательно, функция достигает максимума в точке Б) Алгоритм метода множителей Лагранжа - student2.ru

Пример 12. Фирма производит продукцию по двум технологиям: х1 –количество продукции по первой технологии (т), х2 – по второй (т). По первой технологии затраты на производство составляют Б) Алгоритм метода множителей Лагранжа - student2.ru ден.ед., а по второй - Б) Алгоритм метода множителей Лагранжа - student2.ru ден.ед. Определить, сколько тонн продукции следует производить каждым способом, чтобы затраты на производство были минимальными, если в сутки общий объем произведенной продукции должен составлять 3000 т.

Запишем условия задачи математически.

Составим целевую функцию (минимум затрат на производство):

min Z = Б) Алгоритм метода множителей Лагранжа - student2.ru и ограничение: х1 + х2 = 3000,

условия неотрицательности переменных: х1 ≥ 0; х2 ≥ 0

Решение.

1. Преобразуем ограничение, перенеся все его члены в левую часть х12 - 3000=0.

2. Составляем функцию Лагранжа:

L= х12+ х22+l × ( х12 – 3000).

3. Находим частные производные функции Лагранжа, приравниваем их к нулю и составляем систему уравнений:

Б) Алгоритм метода множителей Лагранжа - student2.ru

1+l = 0; l = - 2х1;

2+l = 0; l = - 2х2;

х1 = х1; 2х1 = 3000; х1 = х2 = 1500, l = - 2 × 1500 = -3000;

Таким образом, найдена стационарная точка (1500; 1500; -3000). Вычисляем значение Z для стационарной точки: Z = 4500000.

Дадим другие значения х1 и х2, близкие к точке (1500; 1500), учитывая, что х1 + х2 = 3000. Например, пусть х1 = 1510, х2 = 1490 и вычислим значение Z в этой точке: Z = 4500200. Пусть х1 = 1495, х2 = 1505 и вычислим значение Z в этой точке: Z = 4500050. Мы видим, что значения Z в этих произвольно выбранных точках превышают значение Z в найденной стационарной точке (1500, 1500). Следовательно, функция достигает минимума в точке Х(1500; 1500; -3000).

Таким образом, для получения минимальных затрат, равных 4500000 ден. ед., необходимо производить продукцию и по первой технологии и по второй по 1500 т.

Контрольные вопросы

1. Почему экстремум называется условным?

2. Как свести задачу на условный экстремум к задаче на безусловный экстремум?

3. Когда используется метод множителей Лагранжа?

4. Как формулируется задача на нахождение условного экстремума методом множителей Лагранжа?

5. Как составляется функция Лагранжа?

6. Как найти стационарные точки функции Лагранжа?

7. Как можно найти искомый максимум (минимум) задачи?

8. Назовите алгоритм метода множителей Лагранжа?

Индивидуальные задания 2

Найти экстремумы функции в номерах 1- 6.

Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru

Б) Алгоритм метода множителей Лагранжа - student2.ru

7 – 24. Для заданной функции полезности Z(x1,x2) на товары x1 и x2определить, какой оптимальный набор товаров выберет потребитель при векторе цен р (р12) и доходе I. Найти максимальное значение функции полезности. Ограничение максимизации функции полезности имеет вид: р1х1 + р2х2 = I

Таблица 2

Варианты заданий

Вариант Z(х1,х2) р1 р2 I Вариант Z(х1,х2) р1 р2 I
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru 1,5
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru 0.7
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru 2,5
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru
Б) Алгоритм метода множителей Лагранжа - student2.ru 0,7 Б) Алгоритм метода множителей Лагранжа - student2.ru
Б) Алгоритм метода множителей Лагранжа - student2.ru 2,5 Б) Алгоритм метода множителей Лагранжа - student2.ru
Б) Алгоритм метода множителей Лагранжа - student2.ru Б) Алгоритм метода множителей Лагранжа - student2.ru

ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ

Задачи выпуклого программирования – это задачи минимизации нелинейной, но гладкой функции выпуклой или вогнутой при ограничениях, заданных нелинейными или линейными неравенствами, определяющими выпуклое множество.

Множество w называется выпуклым, если для любых двух несовпадающих точек найдется отрезок прямой, соединяющий эти точки и целиком принадлежащий множеству w.

Функция называется гладкой,если она имеет непрерывные первые производные.

Функция называется выпуклойна выпуклом множестве w, если она обладает следующим свойством f[(1-t)X¢+tX²]£ (1-t) · f(X¢)+t · f(X²), где 0£t£1, X¢Îw,X²Îw,w - выпуклое множество.

Наши рекомендации