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

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

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

Задача максимизации (9.59)—(9.61) называется задачей выпуклого программирования в том случае, когда все функции Ф,(АГ) являются выпуклыми, а целевая функция f{M) — вогнутой на R".

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

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

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

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

Q = {Me Щ | Ф.(уМ) < О, /= 1, 2,т}

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

266

О Пример. Множество Q = {М(хр х2, х3) є R31 ФХ(М) - х1 + х + + Xі - 4 < О, Ф2(М) - Xj + х2 + хг - 3 < 0} удовлетворяет условию Слейтера, так как если М(1; 1; 1), то ФХ(М) - -1 < 0, Ф2(М) - 0. •

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

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

Точка MQ є R" является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда существует точка Р0 є (Rm)+ такая, что (MQ, PQ) будет седловой точкой функции Ла-гранжа для этой задачи.

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

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

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

(9.65)

(9.66) (9.67)

О Пример. Рассмотрим задачу выпуклого программирования /= 5jCj + 2х2 + 4х3 -х-х- х (max),

Ъх + 6х32 -15 < 0, [ху + 2х2 + х3 - 5 < 0, хх>0, х3>0

иточкуА/дЦ; 1; 1).

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

L(xvx2,xvyvy2) = = 5xj + 2х2 + 4х3-Xі-х-х- j1(9xj + 6х3 - 15) ~У2(Х + 2х2 + х3 - 5).

 

267

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

S-7xl-lSy^l-y2^0,   9х2 + 6х2-15<0,

2 - 2х2 - 2у2 = О,   Xj + 2х2 + х3 - 5 < 0,

4 - 2х3 - 12уЛ-у2<0,        (9х2 + 6х32 - 15)^ = О,

(5 - 2xj - 18j1x1 - у2)хх = О,    (Xj + 2х2 + х3 - 5)j>2 = 0.

(4 - 2х3 - 12ухх3 - у2)х3 = О,

Полагая xt = 1, х2 = 1, х3 = 1, найдем ух = 1/6, у2 = 0. Поэтому Af0(l; 1; 1) является точкой Куна — Таккера для задачи (9.65)—(9.67). Следовательно, Af0(l; 1; 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 | 191 | 192 | 193 |