книги / Математические методы в системах поддержки принятия решений
..pdfточки зрения приближения к оптимальному решению) перевести в основные, выразим через них линейную форму L. Имеем
JC5 = 900 - 4х, - 2х2 - Зх4, х6 = 500 - 2хх - 2х2 - 2х3 - 2х4, х7 = 200 - Xj - х3 - JC4, (2)
L = 5х! + 2х2 + Зх3 + 4х4.
Из анализа линейной формы L следует, что ее значение возрастает при увеличении значений переменных х и х2, х3, х4. Переведем в число основных переменных xlt так как она входит в L с наибольшим коэффициентом. Однако увеличение L за счет увеличения х х может продолжаться до тех пор, пока и{(х) = 1, т.е. пока не нарушается требование не отрицательности переменных. Поэтому из первого уравнения системы (2) следует, что Xj
не должна превышать число |
= 225, чтобы i/|(3c) оставалось равным единице. Аналогич- |
4 но из второго и третьего уравнений системы (2) следует, что переменная Х| должна удов
летворять неравенствам Xj < 500/2 и Х| < 200 соответственно. Итак, при
х, - min{900/4, 500/2, 200/1} = mw{225, 250, 200} = 200,
получим, что после перевода Х| в основные переменные, а х7 — в свободные,
х1- (200, 0, 0, 0, 100, 100, 0 ), причем и2(х') > и2(х°),
так как L(x!) = 1000 > 1(х°) = 0. Теперь х« из третьего уравнения системы (2) подставим в остальные уравнения этой системы и в L:
х х = 200 - х3 —х4 —х7, х5 = 100 - 2х2 + 4х3 + х4 + 4х7, х6 = 100 - 2х2 - 2х7, |
(3) |
L = 1000 + 2х2 —2х3 - х4 - 5х7.
Рассуждая аналогичным образом для (3), приходим к выводу, что х2 следует ввести в
основные переменные, а х6 или х5 вывести (пусть это будет х6). Выражая х2 из третьего уравнения системы в (3) и подставляя в остальные уравнения, имеем
X! = 200 - х3 - х4 - х7, |
х2 = 50 —~ |
+ х7, |
х5 = 4х3 + х4 + х6 + 2х7, |
L = |
1100 - 2х3 - |
х4 - х6 - |
Зх7. |
При этом х2 = 50, и решение х2 = (200, 50, 0, 0, 100, 0, 0) является оптимальным, по скольку все коэффициенты перед Xj в L отрицательны.
Итак,
и2(3?) > и2(х1) и и2(1?) = 1100.
Для получения наибольшей прибыли в 1100 единиц предприятие должно выпустить 200 единиц продукции Dh 50 единиц продукции вида Z)2, а продукцию видов /)3 и D4 про изводить невыгодно. Сырье видов Е2 и Еъ будет израсходовано полностью, а 100 единиц сырья вида Е\ останутся неизрасходованными.
Задача 2. Найти min max /Дх), где/,(х) = Зх, + 2х2 - 1, / 2(х) = Зх2 - х ,,/3(х) = - х { - х2
Х6Е2
(необходимое условие оптимальности решения сформулировано в гл. 5).
Р е ш е н и е . Преобразуем исходную задачу поиска min max /Д х) в задачу математи-
*€£21£/£3
ческого программирования. Для этого введем новую переменную х3, имеющую смысл при
данном х е Е? верхней границы для всех значений f t{x) i = 1, 2, 3. В результате получаем эквивалентную задачу:
х3 - » min
171
при ограничениях
Эх, + 2х2 - 1 2 х3, Зх2 - х, 5 х3> -х , - х 2^ х 3, х = (х ,, х2, x j)e f 3,
которая является задачей линейного программирования. Для ее решения применим симплекс-метод. Предварительно путем введения дополнительных неотрицательных пере менных х4, х5, х6 приведем ее к виду
L = - х 3 min
при ограничениях
ЗХ{ + 2х2 -Х 3 + Х4 = 1, -Xj + Зх2 - *з + х5 = О, ~Х\ - х2 - х3 + х4 = О,
х > 0 , х > 0 , х> 0 .
Здесь три ограничения, а переменных — шесть. Поэтому опорное решение получим, если положим, например, х4, х5 и х6 равными нулю:
Зх| + 2х2 - х 3 = 1, -х , + Зх2 - х 3 = 0, —х, - х2 - х3 = 0; |
(*) |
находим Xj =1/4, х2 = 0, х3 = -1 /4 и опорное решение
х1= (х, =1/4, х2 = 0, х3 = -1/4, х4 =0, х5 = 0, х6 = 0).
Выразим в (*) основные переменные x h х2, х3 и целевую функцию через свободные х4,
*6^
X] = 1/4 - Х4/4 + ЗХ5/16 + xg/16, х2 = xg/4 - Х5/ 4, х3 = -1 /4 + Х4/4 + X5/ I 6 + 1 lxg/16,
L = 1/4 - Х4/4 - Xs/16 + 1 lxg/16.
Поскольку линейная форма L имеет только отрицательные коэффициенты перед свобод ными переменными, то перевод какой-либо_из них в основные переменные не приведет к увеличению. Значит, полученное решение х1 является оптимальным.
Для исходной задачи получаем, что оптимальная минимаксная стратегия х* = (xh х2) =
= (1/4, 0), а искомый min max /}(х) = --!- определяется значением х3.
хе£2 1S/S3 |
4 |
6.5. Методы решения статических безусловных задач недифференцируемой оптимизации
6.5.1. Субградиентный метод
Выбор решения х* е М* c R n осуществляется в результате решения
следующей задачи. Найти m in/(x), гдеДх) — выпуклая недифференци
руемая (негладкая) функция, имеющая в каждой точке некоторый суб градиент dflxk), хк е R". В качестве примера возьмем функцию
/(* ) = (с, х ) + Ртах {(а', х) - Ь(}+,
172
которая строится для задачи линейного программирования
(с,х) -¥ min при ограничениях А х< Ь,
где а, — строка т х п матрицы А \Ь — вектор-столбец размерности т\ Р > 0 подлежит выбору.
При движении по направлению, устанавливаемому субградиентом bfixk) из точки хк, возможно возрастание функции Дх) при любом выбо
ре длины шага (J; однако расстояние до точки минимума от точек, при надлежащих некоторому начальному отрезку на направлении ЭДх*), бу дет убывать монотонно. Это последнее обстоятельство совместно с уменьшением на каждой итерации длины шага составляет основу для построения алгоритма субградиентного метода.
А л г о р и т м
1. Выбрать произвольную точку дс0 s Л".
2. Задать последовательность чисел \ к > 0, такую, что
|
Х* т |
^ 0, I |
х* |
- |
|
|
к=О |
|
|
3. |
Взять любой субградиент ЭДх0) как элемент субдифференциала в точке х0 функции |
|||
Л*). |
|
|
|
|
4. |
Вычислить х, = х0 - Х„ — |
— |
|
|
5. |
1|Э/(*о)|Г' |
|
|
|
Если при этом дДх0) = 0, то решение найдено: х* = х0, в противном случае — взять |
||||
субдифференциал функции в точке х^ и либо перейти к точке |
||||
|
*2 = *i - |
МЛ*1> • Ktei)!"1. |
||
либо, в случае сД^) = 0, считать, что х* = Х| для любого к и т.д.. |
||||
6. |
Построить последовательность {хк}. Если |
эта |
последовательность конечна, то ее |
последняя точка есть решение - точка минимума Дх) на Rn; если последовательность {**) бесконечна (в теоретическом плане), то для выпуклой функции на Rn будет иметь место
подмножество М* * 0 , т.е.
М* - {x*R“|/(х*) = /* = min /(*)}. x e R "
Субградиентный метод называют также методом обобщенного гра диентного спуска; он не может быстро сходиться. Для ускорения сходи мости применяются другие методы — метод отсекающей гипер плоскости (см. п. 6.1.5.), методы с растяжением пространства и др. [22].
6.5.2.Метод обобщенного градиентного спуска
срастяжением пространства
Известно, что для выпуклой функции обобщенный градиент совпа дает с понятием субградиента, а обобщенное градиентное множество - с субдифференциалом. Последний есть замкнутое выпуклое множество. В рассматриваемом здесь методе из субдифференциала функции fix),
173
построенного на шаге к в точке х е R 1, берется субградиент. Далее осу
ществляется движение к точке х*+, в направлении этого субградиента одновременно с растяжением пространства R" в этом же направлении. В
связи с этим становится необходимым введение оператора растяжения FJ&) с коэффициентом а > 0, где £ — вектор из Л".
Оператор растяжения F„(£) действует следующим образом. Пусть за дан вектор £ и определен какой-то вектор o e JP. Тогда вектор а можно однозначно представить совокупностью проекций на подпространство,
порождаемое вектором |
и на подпространство, ортогональное к нему, |
т.е. х = д5(х) • § + d^jix) |
и скалярное произведение (£, </$(*)) = 0. При |
этом F JQ , действующий на вектор х в направлении вектора £, записы |
вается (по определению) в виде |
|
|
|
/\Д )х = ащ(х) • $ + dK(x), |
dK(x) = FJ& x |
||
или, что то же, |
|
|
|
Fa(%)x = а(х, %)% + [ х - (х, |
= (а - |
1)(х, а д + х. |
|
Этот оператор обладает и таким свойством: |
|
||
Га,аг® = Ъ , ( № 2® , |
Ъ Щ |
® |
- 1 « > 0 - |
При растяжении пространства очевидно точка хк е R" переводится в точку ук. Формально этот перевод имеет вид ук = А^ск, где Ак — линей
ный оператор, так как растяжение есть операция линейная. Очевидно также и соотношение для субградиентов функции fix) в точках хк и ук:
d f(y k) = B kdm f(xk), В к’ ={А-к' ) \
где В'к — сопряженный к Вк, Вк = Ак' , Вй = I.
В результате схема алгоритма поиска искомого решения
х* = argmin /(х )
хеЯ"
представляется следующими операциями.
Ал г о р и т м
1.Задать х0 е R".
2. |
Взять любой субградиент дДх0) ФункцииДх) в точке х0. Если при этом д/(х0) - |
то |
||
вычисления прекращаются - точка х0 = xj, иначе - |
переход к операции |
3. |
|
|
3. |
Задать последовательность чисел шаговых |
коэффициентов \ к > |
0, X* --^ |
ое~* |
и коэффициентов растяжения пространства ак > 0.
*=о
174
4. Вычислить d f(yk)= B*kdf(xk \ к = 0, 1, 2, |
В0 = I = А^1. Если dflyk) = О, то вычис |
|
ления прекращаются - точка хк = х*, иначе - |
переход к операции 5. |
|
5. |
Вычислить хк+1 = хк - ВкХ^Дук)\\дДук)\\-К |
|
6. |
Вычислить |
|
|
BM =A-k[r BkF ^ _ & \ |
|
“* + 1 |
ГДе $*+1 “ дД У к>\\дА У к)\\ |
*>4t+l ~ F a k +,(£*+1)'^ а к (?*)"'^0,(^1) A t - |
Т. Переход к оп. |
4 для к + /', /' = 2, 3....... |
Рассмотренный алгоритм не обеспечивает монотонного движения к искомому решению по значению минимизируемой функции. Монотон ность может быть обеспечена, если построить алгоритм с растяжением пространства в направлении разности двух последовательных субгради ентов или применить метод Ньютона, в котором линеаризуется исход ная задача.
6.6. Методы решения статических условных гладких выпуклых задач
Метод проекции градиента. Сущность метода заключается в выпол нении на каждом шаге наискорейшего спуска и ортогонального' проек тирования антиградиента критериальной функции на линейное много образие активных ограничений или их аппроксимаций, причем таких ограничений, которые обращаются в равенства в точке х?к) на Л-й ите рации поиска оптимального решения. Совокупность из q таких ограничений-равенств составляет линейное подпространство М(х^к)).
Это подпространство натянуто на линейно независимые векторстолбцы подматрицы Ач матрицы А исходной системы линейных огра ничений; матрицы, вектор-столбцы которой составляют базис п- мерного пространства. При этом предполагается, что Ач имеет ранг q, т. е. существует матрица (Aq Aq)~l .
Оператор ортогональной проекции определяется выражением
Pq = E „ -A q(AqT Aq)~ 'A q |
( 1) |
где Е„ — единичная матрица.
Действительно, пусть Ачх является ортогональной проекцией векто
ра у на подпространство М (х(к)). Тогда |
|
(AqUy(A qx - y ) = 0 |
(2) |
— соотношение для ортогональных векторов, где Ачх — у — вектор не вязки, ортогональный к подпространству М(х^к)), т.е. к любому его век тору; и = (и1 и2, ..., lA) — некоторые коэффициенты, с помощью
175
которых каждый вектор в подпространстве М(х*к)) представляется ли нейной комбинацией столбцов подматрицы Ач.
Из (2) непосредственно следует, что
A qT Aqx = A * y или x = {ATq Aqy ' A Tq y.
При этом, очевидно,
At x = Aq{AT AqY l A Tq y,
где Aq(Aq Aq)~' Aq = PM(x(t>) — оператор проектирования (проектор) на
М{р6к)), а оператор ортогональной проекции Рч записывается в виде ра
венства (1), которое непосредственно получается из взаимной ортого нальности подпространства М(х*к)) размерности q и подпространства М размерности n — q.
Поиск оптимального решения заканчивается, когда модуль проек ции градиента станет меньше заданной величины е > 0.
Приведем |
схему алгоритма поиска решения |
|
X* |
= aig min f(x ), Х = {хе |
^ 0, / = 1 ,т), |
где Д х) и g^x), i = Tjn — выпуклые и непрерывно дважды дифферен
цируемые функции [24].
Ал г о р и т м
1.Определить начальную точку е X. Если ограничивающие условия составляют систему линейных неравенств, то отыскание д^0) € X сводится к решению этой системы, например, симплекс-методом.
2.Вычислить градиент функции Дх) в точке д^0).
3. Определить в точке |
активные ограничения g,{x) = 0, / = iu |
..., q, и линеаризо |
|||
вать их — составить систему вида |
|
|
|||
|
(Л„ х - |
х0) + &<х<0>) = 0, / = /........... |
|
||
где Л/ = |W |
0)) |
|
»/(*(0)) |
'А |
4 |
’ |
Aq —(tfj,#2*•••» Qq)“ а\ |
4 |
|||
, |
а*' ’ дх2 |
дх" |
|
|
4. Вычислить проекцию антиградиента функции Д*) в точке д^0) на линейное много образие активных ограничений
^ ( - g ra d / ( х <0))) = ( £ - Aq(Aq Aq)~x< ( - g ra d / ( * <0>)).
Вычисления матрицы проектирования Pq = ( £ - Aq(A%Aq)~x A%) целесообразно вы-
полнять по рекуррентным формулам [86]. Здесь Pq — оператор проектирования ошибки
(-grad Д х (0))) - Pq( - grad Д х <0)))
176
на ортогональное дополнение пространства столбцов матрицы Aq. Если при этом Pq(-grad /(* « » )) * 0, то надо определить направление § движения к очередному прибли жению х*1)
P ,(- g ra d /(s (0))) ll^(-g rad /( x <0,))||
Если же выполняются условия оптимальности.
Ad®)) =о, или -grad/(х(0))=уУд,я
/=/,
и
и - (i/1 и2 иР) = ( ^ ) “1^(-grad^0))) ^ О
то при и1£ 0, / = 1, 0, х(°) = дг* — решение задачи. При выполнении таких условий анти градиент критериальной функции записывается в виде линейной комбинации с неотрица тельными коэффициентами градиентов линейных ограничений, содержащих точку
Если некоторая компонента и* < 0, то в качестве матрицы проектирования следует считать Pq_j. Так как векторы аь а2, ...» aq линейно независимы, то
|
|
\ |
Р ^ а ^ О и |
(-grad/( х <0>)) = Pq_x |
= ияРч-\ач * 0; |
|
|
У |
^ - i(g ra d /(* <0)))
ll^ -i (grad /( * (0>))lf
В случае, когда среди векторов аь а2,...» aq имеются линейно зависимые от них век торы, то направление спуска £ из точки х№ отыскивается как решение задачи линейного программирования
min(-grad /( х <0))Д), (</„ $) 5 0 ,/ = /, ,q.
4а. Если множество X допустимых решений определяется линейными ограничения ми, то вычисление проекции Р ^ - grad Az)) Для точки z £ X составляет задачу квадратич ного программирования
||* - z\\2 = I(*v - Zy)2 -> min
и ее решение отыскивается с использованием метода квадратичного программирования,
конкретно, согласно теореме Куна—Таккера [20]. |
|
|
5. Задать последовательность шагов <х0 > otj > |
> ... > <fyj - 1 ,2 , ..., либо шаг а сле |
|
дует определить из условия невыхода очередной точки х*1) за пределы множества X, т.е. из |
||
условия Aqx (0) + a qAqgrad f(x(0)) = bq. |
|
|
Очевидно, при этом для окончательного выбора значения а целесообразно вос |
||
пользоваться правилом: a = m in { a , }, |
a > 0, затем |
вычислить grad / ( х (1)) в точке |
1ZtZq |
|
|
* (1) = х*0) - a grad /( х (0)) и проверить выполнение критерия оптимальности |
||
Pqgrad л * (1)) = 0, |
(AqAq Г 1Адgrad Д х (,) )> 0. |
1 2 - 5396 |
177 |
При невыполнении этого критерия необходимо откорректировать очередное прибли жение по выражению
х<, >=рх<,>+ (1 -р)х(0>,
« * ,grad Л * (0>)f,g rad / ( х<0))) |
|
где р = |
и перейти к one- |
((Я,grad Д х (0) ))r ,grad Д х <0))) - |
((Я,grad Д х (0) ))r ,grad Д х 0 ))) |
рациям 3, 4.
Величину шага OQ можно определить и из решения задачи
min/(x(0) -о £ 0),
с учетом требования невыхода точки (дс<°> - се^о) за пределы множества X, или положить а = а е [0,1), если градиент критериальной функции удовлетворяет условию Липшица
1/4*1 -/Ч О И ^ UW - *11 для всех х е X. |
и перейти к операциям 3 и 4. |
|
Затем вычислить приближение х*1) *» х<°) - |
||
Изложенный процесс вычислений повторяется до выполнения условий оптимально |
||
сти для х1к\ к - 2, 3, |
т. е. до дДО = х*. |
|
Этот метод обобщается на негладкие задачи и преобразуется в метод проекции субградиента.
Задача. Найти решение х* = (*i*,xj)€ X , доставляющее минимальное значение крите
риальной |
функции /(х , ,х2) = -Юх! + х2 - 2 х , х 2 + 2 х | |
при ограничениях х { + х2 £ 6, |
X j + 2 х 2 й |
12, Х| > 0, х2 > 0, формирующих допустимое множество X. |
|
Р е ш е н и е . Зададим начальное приближение х(0) = |
. Вычислим градиент функ- |
ции/{*) в точке х<°> =
Выберем в е л и ч и н у ш а г а а - 0,35 движения на направлении антиградиента; од нако величину шага можно было бы вычислить, как в методе наискорейшего спуска без ограничений, т.е. по правилу
а 0 = aigmin/(x(0) -a(-g rad /(x (0))))=* aigmin /(1+ 10а,1-2а) =
а>0 |
а>0 |
|
aigmin{-10(l+ 10а)+(1+ 10а)2 -2(1+ 10а)(1-2а)+2(1-2а)2)-» в0 * ОД |
||
а>0 |
|
|
Запишем выражение |
для проекции точки х<°> - a gradДх<0>), т.е. х(1) = Рх( х ^ - |
|
- а grad / ( х <0))) = 2*, |
и проверим условия принадлежности точки |
множеству |
X : х, + х2 = 4,5 + 0,3 <6; х, + 2х2 = 4,5 + 2 • 0,3 < 12; 4,5 > 0; 0,3 > 0 — условия выполняются.
178
П риним аем точку |
j в качестве очередного приближ ения |
(так как вы полнены |
проверяемые условия на предшествующей операции). Проверим условие Р/(—grad/(xM)) = 0, /= 1 , 2, 3, 4; для этого воспользуемся выражением
Ря = ( Е - А я(А1 лч г 1Ая )(-grad /( х <п)), q = i.
Так, для q = 1 имеем
Аналогичные вычисления приводят к Р2* О, Р3 Ф о, Р4 ф 0, т.е. точка х*1* не является решением задачи; переходим к второй итерации.
Зададим величину шага на направлении (-grad/fx*1))); пусть а = 0,125. Выполним действия в той же последовательности, что и на предыдущей итерации, получим
х(2) = j. Эта точка принадлежит границе Xj + х2 = 6 множества X. Вычислим проек
цию градиента критериальной функции в точке хР> — она не равна нулю; продолжим по иск искомого решения х*. Зададим а = 0,025 и выполним все вышеназванные действия; в
результате получаем х(3) = j.Эта точка принадлежит границе Xj + х2 = 6 множества X.
Вычислим проекцию антиградиента
/>,(-grad /( * <3>))[£ - АТ(ААТГ 1 А]( - grad Д х (3))) =
(i
Можно считать, что х ^ = |
— искомое решение. |
Метод проекции градиента может быть обобщен и применен при выборе оптимального решения в негладких выпуклых задачах вида
найти minf(x ) ,
х е Х
где X — выпуклое замкнутое множество простой структуры,
Х = {х е R”/ ф,(х) 5 0, / = 1, 2, ..., п}.
Сущность обобщения заключается в том, что в произвольной точке х е X определяется 1(х) — множество индексов активных ограничений
1(х) = {/: (р( (х) = шах(р( (х)} 1SJ1&N
и осуществляется проектирование на X субградиента этих ограничений.
Затем делается шаг по его проекции. Если /(х) = 0 , (точка х находится
12* |
179 |
внутри множества X), то движение к искомому решению осуществляет ся по проекции субградиента целевой функции в точке х е X. Как ре
зультат структура алгоритма выбора решения записывается в виде
х*+' = ./>,(** - |
а***), |
Рх — оператор проектирования, а* -> 0, |
Х а * = |
|
к=\ |
|
е с л и ф ,( х * ) £ 0 , |
[Эф(х*), |
если ф, (х к) > О |
Э ф (**) = ^ Х ^ ф Д х * ) , Х ,£ 0 , £ Х , - J- |
|
/е/(дг*) |
* |
Метод условного градиента. В основе метода лежит идея линеариза ции критериальной функции fix), х е Х а R”с последующей ее миними зацией на заданном выпуклом компактном множестве X. Согласно этой
идее представим схему алгоритма поиска оптимального решения X* = aigm in/(x).
хе Х
Ал г о р и т м
1. |
Задать начальное приближение х0 е X |
|
|
|||
2. |
Линеаризовать/^) в точке х0>а затем в точках хк, к |
- 1,2, ..., и исключить из ли |
||||
неаризованного выражения к о н с т |
а н |
т у £ = 1 , 2 , |
t.e. записать критериальную |
|||
функцию в виде |
|
|
|
|
|
|
|
(f \ x k), х - |
хк), |
х е |
X, |
к = 0, 1, |
2, .... |
3. |
Найти решение задачи, в общем случае, нелинейного программирования |
|||||
|
т т (/'(хк) , х - х к), к - |
0, 1, 2, |
: |
|||
|
х е Х |
|
|
|
|
|
|
*о = ВДВ m in(/'(x0).* - х0) |
и |
х* = aigm in(/'(x* )>*-**). * = 1, 2, ..., |
|||
например, с использованием метода возможных направлений. |
||||||
4. |
Проверить выполнение необходимого условия оптимальности на шаге к = 0, а за |
|||||
тем на шаге к = 1, 2, ..., |
|
|
|
|
|
если (/'(*о),х<> - * о )^ 0, то х*0 =х*
и работа алгоритма завершается; если же это условие не выполняется, то перейти к вы полнению следующей операции.
5.Определить направление Р0движения из точки x j к искомому решению на очеред
ном шаге, т.е. условный антиградиент Р0 = XQ - х; на шаге к здесь устанавливается Рк,
к= 1 2, ....
180