Output Summary 5 страница

Рассмотрим систему уравнений

/,(Х) = 0,1=1,2,...,т. Пусть X* — некоторая фиксированная точка. Используя разложение Тейлора, имеем /₍(Х) * /,(Х*) + V/,(X^k)(X - X*), i - 1, 2, т.

Следовательно, исходная система уравнений приближенно представима в виде

/,(Х*) + V/,(X')(X - X*) = 0, i = 1, 2.....т.

Эти уравнения можно записать в матричной форме:

А_к + ВДХ-Х*) = 0.

Предположим, что векторы /,(Х) независимы, тогда матрица В, является невырож­денной. В результате из предыдущего уравнения получим

х = х'-в;Ч,.

Идея метода Ньютона-Рафсона состоит в следующем. На первом шаге выбирается начальная точка Х°. С помощью полученного уравнения по известной точке X* можно вычислить координаты новой точки X**¹. Процесс вычислений завершается в точке X", которая считается приближенным решением исходной системы, если X^m» X""¹.

20.1. Экстремальные задачи без ограничений

Геометрическая интерпретация данного метода для функции одной переменной f(x) приведена на рис. 20.3. Связь между точками х^к и х^к+1 в этом случае выражается формулой

или

Рис. 20,3. Итерационный процесс в методе Нъютона-Рафсона

На рис. 20.3 видно, что положение точки х^к+1 определяется углом 0 наклона ка­сательной к графику функции f(x) в точке х^к, где tg0= fix").

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

Пример 20.1.3

Для демонстрации работы метода Ньютона-Рафсона рассмотрим задачу нахожде­ния стационарных точек функции

f{x) = (Зх - 2?(2х - З)².

Чтобы найти стационарные точки, надо решить уравнение f'(x) = 0, которое в дан­ном случае принимает вид кубического уравнения

72х³ - 234л:² + 241х - 78 = 0.

Глава 20. Классическая теория оптимизации j

Шаблон Excel ch20NewtonRaphson.xls методом Ньютона-Рафсона может решить лю­бое уравнение с одной переменной. На рис. 20.4 показано решение в этом шаблоне уравнения данного примера. Чтобы найти это решение, надо в ячейку СЗ ввести следующее выражение, заменив переменную х ссылкой на ячейку A3.

72л³ - 234л:² + 24 Ьс -78 216х²-468*+ 241

Отметим, что числитель этого выражения является формулой для вычисления пер­вой производной функции f(x), а знаменатель — формулой второй производной, что и требуется для метода Ньютона-Рафсона при решении уравнения f'(x) = 0. Пе­ред началом вычислений также задается предел точности А (= 0,001) и начальное значение х₀ (= 10). Если разность между значениями х^ь и X^м будет меньше предела точности, то процесс вычислений завершается. В данном примере метод сошелся к значению х = 1,5.

	А		С
	Newton-Raphson (One-Variable) Method
	Input data: Type f(A3)/f '(A3) in C3. where A3 represents x In f(x)
		#3HA4!
	д =	0.0001
	Initial x0=	ю
	Solution: (excel	i Si' te It if =eiertpd *0 rai
	x* =	1.50000]
	Calculations:	ш	rforroc*icui"
		x(k+1)	f(x(k))/f '(x(k))
	10.000000	7 032108	2 967892314
	7.032108	5 055679	1.97642875
	5.055679	3.741312	1.314367243
13.	3.741312	2.869954	0.871358025
	2.869954	2.296406	0.573547408
	2.296406	1.925154]	0.371251989
	1.925154	1 694452	0.230702166
	1.694452	1.565453
	1 565453	1 511296	0.054156405
	1 511296	1.500432	0 010864068
	1 500432	1 500001	0 000431385
21, 1.500001	1.500000	6 70394E-07

Рис. 20.4. Решение алгебраического уравнения методом Ньютона-Рафсона

