Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

9.22. задачи выпуклого квадратичного программирования

Задача максимизации квадратичной функции

п л

/=Х W+Z сілХІ + 2   £ (9-68>

на множестве решении системы

ХяіЛ<6і.і*=1,2,...,іи; (9-69) 2,..., я, (9.70)

называется задачей квадратичного программирования. Если квадратичная форма

л

 

является отрицательно-определенной, то квадратичная функция (9.68) является вогнутой. В этом случае задача (9.68)—(9.70) называется задачей выпуклого квадратичного программирования.

(9.71) (9.72)

Точка М0 (хх°; ...; *Я) является оптимальным решением задачи выпуклого квадратичного программирования (9.68)—(9.70) тогда и только тогда, когда существуют числа у°, v°, i=, 2,     т, и uj.j—l, 2,'..., п, такие, что:

*>? = (),;= 1,2, ...,в;

b?^? = 0,j=1,2,...,jii;

вектор а° = (х?;х°„;у?;и?; ...;mJJ;»?; w°) является опорным решением системы ограничений

-—Z а^+«/=0,У=1, 2,     п, (9.73)

л

£ я0х,+«>(=Л, /=1, 2, /и, Xj^O, Иу>0, «(>0,і=1, 2,     «, /= I, 2, m.

Два вектора условий для системы (9.73) назовем сопряженными, если они соответствуют либо неизвестным Xj, Uj при некотором j, либо неизвестным у;, V, при некотором i.

Таким образом, для решения задачи выпуклого квадратичного программирования (9.68) (9.70) достаточно найти опорное решение системы (9.73), базис которого не содержит сопряженных векторов условий. Такое опорное решение можно найти методом искусственного базиса.

О Рассмотрим задачу выпуклого квадратичного программирования

/=х| + 10х2 — jc і — х(max), ' Хі+хг^4, Хі^О, х23*0.

д/ а/

Так как —~—2х{, — — 10 — 2х2, то в данном случае система дх дх2

(9.73) имеет вид

f  1—2х,—>, + «, = 0, 10-2х2~у] + и1=0, Xi+x2 + vt = 4, х,>0, х2>0, ^5=0, м,5= 0, и2^0, i>,^0.

 

Составим вспомогательную задачу:

2дг,+^ — ы, 4-г, = 1, 2x2+yl-u1 + z2 = 10,

x|+x2 + Vi+23=4,

х^О, х2^0, >,>0, и,>0, и23*0, »,>0, z,>0, z2>0, z32sO; <p=z,+z2 + z3 (min).

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

 

9.23. Приближенные методы решения задач нелинейного программирования

Предположим, что задача максимизации функции

f=f(M) (9.74)

на множестве

Cl={MeR" |Ф, (А/)«О, 1=1, 2,     т]   (9.75)

имеет оптимальное решение А/0.

Пусть е — некоторое положительное число. Точка A/.eQ называется приближенным решением задачи (9.74)-*-(9.75) с точностью £, если она удовлетворяет неравенству

/(Л/0)-/(А/,)<£,

Обычно приближенное решение задачи нелинейного програм мирования (9.74)—{9.75) ищут с помощью релаксационного пр:< цесса. Релаксационный процесс — это процесс построения последовательных приближений  Ми  Мг,        Мк,  ...  таких, чго МцЄІІ (к=1, 2, ...) н f (Mk+i)>f (Мк). При этом релаксационный процесс называется сходящимся, если

timf(Mk)=f(MB).

 

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

Чтобы задать релаксационный процесс решения задачи нелинейного программирования, достаточно указать точку М є П и правило перехода от точки Мк к точке Мк+.

В большинстве случаев переход от точки Мк (хк); хгк ж і'1) к точке Мк+І осуществляют по следующей схеме:

Выбирают некоторый вектор ак=(ак); af; а{к)) (направление перемещения из точки Мк) и рассматривают точки вида

Мк,, (x^+afH; xf + aft;     x?> + a«/),

где t — некоторый положительный параметр.

Подбирают значение параметра t так, чтобы

М,,еГ1иЯЛ/*,,)>/(м*).

Если tk — найденное значение параметра /, то полагают Мк+1 = Мк,к.

Известны различные методы выбора направления перемещения и значения параметра t, которые для задач выпуклого программирования гарантируют сходимость релаксационного процесса. К таким методам, например, относится метод возможных направлений (см. п. 9.24).

Для решения задачи максимизации вогнутой дифференцируемой функции / (М) на всем пространстве R* можно использовать градиентный метод, в котором точку MieR" выбирают произвольным образом, а направление перемещения из точки Мк (к-, 2, ...) считают равным

grad/lм. = f (Мк); f (Мк); ...; f (Мк).

 

При этом если grad/| и—в> то Л/*— оптимальное решение задачи.

Одной из разновидностей градиентного метода является метод скорейшего подъема. В методе скорейшего подъема на Л-м шаге значения параметра t подбирают так, чтобы достигалось наибольшее значение функции f{MKi,) одной переменной /.

Точку М, называют обобщенным приближенным решением задачи (9.74)—(9.75) с точностью е, если она удовлетворяет следующим неравенствам:

f(Ma)-f(Me)<E,

Ф((М,Не, i=h 2, т.

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

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

Если функция £ (t) удовлетворяет следующим условиям:

і (0 = 0 при f^O;

(:)>0 при ?>0;

{ (/а)>{ (/О при /г>/,>0;

lim £ (0=оо,

 

— то функция

 

где Л=(гь г2  тт) — набор положительных параметров, назы-

вается штрафной функцией задачи (9.74)—(9.75). Основное свой-

ство штрафной функции:

Л (М, R)=Q при А/еП и Л (Л/, Л)>0 При МфО.

Метод штрафных функций состоит в том, что вместо задачи нелинейного программирования (9.74)—(9.75) решают задачи максимизации на всем пространстве R" функции

/х(М)=/(М)-Л(м,ю

 

при различных параметрах ги г2, гт.

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

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

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

Рассмотрим задачу максимизации функции f(M) на множестве

0={МєНя|Ф, (А/КО, іє/}.

 

Предположим, что выполнены следующие условия:    , .

I.          /=/л U Л. и если ієІ„, то Ф, (М) — линейная функция, если

то Фі (Л/) —выпуклая дифференцируемая функция на про-

странстве R",

Множество £! удовлетворяет ^ловию Слейтера, т. е. существует точка А/єП такая, что Ф, (А/)<0 для всех /є/,.

/ (М) — вогнутая дифференцируемая функция на допустимом множестве Q.

В методе возможных направлений точку Л/|ЄП выбирают

произвольным образом. Переход от точки Мк (хкі; х[к): xf>) к точке Мк+1 осуществляют следующим образом (к = 1, 2, ...). Направление перемещения ак из точки Мк ищут так, чтобы:

('grad Днк<*к>0,

< gradФ,|Uk■ ак<О, І6/(Мк)f] 1И, {9Щ Ц^Ф,Ц ос*<0, i€l(Mk)fI„

 

где/(Л/*) = {»'єЛФ((А/*)=0}.

Заметим, что если вектора, удовлетворяющего условиям (9.76), не существует, то Мк — оптимальное решение задачи максимизации.

Пусть ак=(ак); ajj4; а і*') удовлетворяет условиям (9.76). Тогда существует число Т>0 такое, что при всех t, 0<1<Т,

f (Mk. ,)>f(Mk) и Mk, ,еП, (9.77)

 

где A/*,, (x* + akh; хф+афг,     x^ + aft).

После того как определено направление перемещения ак, необходимо подобрать значение />0 так, чтобы выполнялись условия (9.77). Это можно сделать, перебрав несколько доста-

точно малых значений t. Если tk — найденное значение параметра /, то полагают

 

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

О Рассмотрим задачу максимизации функции

/(A/)=13x, + 3x2 + 17x3-xf-x^-JC3

на множестве

й-{М (х,; хг хг) | Ф, (М) = 2х] + Ъх + х-24^Ъ, Ф2 (Af)=xl + 2x2 + xi~6^0, Ф3 (М)= -х2Щ.

Эта задача удовлетворяет условиям I—III. Заметим, что grad/={13-2*,; 3-2*2; 17-2х3}, grad^,^*,; 6х2; 2х3}, grad02={l; 2; 1}, gradOj = {0; 0}.

 

Рассмотрим точку Л/, (1; 1; 1)є£ї. Тогда

ЛА/,)=30; Ф. (А/,)=г - 18; Ф2 (А/,)= -2; Ф,(А/,)=-1;втасі/|Иі = {11; 1; 15}.

Направление перемещения <ti = (a\{) а2"; a30) определим из условия llaj^+a^ + lSflj'^O (grad/|M а,>0). Положим а, = (2; 1; 2). Тогда Л/,,, (1 +2/; 1 +1; 1 +2/). При' /=1/3 имеем М2 (5/3,4/3, 5/3), причем

 

Положим а2 = (1; -2; 1). Тогда Мг , (5/з + '; 4/з~2/; 5/э + ')-Если /=2/3, то Л/э (7/3, 0, 7/3) и

/(M3)=59V»; Ф, (А/э)= -72/3; Ф2 (А/3)= -4А;

Фі(АГ3) = 0; grad/|w, = {2S/3; 3; 37/3}.

Направление а3 = (а5э); ді3'; а33)) определим из условий f"/3flf + 3а23> + 37/эа33)>0,

 

Положим а3 = (—1; 0; 1). В этом случае Мх , Ch~К 0; 7/э + 0 Если (=1/3, то А/4 (2; 0; 4). Тогда

/(А/4) = 74; Ф, (АЛ) = 0; Ф2 (А/4) = 0; Ф3(А/4) = 0; grad/U={9; 3; 9}.

4

Направление а4 = (д}4); a24)l я34)) определим из условий:

(9а*)+3а[4> + 9а?>0, J 8a j4>+0a (4> + 8a І4) < 0 (grad Ф, Ц а, < 0),

] аі4Ч2а24Ча34)<0,

 

Если сложить третье и четвертое неравенства, умноженные на подходящие числа, то получим

9аї4ЧЗа24Ч9а34Ч0,

что противоречит первому неравенству. Допустимого направления не существует. Значит, М4 (2; 0; 4) — оптимальное решение данной задачи.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 |