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

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

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

Задача максимизации (9.59)—(9.61) называется задачей выпуклого программирования в том случае, когда все функции Ф; {М)

являются выпуклыми, а целевая функция/ (М) — вогнутой на R".

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

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

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

Говорят, что множество

ҐІ = {Л/єІІ}|Ф,(іИ)*;0, і=1, 2, т)

удовлетворяет условию Слейтера, если существует уточка MeQ такая, что для всех нелинейных функций Ф, (М), Ф, (М)<0.

О Множество £1 = {М (хи х2 х3)€К3|Ф, (М) = х+х22 +

+ х э —           Ф2 (M) = xt + *2 + *з — 3^0} удовлетворяет условию

Слейтера, так как если М (1, 1, 1), то Ф, (А/)=-1<0, Ф2 (А0=0. •

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

Предположим, что допустимое множество задачи выпуклого программирования (9.59)——(9.61) удовлетворяет условию Слейтера. Тогда имеют место следующие утверждения:

1. Точка A/0eRJ является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда существует точка P0€(Rmy такая, что (Ма, Р0) будет седловой точкой функции Лагранжа для этой задачи.

На основании этого утверждения построена теория двойственности в выпуклом программировании.

2. Если функции/(Л/) и Ф, (Л/), j= 1, 2, т, дифференцируемы в точке A/0eR}, то эта точка является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда она является точкой Куна—Таккера для этой задачи.

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

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

(9.66)

х^О, Xj^O (9.67)

f=5xl + 2x2+4xi-x]-x22-xl (max), (9.65) (9х? + 6х3г-15^0, д:, -t-2x2+x3 — 5^0,

и точку M0 (1; 1; 1).

Функция Лагранжа для задачи (9.65)—(9.67) имеет вид

L (х,, х2, хь у,, y2) = 5xi+2x2+4x3-x2-x22-xl-

-у, (9х? + 6х3-15)--у2 (х,+2х2+х3-5).

Запишем условия Куиа—Таккера:

5-2х1-18у,х1-у2<0, 9х2+6х3-15^0,

2-2х2-2у2 = 0,           xj +2x2+^-5^ 0,

4-2х3-12у1Хз-у2<0, (9xj + 6x]-l5) Уі = 0,

(5-2х,-18у1х,-у2) х, = 0,       (х1 + 2х2-г-хэ-5)^ = 0.

(4-2ХЗ-12У.ХЗ-У2) х3 = 0,

Полагая в этой системе х, = 1, х2= 1, х3 = 1, найдем у, = 1/6, у2 = 0. Поэтому А/о (1; 1; 1) является точкой Куна—Таккера для задачи (9.65>—(9.67). Следовательно, А/0 (1; J; 1) — оптимальное решение этой задачи, ф

 

Страница: | 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 |