На самом деле наша функция f(x) имеет три стационарные точки х = 2/3, х = 13/12 и х = 3/2. Оставшиеся две стационарные точки можно найти, если задать соответ­ствующие начальные значения, например, л:₀ = 0,5 и х₀= 1. В общем случае надо сделать несколько попыток решения задачи методом Ньютона-Рафсона при раз­личных начальных значениях, чтобы отыскать все корни уравнения. В данном примере нам "повезло" — мы знаем, что наше уравнение имеет три корня. Однако в случае сложных уравнений или уравнений, зависящих от нескольких перемен­ных, как правило неизвестно ни количество корней, ни их местоположение.

20.2. Задачи на экстремум при наличии ограничений

УПРАЖНЕНИЕ 20.1.2

1. Примените метод Ньютона-Рафсона для решения упражнений 20.1.1.1, с и 20.1.1.2, Ъ.

20.2. ЗАДАЧИ НА ЭКСТРЕМУМ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

В настоящем разделе рассматриваются задачи поиска экстремумов непрерывных функций при наличии ограничений на переменные. В разделе 20.2.1 рассматривается ситуация, когда дополнительные ограничения имеют вид равенств, а в разделе 20.2.2 — неравенств. Основная часть материала раздела 20.2.1 изложена в соответствии с [2].

20.2.1. Ограничения в виде равенств

В данном разделе рассматривается два метода решения оптимизационных задач при наличии ограничений в виде равенств: метод Якоби и метод Лагранжа. Метод Лагранжа можно логически получить из метода Якоби. Эта связь позволяет дать интересную экономическую интерпретацию метода множителей Лагранжа.

Метод приведенного градиента (метод Якоби). Рассмотрим задачу

минимизировать z = /(X)

при ограничениях

g(X) = 0,

где

X = (Xj, х₂, х_п),

