pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

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

Пусть М - абсцисса искомой точки оптимума (для определенно­ сти - максимума) (рис. 4.9). Вначале целевая функция вычисляется в неко­ торой произвольной точке 7 внутри диапазона варьирования переменной х\. Пусть результат вычислений равен у\. Из этой точки желательно сдви­ нуться в направлении точки М, в данном случае - влево. Но поскольку по­ ложение точки М заранее не известно, сначала делается пробный шаг в од­ ном из двух возможных направлений, т. е. влево или вправо от точки 7.

Рис. 4.9. Схема градиентного метода (случай одной переменной)

Пусть, например, пробный шаг сделан вправо (точка 2) и результат его уъ Из того, что уг<у\, можно сразу заключить, что точка М находится левее точки 7. Поэтому следующий рабочий шаг делается влево от точки 7 в точку 3. Так как уъ>уи то очередной рабочий шаг делается в том же на­ правлении, то есть в точку 4, и т. д. Придя, наконец, в точку б, убеждаемся, что ув<у5 • Значит, точка М находится между точками 5 и 6. Если точность, с которой найдена абсцисса точки М, недостаточна, движение продолжает­ ся вправо от точки 6 с уменьшенной длиной шага.

4.3. Методы поиска экстремума функций нескольких переменных

Рассмотрим задачу отыскания экстремума функций нескольких пе­ ременных у =/(*!, х2, хп) в предположении, что каждая из п переменных может принимать любое действительное значение - положительное или отрицательное. В задачах с практическим содержанием, где переменные

х\, х2, имеют физический смысл, их диапазоны изменения всегда ог­ раничены; тем не менее, рассмотрение данной задачи оказывается полез­ ным, поскольку те идеи, которые будут предложены для ее решения, ока­ жутся применимыми и для задач оптимизации с ограничениями, т. е. задач нелинейного программирования, имеющих большое практическое значе­ ние.

4,3. 1. Необходимые и достаточные условия экстремума

Предположим, что функция y= f(x i, х2, ..., хп) имеет непрерывные производные по своим аргументам. Если эта функция имеет экстремум в

точке	= (x f \ x f \	...,	то все ее частные производные в этой точке
обращаются в нуль:		df/dxi = 0 при z = 1, 2, ..., п. Иными словами, если

приравнять нулю все частные производные от у по *,• и решить полученную систему уравнений

Qf/дхi=0; "

df/дх2 = 0;

(4.18)

¥ /д х „ = 0,

то среди найденных решений окажется и точка экстремума. Точки, удовле­ творяющие системе (4.18), называются критическими.

Достаточные условия экстремума сформулируем только для функ­

ции двух переменных y=f(xu х2). Предположим, что точка М		яв­
ляется критической точкой функции/(хь х2), то есть
д /(* 1° ; * 2° ) _ 0;	д/(х?;х<>) 0
дх}	дх2

Пусть, кроме того, в некоторой области, содержащей точку М, функцияf(xi, х2) имеет непрерывные частные производные до третьего по­ рядка включительно. Вычислим в этой точке вторые производные функции f(x u x2):

,		f y / t f i . 4 - 1) . с = а % М З .
дх?	9	дххдх2 ’	дх\

Обозначим через D выражение А С -В 1. Тогда функцияfix ь х2) име­ ет в точке М:

1)минимум, если D> 0 и А > 0;

2)максимум, если D > 0 и А < 0;

3)отсутствие экстремума, если D< 0.

Если же D=О, то экстремум в точке М может быть или не быть (в этом случае требуется дополнительное исследование).

Задача оптимизации размеров тарного ящика. Предположим,

что ящик имеет форму прямоугольного параллелепипеда, все его стенки имеют одинаковую толщину и изготовлены из одного и того же материала. Требуется найти оптимальные размеры ящика (без крышки) при заданной его вместимости V.

Обозначим длину, ширину и высоту ящика через х9у и z соответст­ венно. Тогда

V = xyz.

(4.19)

С учетом принятых предположений количество материала, необхо­ димое для изготовления ящика, пропорционально площади всех его сте­ нок, равной W~xy+2yz+2xz. Это выражение служит целевой функцией, подлежащей минимизации.

Подставив в него соотношение z = V/ixy), полученное из формулы (4.19), перепишем целевую функцию в виде функции двух переменных:

W = xy + 2V/x + 2V/y.

Воспользуемся необходимыми условиями экстремума. Для этого запишем систему уравнений вида (4.18) так:

dW/dx = 0; dW/dy = 0.

Вычислим производные: dW/dx = у -2 V /x 2; dW /dy = x - 2 V /y 2. Тогда записанная выше система уравнений примет такой вид:

у ~2V/x2 =0;	х2у = 2V;'
x - 2 V /y 2 = 0 ,\	или
	ху2 = 2V. ,

Решением ее будут выражения: хот = у оит= lf2V . Далее получаем значение

zonT = r/{xm y m ) = v / t f ? v f =

Поделив л:0ггг на zonT, найдем соотношение между стороной и высо­ той ящика: xonT/z om = 2. Таким образом, найденное решение соответствует ящику, имеющему одинаковую длину и ширину, а высоту - вдвое мень­ шую, чем длину.

