Условия Куна-Таккера.

В предыдущей лекции рассматривались ограничения g (x) = 0, т.е. ограничения в виде равенств. Некоторые экономические проблемы сводятся к задачам, в которых имеются ограничения другого вида, например,
неравенства x ₀ ≥ 0, x₁ ≥ 0,..., x _n≥ 0 и g (x) ≤ b.

Рассмотрим геометрическую интерпретацию ограничений вида х ≥ 0. Они определяют n-мерный положительный ортант. Ортант — одна из 2ⁿ областей, на которые n-мерное пространство делится n взаимно перпендикулярными координатными гиперплоскостями. Неравенство g (х)≤ b определяет подмножество этого ортанта.

Если решение задачи лежит на границе области,
задаваемой ограничениями, то методом Лагранжа его
найти нельзя. Для решения таких задач используются
другие средства, например, теорема Куна-Таккера. Рас-
смотрим её формулировку.

Пусть требуется найти максимум целевой функции
и = и(x) при ограничениях g (x) ≤ b, x ≥ 0. Ограничения типа неравенства можно преобразовать
в равенства. Для этого рассмотрим вектор s= b-g (x)= (s₁,..., s_m). Тогда задача формулируется так:

и = и(х) → max,
g (x) + s = b и х ≥ 0, s ≥ 0

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

Пусть (x ₀, х ₁ ,..., х _n, ₁,..., _m) = (х, ) — стационарная точка, тогда в ней выполняются условия Ку
на-Таккера:

5.12

5.13

5.14

5.15

5.16

5.17

Поскольку выполнены неравенства (5.12) и (5.14) в

уравнении (5.13) либо ,либо х^*=0, либо эти равенства выполнены одновременно. Аналогично, в
силу неравенств (5.15) и (5.17) из уравнения (5.16) следует, что либо , либо λ ^* = 0, либо эти равенства выполнены одновременно. Запишем эти условия подробно:

.

 

Из этих равенств и неравенств (5.14) и (5.17) следует другая формулировка условий Куна-Таккера:

, если , j = 0, …., n

, если i = 1,….,m

g_i (x^*)= b, если i = 1,….,m

, если g (x ^*)<b, i = 1,….,m

Условия Куна-Таккера в виде (5.18) называются
условиями дополняющей нежесткости.

Рассмотрим пример. Пусть решается задача:

u (x ₁, x ₂)= -4

x₁+x₂≤2

0.125

x ₁≥0; x₂ ≥0

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

Условия Куна-Таккера:

-8x₁+6x₂-25-λ₁-0,25 λ₂x₁ ≤ 0

-10x₂+6x₁+40- λ₁-6 λ₂x₂ ≤ 0

(-8x₁+6x₂-25- λ₁-0,25 λ₂x₁)x₁+(-10x₂+6x₁+40- λ₁-6 λ₂x₂)x₂ = 0

x₁ ≥ 0, x₂ ≥ 0

2-x₁-x₂ ≥ 0

2 - 0,125 - 3 ≥ 0

λ₁(2 – x₁ – x₂) + λ₂(2 - 0,125 - 3 )=0

λ₁ ≥ 0; λ₂ ≥ 0

На рис. 5.5 заштриховано множество, удовлетворяющее ограничениям задачи. Целевая функция вогну-
та, её первое пересечение с множеством — точка А
координатами (0, 1). Она является решением задачи.
Другие граничные точки множества В 0 (0, 0) и С (2, 0) не удовлетворяют всем
условиям Куна-Таккера.

Условия Куна-Такке
ра полностью характеризу-
ют решение, однако в прак-
тических проблемах часто
они не дают аналитического
решения. Поэтому алгорит-
мы решения таких задач
используют численные ме-тоды.

 

 

Приложения: