На каждой итерации метода наискорейшего спуска необходимо решать задачу (7.149), например методом золотого сечения ..

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

Методы штрафных функций. Эти методы позволяют свести задачу нелинейного программирования (7.143) - (7.144) точно или приближенно к задаче на безусловный экстремум, т. е. к минимизации (максимизации) некоторой функции, представляющей сумму минимизируемой (максимизируемой) .функции и некоторой функции невязок в ограничениях задачи. Метод штрафных функций впервые был предложен Курантом в 1943 г. для решения некоторых задач математической физики.

Исходя из задачи (7.143) - (7.144) строится функция

F{X,s) +S{h{X),...,fm{X),s), (7.150)

где S ~ {St}j-вектор управляющих параметров; S - функция

чгт ja (вещественная), действие которой реализуется вектором s. функция штрафа должна обладать свойством

lim S{h{X),...,fm(X)rs) =\f< Ifn;

l-l-oo - в противном случае.

g.->-oo

г=1, т

Идея метода штрафных функций сводится к минимизации функции F {X, s) вместо решения задачи (7.143) - (7.144). Штрафные функции могут быть заданы в различном виде, определены - на всем пространстве, но в области допустимых решений они равны нулю, вне этой области положительны и возрастают при

fi(X)-oo, i=l,m.

Примером функции штрафа может быть функция

S{f,s) =-S{x) =-£s4fi{x)),

Р^где s-Jпoлoжитeльнoe число; S(fi (X)) 3 определенная при лю-бом fi{X) непре^рывная функция; S{fi{X))- +00 при iiiX)- ~-Ьоо и S(fiiX))-0 при и(Х)0 для ограничений типа неравенств или S{fi(X))--{-00 при fi{X)-+00 для ограничений типа равенств.

В качестве функций штрафа могут быть также следующие функции:

для ограничения исходной задачи типа неравенств

S(fi(X)) = [тах{0,/,()}];

для ограничений исходной задачи типа равенств

SHhix)) = ihix)V-

Обычно вид функции штрафа выбирается в зависимости от требования методов, применяемых для минимизации функции

Рассмотрим решение задач нелинейного программирования в случае ограничений-равенств. Необходимо решить задачу: минимизировать

mmfo{xi,X2,...,Xn) (7.152)

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

и {хи Хг,Хп) =0, i = 1,т. (7.153)

Лусть целевая функция и функции-ограничения fi(Xi,Хп), t= =0, 1,...,/п, дифференцируемы.

Вводятся множители Лагранжа Яг, t=l,m, и строится функция Лангранжа

т

L{Xi, Х2, ...,Хп, ЯьЯа, ...,?Cm) == fo{Xl, ...,Хп) -\-Eifi{Xl,-,Xn).

=1 (7.154)

Вектор Хо= (х?.....х^п) является оптимальным решением задачи

(7.152) - (7.153), если существует вектор Яо= (Я?,Я^), при котором выполняются соотношения:

дЦХо.Хо) dfoiXo) . а/.-(Го)

дх, dxj dxj

= 0. j=,n; (7.155)

=fi{Xo) =0, i=l,m. (7.156)

Система (7.155)--(7.156) содержит п-\- т уравнений и столько

>ке неизвестных Xj, / = 1, п, и Яг, i = 1, /п.

Решая систему (7.155) - (7.156), находят решения задачи (7.152) -(7.153), т. е. Хо = (х°,.д^,х^), и исследуют эти точки

на экстремум.

Рассмотрим решение задачи нелинейного программирования в случае ограничений-неравенств. Пусть необходимо решить задачу:

минимизировать

h{xu...,Xn) (7.157)

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

/г(хь...,х„)<0, i = T7 (7.158)

Предполагается, что целевая функция fo(xi,л: ) нелинейна, а ограничения fi{Xi, ...,Хп), i=\,tn, могут ыть как линейными, так и нелинейными функциями. Если точка Хо является решением задачи (7.157) - (7.158), среди ограничений (7.158) найдутся такие, что friXo) = О и fiiXo) <: О, г ф I.

Допустим, что ограничения (7.158) являются линейными функциями, т. е. имеют вид

h {Хи .... Хп) =-ВгХ + Su i = I, т. . (7.159)

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

экстремум (7.157) -(7.159) можно решить задачу на безусловный экстремум функции

F{Xu...,Xn) =foixu...,Xn)+t>hfiixi,...,Xn),7i>0, (7.160)

причем оптимальное решение Хо = (л^°, -,хР) удовлетворяет следующим условиям:

VFiXu ...,Хп) =(Xi, ...,Хп) +Т,%гЩ(Хи ...,Хп) = 0; (7.161)

Ц hfi {Xl,xl) = О^г > О, t = 1, m. (7.162)

В случае ограничений вида неравенств (fiixi,Хп) 0) удовлетворение соотношений (7.161) - (7.162) требует условия регуляр-нпстч ограничений Слейтера, т. е. существует по крайней мере одна гочка X, для которой fi (X) 0, i= 1, т.

ловия (7.161), (7.162) являются условиями оптимальности задачи нелинейного программирования в случае линейных ограничений.

Условия оптимальности задачи (7.157) - (7.158) определяются основной теоремой нелинейного программирования - теоремой Куна - Таккера.

Пусть целевая функция и ограничения fi{X), i=0, 1,т, имеют непрерывные частные производные на некотором множестве, , содержащем точку Хо- Если эта точка является решением задачи (7.157) - (7.158) и ограничения удовлетворяют условиям регулярности в виде линейной независимости, то существуют такие мно- , жители Лагранжа Я i=l,m, при которых выполняются условия:

V/o (Хо) + Ц Яг V/i (Хо) 0; (7.163)

Z hfi {Хо) = о, Яг > о, i = 1, т. (7.164)

Введя функцию Лагранжа

т

L (X. Я) = fo (X) + Ц hfi (X), (7.165)

условия (7.163) - (7.164) можно переписать в виде

У„Ь(Х,Я)=0; (7.166)

S7L{X,K)0; (7.167)

Я^УлЬ(Х,Я) = 2:hfi{X) = 0. (7.168)

Если целевая функция и все ограничения fi{X), ==0, 1.....т,

выпуклы и ограничения fi(X), i=l,m, удовлетворяют условию регулярности Слейтера, то вектор Хо будет решением задачи (7.157) - (7.158) тогда и только тогда, когда существует вектор

ЛоО, при котором пара векторов Хо, hi является седловой точкой, т. е. выполняются условия:

Ь{Хо,1ХЬ{ХоЛоХЬ{Х,Ко); (7.169)

lUiiXo) =0, t= l,m. (7.170)

В седловой точке {Хо, Яо)

Ь(ХоДо) = maxjninL(X,) = jnin maxL(X,Я). (7.171)

Следовательно, решение задачи нелинейного программирования сводится к отысканию седловой точки функции Лагранжа.

Если в задаче нелинейного программирования на вектор управляющих воздействий накладывается условие неотрицательности, т. е. ХоО, а функция цели и ограничения fi{X), i=0, \,...,т, дифференцируемы и выпуклы по X, то вектор ХоО будет оптимальным решением задачи тогда и только тогда, когда существует такой вектор ЯоО, что пара векторов Хо, Яо является седловой точкой функции Лагранжа L{X, Я), т. е. выполняются следующие условия:

а1(ГоДо)

>0, j= 1,п; (7.172)

dXj 3

х' = 0, j=l,n; (7.173)

=h{Xo) <0, i=l,m; (7.174)

Я /г(Хо) =0, 1=177 (7.175)

Для задачи нелинейного программирования максимизировать

Ши...,Хп) (7.176)

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

h{xi,...,Xn)>0, i= l,m; (7.177)

Х== {хи...,Хп)>0 (7.178)

условия оптимальности следующие:

если /г(Х), 1=0, 1,гп,- дифференцируемые и вогнутые функции, то для того, чтобы вектор Хо являлся оптимальным решением задачи (7.176) -(7.178), необходимо и достаточно, чтобы существовал такой вектор ЯоО, для которого выполняются условия:

. <0, ,=-п: (7.179)

дЦХо,Ко)

х] = 0, j = l,n;

dL(Xo,i:o)

Я'==0, i=l,m.

(7.180) (7.181) (7.182)

Метод Эрроу - Гурвица. Пусть задача нелинейного программирования имеет вид: максимизировать

fo{xu...,Xn) (7.183)

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

fi{Xi,...,Xn)>0, i = l,m; (7.184)

X {хи...,Хп)>0. (7.185)

Если все функции fi{X), i=0, l,...,m,- дифференцируемы и выпуклы вверх, то решение задачи (7.183)-(7.185) сводится к отысканию седловой точки функции Лагранжа

т

L(x,%) =fo{x) +2:шх),

т. е. к решению задачи max min L {X, Л).

Седловую точку {Хо, hi) можно найти по правилу

Xh+i = Xh + р VxL {Xh, Jk);

(7.186) (7.187)

где

Kk+i = max {0, Xk - p V%L{Xk,U)},

дЦХ,Лн) dL(X7U) 1