Убедимся, что полученное решение действительно доставляет ми­ нимум целевой функции. Для этого воспользуемся сформулированными в

п. 4.3.1 достаточными условиями. Вычислим вторые производные целевой функции W\

d2W /dx2 = 4V /x3; d2W/dxdy = \; d2W /dy2 =4V /у 3.

Подставив в эти формулы найденные значения для хот, у от и zom, получим: А=2; В= 1; 0=2. Вычислим D=AC - В2=3. Имеем D >Ои А>0. Сле­ довательно, найденные размеры ящика соответствуют минимальной пло­ щади его поверхности.

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

Действительно же корректной была бы задача оптимального проек­ тирования изделия, исходя из некоторого экономического критерия, с уче­ том прочностных, функциональных и других характеристик.

Сформулированные выше необходимые и достаточные условия экстремума функций лишь в редких случаях удается использовать для ре­ шения практических задач прежде всего из-за сложности решения системы (4.18), которая, как правило, оказывается нелинейной. Чаще здесь исполь­ зуют численные методы, которые описаны ниже (пп. 4.3.2 - 4.3.6).

Будем по-прежнему отыскивать максимум функции и предполагать его единственность, хотя в многомерном случае это предположение зна­ чительно менее вероятно, чем в одномерном.

4.3.2. Метод покоординатного поиска

Иногда этот метод называют методом Гаусса - Зейделя. Согласно данному методу переменные варьируются в ходе исследования поочеред­

но. Вначале задается исходная точка Зс^ =

xj>°\

в которой ста­

вится первый опыт. Затем последовательно изменяются значения только одной переменной, например хь а остальные переменные х2, х3, ...,х пфик­ сируются на своих начальных уровнях x f \

Из поставленных опытов отыскивается наилучший, т. е. тот, для ко­ торого значение у максимально. Соответствующее значение переменной xi фиксируется. В этих условиях последовательно изменяют значения пере­ менной хъ Для опытов этой серии отыскивается и фиксируется ее наилуч­ шее значение. В следующей серии варьируется только х3, если число пере­ менных больше двух, и т. д. до х„. Затем цикл поочередного варьирования переменных проводят заново, начиная с х\. Эта процедура повторяется до тех пор, пока не будет найдена точка, смещение относительно которой варьированием любого фактора приводит только к ухудшению результата. Она принимается за точку оптимума.

Для двумерного случая (п=2) на рис. 4.10 дана геометрическая ин­ терпретация метода. Условия опытов здесь изображены точками на плос­ кости, по координатным осям которой откладываются значения перемен­ ных jci и х2. На этом рисунке нанесены также линии уровня, или линии равного выхода. Для всех точек, лежащих на данной г-й линии уровня, зна­ чение отклика одинаково и равно некоторому значению^,. Условия опытов первой серии изображены точками 1 - 5 . Лучшим среди них оказался чет­ вертый опыт. Соответствующее ему значение переменной х\ сохраняется

Рис. 4.10. Схема метода покоординатного поиска

для всех опытов следующей серии, где варьируется х2 (точки 6 -1 1 ). Здесь лучший опыт - десятый. Затем вновь варьируется переменная х\ и т. д. Всего для достижения области оптимума (точка 19) в данном случае понадобилось пять серий опытов.

Основное достоинство метода заключается в простоте его реализа­ ции. Алгоритм метода предусматривает только вычисления значений целе­ вой функции без использования ее производных. Такие методы называют

прямыми, или методами нулевого порядка. С другой стороны, именно из-за того, что при поиске экстремума по данному методу не используется информация о значениях производной целевой функции, он не относится к числу эффективных. В частности, метод покоординатного поиска работает плохо, если имеет место взаимодействие между какими-либо переменными

и Xj, то есть в выражение для целевой функции входит произведение XfXj.

116

4.3.3. Градиентный метод

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

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

приблизиться к точке оптимума за конечное	число шагов.
Вначале выбирают начальную точку	x f \ .	.	Если в

одномерном случае (см. п. 4.2.6) из нее можно было сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстри­ рующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отно­ шению к точке А (например, направления 1 -3 ), а по другим направлениям приводит к его уменьшению (направления 5 - 5). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в ко­ тором целевая функция возрастает быстрее всего. Это направление назы­ вается градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора

градиента функцииy=f(x\, х2,	хп) являются ее частными производными
по аргументам, т. е.
grad /(:	)= { д у /д х г ,д у /д х 2,..., д у / дхп}.	(4.20)

Таким образом, при поиске максимума по методу градиента на пер­ вой итерации вычисляют составляющие градиента по формулам (4.20) для начальной точки Зс(°) и делают рабочий шаг в найденном направлении, т. е. осуществляется переход в новую точку х^ с координатами:

(4.21)

117

Рис. 4.11. Геометрическая интерпретация понятия градиента функции

Рис. 4.12. Геометрическая интерпретация градиентного метода (двумерный случай)

или в векторной форме

х(1) = х ® + Л grad /(зс^),

