Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
МЕТОД АППРОКСИМИРУЮЩЕГО ПРОГРАММИРОВАНИЯ |
|
|
Метод аппроксимирующего программирования (МАП) относится к численным методам решения задач условной оптимизации. Наиболее простой и хорошо изученной задачей условной оптимизации является задача линейного программирования (ЛП). МАП является одним из методов решения задач нелинейного программирования. В данном случае исходная задача нелинейного программирования преобразуется в последовательность задач ЛП с помощью процедур линеаризации. Рассмотрим задачу условной минимизации вида f (х) ^ min, хе X = {хе R+ : g,(х) < 0, i = \r}, где f (х), g, (х) - произвольные нелинейные функции. МАП является итерационным методом. На к-й, к = 1,2,..., итерации определяется точка х(к) - к-е приближение к точке минимума х*; при этом исходной точкой для к-й итерации является точка х(к-1). В результате, исходя из заданной начальной точки х(0), находится последовательность точек х(1),х(2),..., сходящая* ся при определенных условиях к решению х исходной задачи нелинейного программирования. Отметим, что в качестве начальной точки х(0) выбирается некоторая точка из допустимого множества X, т.е. х(0) е X; точка х(0) выбирается произвольно, принадлежность к X определяется проверкой выполнения ограничений для этой точки. На к-й, к=1,2,..., итерации в окрестности точки х(к-1) осуществляется линейная аппроксимация (линеаризация) задачи нелинейного программирования, т.е. каждая из нелинейных функций исходной задачи заменяется двумя первыми членами в разложении в ряд Тейлора. В результате получается задача ЛП f (х) = f (х(к-1)) + (f '(х(к-1)), (х - х(к-1))) ^ min , ~ (x) = gi (x (k-1)) + (g' (x(k-1)), (x - *(k-1))) < o, i = 1, r, x e R+. Затем находится решение x0 задачи ЛП, после чего определяется точка x(k) по известным x(k-1) и x0. Эта точка должна удовлетворять условиям x(k) e X, (8.1) f (x(k)) < f (x где Xk - параметр (скаляр), определяющий длину шага из точки ( k -1 ) o x ' в направлении точки x . Очевидно, что при Xk = 1 выполняется x(k) = xo, при xk = o x(k) = x(k-1). Величина Xk выбирается так, чтобы выполнялись условия (8.1). Процесс выбора шага, удовлетворяющего данным условиям, во многом аналогичен соответствующему процессу в случае градиентного метода с дроблением шага. Выбирается константа o <в< 1 (в данном случае а = 1). На k-й, k = 1,2,..., итерации проверяется выполнение условий (8.1) при Ak=1, т.е. для x(k) = xo . Если они не выполняются, то производится дробление шага, т.е. полагается Xk = в, и вновь проверяется выполнение условий (8.1). Процесс дробления, т.е. умножения текущего зна-чения Xk на в, продолжается до тех пор, пока условия (8.1) не окажутся выполненными. Алгоритм решения задачи условной минимизации методом аппроксимирующего программирования заключается в следующем. 1. Задаются в, ^, <52; выбирается x(o); полагается k = 1. Осуществляется линеаризация исходной задачи в окрестности точки х(к-1). В результате получается задача ЛП. Находится решение х0 задачи ЛП. Полагается Хк = 1. Вычисляется х(к) = х(к-1) + Xk (х0 - х(к-1)) . Проверяются условия выбора х(к): g, (х(к)) < 0, i = 1,7; f (х(к)) < f (х(к-1)). Если они выполняются, то осуществляется переход к п.7. Если условия не выполняются, то полагается Хк = Хк в и осуществляется переход к п. 5. 7. Проверяются условия окончания решения исходной задачи: f ( х(к)) - f ( х(к-1)) <*1, f ( х(к-1)) j = 1 П. х f) - х j-1) х j-1) Если они выполняются, то полагается х* = х(к) , f * = f (х(к)) и вычисления завершаются. Если условия не выполняются, то полагается к = к +1 и осуществляется переход к п.2. Пример. Решить методом аппроксимирующего программирования задачу условной минимизации f (х) = 4х1 - х22 -12 ^ min, х12 + х22 < 25, 10х1 - х? +10х2 - х22 > 34, х1 > 0, х2 > 0 при в = 0,7, S1 = 0,1, д2 = 0,3 . Решение. Преобразуем ограничения исходной задачи к виду gi (х) < 0: g1 (х) = х2 + х22 - 25 < 0, g2 (х) = х2 -10х1 + х22 -10х2 + 34 < 0. Находим fXх), g1(х), g2(х): f = 4, f = -2х2 ^ f'(х) = (4,-2х2); дх1 дх2 dg1 = 2х1, ^ = 2х2 ^ g[ (х) = (2х1,2х2); дх1 дх2 = 2х1 -10, dg2 = 2х2 -10 ^ g2(х) = (2х1 -10,2х2 -10). дх1 дх2 Проверяем принадлежность точки х(0) к допустимой об- Выберем х(0) = (2, 4) . П ласти X: g1 (х(0)) = 22 + 42 -25 = -5 < 0, g2(х(0)) = 22 -10Х 2 + 42 -10Х 4 + 34 = -6 < 0, х{0) > 0, х20) > 0. Поскольку ограничения выполняются, то точка х(0) = (2, 4) является допустимой, т.е. х(0) е X . |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "МЕТОД АППРОКСИМИРУЮЩЕГО ПРОГРАММИРОВАНИЯ" |
|
|