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

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
формулы изменения компонент опорного плана при переходе от A
1
,A
2
,...,A
l−1
,A
l
,A
l+1
,...,A
m
к
базису A
1
,A
2
,...,A
l
,A
k
,A
l+1
,...,A
m
имеют вид
x
i
= x
∗
i
−
x
∗
l
x
lk
x
ik
x
k
=
x
∗
l
x
l
k
При переходе к новому базису изменяются и коэффициенты разложения вектора A
j
по векторам
базиса. Как это происходит, видно из следующих тривиальных преобразований. Для нашего случая
при базисе, состоящем из первых m векторов, имеем
A
j
= x
1j
A
1
+ x
2j
A
2
+ ···+ x
lj
A
l
+ ···+ x
mj
A
m
(17)
в том числе для j = k
A
k
= x
1k
A
1
+ x
2k
A
2
+ ···+ x
lk
A
l
+ ···+ x
mk
A
m
.Отсюда
A
l
=
1
x
lk
(A
k
−
i=l
x
ik
A
i
)
и подставляя в (17), получаем разложение A
j
по векторам нового базиса
A
1
,...,A
l−1
,A
k
,A
l+1
,...,A
m
.
A
j
=(x
ij
−
x
lj
x
lk
)A
1
+ ···+
x
lj
x
lk
A
k
+ ···+(x
mj
−
x
lj
x
lk
)A
m
Таким образом, формулы пересчета коэффициентов разложения имеют вид
x
ij
= x
ij
−
x
lj
x
lk
x
ij
,i= k
x
kj
=
x
lj
x
lk
Здесь штрих обозначает компоненты нового вектора коэффициентов разложения вектор-столбца
A
j
. Замена одного базисного вектора A
l
на другой вектор геометрически означает переход от одной
крайней точки (вершины) к другой. Однако, такой переход должен быть направленным, то есть
должен вести к уменьшению линейной формы. Рассмотрим, как осуществить выбор вектора A
k
,
включаемого в базис, чтобы это привело к уменьшению значения целевой функции.
Для этого достаточно проследить, как изменяется значение линейной формы при смене базиса.
Используя формулы перехода от одного опорного плана к другому, можно легко получить, что на
новом опорном плане x
(c, x
)=(c, x
∗
) − Θ
0
(c
0
,x
k
)+Θ
0
c
k
=(c, x
∗
) − Θ
0
(z
k
− c
k
)
где z
k
=
m
i=1
c
i
x
ik
=(c
0
,x
k
). Вообще говоря, Θ
0
зависит от индекса k, пренебрегая этой зависимо-
стью, мы видим, что в базис необходимо вводить вектор A
k
, для которого
z
k
− c
k
= max
j
(z
j
− c
j
),z
j
− c
j
> 0 (18)
Вообще говоря, в базис можно вводить и любой другой вектор A
j
, для которого z
j
− c
j
> 0, но при
таком выборе значение линейной формы уменьшается наиболее быстро.
Правило выбора вектора a
l
, замещаемого в базисе вектором A
k
, мы уже вывели: l определяется
индексом i, на котором достигается
min
i
x
∗
i
x
ik
=
x
∗
l
x
lk
=Θ
0
Если min достигается для нескольких l,томожновзятьзаl любое из них.
8

формулы изменения компонент опорного плана при переходе от A1 , A2 , . . . , Al−1 , Al , Al+1 , . . . , Am к
базису A1 , A2 , . . . , Al , Ak , Al+1 , . . . , Am имеют вид
                                                      
                                                                 x∗
                                                       xi = x∗i − l xik
                                                                  xlk
                                                             x∗
                                                       xk = l
                                                             xl k
При переходе к новому базису изменяются и коэффициенты разложения вектора Aj по векторам
базиса. Как это происходит, видно из следующих тривиальных преобразований. Для нашего случая
при базисе, состоящем из первых m векторов, имеем

                                 Aj = x1j A1 + x2j A2 + · · · + xlj Al + · · · + xmj Am                             (17)

в том числе для j = k

                                 Ak = x1k A1 + x2k A2 + · · · + xlk Al + · · · + xmk Am

. Отсюда
                                                                 1        
                                                Al =                (Ak −   xik Ai )
                                                                xlk
                                                                          i=l

и      подставляя          в       (17),     получаем            разложение     Aj     по     векторам   нового   базиса
A1 , . . . , Al−1 , Ak , Al+1 , . . . , Am .
                                            xlj               xlj                     xlj
                            Aj = (xij −         )A1 + · · · +     Ak + · · · + (xmj −     )Am
                                            xlk               xlk                     xlk
Таким образом, формулы пересчета коэффициентов разложения имеют вид
                                           x
                               xij = xij − lj xij , i = k
                                            xlk
                               xkj = xlj
                                       xlk
Здесь штрих обозначает компоненты нового вектора коэффициентов разложения вектор-столбца
Aj . Замена одного базисного вектора Al на другой вектор геометрически означает переход от одной
крайней точки (вершины) к другой. Однако, такой переход должен быть направленным, то есть
должен вести к уменьшению линейной формы. Рассмотрим, как осуществить выбор вектора Ak ,
включаемого в базис, чтобы это привело к уменьшению значения целевой функции.
    Для этого достаточно проследить, как изменяется значение линейной формы при смене базиса.
Используя формулы перехода от одного опорного плана к другому, можно легко получить, что на
новом опорном плане x

                           (c, x ) = (c, x∗ ) − Θ0 (c0 , xk ) + Θ0 ck = (c, x∗ ) − Θ0 (zk − ck )
        m
где zk = i=1 ci xik = (c0 , xk ). Вообще говоря, Θ0 зависит от индекса k, пренебрегая этой зависимо-
стью, мы видим, что в базис необходимо вводить вектор Ak , для которого

                                        zk − ck = max(zj − cj ),                zj − cj > 0                         (18)
                                                            j

Вообще говоря, в базис можно вводить и любой другой вектор Aj , для которого zj − cj > 0, но при
таком выборе значение линейной формы уменьшается наиболее быстро.
   Правило выбора вектора al , замещаемого в базисе вектором Ak , мы уже вывели: l определяется
индексом i, на котором достигается
                                                                 x∗i  x∗
                                                    min              = l = Θ0
                                                        i        xik  xlk
Если min достигается для нескольких l, то можно взять за l любое из них.

Страницы