где Л- постоянный или переменный параметр, определяющий длину рабо­ чего шага, X > 0. На второй итерации снова вычисляют вектор градиента уже для новой точки xW, после чего по аналогичной формуле переходят в точку *(2) и т. д. (рис. 4.12). Для произвольной к-й итерации имеем

118

(4.22)

Если отыскивается не максимум, а минимум целевой функции, то на каждой итерации делается шаг в направлении, противоположном на­ правлению градиента. Оно называется направлением антиградиента. Вме­ сто формулы (4.22) в этом случае будет

(4.23)

Существует много разновидностей метода градиента, разли­ чающихся выбором рабочего шага. Можно, например, переходить в каж­ дую последующую точку при постоянной величине Я, и тогда длина рабо­ чего шага - расстояние между соседними точками х М и 5с(*+1) - окажется пропорциональной модулю вектора градиента. Можно, наоборот, на каж­ дой итерации выбирать Я таким, чтобы длина рабочего шага оставалась по­ стоянной.

Пример. Требуется найти максимум функции >/ = 110 - 2 ^ - 4)2 - з(*2 - 5)2.

Разумеется, воспользовавшись необходимым условием экстремума, сразу по­ лучим искомое решение: х\=4; Х2=5 . Однако на этом простом примере удобно проде­

монстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

	grad У = {ду/дх,; ду/дх2} = {4(4 - х ,); 6(5 -		)}
и выбираем начальную точку
Значение	целевой функции	для этой точки, как легко		подсчитать,	равно
_у(х^)=3. Положим, yl=const=0,l.		Величина градиента-,	в	точке Зс(°)	равна
grad у (х ^ )= {16;	30}. Тогда на первой итерации получим согласно формулам				(4.21)
координаты точки	:
	дг,(1) = 0 + ОД • 16 = 1,6; X® = 0 + 0,1 • 30 = 3.

Соответствующее значение целевой функции

Как видно, оно существенно больше предыдущего значения. На второй итерации имеем по формулам (4.22):

жр1 = х,(1) + Х-^-

= 1,6+ 0,1 • 4(4 - 1,б) = 2,56;

*(')

119

=3 + 0,1 ’б(5 -3) = 4,2.

дх. *(1>

Для этой точки

= 103,9328

и т. д.

Если непосредственное вычисление производных целевой функции при определении градиента затруднительно, то применяют приближенные численные методы их вычислений. Для этого делают пробные шаги, т. е. вычисляют целевую функцию в дополнительных точках. Так, сделав не­ большой пробный шаг вдоль положительного направления оси хь т. е. пе­ рейдя из точки х М в точку (xW + gej) (рис. 4.13), можно приближенно

оценить первую составляющую градиента функции в точке xW:

ду

+ ge,)~ ;v(*W)]>

дхх*(*) S

где g - величина пробного шага; ej - единичный вектор в направлении оси

х\. По результатам п пробных шагов вдоль каждой из координатных осей аналогичным образом вычисляют все п составляющих градиента целевой функции:

» -[y (x w + ge,)-^(*W )], /=1,2, dxi *(*) 8

Рис. 4.13. Схема приближенного метода вычисления составляющих градиента функции

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

120

4.3.4.Метод наискорейшего подъема

Вслучае поиска минимума его называют методом наискорей­ шего спуска. Он представляет собой разновидность градиентного мето­ да. По этому методу величина X на каждой итерации выбирается такой, чтобы приращение целевой функ­ ции при движении в данном на­ правлении было наибольшим. Лег­ ко показать, что при этой про­ цедуре направление градиента в

	очередной точке 3tW перпендику­
	лярно к направлению его в преды­
	дущей точке	Действитель­
	но, пусть градиент в начальной точ­
Рис. 4.14. Схема метода наискорейшего	ке jc(°) направлен	по лучу /
подъема	(рис. 4.14). Из этой точки выполня­
	ется переход в точку Зс^, для кото­

рой значение целевой функции, равное некоторому числу у и больше, чем в любой другой точке, находящейся на луче /. Отсюда следует, что линия уровня, соответствующая значению у=уи пересечет луч / в единственной точке ЗсМ, то есть будет касаться этого луча. Поскольку’ градиент в точке ЗсМ перпендикулярен к касательной к линии уровня у=у\, то он будет пер­ пендикулярен и к градиенту в точке Зс(°).

Покажем, как на первых двух итерациях будет происходить движе­ ние к экстремуму по методу наискорейшего подъема для целевой функции из предыдущего примера.

Начальную точку оставим прежней: 3f(°) = {О; о}. Координаты следующей точ­

ки х М по результатам первого рабочего шага определим по формулам (4.21):

(1)	(о)	^ - д У	= 16А;
х, ' = X,		+ л---
1	1	д х х х(о)	(4.24)
j4'> = х,(о) +А—			= ЗОЯ.
		дх ~
		Зс(о)

Составим выражение для приращения целевой функции на первом рабочем

Ду, = >-(xW )- у ( х ^ ) = 110	-	2(Ш - 4)2 - 3(30Я - 5)2 - 3 =
= 107 - 32(4Л	-	1)2 - 75(6Л- 1)2.