S (.§!> &2> *

Функции /(X) и g,(X), t= 1, 2, т, предполагаются дважды непрерывно диффе­ренцируемыми.

Идея использования приведенного градиента заключается в том, чтобы найти замкнутое аналитическое выражение для первых частных производных функции /(X) во всех точках, удовлетворяющих ограничениям g(X) = 0. Соответствующие стационарные точки определяются из условия равенства нулю указанных частных производных. Затем можно использовать достаточные условия, сформулированные в разделе 20.1, для классификации найденных стационарных точек.

Для пояснения изложенной идеи рассмотрим функцию f(x_v х₂), график которой представлен на рис. 20.5. Предположим, что эту функцию необходимо минимизи­ровать при ограничении

g,(*i> х₂) = х_г - Ь = 0,

где Ь — некоторая константа. На рис. 20.5 видно, что кривая, которая проходит через точки А, В и С, состоит из значений функции f(x,, х₂), для которых заданное ограничение выполнено. В соответствии с рассматриваемым методом определяются компоненты приведенного градиента функции f(x_lt х₂) в каждой точке кривой ABC. Точка В, в которой приведенная производная обращается в нуль, является стацио­нарной для рассматриваемой задачи с ограничением.

Теперь рассмотрим общую математическую формулировку метода. Из теоремы Тейлора следует, что для точек X + АХ из окрестности точки X имеем

/(х+дх)-/(х) = у/-(х)дх+о(дх²),

g(X + AX)-_g(X) = Vg(X)AX + 0(Ax²).

Глава 20. Классическая теория оптимизации

Лх_{,х₂)

/ J / 1 1 1 \ 1 \ \	\ \ х\ \ \ •: 1 ч в У7\
х2	----^ \ х2 = ь Линия минимального значения целевой функции

Рис. 20.5. Иллюстрация к методу Якоби

При Д#. -» 0 эти уравнения принимают вид

6/(X) = V/(X)c5X,

dg(X) = v_g(X)sx.

Поскольку g(X) = 0, 9g(X) = 0 в допустимой области. Отсюда следует, что

о/(Х) - V/(X)3X = 0,

vg(x>ax = o.

Как видим, задача сводится к решению т + 1 уравнений с п + 1 неизвестными, ко­торыми являются 9/(Х) и ЭХ. Неизвестную величину Э/(Х) можно определить, как только будет найден вектор ЭХ. Это означает, что, по существу, имеется т уравне­ний с п неизвестными.

При т > п по меньшей мере т- п уравнений системы являются избыточными. После устранения избыточности количество независимых уравнений в системе ста­новится равным т (< п). Если т = п, решением является ЭХ = 0. При этом точка X не имеет допустимой окрестности, и, следовательно, пространство решений задачи состоит из единственной точки. Такая ситуация является тривиальной. Ситуацию, когдат<п, рассмотрим подробно.

Пусть X = (Y, Z), где

Y = (j/p у_г,...,y_m)nZ = (z₁,z₂,...,z_n__m)

20.2. Задачи на экстремум при наличии ограничений

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

v/(y, z) - (v_y/, v_z/), Vg(y, z) = (V_Yg, V_zg). Введем в рассмотрение матрицы

fv_Yg, ] J=v_Yg=;,

c = v_zg =

Матрица J_mXm называется матрицей Якоби, a C_mX((1__m) — матрицей управления. Мат­рица Якоби J предполагается невырожденной. Это всегда можно обеспечить, по­скольку рассматриваемые т уравнений являются независимыми по определению. Поэтому компоненты вектора y можно выбрать среди компонентов вектора x та­ким образом, что матрица J окажется невырожденной.

Исходную систему уравнений с неизвестными 9/(Х) и ЭХ можно переписать в следующем виде

a/(y, Z) = v_Y/r3Y + v_z/dZ, JoY = -CdZ.

Так как матрица J невырожденная, существует обратная матрица J^-1. Следова­тельно,

sy = - j'caz.

Подставляя это выражение oY в уравнение для 9/(y, Z), можно выразить df через 9Z в следующем виде

a/(y, Z) = (V_zf-V_YfJ¹C)dZ.

Из этого уравнения получаем формулу для производных функции f по вектору не­зависимых переменных Z

v_£/ =

g_c/(Y,Z)

= v_z/-v_y/j-'c,

где VJ представляет вектор приведенного градиента функции / по z. Следователь­но, вектор v_c/(y,z) должен обращаться в нуль в стационарных точках.

Достаточные условия экстремума в стационарной точке аналогичны изложен­ным в разделе 20.1. В этом случае элементы матрицы Гессе будут соответствовать компонентам вектора независимых переменных z. Между тем элементы матрицы Гессе должны быть приведенными вторыми производными. Чтобы показать, как они вычисляются, положим

v_e/ = v_z/-wc.

Глава 20. Классическая теория оптимизации

Отсюда следует, что i-й строкой приведенной матрицы Гессе является вектор dV_cf/dz_t. Заметим, что W — функция от Y, a Y, в свою очередь, — функция от Z. Следовательно, при вычислении частной производной V_c/ по z_t следует применять правило дифференцирования сложной функции, а именно

d\Vj d\Vj by _s dz_t by_j 8z,

Пример 20.2.1

Рассмотрим следующую задачу.

f(X) = xf+3x²₂+5_Xlxl,

g, (X) = х,х₃ + 2x₂ + xj -11 = 0,

g₂ (X) = x,² + 2x,x₂ + xl -14 = 0.

Известна допустимая точка X° = (1, 2, 3). Требуется оценить приращение функции/ (= 3J) в допустимой окрестности точки Х°.

Пусть Y = (х_рх₃) и Z = х₂. Имеем

/б/ б/"

V_Y/ =

= (2x_t+5x²,\0x_lx,),

V_z/ = #- = 6x_2> ox,

J =

C =

	Их,
(d8<)
Bx2
{dx2j

_y2x_{+2x₂ 2х_ъ)

Оценка приращения д/ в окрестности допустимой точки X =(1, 2, 3), вызванного малым изменением 8х₂ = 0,01, получается следующим образом:

J-'C =

6 6

' _6_	1 ^
, 12	12,
	(2,83 4
	"1-2,50,

Следовательно, приращение функции/с учетом ограничений равно

3J=(V_Z/-V_Y/J-'C)0Z =

6x2-(47,30)

'2,83^s ,-2.5, дх₂ =-46,01&₂.

20.2. Задачи на экстремум при наличии ограничений

Если указана величина изменения дх₂ независимой переменной х₂, то допустимые значения дх_х и 8х₃ зависимых переменных х_х и х₃ определяются по формуле

з\ = -г'сэг.

При дх₂ = 0,01 получаем

(сЬсЛ _т. (-0,0283^1

= -J Сох, =

дх-

1, 0,0250)

Чтобы проверить точность полученной выше оценки для д/, можно вычислить зна­чения функции/в точках Х° и Х° + ЭХ. Получаем

Х° + ЭХ = (1 - 0,0283, 2 + 0,01, 3 + 0,025) = (0,9717, 2,01, 3,025).

Отсюда следует, что

ДХ) = 58 иДХ° + ЭХ) = 57,523

или

Й/=ЛХ° + ЭХ) -ДХ°) = -0,477.

Полученный результат свидетельствует об уменьшении значения функции / по сравнению с вычисленным выше в соответствии с формулой для Э</. Это различие между двумя полученными результатами (-0,477 и -0,4601) является следствием линейной аппроксимации в окрестности точки Х°. Поэтому приведенная выше фор­мула дает хорошие результаты лишь тогда, когда отклонения от точки X^е малы.

УПРАЖНЕНИЕ 20.2.1

1. Вернитесь к задаче из примера 20.2.1.

a) Вычислите величину 8J двумя способами, как это было проделано в при­мере, используя дх₂ = 0,001 вместо дх₂ = 0,01. Будет ли влияние линейной аппроксимации менее существенным при уменьшении величины Эдг₂?

b) Установите зависимость между приращениями dx_v дх₂ и дх₃ в допустимой точке Х° = (1,2,3) при условии, что точка (дг" + дх,,х₂ +8х₂,х, + 8х_}) также является допустимой.

c) Если Y= (х₂, х₃) и Z = дг,, то каким должно быть значение dx_v чтобы вели­чина приращения dj была такая же, как в рассмотренном примере?

