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

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

В разделе 2.3 мы графически показали, что оптимальное (конечное) решение двухмерной задачи ЛП соответствует крайней (угловой) точке пространства допустимых решений. Этот результат основан на том факте, что в задачах ЛП любая допустимая точка представима как функция крайних точек пространства решений. Например, в выпуклом множестве на рис. 7.1, а имеется шесть крайних точек X Х2, Х6, произвольную допустимую точку X можно представить как линейную комбинацию крайних точек:

X - оцХ, + сс2Х2 + ОзХ3 + сс4Х4 + сс5Х5 + сс6Х6,

где все коэффициенты ос, > 0 и выполняется равенство

Таким образом, множество крайних точек полностью определяет пространство допустимых решений.

Пример 7.1.1

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

С = {(х х,) х, < 2, х2< 3, х, > 0, х2 >0}. Пусть X, ={х л2} и X, = [х;,х;) - две различные точки из множества С. Если множество С выпукло, тогда точка X = (х хг) = otjX, + ос-Д., должна принадлежать этому множеству. Чтобы точка X принадлежала множеству С, ее координаты должны удовлетворять неравенствам, которые определяют это множество.

х, = a,xj + a, xj* < a, х 2 + a, х 2 = 2 .

x, = asx\ + a2x\ < a, x3 + a, x3 = 3 .

Таким образом (поскольку a, + a2 = 1), x, < 2 и x2 < 3. Так как коэффициенты a, и otj неотрицательны, то координаты также удовлетворяют условиям неотрицательности.

УПРАЖНЕНИЯ 7.1.1

1. Покажите, что множество Q = {xt, х21 х, + х2 < 1, х, > 0, х2 > 0} выпуклое. Существенно ли в данном случае условие неотрицательности переменных?

2. Покажите, что множество Q = {х х2 х> 1 или х2 > 2} не является выпуклым.

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

Q = {х х21 х, + х2 < 2, х, > 0, х2 > 0}.

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

4. Представьте внутреннюю точку (3, 1) пространства решений, показанного на рис. 7.2, как выпуклую комбинацию крайних точек А, В, С и D, где каждая крайняя точка должна иметь строго положительный весовой коэффициент.



5 4 3 2 1

О 1 2 3 4 5 6 Рис. 7.2. Пространство решений для упражнения 4

7.1.1. Базисные решения

В этом разделе задачу ЛП, записанную в стандартной форме (см. раздел 3.1), представим в новой форме записи с использованием матричных обозначений. Обозначим

через X = (х х2.....хп)т n-мерный вектор переменных, через А - матрицу размер

тхп, содержащую коэффициенты левых частей ограничений, b = (ft b2, bm)T - m-мерный вектор правых частей ограничений, С = (cv с2, сп) - л-мерный вектор коэффициентов целевой функции. С помощью матричной формы записи стандартную задачу ЛП можно представить следующим образом.

Максимизировать или минимизировать г = СХ

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

АХ = Ь, Х>0.

На основе стандартной формы для симплекс-таблиц из главы 3 (см. также рис. 4.1) т крайних справа столбцов матрицы А всегда можно представить в виде единичной матрицы I, для чего, возможно, придется надлежащим образом расположить переменные и использовать при необходимости искусственные переменные.

Базисное решение системы уравнений АХ = b получается путем присвоения п -т переменным нулевых значений и последующим решением системы из т уравнений относительно оставшихся т переменных (предполагается, что эта система имеет единственное решение). Теория линейного программирования устанавливает следующее соответствие между геометрическим определением крайних точек и алгебраическим определением базисного решения.

Крайние точки множества {X АХ = Ь} <=> Базисные решения системы АХ = Ь. Это соответствие означает, что все крайние точки области решений задачи ЛП полностью определяются базисными решениями системы АХ = b и наоборот. Отсюда следует, что множество базисных решений содержит всю информацию, необходимую для оптимального решения задачи ЛП. Более того, если наложить условия неотрицательности X > 0, поиск оптимального решения ограничится только множеством допустимых базисных решений.




Чтобы формализовать определение базисного решения, представим систему АХ = b в векторной форме

где вектор Р; - j-й столбец матрицы А. Подмножество из т векторов Ру формирует базис В тогда и только тогда, когда эти векторы линейно независимы. Для этого необходимо (и достаточно), чтобы определитель матрицы В, состоящей из данных т векторов, был отличен от нуля, т.е. det(B) Ф О.1 В этом случае матрица В называется невырожденной. Обозначим через Хв вектор из т переменных, ассоциированных с векторами Р;, составляющих невырожденную матрицу В. Тогда Хв будет базисным решением, если он будет решением системы ВХВ = Ь.

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

XB = Bb.

Если выполняется неравенство B b > 0, тогда Хв будет допустимым решением.

В заключение отметим, что количество базисных решений у системы из т уравнений с п неизвестными не превышает величины

т\(п - т)\

Пример 7.1.2

Найдем и классифицируем (как допустимые или недопустимые) все базисные решения следующей системы уравнений


В следующей таблице показаны все базисные решения. Матрица, обратная к матрице В, вычислена методами, приведенными в разделе А.2.7.

BXs = b

Решение

Статус

(Рь Рг)

(Pi. Рз) (Рг, Рз)

Не является базисом

3>

1 \*

( Л

1 1

4 8

1 3

ч~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 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