pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

Можно найти значение Я, для которого это приращение максимально. Для это­ го возьмем производную по Я от найденного выражения для Ду, и приравняем ее нулю.

Результат решения полученного уравнения: Я = 0,18. Подставив это значение Я в фор­

мулу (4.24), найдем координаты точки jcf1^=2,88; дг^ =5,4. Значение целевой

функции для этой точки равно >»(зс^1^)= 107,0112 (сравните с значением у (* Щ в пре­

дыдущем примере).

Для второй итерации рассчитаем координаты точки х ^ :

	) + я^		= 2,88 + X - 4(4 - 2,88) = 2,88 + 4,48Л,
		х(')
*(*>=*(•) + il L			= 5,4 + X ■б(5 - 5,4) = 5,4 -	2,41
2	2	д х2 хМ
На этом шаге	выражение		для приращения целевой	функции имеет вид
дУ2 = ^ (2)) - у(х'tI))= 1110 - 2(2,88 + 4,481 - 4)2 - 3(5,4 - 2,4Я -				5)2 - 107,0112 .
Решив уравнение		5Ду2/дЯ = 0, получим Я «0,225. Поэтому на второй ите­
рации приходим в точку

х,(2) = 2,88 + 4,48 • 0,225 = 3,888; х<2) = 5,4 - 2,4 • 0,225 = 4,86.

Для нее легко подсчитать значение целевой функции: у= 109,916, что близко к

оптимальному значению, равному 110.

4.3.5. Методы случайного поиска

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

Приведем несколько алгоритмов случайного поиска.

1.Поиск с линейной тактикой. Пусть выбрано исходное значение

вектора переменных х® = дс^, Рассмотрим единичный слу­

чайный вектор 4, т* е. вектор единичной длины, компоненты которого

случайные числа: ^ = В данном случае составляющие векто­

ра \ равномерно распределены по всем направлениям пространства пере­ менных (для получения случайных чисел на ЭВМ имеются специальные подпрограммы, см. главу 8).

На первом этапе выполняется рабочий шаг в случайном на­ правлении:

122
ЗсО) = Зс(°) + ДхО) = Зс(°) +		(4.25)
где Ах(1) - вектор смещения переменных,	= {Ах^\ Длг^, ..., Ajc^);

а - выбранная заранее длина рабочего шага.

Векторная запись (4.25) эквивалентна, очевидно, следующей записи по компонентам:

= + м , 2 ...... ».

Дальнейшая стратегия определяется тем, удачен или неудачен сде­ ланный шаг. Если :к(зё^)>>{зс^), шаг удачен, то следующий шаг делается

в том же направлении, что и предыдущий, т. е. х&) = 3tW + Ах^2\ где

А3с(2) = AxW. Если >»(зс^)<_у(зс^^), шаг неудачен, то из состояния х М снова

делается случайный шаг: х ^ =	.
Аналогично, на к-м этапе вектор смещения переменных равен
a*m , [ ^ « л	» у (г<*-'>)>Л*<м ) );
j а^9если	у(зс^~2))

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

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

Для данного метода

А х ^ ]\е с т у { х {к-]))> у{х^ -2))

	Ах(*) = -Л х(ы ) + 4	(*) приДЗс(*-|>= ДЗс(*-2)	если	< у(х(к~2)).
	-	при Д*<ы ) * ДЗс<*-2>

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

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

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

3. Поиск с парными пробами. В данном алгоритме на каждом эта­ пе делается два пробных шага. Допустим, что после (&-1)-го этапа состоя­ ние объекта определяется вектором Тогда первый пробный шаг на к-м этапе переводит объект в состояние яК*-1) + g%, где g>0 - длина проб­ ного шага. В полученной точке вычисляется значение целевой функции

+ g£;). Затем рассматривается состояние	для которого
также вычисляется значение целевой функции y	( j - g^). Далее делает­

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

Зс (*) =	+ ДЗсМj
где

Дх(4) = аЁ,sgn[y(x(*_l) + g t)~ у{х(к-Х) -

а функция ;/=sgn t определяется следующим образом: +1, если t > 0;

у = sgn t = -< 0, если t = 0; -1, если / < 0.

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

4. Алгоритм с возвратом при неудачном шаге. Здесь из очеред­ ной точки делается случайный шаг ДЗс^) = а \. Если значение целе­

вой функции в полученной точке х W = Зс(*-1) + АЗсМ оказалось лучше, чем в предыдущей: 1у(зс^^)>>у(зс^"1^), то следующий случайный шаг делается

из новой точки 5с W. Если же шаг оказался неудачным, т. е. у(3с^))<7(3с^_1)), то следующий шаг в случайном направлении делается из

старой точки .

4.3.6. О методах поиска глобального экстремума функций

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

