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

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

найти max (min) Z (Х) = при ограничениях

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

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

, где - множители Лагранжа. То есть функция Лагранжа равна сумме, причем в качестве первого слагаемого переписывается целевая функция без изменений, а каждое ограничение (правая часть ограничений равна нулю) умножается на множитель Лагранжа l_i (i=1¸m), и полученные выражения приписываются к целевой функции в виде слагаемых. Функция Лагранжа имеет n+m переменных: х₁, х₂, …, х_n, l_1, l_2,…, l_m.

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

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

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

Пример 11. Найти

Решение.

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

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

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

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

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

Ранее нашли, что и . Отсюда

Так как хy=2, то х_1,2 = , а .

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

Вычисляем значение Z для стационарных точек: Следовательно, функция достигает максимума в точке

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

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

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

min Z = и ограничение: х₁ + х₂ = 3000,

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

Решение.

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

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

L= х₁²+ х₂²+l × (х₁+х₂– 3000).

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

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

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

х₁= х₁; 2х₁= 3000; х₁= х₂= 1500, l = - 2 × 1500 = -3000;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2

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

Вариант	Z(х_1,х₂)	р₁	р₂	I	Вариант	Z(х_1,х₂)	р₁	р₂	I
								1,5

							0.7
								2,5


		0,7
			2,5

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

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

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

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

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