Пример 20.2.2

Данный пример иллюстрирует процедуру использования метода приведенного гра­диента. Рассмотрим задачу

минимизировать /(X) = х\ + х\ + дг,

при ограничениях

g₁(X) = x₁+x₂ + 3x₃-2 = 0, Я₂(Х) = 5х₁ + 2дг₂+х₃-5 = 0.

Глава 20. Классическая теория оптимизации

Определяем экстремальные точки целевой функции при наличии ограничений сле­дующим образом. Пусть Y = (х,, х₂) и Z = х₃. Тогда

V_Y/ =

= (2дг„2х₂), 4J = $- = 2x_v

ох.

J =

1 п

_ч5 2,

J =

(2 3 5 3 3

~ъ)

Следовательно,

V_c/ =!^ = 2a-,-(2x„2x₂)

д_сх,

(2 3 5 V 3

0;

Ю 28. --—х,-—х_г + 2х_ъ.

В стационарной точке выполняется равенствоУ/= 0, которое вместе с ограниче­ниями g,(X) = 0 и g₂(X) = 0 определяет искомую стационарную точку (или точки). В данном случае система уравнений

V/=0, £,(Х) = 0, &(Х) = О,

'10	-28	6'	V		'0У
			хг	=
v 5					Л

имеет решение Х°»(0,81, 0,35, 0,28).

Далее устанавливаем тип полученной стационарной точки путем проверки выпол­нения достаточных условий экстремума. Так как х₃ — независимая переменная, из равенства \7/= 0 следует, что

3.7		dx,		dx2
дсх]	" 3	[dx,j		[dxj

+ 2 =

10 28

dx, dx₂ + 2.

В соответствии с методом Якоби получаем

