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

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

примет значение 0 (как показано в таблице), т.е. получим вырожденное базисное решение. Оптимальное решение получается на следующей итерации.

Что же практически приводит к вырожденности решения? Рассмотрим рис. 3.9, графически представляющий решение этой задачи. Точка оптимума х, = О, хг - 2 является пересечением трех прямых. Поскольку данная задача двухмерна, эта точка переопределена (на плоскости для определения точки достаточно двух прямых), и, следовательно, одно из ограничений избыточно.

Оптимальное вырожденное решение


Рис. 3.9. Вырожденность задачи примера 3.5.1

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

С вычислительной и теоретической точек зрения вырожденность может привести к двум последствиям. Во-первых, в процессе вычислений может возникнуть зацикливание. Если в приведенной выше таблице сравнить первую и вторую итерации, то можно заметить, что значение целевой функции не изменилось (z = 18). Поэтому может возникнуть ситуация, когда при реализации симплекс-метода некоторая последовательность будет повторяться, не изменяя значения целевой функции и не приводя к завершению вычислительного процесса. Существуют методы, предотвращающие зацикливание, однако они значительно замедляют процесс вычислений. Поэтому в большинстве программ, реализующих симплекс-метод, отсутствуют специальные средства защиты от зацикливания, тем более, что вероятность зацикливания очень мала.

Во-вторых, последствие вырожденности решения можно обнаружить, сравнивая первую и вторую итерации в приведенной выше таблице. Хотя в этих итерациях состав базисных и небазисных переменных различен, значения всех переменных и значение целевой функции не изменяются:

х, = 0, х2 = 2, х3 = 0, х4 = 0, z = 18.

Можно ли, несмотря на то, что оптимальное решение не достигнуто, остановить вычисления на первой итерации (когда впервые обнаруживается вырожденность)? Ответ отрицательный, так как решение может быть только временно вырожденным (упражнение 3.5.1.2).



УПРАЖНЕНИЯ 3.5.1

1. Рассмотрите графическое представление пространства решений (рис. 3.10). Предположим, что выполнение симплекс-метода начинается из точки А, оптимальное решение соответствует точке D, а целевая функция такова, что в точке А вводимой переменной будет х,.

a) Покажите (на рисунке) крайние точки, которые соответствуют последовательности симплекс-итераций, приводящих к точке оптимума.

b) Определите максимально возможное число симплекс-итераций, необходимых для достижения оптимального решения.

2. Покажите (графически и с помощью TORA), что следующая задача имеет временно вырожденные решения.

Максимизировать z = Зх, + 2х2

при выполнении условий

3. Используя в программе TORA опции, позволяющие управлять процессом вычислений, выполните последовательность симплекс-итераций в следующей задаче ЛП (задача придумана Е. М. Beale). Начальное допустимое базисное решение, состоящее из дополнительных переменных, повторится на седьмой итерации. Этот пример иллюстрирует явление зацикливания при выполнении симплекс-метода; в этом случае оптимальное решение никогда не будет достигнуто.


Рис. 3.10. Пространство решений для упражнения 1

4х, + 3х2<12, 4х, - х2< 8, 4х,+ х2<8, х х2>0.

Максимизировать z


при выполнении условий

8х2 - х3 + 9х4 < 0,



12х,

>--х* + Зх. < 0.

2 2



х,<1,

Х2> 3 Х4 ~

Интересно отметить, что если сделать все коэффициенты в этой задаче целыми (путем умножения на соответствующие множители), то алгоритм симплекс-метода достигнет оптимального решения за конечное число итераций (проверьте это!).

(Предостережение. Не используйте программу TORA в автоматическом режиме, так как в этом случае циклические вычисления будут выполняться бесконечно.)

3.5.2. Альтернативные оптимальные решения

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

Пример 3.5.2. Бесконечное множество решений

Рассмотрим следующую задачу ЛП.

Максимизировать z = 2xx + 4х2

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

л-, + 2х2 < 5, х, + х,<4, xvx2>0.

На рис. 3.11 показано множество альтернативных оптимальных решений, которые являются следствием того, что прямая, представляющая целевую функцию, параллельна прямой;- соответствующей связывающему ограничению. Каждая точка отрезка ВС соответствует оптимальному решению со значением целевой функции z = 10. Последовательные итерации выполнения симплекс-метода представлены в следующей таблице.

Итерация

Базис

Решение

Начальная

Вводится хг

Исключается *з

Первая (оптимум)

Вводится Х\

Исключается хд

-1/2

Вторая

(альтернативный

оптимум)



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