Математические методы экономических исследований

Общая постановка задачи состоит в нахождении максимума (минимума) функции: f(x1, x2, ., xn) при условии: g(x1, x2, .,xn) = bi , i = 1, 2, ., m.

Условия неотрицательности xj могут отсутствовать. Имеем задачу на условный экстремум - классическая задача оптимизации.

Задача решается следующим образом. Вводят набор переменных li (i = 1, 2, ., m) - множителей Лагранжа и составляют функцию: <

p>.

Далее определяют частные производные:

(j = 1, 2, ., n) и , (i = 1, 2, ., m).

На следующем шаге рассматривают систему n + m уравнений:

Любое решение этой системы определяет точку , в которой может иметь место экстремум функции f (x1, x2, ., xn). Таким образом, разрешив построенную систему, определяют все точки, в которых функция f может иметь экстремум. Дальнейшее исследование идет как в случае безусловного экстремума.

Итак, этапы решения задачи нелинейного программирования методом множителей Лагранжа заключаются в следующем:

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

2.Находят частные производные функции Лагранжа по xj и li и приравнивают их 0.

3.Решая полученную систему, находят точки, в которых целевая функция задачи может иметь экстремум.

4.Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, вычисляют значения f(x1, x2, .,xn) в этих точках и среди них выбирают те, которые удовлетворяют условиям задачи.

Выпуклое программирование

Суть общей постановки задачи состоит в определении максимального (минимального) значения функции:

f(x1, x2, .,xn)

при условиях:

gi(x1, x2, ., xn) £ bi (i = 1, 2, ., m), xj ³ 0 (j = 1, 2, ., n).

Универсальных методов решения поставленной задачи в общем виде не существует. Однако, при определенных ограничениях решение этой задачи может быть найдено.

Несколько определений.

Функция f(x1, x2, ., xn) на выпуклом множестве X называется выпуклой, если для любых двух точек X2 и X1 из X и любого 0 £ l £ 1, выполнено соотношение:

f[lX2 + (1 - l)X1] ³ lf(X2) + (1 - l)f(X1).

Множество допустимых решений удовлетворяет условию регулярности, если существует хотя бы одна точка Xi этой области такая, что gk(Xi) < bk (k = 1, 2, ., m).

Задача выпуклого программирования возникает, если функция f является вогнутой (выпуклой), а gi - выпуклы.

Любой локальный максимум (минимум) является глобальным максимумом (минимумом). Наиболее характерным методом решения задач выпуклого программирования является метод множителей Лагранжа. При этом точка (X0, L0) называется седловой точкой функции Лагранжа, если:

F(x1, x2, ., xn, ) £ F()£

£ F(), для всех xj ³ 0 и li ³ 0.

Для задачи выпуклого программирования, множество допустимых решений которой обладает свойством регулярности, точка X0 = () является оптимальным решением тогда, когда существует такой вектор L0= (), что точка (X0, L0) является седловой точкой функции Лагранжа, построенной для исходной задачи.

Для задачи определения максимума, условиями седловой точки будут:

(частные производные берутся в седловой точке).

Для задачи нахождения минимума седловая точка определяется соотношениями:

F() £ F()£ £ F().

Условия седловой точки в этой задаче представляются в виде:

,

.

Градиентные методы

Градиентными методами можно найти решение любой задачи нелинейного программирования. Однако в общем случае эти методы позволяют найти точку локального экстремума. Наиболее целесообразным является использование этих методов для решения задач выпуклого программирования, где всякий локальный экстремум является глобальным.

Суть метода заключается в том, что начиная от некоторой точки X(k) осуществляется последовательный переход к другим точкам до тех пор, пока не будет получено приемлемого решения исходной задачи. Методы можно разделить на две группы.

Первая группа, когда исследуемые точки не выходят за пределы области допустимых решений (здесь используется метод Франка-Вулфа).

Вторая группа, когда эти точки не обязательно входят только в область допустимых решений, однако в итерационном процессе такие точки будут. (Здесь используется метод штрафных функций и метод Эрроу-Гурвица).

Нахождение решения идет итерационным процессом до тех пор, пока градиент функции f(x1, x2, ., xn) в очередной точке X(k+1) не станет равным 0, или пока | f(X(k+1)) - f(X(k)) |< e, где e достаточно малое положительное число. Эту величину часто называют точностью полученного решения.

Метод Франка-Вулфа

Найти максимум вогнутой функции: f(x1, x2, ., xn), при условии:

.

Здесь имеем линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной функции линейной, тогда решение исходной задачи сводится к последовательному решению ряда задач линейного программирования.

Начинается процесс решения с определения точки, принадлежащей области допустимых решений. Пусть это точка X(k). В ней вычисляют градиент функции f:

Ñf(X(k)) =

и строят линейную функцию:

F = .

Находят максимум функции F при сформулированных ограничениях. Пусть решение этой задачи Z(k). Тогда за новое допустимое решение принимают:

X(k+1) = X(k) + lk(Z(k) - X(k)),

где lk ‑ некоторое число, называемое шагом вычислений (0 £ lk £ 1). Число lk - произвольное и выбирают его так, чтобы значение функции в точке X(k+1) , зависящее от lk, было максимальным. Для этого надо найти решение уравнения и выбрать его наименьший корень. Если корни уравнения больше 1, то берется lk = 1. Затем определяют X(k+1) и f(X(k+1)) и выясняют необходимость перехода к точке X(k+2). Если такая необходимость имеется, то в точке X(k+1) вычисляют градиент целевой функции и переходят к соответствующей задаче линейного программирования и решают ее. Определяют координаты точки X(k+2) и необходимость дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

 Скачать реферат