Рис. 4.15. Геометрическая интерпретация поиска глобального экстремума функции

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

будет точка 0 2, то поиск закончится в точке В. Стрелки, выходящие из то­ чек 0\ и 0 2, указывают направления градиента функции в этих точках. Это указывает на возможность модернизации рассмотренных методов поиска, с тем, чтобы приспособить их для отыскания глобального экстремума мно­ гоэкстремальных функций. Для этого можно рекомендовать повторение процедуры поиска несколько раз из различных исходных точек. Получен­ ные значения локальных экстремумов сравниваются между собой, и из них выбирается наибольшее (при поиске глобального максимума). Для выбора положений исходных точек может использоваться как случайная, так и де­ терминированная процедура.

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

целевой функции y = f	(хь х2,	хп) задан диапазон его изменения:
ximin < xi < *tmax, г-1, 2,	..., п. В пространстве переменных хь x2i		сис­

теме этих неравенств соответствует многомерный параллелепипед, яв­ ляющийся областью допустимых значений аргументов целевой функции. Для случая функции двух переменных y= f(x ь х2) имеем прямоугольник (рис. 4.16). Диапазон [(^ min---^ max)] изменения каждой переменной разби­ вается на достаточно большое число т( равных отрезков. Это число вы­ бирают, исходя из заданной точности отыскания точки экстремума. В ре­ зультате в области допустимых значений выделяется конечное число то­ чек. Для каждой из них вычисляется значение целевой функции, а из полу­ ченного множества этих значений выбирается максимальное (или минимальное).

125

2 max

1 max

Рис. 4.16. Схема метода глобального перебора

Практически этот метод применим только при числе переменных целевой функции не больше 3 - 4 из-за того, что его трудоемкость быстро возрастает с ростом размерности задачи. В самом деле, пусть заданная точность решения задачи будет достигнута, если на каждом отрезке [xt min, %i max] взять 10 равноотстоящих точек. Тогда для отыскания экстремума функции двух переменных надо вычислить ее значения в 100 точках, яв­ ляющихся узлами полученной сетки. Для функции трех переменных по­ требуется уже 103= 1000 ее вычислений и т. д.

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

4.4. Методы нелинейного программирования

4.4.1.Особенности задач нелинейного программирования

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

Такой случай иллюстрируется рис. 4.17, на котором изображены линии уровня максимизируемой целевой функции и область допустимых реше­ ний задачи, ограниченная многоугольником ABCD. В точке В функция достигает локального, а в точке D глобального максимума на множестве допустимых значений.

Рис. 4.17. Геометрическая интерпретация особенностей задач нелинейного программирования

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

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

Методы нелинейного программирования рассчитаны на при­ менение ЭВМ, причем используемые программы, как правило, достаточно громоздки из-за сложности алгоритмов.

4.4.2. Необходимые условия экстремума функций с ограничениями-равенствами.

Метод множителей Лагранжа

Рассмотрим задачу нелинейного программирования с ограничения­ ми-равенствами:

min (max);	(4.26)
%-(xl9...9xn)=bj9 y-1, 2,..., m.	(4.27)

Необходимые условия экстремума функции (4.26) при ограничени­ ях (4.27) даются методом множителей Лагранжа и записываются следую­ щим образом:

т
дф/дх1= а / / дх, - £ XJдер / дх, =0, i = 1,..., п;		(4.28)
М	[
ЭФ/dXj =bj -<?J(xl,...,x n) = 0,	7 = 1,..., т,

где функция

<I>{xx,...,x n,l\,...,X m) = f(x A,...,x n)+ Y JXJ{bj -<?J{xi,...,xn^ (4.29)

называется функцией Лагранжа; Яь ..., Лт- множители Лагранжа.

Согласно методу множителей Лагранжа задача оптимизации (4.26), (4.27) решается в следующей последовательности:

1)составляется функция Лагранжа (4.29);

2)отыскиваются ее частные производные по переменным х\9x2f хпи по Х\9Я2, . . Лт9которые приравниваются к нулю;

3)в результате получается система (4.28) из (п + т) уравнений, ко­ торую следует решить. Среди решений этой системы содержатся искомые точки экстремума функции (4.26), удовлетворяющие ограничениям (4.27).

При непосредственном применении метода множителей Лагранжа для решения практических задач оптимизации часто возникают трудности, связанные прежде всего с решением системы (4.28).

Для задач нелинейного программирования с ограниченияминеравенствами также получены необходимые условия экстремума [30]. С использованием этих условий разработан простой алгоритм, являющийся вариантом симплекс-метода, для решения одного специального типа задач нелинейного программирования. Это задачи, в которых минимизируемая целевая функция является квадратичной, т. е. имеет вид

W = f tcixi + f t d.jx.xj ,

i=1 1,7=1 i*j

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

Функция f ( x ) называется выпуклой функцией в выпуклой области

G, если для любых двух точек Зс^ и х из G выполняется отношение

/[ЛЗсО) + (1 - Х)хЩ < А/(Зс(0) + (1 - Х )/(хЩ где 0 < Л< 1.

Задача минимизации выпуклой функции W = f(x ) при ограничени­ ях срДЗс)<0 (у=1, ..., т) и х > 0 , где фу(х) - тоже выпуклые функции, на­

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

В деревообработке оптимизационную модель иногда строят по ре­ зультатам экспериментальных исследований и формулируют в виде задачи минимизации квадратичной функции при простых ограничениях x/min < xt < ximax, / = 1, ..., п. Поскольку целевая функция здесь не обяза­

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

4.4.3. Методы линейной аппроксимации

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

заменяют членами первого порядка в разложении ее в ряд Тейлора в окре­ стности исходной точки xjM):

Рис. 4.18. Схема метода линейной аппроксимации для одномерного случая

129

Это эквивалентно тому, что функция аппроксимируется уравнением плос­ кости, касательной к ней в точке [х\° \..., *(°)). На рис. 4.18 приведен при­

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

4.4.4. Методы штрафных функций

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

Пример. Пусть требуется минимизировать функцию двух переменных

W = f{ x ], х2) = х* +3*2	min		(4.30)
при ограничении типа равенства
х\ + 4*2 +3 =0.			(4.31)
Вместо этой задачи рассмотрим задачу безусловной минимизации для функции
, х2) = х\ + Зх* + £(*i + 4х2 + З)2		min,	(4.32)

