Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ МНОГОЭКС-ТРЕМАЛЬНЫХ ФУНКЦИЙ |
|
|
На практическом занятии рассматриваются методы отыскания глобального минимума функций одной переменной. Предполагается, что заданы исходный отрезок Л = [a, b] и количество вычислений N значений функции f (х) . Требуется определить оценки точки глобального минимума х* и величины ми* * нимума f = f (х ) . Простейшим методом глобальной оптимизации является так называемое сканирование (метод перебора), которое состоит в последовательном переборе точек Х, е Л, i = 1, N. В простейшем случае точки выбираются равномерно. При этом исходный отрезок Л разбивается на N интервалов длины h = bЧa, средними N точками которых и являются хi. Таким образом, h b - a х, = a + (i - 1)h + - = a + (2i - 1), i = 1, N. (5.1) i 2 2N При записи алгоритмов и решении задач используются следующие обозначения: ** х1 и fi , i=1,2,..., - соответственно оценки точки глобального минимума и величины глобального минимума, полученные после i вычислений; а - любое число, не принадлежащее исходному отрезку [a, b], т.е. а? [a,b]; в - число, заведомо большее f , т.е. в > f . Алгоритм поиска глобального минимума методом сканирования заключается в следующем. Задаются N, а и в ; полагается х* = а, f0* = в, i = 1. Вычисляются Х, и f (Х, ). Полагается fi = x,, если./(x,) < ft-i, x*_i, если f (x) > f (x), если/ (x) < f*-i, f-1, если f (xi) > f*1. 4. Проверяется условие окончания вычислений i=N. * * * * Если оно выполняется, то полагается x = xN, / = /N и вычисления завершаются. Если условие не выполняется, то полагается i=i+1 и осуществляется переход к п. 2. Пример. Определить с помощью сканирования минимум функции f (x) = 2x4 - 8x3 + 8x2 - x, заданной на отрезке A = [-1,4], при N=10. Решение. Задаем а=10, ?=1000. Определяем xi с помощью соотношения (5.1): 4 +1 x, =-1 + (2i -1) = -1,25 + 0,5i, i = 1,10. i 20 Результаты вычислений заносим в табл. 5.1. Таблица 5.1 Номер отсчета x, f (x,) > < /*, * x,-1 1 -0,75 9,26 < 1000 10 2 -0,25 0,883 < 9,26 -0,75 3 0,25 0,133 < 0,883 -0,25 4 0,75 1,01 > 0,133 0,25 5 1,25 0,508 > 0,133 0,25 6 1,75 -1,37 < 0,133 0,25 7 2,25 -1,62 < -1,37 1,75 Окончание табл. 5.1 8 2,75 5,76 > Ч1,62 2,25 9 3,25 29,8 > Ч1,62 2,25 10 3,75 82,4 > Ч1,62 2,25 Ч1,62 2,25 Поскольку i=10=N, то вычисления завершаются. Ответ: х = 2,25, f = Ч1,62 . Модификацией сканирования с целью уменьшения количества вычислений является поиск (сканирование) с уточнением. В этом случае процедура равномерного сканирования выполняется n раз. На 1 -м этапе осуществляется сканирование во всей зоне поиска (на всем отрезке) Л(0) = [a(0) = a, b(0) = b]. При этом выполняется N1 вычислений, т.е. исходный отрезок разбивается на N1 отрезков длины h(1) = ~~~, в средних точках хг(1) которых вычисляются значения функции f (х) . В результате определяют- *(1) *(1) ся оценки х^' и jNy'. На 2-м этапе осуществляется сканирование на отрезке Л(1) = [a(1), b(1)], границы которого определяются следующим образом. Пусть х^) = хк1, k е {1,2,..., N1}, тогда a(1) = х&, b(1) = хл , здесь принято, что х01) = a(0), х$+1 = b(0). Отметим, что х0(2) = f0 (2) = fN*(1). На 2-м этапе выполняется N2 вычислений, в результате которых определяются *(2) *(2) оценки хn( ) и fN( ) . Затем выполняются 3-й, 4-й, ..., n-й этапы. Поскольку общее количество вычислений равно N, то Nj, j = 1, n, должны удовлетворять условию IN = N. j=1 * Итоговыми оценками точки глобального минимума х и величины глобального минимума f являются величины xJ-n) и n f*(n), т.е. х* = y*(n) г * = г *(n) NN nn Пример. Определить с помощью поиска с уточнением минимум функции f (х) = 2х4 - 8х3 + 8х2 - х, заданной на отрезке А = [-2, 4], при N=10, n=2, N1 =6, N2 =4. Решение. Первый этап Задаем а=10, ?=1000. Определяем х(1) с помощью следующего соотношения: х(1) = a + - (2i -1), i = TTNT. 4+2 (1) = -2 + (2i -1) = -2,5 + i, i = 1,6. л 12 В итоге получаем х(1) =-2 + - Результаты вычислений заносим в табл. 5.2. Таблица 5.2 Номер отсчета х(1) f ( хг(1)) > < f *(1) Ji-1 Y*(i) xi-1 1 -1,5 56,6 < 1000 10 2 -0,5 3,63 < 56,6 -1,5 3 0,5 0,625 < 3,63 -0,5 г 2N1 V b 1 Окончание табл. 5.2 4 1,5 -0,375 < 0,625 0,5 5 2,5 0,625 > -0,375 1,5 6 3,5 51,6 > -0,375 1,5 -0,375 1,5 Поскольку i = 6 = N1, то вычисления завершаются. В итоге получаем х6*(1) = хл = 1,5, /;(1) =-0,375. Второй этап Определяем Д(1) = [ xf, xf] = [0,5; 2,5]. Полагаем x*(2) = 1,5, f0*(2) =-0,375. Определяем x(2) с помощью следующего соотношения: b(1) - а(1) x(2) = а(1) + - Ч(2i-1), i = 1,N2. 2 N 2 В итоге получаем :р) = 0,5 + 25Ч05(2i - 1) = 0,25 + 0,5i, i = 1,4. 8 x(2) = 0,5 + ^ г 8 Результаты вычислений заносим в табл. 5.3. Таблица 5.3 Номер отсчета x(2) f ( x(2)) > < f *(2) Ji-1 v*(2) xi-1 1 0,75 1,01 > -0,375 1,5 2 1,25 0,508 > -0,375 1,5 3 1,75 -1,37 < -0,375 1,5 4 2,25 -1,62 < -1,37 1,75 -1,62 2,25 Поскольку i=4= N2, то вычисления завершаются. Ответ: x = 2,25, f = -1,62 . Развитием и обобщением поиска с уточнением является поиск с разведкой. В этом случае исходный отрезок локализации разбивается на 2 равных по величине отрезка (зоны) D1 и D2: a, D 2 = Л = b = [a2, b2 ]. = h, b ] a + b 2 : a + b 2 На первом этапе в каждой из зон проводится разведка. Для этого из общего количества вычислений N выделяется N0 вычислений (в каждой из зон выполняется по N0 / 2 вычислений). Цель разведки состоит в выборе одной из зон для дальнейших исследований. Разведка заключается в сканировании каждой из зон. Обозначим точки, в которых производятся вычисления в зонах D1 и D2, через у, и zt, i = 1,N0/2, соответственно. В результате вычислений определяются оценки точек минимума yN /2 и zN /2, * * значений минимума f (yN /2) и f (zN /2) и средние значения M1 и M 2 f (х) в зонах D1 и D2 соответственно: /2 f (У,) N M i = I M NI2 fM =i N0/2' i=1 N0/2- Если M1 < M2 , то для дальнейших исследований выбирается зона D1, в противном случае - зона D2 . На втором этапе осуществляется сканирование выбранного отрезка ( D1 или D2 ), при этом выполняется N-N0 вычислений. В качестве начальных значений искомых точки глобального минимума и значения глобального минимума выбираются полученные на первом этапе оценки, т. е. (y х N. /2 или ZN0/2), f0 = ( f (У N0 / 2 ) или f(zN0/2 В результате определяются xNи fN-= f (xN-^ ), которые считаются оценками искомых величин, т.е. * ~ * Г* ~ Г* x = XN - N 0 , J = JN - N 0 . Пример. Определить с помощью поиска с разведкой минимум функции f (x) = 2x4 - 8x3 + 8x2 - x, заданной на отрезке А = [-2,4], при N=10, N0=6. Решение. Определяем D1 и D2: Dx = [-2,1], D2 = [1,4]. Первый этап Проводим разведку в D1. Задаем а=10, ?=1000. Определяем y, с помощью следующего соотношения: У, = л1 + ^ (2i -1), j = W2. N 0 В итоге получаем 1 + 2 - У, = -2 + (2i -1) = -2,5 + i, i = 1,3. 6 Результаты вычислений заносим в табл. 5.4. Таблица 5.4 Номер отсчета У, f (У,) > < * Уi-1 1 -1,5 56,6 < 1000 10 2 -0,5 3,63 < 56,6 -1,5 3 0,5 0,625 < 3,63 -0,5 0,625 0,5 Поскольку i=3=N0 / 2, то вычисления завершаются. В итоге получаем .Уз = 0,5, f (уз) = 0,625, w 56,6 + 3,63 + 0,625 ДлД M, =Ч = 20,3. 1 3 Проводим разведку в D2 . Задаем а=10, ?=1000. Определяем zi с помощью следующего соотношения: Zi = л2 + ^Nr2- (2i -1), i = 1^. N 0 4 -1 - Z: = 1 + (2i -1) = 0,5 + i, i = 1,3. г 6 В итоге получаем i 4 - z' =1 +1 Результаты вычислений заносим в табл. 5.5. Таблица 5.5 Номер отсчета zi f (z) > < з zi-1 1 1,5 -0,375 < 1000 10 2 2,5 0,625 > -0,375 1,5 3 3,5 51,6 > -0,375 1,5 -0,375 1,5 Поскольку i=3=N0 / 2, то вычисления завершаются. В итоге получаем z* = 1,5, f (z* ) = -0,375, - 0,375 + 0,625 + 51,6 M 2 = 2 2 !_ = 17,3. 2 3 Поскольку M1 > M2, то выбираем для дальнейшего исследования D2 . Второй этап Полагаем х* = 1,5, f0 =-0,375. Определяем xi с помощью следующего соотношения: v. = a2 + f2 a . (2i -1), i = 1,N-N0. 1 2 2(N - N 0 ) 0 В итоге получаем 4 -1 Ч x, = 1 + (2i -1) = 0,625 + 0,75i, i = 1,4. 8 Результаты вычислений заносим в табл. 5.6. Таблица 5.6 Номер отсчета f (xt) > < * xi-1 1 1,375 1,02 > -0,375 1,5 2 2,125 -1,98 < -0,375 1,5 3 2,875 9,78 > -1,98 2,125 4 3,625 65,8 > -1,98 2,125 -1,98 2,125 Поскольку i=4= N - N0, то вычисления завершаются. Ответ: x = 2,125, f = -1,98. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ МНОГОЭКС-ТРЕМАЛЬНЫХ ФУНКЦИЙ" |
|
|