- j- ; (/.166)

WxL(Xh,lk) =

VKL{Xk,U) =

dxi . dxn дЦХн,1н) дЬ(ХкЛк)

дкт

(7.189)

Таким образом, для отыскания седловой точки {Хр, Яр) необходимо осуществить движение по переменным х j=l,n, в направлении градиента функции L{X, К), а по переменным Яг, i=l,m,- по антиградиенту этой функции. Последовательность Xk, Kk сходится к седловой точке, если выполняются условия Слейтера

Д]Яг/г(л: ...,х„) = 0.

Квадратичное программирование. Пусть необходимо решить задачу:

максимизировать ,

Z CjXj + - Z 2 CjkXjXk (7.190)

3=1 3=1 k=l

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

2 йгзХз + Гг = ЯгО, J = 1, (7.191)

XjO, j = l,n; (7.192)

/ j>0, J = l,m. (7.193)

Таким образом, функция цели /о(Х), имеющая вид (7.190), является квадратичной, вогнутой, а все ограничения - линейные.

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

Условия теоремы Куна - Таккера позволяют перейти от нелинейной задачи (7.190)-(7.193) к линейной.

В векторном виде задача (7.190) - (7.193) записывается так: максимизировать

(в-Х+~Х-Сх) (7.194)

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

Ао - 1Х>0; (7.195)

Х>0. (7.196)

Условия теоремы Кунна - Таккера для задачи (7.194) - (7.196) следующие:

б1(ГоДо)

= B + CX - AK+V = 0; (7.197)

= Ao - AX - W = Q; (7.198)

F-X = 0; (7.199)

W% = 0. (7.200)

Здесь функция Лагранжа имеет вид

L (X, %) = Б-Х +, 4- Х-СХ -f I {Ао - АХ);

Т - (f 1,Vn) - вектор остаточных переменных; W= {Wu .... tfm) - вектор избыточных переменных.

дЦХо,1о) dL{Xo,h) Vj > О, если --< О и 3 = О, если ---= G;

iwi > 0, если--> 0 и Wi =0, если---= 0.

Полученные первые два условия образуют систему из n+m уравнений с 2(n+fn) неизвестными X, К V, W. Последние два условия (условия Слейтера) свидетельствуют о том, что п переменных т X я V к т переменных из I и W должны быть равны нулю. Поэтому, если существует решение задачи (7.194) - (7.196), то оно должно быть одним из базисных решений задачи:

СХ - Ж + F = -Б; (7.201)

AX + W = Ао. (7.202)

Применяя метод искусственных переменных, получим задачу: минимизировать

т п

{HMyi + TMzi) (7.203)

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

СХ - Л^Г-Ь F -f Z = -В; (7.204)

ZX + TF + F = Ло, (7.205)

Z = (Zi, Z2,z ); F = (Уь У2, -, Уш); Z>0; FO.

При решении задачи (7.203j-(7.205) необходимо учитывать условия Слейтера: FX=0 и WkQ.

Если удается вывести все искусственные переменные, то найденное базисное решение будет оптимальным.

Пример 1. Решить задачу: минимизировать

при ограничений

Xl+.X2 = 9.

Решение. Составляем функцию Лагранжа

L{xuX2,l) = (х,-4)2+(х2-3)2 + Х(9-л:, -Хг). Определяем частные производные: dL(xi,X2,X)

dxi dL{xi,X2, Я)

dD(xi,X2,K)

= 2(Xi -4)-Х = 0; = 2(X2 -3)-Я = 0; - = 9 -Xl-X2 = 0.

Решаем систему и находим: х^ = 5; = 4; X = 2.

Исследуем функцию fixi.Xs) = (х,-4)2--(х2 - 3) в окрестности точки 0= (а-о = 5, х = 4):

9 260 249

Поскольку fn{Xo) > о и

dxidx2 hi hi

= fl2 = hi = 0.

> 0, TO функция f(xi, X2) выпукла и в точ-

ке Хо - (5, 4) имеет абсолютный минимум.

Пример 2. Решить задачу: максимизировать

/(xi.xs) = (44х, + 130x2-4x2- 16x2)

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

4X1-f 7X2 < 30; 4x1-Х2<10; Xi>0, Х20. Решение. Исследуем целевую функцию:

f.=-=44-8x.; f = i=-8<0;

dxi ах2

= 130-32x2; f22 =-rV =< 0;

fi2 - h

6X16X2

= 0; Д =

>o.

Поскольку /п < О, a Д > О, то функция f(xi,X2) вогнута и задача является задачей квадратичного программирования. Составляем функцию Лагранжа