где к - некоторое достаточно большое положительное число. Функцию Р(х\, хг) назы­

вают штрафной функцией. Из выражения (4.32) видно, что она включает в качестве слагаемых целевую функцию (4.30) исходной задачи и квадрат функции из ограниче­ ния (4.31). Поэтому несоблюдение данного ограничения приводит к увеличению значе­ ния штрафной функции - своего рода штрафу. Следовательно, достижению минимума функции Р(х 1, х2) способствуют как минимизация целевой функции (4.30), так и более строгое выполнение ограничения (4.31). Тем не менее, точка минимума функции Р(хь х{) не совпадает с решением задачи (4.30), (4.31).

Для доказательства решим каждую из этих задач. Для отыскания решения за­ дачи (4.30), (4.31) выразим х\ из ограничения (4.31) и подставим найденное выражение в (4.30). Получим задачу 19x1 + 24х2 + 9 -> min . Приравняв производную по х2 от этой

функции к нулю, найдем х2от = -12/19. А из равенства (4.31) получим х1опт = -9 /1 9 .

(Использованный здесь метод подстановки иногда применяется при решении задач не­ линейного программирования с ограничениями-равенствами.)

Для решения задачи безусловной минимизации (4.32) продифференцируем функцию Р(х I, х2) последовательно по х\ и х2 и приравняем к нулю найденные произ­

водные. Получим систему уравнений:

х{(l + к) + 4кх2 = -3&;

4кх, + * 2(з + 16*)=-12А.

Решением ее являются значения х1огп = - 9/(3/к + 19); х 2ат = -12/(3/£ + 19). Отсюда

видно, что при любом к решения задачи минимизации с ограничениями (4.30) и (4.31) и задачи безусловной минимизации (4.32) не совпадают. Однако в пределе при к -> °о

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

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

W = f(x l,...,x n)->mm;	(4.33)
Фj(xx,...,x n)<bj,	(4.34)

Обозначим через а число а* = шах {а, 0}, т. е.

а, если а > 0;

0, если а < 0.

Введем в рассмотрение функцию

ф (х)=ф (х1,...,дг„)=|;[(фу(д:1,...,х п) - 6 >)+]4.

М

Выражение [ с р Д ^ , хп)~ bj]+ возведено в четвертую степень, чтобы сделать его достаточно гладким. Очевидно, что Ф(3с)>0, причем ф(3с)=0 тогда и только тогда, когда (pj (x],...,x 2)<bj для всех j= 1, ..., т, то есть

при выполнении всех ограничений.

Рассмотрим задачу безусловной минимизации для штрафной функ­ ции Р(х],...,х п) = f(x v . . . , х л)+ £0(*j,. . . , хп). Можно показать, что после­

довательность решений этой задачи сводится к решению задачи (4.33), (4.34) при к -> оо. Это позволяет вместо задачи (4.33), (4.34) решить при некотором большом значении к задачу

/( х и . . .

, х „ ) + к Ф ( х min.

(4.35)

На практике обычно поступают следующим образом. Задаются ма­ лым числом е > 0, характеризующим допустимую степень невыполнения