Задача линейного программирования. Горячев Л.В. - 7 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

7
вершину проходит более, чем n гиперплоскостей. Таким образом, вырожденному опорному плану
может отвечать несколько базисов.
Из сказанного следует, что переход от одной вершины к другой равносилен переходу от одного
базиса к другому. Сформулируем правила этого перехода.
Итак, пусть мы имеем задачу ЛП канонического вида (10)–(13) и пусть известен ее опорный
план x
∗
=(x
∗
1
,x
∗
2
,...,x
∗
n
). Не ограничивая общности рассуждений, положим, что он не вырожден
и базис его состоит из первых m векторов-столбцов матрицы A. Тогда имеем, что
x
∗
1
A
1
+ x
∗
2
A
2
+ ···+ x
∗
m
A
m
= b (13)
x
∗
m+1
= x
∗
m+2
= ···= x
∗
n
=0
Обозначим через B =(A
1
,A
2
,...,A
m
), тогда из (14)
x
∗
=(x
∗
1
,x
∗
2
,...,x
∗
m
)=B
−1
b −
n
j=m+1
B
−1
A
j
x
∗
j
Введем обозначения
x
j
= B
−1
A
j
=
x
1j
x
2j
.
.
.
x
mj
Легко видеть, что x
j
— вектор коэффициентов разложения вектора A
j
по векторам базиса
A
1
,A
2
,...,A
m
.
При этих обозначениях
x
∗
= B
−1
b −
n
j=m+1
X
j
x
∗
j
,x
∗
j
=0,j= m +1,...,n (14)
Допустим, что мы переходим к другому опорному плану, который отличается от нашего тем, что
одна из базисных компонент замещена переменной x
k
(k>m). Это означает, что один из векторов
базисного плана
x
∗
заменяется на вектор A
k
. Тогда из (??) мы получаем
X = B
−1
b = B
−1
A
k
Θ (15)
,гдеΘ — значение x
k
, которое мы должны определить. Покомпонентно равенство (15) запишется
так:
x
1
= x
∗
1
− x
1k
Θ
x
2
= x
∗
2
− x
2k
Θ
.
.
.
x
m
= x
∗
m
− x
mk
Θ
x
k
=Θ, Θ > 0
(16)
Все оставшиеся x
j
=0, j =1, 2,...,l− 1,l+1,...,m, j = k.
Для того, чтобы план (16) был опорным, необходимо, чтобы общее число ненулевых компонент
было равно m (меньше m в случае вырожденности нового опорного плана). Очевидно, что Θ должно
удовлетворять условиям
x
i
= x
∗
i
− Θx
ik
≥ 0,i=1, 2,...,m
x
k
=Θ> 0
Из этих условий с очевидностью вытекает, что для Θ=Θ
0
= min
i
(x
i
/x
ik
), при x
ik
> 0 одна из
компонент плана (16) обратится в нуль, ее заменит x
k
=Θ.Еслиmin достигается только для
одного i, то новый опорный план также невырожден, в противном случае будем иметь вырожденный
опорный план. Если положить для определенности, что min достигается на i = l, то, очевидно,
                                                                                                    7

вершину проходит более, чем n гиперплоскостей. Таким образом, вырожденному опорному плану
может отвечать несколько базисов.
   Из сказанного следует, что переход от одной вершины к другой равносилен переходу от одного
базиса к другому. Сформулируем правила этого перехода.
   Итак, пусть мы имеем задачу ЛП канонического вида (10)–(13) и пусть известен ее опорный
план x∗ = (x∗1 , x∗2 , . . . , x∗n ). Не ограничивая общности рассуждений, положим, что он не вырожден
и базис его состоит из первых m векторов-столбцов матрицы A. Тогда имеем, что

                                        x∗1 A1 + x∗2 A2 + · · · + x∗m Am = b                      (13)

                                         x∗m+1 = x∗m+2 = · · · = x∗n = 0
Обозначим через B = (A1 , A2 , . . . , Am ), тогда из (14)
                                                                           n
                                                                           
                             x∗ = (x∗1 , x∗2 , . . . , x∗m ) = B −1 b −           B −1 Aj x∗j
                                                                          j=m+1

Введем обозначения                                                         
                                                                     x1j
                                                                    x2j    
                                                                           
                                            xj = B −1 Aj =           ..    
                                                                      .    
                                                                    xmj
Легко видеть, что xj — вектор коэффициентов разложения вектора Aj по векторам базиса
A1 , A2 , . . . , Am .
    При этих обозначениях
                                           n
                                           
                         x∗ = B −1 b −            Xj x∗j ,       x∗j = 0, j = m + 1, . . . , n    (14)
                                         j=m+1

   Допустим, что мы переходим к другому опорному плану, который отличается от нашего тем, что
одна из базисных компонент замещена переменной xk (k > m). Это означает, что один из векторов
базисного плана x∗ заменяется на вектор Ak . Тогда из (??) мы получаем

                                              X = B −1 b = B −1 Ak Θ                              (15)

, где Θ — значение xk , которое мы должны определить. Покомпонентно равенство (15) запишется
так:                                          ∗
                                       x1 = x1∗ − x1k Θ
                                      
                                      
                                      
                                       x2 = x2 − x2k Θ
                                      
                                        ..                                              (16)
                                        .
                                      
                                               ∗
                                      
                                        x  = x   − x    Θ
                                       m       m    mk
                                         xk = Θ, Θ > 0
Все оставшиеся xj = 0, j = 1, 2, . . . , l − 1, l + 1, . . . , m, j = k.
   Для того, чтобы план (16) был опорным, необходимо, чтобы общее число ненулевых компонент
было равно m (меньше m в случае вырожденности нового опорного плана). Очевидно, что Θ должно
удовлетворять условиям
                                xi = x∗i − Θxik ≥ 0, i = 1, 2, . . . , m
                                                     xk = Θ > 0
Из этих условий с очевидностью вытекает, что для Θ = Θ0 = min(xi /xik ), при xik > 0 одна из
                                                                                      i
компонент плана (16) обратится в нуль, ее заменит xk = Θ. Если min достигается только для
одного i, то новый опорный план также невырожден, в противном случае будем иметь вырожденный
опорный план. Если положить для определенности, что min достигается на i = l, то, очевидно,

Страницы