L (XI, Х2, %и Я2) = (44X1 + 130x2 - 4x2 162) +

+ h (30 ->(4xi + 7x2)) + М10 - (4X1 - Хг)).

Применим теорему Куна - Таккера и получим условия для определения оптимального решения:

-X, = 0;

dxi dL

dXi dL

44 -8xi -4Xi -42<0; : 130 -32X2 -77.1-f 7.2 <0; 30 - 4xi - 7X2 > 0; = 10 - 4xi -f X2 > 0;

6x1 dL dXi dL dXi dL

-X2 = 0; = 0;

7,2 = 0.

Введя в эти системы свободные переменные (остаточные и избыточные) Il, V2 и Wi, W2, получим систему и условия дополняющей нежесткости:

44 -8X1 -41 -4X2 + 1 = 0; \ Xii = 0;

130 - 32X2 - 77,1 -f Я2 -f 1)2 = 0; ХгКг = 0;

30 -4х, -7X2 -Ш1 = 0; Т^ш, = 0;

10 - 4xi + Х2 - 12 = 0; . ) 7,2Ш2 = 0.

Перепишем систему в виде + 4к, + 4К2 -VI = 44

з2л + 7я..-2-2= 130;

Для решения задачи необходимо найти допустимое базисное решение системы V ппи выполнении условий IV.

Решение можно получить, применив симплекс-метод, для чего необходимо ввести искусственные переменные, так как в системе V нет единичного базиса. Введя искусственные переменные в первое и второе уравнения системы V, подучим следующую задачу линейного программирования: минимизировать

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

+ 41 + 4Я,2 - f 1 Ч- г/1 = 44; 32*2 + 71 - Яг - f 2 -f i/2 = 130; 4Xi-r<x-: + Wi =30; 4л:, --f 2 = 10.

taKHM образом, задача квадратичного программирования свелась к задаче линейного программирования.

7.5. СТОХАСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Термин стохастическое программирование введен в начале 50-х годов математиками Данцигом, Чернсом, Купером при изучении задач линейного программирования со случайными коэффициентами. Обычно эти задачи гораздо сложнее задач нелинейного программирования и для их решения разработаны специальные численные методы, обобщающие детерминированные методы нелинейного программирования.

Стохастическое программирование включает методы решения задач в условиях риска и неопределенности. Задачи в условиях риска характеризуются известными вероятностями возможных частных исходов принимаемых решений.

Для задач в условиях неопределенности вероятности возможных исходов принимаемых решений неизвестны.

Пусть имеются m допустимых решений, п возможных исходов этих решений и сц - затраты, связанные с решением i, i- l,m, при исходе /, у = 1, п. Истинный исход при принятии решения i Неизвестен. Задача заключается в выборе такого допустимого решения г, которое в смысле некоторого критерия является наи- Яучшим.

8* 251

Если бы любое решение однозначно приводило к определенному исходу, то задача была бы эквивалентна задачам линейного или нелинейного программирования, так как необходимо выбрать такое решение i при заданном исходе /, для которого величина

была бы минимальной. Но исход / не задан, потому задача выбора решения усложняется.

При решении задачи в условиях риска заданы вероятности ис-

п

ХОДОВ рь рп, причем ЕРз = 1- Часто критерием выбора реше-

ния i является минимизация средних затрат

hEciiPh i=l,m, (7.206)

или максимизация вероятности

/г = P{Cij<c,/ = i=l,m, (7.207)

где с - некоторые заданные затраты.

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

При решении задач в условиях неопределенности, т. е. в условиях, когда вероятности исходов р;, j=l,n, неизвестны, может быть принят один из следующих критериев оптимальности решения.

1. Минимизация максимально возможного убытка (гарантированный уровень)

f = min max dj. (7.208)

Оптимальным является то решение io=f, при котором максимальный убыток достигает минимума.

2. Критерий минимаксного риска (критерий Сэвиджа)

f - min max cij = min max (Cij - min Cij), (7.209)

lim Kjn lim ljn Kim

где Cjj - элементы матрицы риска

C=\\cij\\=[[Cij- min CijW..

3. Критерий оптимальности по Парето. Решение i называется оптимальным, если не существует si, при котором

Csj<Cij, j=l,n. (7.210)

4. Принцип недостаточного основания Бернулли (принцип равновероятности исходов). Если нет оснований считать, что какой-то исход вероятней другого исхода, то все исходы принимаются равновероятными. Этим задачу в условиях неопределенности сводят к задаче в условиях риска.

На практике часто вероятности исходов определяются на основе экспертных оценок.