Алгоритм решения задачи

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

L(x, λ,λ₀) = l₀ ¦(x) + l_i g_i(x) + l_i g_i(x)

Шаг 2.Записать необходимые условия минимума (максимума) первого порядка:

1) ;

2) ;

3) , (для минимума), , (для максимума);

4) .

Шаг 3. Решить систему для двух случаев:

1) ;

2) (при этом поделить условия, стоящие выше, т.е.1), 3), 4), на и заменить ). В результате найти условно-стационарные точки х*, выделив из них полученные при (они могут быть регулярными точками экстремума). В каждом из двух случаев следует начинать с рассмотрения 2^m-l вариантов удовлетворения условия «г» дополняющей нежесткости.

Шаг 4.Для выделенных на шаге 3 точек проверить достаточные условия экстремума первого или второго порядка.

Для проверки достаточных условий первого порядка следует:

1) определить число k ограничений-равенств и активных ограничений неравенств;

2) если k = nи > 0для всех , т.е. для всех активных ограничений-неравенств, то в точке – локальный минимум. Если k = n и < 0 для всех , то в точке х*– локальный максимум. Если k < n или соответствующие множители Лагранжа не удовлетворяют достаточным условиям первого порядка, проверить достаточные условия второго порядка.

Для проверки достаточных условий второго порядка следует:

1) записать выражение для второго дифференциала классической функции Лагранжа в точке :

;

2) записать условия, накладываемые на первые дифференциалы ограничений-равенств и активных в точке ограничений -неравенств:

, и , λ_i* > 0 (λ_i* < 0), (7.26)

, , λ_i* = 0;

3) исследовать знак второго дифференциала функции Лагранжа для ненулевых , удовлетворяющих (7.26). Если > 0, то в точке х* – условный локальный минимум. Если < 0, то в точке х* – условный локальный максимум. Если достаточные условия экстремума не выполняются, следует проверить выполнение необходимых условий второго порядка, следуя аналогичной процедуре. Если они выполняются, то требуется дополнительное исследование, а если нет, то в точке нет условного экстремума.

Шаг 5. Вычислить значение функции в точках условного экстремума.

Условия экстремума в задаче (7.17)…(7.19) приведены в табл. 7.1, 7.2.

Таблица 7.1

Необходимые и достаточные условия первого порядка в задаче поиска условного

экстремума при смешанных ограничениях

Необходимые условия первого порядка	Достаточные условия первого порядка
№ п/п				λ0*≥0, λi*	Число l огра-ничений-равен-ств и активных ограничений-неравенств		Тип условно-стационарной точки
			≤0	≤0	N	>0	Условный локаль-ный минимум
			≤0	≤0	N	<0	Условный локаль ный максимум

 

Таблица 7.2

 

Необходимые и достаточные условия второго порядка в задаче поиска условного

экстремума при смешенных ограничениях.

 

№ п/п						Тип условно-стационарной точки
	>0	0,	0,		≤0	Условный локальный минимум
	<0	0,		0,	≤0	Условный локальный максимум
	≥0				≤0	Может быть условный локаль-ный минимум, требуется дополнительное исследование
	≤0				≤0	Может быть условный локальный максимум, требуется дополнительное исследование
	=0				≤0	Требуется дополнительное исследование
	=0				≤0	Требуется дополнительное исследование
	≠0				≤0	Нет эктремума
	≠0				≤0	Нет экстремума

Пример 7.10.Износ периферийного оборудования ЭВМ зависит от количества выполненных вычислений, причем различные типы оборудования имеют разный износ.

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

И₁(х₁) = а₁х₁ + а₂х₁²,

где а₁, а₂ – известные коэффициенты; х₁ – вычислительная продукция, полученная на первом оборудовании.

Функция износа второго оборудования имеет квадратичную зависимость от количества х₂ выполненных вычислений:

И₂(х₂) = а₃х₂²,

где а₃ – известный коэффициент.

Всего вычислительной продукции выдается n= х₁ + х₂. Требуется так распределить работу оборудования, чтобы вся вычислительная продукция была получена при минимальном общем износе оборудования.

Решение.Целевой функцией является

f(x) = а₁х₁ + а₂х₁² + а₃х₂².

Эту функцию нужно минимизировать при ограничении - равенстве

П = х₁ + х₂,

где П – известная положительная величина.

Составим функцию Лагранжа

L(x, λ) = а₁х₁ + а₂х₁² + а₃х₂² + λ(П - х₁ - х₂).

Для отыскания оптимального решения запишем частные производные от функции Лагранжа по всем переменным:

В итоге имеем систему трех уравнений с тремя неизвестными. Решая систему, получим:

Пример. Предпочтения потребителя заданы в виде функции

,

где х₁ и х₂ – объемы потребления 1-го и 2-го товаров соответственно. Доход равен 70 отн. ед. Цены 1-го и 2-го товаров соответственно равны Ц₁ = 1, Ц₂ =2. Найти оптимальный набор потребительских товаров.

Решение.Используем метод штрафных функций и составим обобщенную функцию

f(x, k) = + k(Ц₁х₁ + Ц₂х₂ – 70)².

Решая, полученные уравнения, получим х₁ = 64, х₂ = 3.