(dxA		' £N
dx, dx2	= -j'C =
		, 3,

Теперь путем подстановки находим, что d²J 460 д,х\ 9 > 0. Следовательно, X — точка

минимума.

20.2. Задачи на экстремум при наличии ограничений

Анализ чувствительности с помощью метода Якоби. Метод Якоби можно использо­вать для анализа чувствительности оптимального значения целевой функции / к малым изменениям правых частей ограничений оптимизационной задачи. В частности, можно определить, как повлияет на оптимальное значение функции / замена ограничения g,(X) = О на g,(X) = dg_r Исследование такого типа именуется анализом чувствительности и в некотором смысле аналогично соответствующей процедуре, которая была рассмот­рена в линейном программировании (глава 4). Следует однако заметить, что анализ чувствительности в нелинейном программировании приводит к результатам, спра­ведливым лишь в малой окрестности экстремальной точки. Знакомство с такими процедурами будет полезно при изучении метода множителей Лагранжа.

Выше было показано, что

адт, z> = v_Y/dY + v_z/az,

dg = JSY + CdZ.

Предположим, что dg * 0, тогда

бт = J"'ag- jt'c az.

Подставляя последнее выражение в уравнение для 3/(Y, Z), получаем

o/(Y,z) = v_Y/i-'ag+v_c/az,

где V_c/ = V₂./ -V_Y/J~'C, как было определено ранее. Полученное выражение для a/(Y, Z) можно использовать при анализе изменений целевой функции f в малой окрестности допустимой точки Х°, обусловленных малыми изменениями dg и дЪ.

В экстремальной (фактически любой стационарной) точке Х₀ = (Y₀, Z₀) приве­денный градиент V_c/ должен быть равен нулю. Следовательно, в точке Х₀ имеем

a/-(Y₀,z₀)=v_Yn/j-'ag(Y₀,z₀)

или

dg ^Y'^J

вычисленному в точке Х₀. Это значит, что влияние малых изменений dg на опти­мальное значение функции / можно оценить через скорость изменения функции / по отношению к изменениям g. Эти величины принято называть коэффициентами чувствительности.

Пример 20.2.3

Рассмотрим задачу из примера 20.2.2. Оптимальной точкой является X₀=(x,V₂V₃°) = (0,81, 0,35, 0,28). Так как Y₀ = (х°,х°₂), то

^Vv„/ =

'ид

_чйх,'йх₂,

= (2jc,°,2x₂) = (1,62, 0,70).

Следовательно,

= V_Yo/J-'=(1,62,0,7)

(2 I)

3 3

5 _ 1

3 3,

= (0,0876,0,3067).

Глава 20. Классическая теория оптимизации

Это свидетельствует о том, что изменение dg_x = 1 приводит к увеличению значения целевой функции / приблизительно на 0,0867. Аналогично при dg₂ = 1 имеет место увеличение значения/приблизительно на 0,3067.

Использование метода Якоби в задачах линейного программирования. Рас­смотрим задачу линейного программирования.

Максимизировать г — 2л:, + Зх_г

при ограничениях

х_х -Ь х₂ ~Ь х₃ ⁼ 5, х_г — х₂ + x_t = 3,

^3' ^4 — ^'

Для каждого условия неотрицательности x_f > 0 введем соответствующую (неотрицательную) дополнительную переменную w². Таким образом, дг, - w² = 0

или Xj = w². При такой замене условия неотрицательности становятся неявными,

и исходная задача принимает вид

максимизировать z = 2w² + 3w₂

при ограничениях

w, + ve, + w, = 5,

= 3.

Для метода Якоби положим Y = (u>,, w₂) и Z = (u>₃, ц>₄). (В терминологии линейного программирования векторы Y и Z образованы базисными и небазисными перемен­ными соответственно.) Следовательно,

J =

(2w, 2w₇}

J-' =

J__1_

4ve, 4vv,

J__-1_

4vv, 4ve,

w, и W, * 0,

так что

'2w, 0 ⁴ 4 ⁰ 2w₄,,V_Y/ = (4w„6w₂),V_z/ = (0,0),

V_c/ = (0,0)-(4w„6w₂)

4vv, 4vv,

4ve₂ 4w₂,

2w, 0 0 2w₄ =(-5w₃,w₄).

Решение системы уравнений, состоящей из уравнения V/ = 0 и ограничений зада­чи, позволяет определить стационарную точку w₁ = 2, w₂=l, w₃ = 0, w₄ = 0. При этом матрица Гессе имеет вид

20.2. Задачи на экстремум при наличии ограничений

' 57
	6>35rw4		'-5
Aw3acw4

Поскольку H_c является неопределенной матрицей, стационарная точка не будет точкой максимума.

На самом деле полученный результат не является неожиданным, поскольку (небазисные) переменные w₃ и ш₄ (и, следовательно, х₃ и х₄) равняются нулю, как и предусмотрено теорией линейного программирования. Следовательно, решение, полученное с помощью метода Якоби, определяет ту или иную крайнюю точку про­странства допустимых решений рассматриваемой задачи, которая связана с кон­кретным выбором векторов Y и Z. При этом найденное решение может как быть, так и не быть оптимальным. Однако метод Якоби позволяет распознать оптималь­ное решение задачи путем использования достаточных условий экстремума.

Приведенные рассуждения свидетельствуют о том, что для оптимального реше­ния задачи линейного программирования необходимо менять конкретный выбор Y и Z, пока не будут выполнены достаточные условия. Пусть, например, Y = (w₂, w_t) и Z = (ц>,, w₃). Тогда соответствующий приведенный градиент принимает вид

V,/ = (4w_p0)-(6w₂,0)

I

2ve₂ l

2w.

о

2w.

(2w, 2w,

2ve₃ 0 =(-2w_p6w₃).

Соответствующая стационарная точка определяется значениями w_l = О, w₂ w₃ = 0, w_t=J&. Так как матрица

-2 0}

-Л,

Н =

0 -6)

