Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 78 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

Составители: 

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
78
В первом случае
Æ
=
U . Действительно, если бы существовала точка
U
u
Î
,
то выполнялось бы Z
u
z Î
÷
÷
ø
ö
ç
ç
è
æ
=
0
и )(0)(
11 *
<= zIzI , что невозможно.
Пусть имеет место второй случай. Тогда
m
wwzI
***
++==
L
1
1
)(0 .
В силу 0
³
w отсюда выводим
(
)
0,0
1 **
**
=Þ=== vzww
m
L
.
Покажем, что
*
v – угловая точка множества
U
. Неравенство 0³
*
z влечет
за собой неравенство 0³
*
v , а включение Zz Î
*
– равенство bAv =
*
. Таким
образом, Uv Î
*
. Рассмотрим представление точки
*
v
(
)
21
1 uuv
aa
-+=
*
, )1,0(
Î
a
, Uuu Î
21
, . (1)
Докажем, что оно возможно лишь когда
21
uuv ==
*
. Точки
÷
÷
ø
ö
ç
ç
è
æ
=
÷
÷
ø
ö
ç
ç
è
æ
=
0
,
0
2
2
1
1
u
z
u
z
принадлежат
, а из равенства (1) следует, что
21
)1( zzz
aa
-+=
*
. (2)
Точка
*
z
– угловая для множества
, и поэтому ее представление (2)
возможно лишь при
21
zzz ==
*
. Тогда
21
uuv ==
*
и точка
*
v является угловой для
допустимого множества исходной задачи.
Таким образом, доказано, что если допустимое множество задачи 2 не
пустое, то оно содержит угловую точку. В этом случае, не теряя общности,
можно считать, что
[]
rangArm
==
. Действительно, ограничения задачи
содержат ровно
r
независимых непротиворечивых равенств. Остальные
равенства являются их линейными комбинациями и могут быть отброшены.
Тогда процедура симплекс метода, описанная в п. 4, позволяет либо получить
решение задачи 2 в виде угловой точки допустимого множества, либо
установить неограниченность решения. Приведенные выше рассуждения 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


     В первом случае U = Æ . Действительно, если бы существовала точка u ÎU ,
                            æu ö
то выполнялось бы z = çç ÷÷ Î Z и I 1 ( z ) = 0 < I 1 ( z * ) , что невозможно.
                       è 0ø

     Пусть имеет место второй случай. Тогда

                                      0 = I 1 ( z * ) = w*1 + L + w*m .

     В силу w ³ 0 отсюда выводим

                                   w1* = L = w m* = 0 Þ z * = (v * ,0 ) .

     Покажем, что v* – угловая точка множества U . Неравенство z * ³ 0 влечет
за собой неравенство v* ³ 0 , а включение z * Î Z – равенство Av* = b . Таким
образом, v * ÎU . Рассмотрим представление точки v *

                           v * = au1 + (1 - a )u 2 , a Î (0,1) , u1 , u 2 Î U .                  (1)

                                                                                         æu ö   æu ö
     Докажем, что оно возможно лишь когда v * = u1 = u 2 . Точки z1 = çç 1 ÷÷, z 2 = çç 2 ÷÷
                                                                       è0ø            è0ø
принадлежат Z , а из равенства (1) следует, что

                                            z * = az1 + (1 - a ) z 2 .                           (2)

     Точка z * – угловая для множества Z , и поэтому ее представление (2)
возможно лишь при z * = z1 = z 2 . Тогда v * = u1 = u 2 и точка v* является угловой для
допустимого множества исходной задачи.

     Таким образом, доказано, что если допустимое множество задачи 2 не
пустое, то оно содержит угловую точку. В этом случае, не теряя общности,
можно считать, что            rang[ A] = r = m .          Действительно, ограничения задачи
содержат ровно r           независимых непротиворечивых равенств. Остальные
равенства являются их линейными комбинациями и могут быть отброшены.
Тогда процедура симплекс метода, описанная в п. 4, позволяет либо получить
решение задачи 2 в виде угловой точки допустимого множества, либо
установить неограниченность решения.                      Приведенные             выше   рассуждения



                                                     78

Страницы