Шпаргалки по "Основам эконометрики и математического моделирования"

11,12.Метод множителей Лагранжа для задач нелинейного  и выпуклого программирования.Теорема Куна-Такера

Функция f определена множестве x. Функция наз. Выпуклой, если для люб. 2 точек отрезок, проведенный между ними, лежит внутри множества x.

F(x)- выпукл. Ф-ция, определенная на множестве x

Теорема Куна- Такера

Задача 1. Найти min f(X) при j(X) <=0, i=l,m

                                   x>=0

Т.о. x-вектор, x= (x1,x2,…xn)

 

Для этой задачи сост-ся ф-ция Лагранжа

                     m

L (x,λ)= f(x)+ S λi ji(x)

                    i=1

(λi-множитель Лагранжа)

(x*, λ*)- будем называть типовой точкой для функции Лагранжа, если выполняется след. Неравенство

L (x*,λ) <=L (x*,λ*) <=L (x,λ*) " x, λ(*)          (*)

λ= (λ1, λ2,…, λm)

 

Формулировка  теоремы Куна-Такера

Пусть $x>=0 : ji(x) <0, i= 1,m;

Чтобы х* была решением задачи 1, необходимо и достаточно, чтобы  существовала такая т. Х*, которая уд-ла (*)

Если потребовать, чтобы  функция f(x) и j(х) были дифференц-мы, то теорема Куна-Такера м.б. сформулирована след. Образом:

δL (x*,L*) /δx ³0

x* умножить  δL(x*,L*)/ δx=0

x*³0

δL (x*,λ*) / δλ £ 0

λ* умножить δL(x*, λ*) / δλ=0

λ³0

 

2.Основные  виды записи ЗЛП.

Общей задачей линейного  программирования (ОЗЛП) называют задачу

  (1.24)

при ограничениях:

 

 (i=1,..,m₁)  (1.25)

 (i=m₁+1,..,m₂)  (1.26)

 (i=m₂+1,…,m)  (1.27)

x_j≥0 (j=1,..,n₁)   (1.28)

x_j – произвольные (j=n₁+1,…,n)  (1.29)

 

где c_j, a_ij, b_i – заданные действительные числа; (1.24) – целевая функция; (1.25) – (1.29) – ограничения; х=(x₁;…;x_n) план задачи.

 

Симметричной  формой записи ЗЛП называют задачу

 

  (1.30)

 (i=1,..,m)   (1.31)

x_j≥0 (j=1,..,n)   (1.32)

 

или задачу

  (1.33)

 (i=1,..,m)   (1.34)

x_j≥0 (j=1,..,n)   (1.35)

 

В экономической практике задача (1.30) – (1.32) (или (1.33) – (1.35)) встречается  наиболее часто.

 

Канонической формой записи ЗЛП называют задачу

 

  (1.30)

 (i=1,..,m)                    (1.31)

x_j≥0 (j=1,..,n)   (1.32)

 

Рассмотрим еще два  употребительных вида записи – матричную  и векторную. В модель (1.36) – (1.38) введем обозначения:

 

C=[c₁ c₂ … c_n], , ,

 

 где C – матрица–строка; A – матрица системы управлений; X – матрица–столбец переменных; A₀ – матрица–столбец свободных членов.

Каноническая форма  задачи примет вид:

max Z=[c₁ c₂ … c_n][x₁ x₂ … x_n]^T

, X≥0,

или

max Z=CX, AX=A₀, X≥0

Полезной является также векторная форма ЗЛП. Для столбцов матрицы A введем обозначения:

Тогда задача (1.36) – (1.38) в  векторной форме записи примет вид:

max Z=cx;

A₁x₁+…+A_jx_j+…+A_nx_n=A₀, x≥0

где cx – скалярное произведение векторов c=(c₁;…;c_n) и x=(x₁;…;x_n).