КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Метод множителей Лагранжа
Классические методы оптимизации. Нелинейное программирование. Во многих экономических моделях исследования зависимости между постоянными и переменными факторами не всегда оказываются линейными. В этом случае возникает задача нелинейного программирования. В нелинейном программировании существует несколько методов определения экстремумов. Основным из них является: - классические методы оптимизации Различают локальные, глобальные и условные экстремумы. а) Локальный экстремум. Необходимые условия экстремума: если в точке х* функция z=f(x) имеет экстремум, то частные производные в этой точке равны 0. fxi(x*)=0, i = 1,2..n (количество переменных). Точка х*, в которой все частные производные функции z=f(x) равны 0, называется стационарной точкой.
Достаточные условия экстремума: Для функции 2-х переменных z=f(x1,x2) cсуществуют 4 частные производные II порядка, из них две смешанные производные равны. f′′х12(x1,x2); f′′х1х2(x1,x2); f′′х2х1(x1,x2); f′′х22(x1,x2); Найдем значения частных производных II порядка в стационарной точке х0(х10,х20) а11=f′′х12(х0) а12=f′′х1х2(х0) а21=f′′х2х1(х0) а22= f′′х22(х0) Составим определитель, составленный из аij
∆= а11 а12 =а11а22-а21а12 а21 а22
Тогда достаточные условия экстремума функции 2х переменных имеют вид: а)Если ∆>0 и а11<0 (а22<0), то функция в точке х0 имеет max. Если ∆>0 и а11>0 (а22>0), то функция в точке х0 имеет min. б)Если ∆<0, то экстремума нет. в)Если ∆=0, то вопрос об экстремуме остается открытым. Пример: Исследовать на экстремум функцию Z=x14+x24-x12-2x1x2-x22 Находим частные производные: Z ′(x1)= 4x13- 2x1-2x2 (*) Z ′(x2) = 4x23- 2x1-2x2 Приравниваем частные производные к 0
4x13- 2x1-2x2=0 (1) 4x23- 2x1-2x2=0 (2) Вычитая из (1)-(2) получим 4x13-4x23 =0 х1=х2 из (1) x13-x1=0, х1=0 и х1= ±1 Имеем 3 стационарные точки х1=(0,0), х2=(1,1),х3=(-1,-1)
Найдем вторые частные производные, используя(*) Z″ x12=(4x13- 2x1-2x2)′х1 =12x12-2
Z″ x1x2=(4x13- 2x1-2x2)′ x2 = -2
Z″ x2x1=(4x13- 2x1-2x2)′ x3 = -2
Z″x2 2 =(4x13- 2x1-2x2)′x4 = 12x2 -2
В т.x′1=(0,0), a11= -2, a12= a21= -2, a22= -2 ∆= -2 -2 =0 -2 -2 Вопрос об экстремумах остается открытым (такая точка называется седловиной) Вт. x′2=(1,1) и В т x3=(-1,-1) a11= 10, a12= a21= -2, a22= 10 ∆= 10 -2 =96 -2 10 функция в этих точках имеет min, так как ∆>0, a11>0 zmin= 14+14-12-2∙1∙1-12= -2 б)Глобальный экстремум (наибольшее, наименьшее значение функции).
Если область D замкнута и ограничена, то дифференцируемая функция z=f(x) достигает в этой области своего наибольшего и наименьшего значения в стационарной точке или в граничной точке области (теорема Вейерштрасса) следовательно, чтобы найти глобальный экстремум функции z в области D необходимо: 1)Найти все стационарные точки внутри области D и вычислить функции в них. 2)Исследовать функции на экстремум на границе области D. 3)Сравнить значения функции, полученные в пункте 1 и 2. Наибольшее или наименьшее из этих чисел и будет глобальным экстремумом.
в)Условный экстремум.
Пусть необходимо найти экстремум функции z=f(х1,х2,…,хn) при условии, что эти переменные (х1,х2,…,хn) удовлетворяют уравнению φ(х1,х2,…,хn)=0, которое называется уравнением связи. Говорят, что в точке х0(х01,х02,…,х0n), удовлетворяющему уравнению связи, функция z=f(x) имеет условный max (min), если f(х0)≥ f(x) (f(х0)≤ f(x)) имеет место для всех точек х, координаты которых удовлетворяют уравнению связи. Пример. Дана производственная функция z=x12x22(4-x1-x2) (1). Цены С1=1, С2=2 и издержки b=4. Необходимо найти х1 и х2, удовлетворяющие уравнению х1+2х2=4 (2) (уравнение связи) превращающее производственную функцию (1) в max.
Уравнение (2) и условие неотрицательности на плоскости х1Ох2 образуют замкнутую ограниченную област. (см. рис.) Согласно теореме Вейерштрасса max функции может быть достигнут либо внутри этого отрезка, либо в граничных точках А(4;0) и В(0;2).Следовательно необходимо найти условный экстремум функции (1), если уравнение связи(2). Из (2) находим: х1=4-2х2 тогда z=(4-2х2)2x2(4-4+2x2-x2), z=4(2-х2)2x22 Найдем глобальный экстремум z′=16(2-x2)x2(1-x2)=0, стационарная точка x2=0; x2=1; x2=2; значение функций в этих точках z(0)=0; z(1)=4; z(2)=0; Максимальный объем производства zmax=4 единицы, достигается при условии, что затраты х1=2 и х2 = 1 ед. Другой способ определения условного экстремума осуществляется с построения вспомогательной функции Лагранжа, которая достигает max для тех же х1,х2,…,хn, что и целевая функция z. Пусть решается задача определения условного экстремума функции z=f(x) при ограничении φ(х)=0. Составим функцию, которая называется функция Лагранжа m L(x)=f(x)+∑λiφi(x) i=1 λi – постоянные множители (множитель Лагранжа).
Определение стационарных точек приводит к решению системы уравнений: ∂L(x)/ ∂Xj=0, j=1,2,…n. ∂L(x)/ ∂λi =0, i=1,2,…m. отсюда видно, что L′λi(x)= φi(x) Таким образом, задача нахождения условного экстремума функции z=f(x) сводится к нахождению локального экстремума функции L(x). Если стационарная точка найдена, то вопрос о существовании экстремума решается на основании достаточного условия экстремума. Пример: Найти наибольшее и наименьшее значения функции z=9x12+4x22+x32-(3x12+2x22+x32) при условии, что х1 х2 х3 удовлетворяют уравнению х12+х22+х32=1, которое определяет сферу единичного радиуса. Согласно теореме Вейерштрасса, функция достигает на этой сфере свое наибольшее и наименьшее значение. Находим условный глобальный экстремум. Запишем уравнение связи в виде: х12+х22+х32-1=0; Составим функцию Лагранжа: L=9x21+4x22+x23-(3x21+2x22+x23)+λ(x21+x22+x23-1) Найдем частные производные этой функции по х1, x2, x3, λ и приравняем их к 0. L′(x1)=х1((9+λ)-6(3 х12+2х22+х32))=0 L′(x2)=х2((4+λ)-4(3 х12+2х22+х32))=0 L′(x3)=х3((1+λ)-2(3 х12+2х22+х32))=0 Lλ′= х12+2х22+х32)) =1 Решая систему, получим стационарные точки(6 точек), в которых найдем значения функции z наибольшее=1 и z наименьшее=0 Однако применение классических методов в исследовании операций весьма ограничено, так как задача определения условного экстремума функции n переменных весьма трудоемка.
Поэтому разработаны приближенные методы решения нелинейных задач программирования, например, для выпуклых(вогнутых) функций.
Дата добавления: 2014-01-06; Просмотров: 528; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |