Промышленный лизинг Промышленный лизинг  Методички 

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 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 [ 253 ] 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

dcw3drwt

Поскольку Н. является неопределенной матрицей, стационарная точка не будет точкой максимума.

На самом деле полученный результат не является неожиданным, поскольку (небазисные) переменные w3 и ш4 (и, следовательно, х3 и х4) равняются нулю, как и предусмотрено теорией линейного программирования. Следовательно, решение, полученное с помощью метода Якоби, определяет ту или иную крайнюю точку пространства допустимых решений рассматриваемой задачи, которая связана с конкретным выбором векторов Y и Z. При этом найденное решение может как быть, так и не быть оптимальным. Однако метод Якоби позволяет распознать оптимальное решение задачи путем использования достаточных условий экстремума.

Приведенные рассуждения свидетельствуют о том, что для оптимального решения задачи линейного программирования необходимо менять конкретный выбор Y и Z, пока не будут выполнены достаточные условия. Пусть, например, Y = (ц>2, wt) и Z = (ц> w3). Тогда соответствующий приведенный градиент принимает вид

VJ = (4w 0)-(6w2,0)

2ve2 l

f2w, 2w,

2ve3 0

=(-2wp6wj).

Соответствующая стационарная точка определяется значениями wl = О, w2 w3 = 0, wt=J&. Так как матрица

-2 0}

0 -6)

является отрицательно определенной, то указанная точка - точка максимума.

Полученный результат можно проверить графически, используя рис. 20.6. Первое из найденных решений (дг, = 4, дс2 = 1) не является оптимальным, в то время как второе (х, = 0, дс2 = 5) оказывается таковым. Читатель имеет возможность проверить, что две оставшиеся крайние точки пространства допустимых решений не являются точками максимума. Кроме того, с использованием достаточных условий экстремума можно показать, что в точке дг, = 0, дс2 = 0 возникает минимум целевой функции рассматриваемой задачи.

Заметим, что введенные ранее коэффициенты чувствительности VYj/J в задаче

линейного программирования являются переменными двойственной задачи. Чтобы проиллюстрировать это на рассматриваемом численном примере, обозначим через и, и и2 соответствующие переменные двойственной задачи. В оптимальной точке и>1 = 0, w2 = VJ, w3 = 0, w4 = переменные двойственной задачи вычисляются по формуле

( 2) = VYr=(6w2,0)

24 2w4

=(3,0).




Рис. 20.6. Пространство решений задачи ЛП

В точке (3, О) целевая функция двойственной задачи равна 5и, + Зиг = 15 и совпадает с оптимальным значением целевой функции прямой задачи. Полученное решение также удовлетворяет ограничениям двойственной задачи, т.е. является допустимым и, следовательно, оптимальным. Это значит, что коэффициенты чувствительности совпадают с переменными двойственной задачи линейного программирования.

Из процедуры применения метода Якоби к решению задач линейного программирования можно сделать несколько общих выводов. Рассмотренный численный пример показывает, что в силу необходимых условий экстремума независимые переменные задачи равны нулю. Достаточные же условия указывают на то, что матрица Гессе является диагональной. Следовательно, все диагональные элементы этой матрицы должны быть положительными, если в рассматриваемой точке имеет место минимум, и отрицательными - в случае максимума.

Из вышесказанного следует, что необходимое условие экстремума равносильно указанию на то, что оптимальное решение задачи следует искать только среди ее базисных решений. В этом случае в качестве небазисных переменных задачи линейного программирования выступают независимые переменные. Достаточное же условие приводит к выводу, что между диагональными элементами матрицы Гессе и разностями zf - с, задачи линейного программирования (см. раздел 7.2), получаемыми с помощью симплекс-метода, существует строгое соответствие.1

УПРАЖНЕНИЯ 20.2.2

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

1 Формальное доказательство справедливости этих утверждений для общей задачи линейного программирования можно найти в статье Taha Н. and Curry G. Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs , Operations Research, Vol. 19, 1971, pp.1045-1049. В этой статье показано, что все основные положения симплекс-метода могут быть получены с помощью метода Якоби.



a) Будут ли производные новой целевой функции (выраженные через переменную х3) отличаться от полученных с помощью метода Якоби?

b) В чем основное отличие описанной процедуры решения задачи от метода Якоби?

2. Примените метод Якоби к решению задачи из примера 20.2.1, выбирая Y = (x2, х3) и Z = (x,).

3. С помощью метода Якоби решите следующую задачу.

Минимизировать /(X) = х,2

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

П* = с,

где С - положительная константа. Пусть теперь правая часть ограничения равна С + S, где S- малое положительное число. Найдите соответствующее изменение оптимального значения целевой функции /.

4. Решите методом Якоби следующую задачу.

Минимизировать /(X) = 5.x,2 + лг2 + 2х,х2

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

g(X) = Xlx2 - 10 = 0.

a) Найдите изменение оптимального значения целевой функции /(X), если ограничение задачи примет вид хух2 - 9,99 = 0.

b) Найдите изменение значения целевой функции /(X) в окрестности допустимой точки (2, 5) при условии, что х1х2 = 9,99 и Эх, = 0,01.

5. Решите следующую задачу.

Максимизировать /(X) = х2 + 2х\ + КЪг2 + 5х,х2

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

g, (X) = х, + х\ + Ъхгхг -5 = 0,

g2 (X) = х,2 + 5х,х2 + х32 - 7 = 0.

Используйте метод Якоби для нахождения df(X) в окрестности допустимой точки (1, 1, 1). Пусть указанная окрестность определяется условиями dgl = -0,01, dg2 = 0,02 и дх1 = 0,01.

6. Решите следующую задачу.

Минимизировать /(X) = х,2 + х\ + х] + х\

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

g,(X) = хг + 2х2 + Зха + 5xt - 10 = 0,

g2(X) = х1 + 2х2 + 5х3 + 6х4 -15 = 0.

а) Покажите, что при выборе х3 и xt в качестве независимых переменных метод Якоби не дает оптимального решения.



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 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 [ 253 ] 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292