является отрицательно определенной, то указанная точка — точка максимума.

Полученный результат можно проверить графически, используя рис. 20.6. Пер­вое из найденных решений (дс, = 4, х_г = 1) не является оптимальным, в то время как второе (jc, = 0, х₂ = 5) оказывается таковым. Читатель имеет возможность прове­рить, что две оставшиеся крайние точки пространства допустимых решений не яв­ляются точками максимума. Кроме того, с использованием достаточных условий экстремума можно показать, что в точке x_t — 0, х_г = 0 возникает минимум целевой функции рассматриваемой задачи.

Заметим, что введенные ранее коэффициенты чувствительности V_Yj/J"' в задаче

линейного программирования являются переменными двойственной задачи. Чтобы проиллюстрировать это на рассматриваемом численном примере, обозначим через и, и и₂ соответствующие переменные двойственной задачи. В оптимальной точке w₁ = 0, w₂ = VJ, w₃ = 0, w₄ = -To" переменные двойственной задачи вычисляются по формуле

(«„«₂) = V_Yr'=(6w_2;0)

1

2w,

^2w₄ 2w₄

=(з.о).

Глава 20. Классическая теория оптимизации

Рис. 20.6. Пространство решений задачи ЛП

В точке (3, О) целевая функция двойственной задачи равна 5и, + Зи_г = 15 и совпадает с оптимальным значением целевой функции прямой задачи. Полу­ченное решение также удовлетворяет ограничениям двойственной задачи, т.е. является допустимым и, следовательно, оптимальным. Это значит, что коэффи­циенты чувствительности совпадают с переменными двойственной задачи линейного программирования.

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

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

УПРАЖНЕНИЯ 20.2.2

1. Предположим, что задача из примера 20.2.2 решена следующим образом. Сначала из ограничений задачи выражаем переменные дс, и х_г через дс₃; затем используем полученные соотношения для представления целевой функции в зависимости лишь от переменной х₃. Дифференцируя полученную целевую функцию по х₃, находим точки минимума и максимума.

¹ Формальное доказательство справедливости этих утверждений для общей задачи ли­нейного программирования можно найти в статье Taha Н. and Curry G. "Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs", Operations Research, Vol. 19, 1971, pp.1045-1049. В этой статье показано, что все основные положения симплекс-метода могут быть получены с помощью метода Якоби.