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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
63
ï
î
ï
í
ì
+=
=×+
=
+
nkp
kpv
v
p
j
j
p
p
,,1,0
,,,1,
L
L
ae
и точку
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
-
-
-
n
v
v
v L
1
с координатами
ï
î
ï
í
ì
+=
=×-
=
-
.,,1,0
,,,1,
nkp
kpv
v
p
j
j
p
p
L
L
ae
Умножим равенство (3) на
e
и сложим результат с равенством (2).
Получим
(
)
(
)
bvAvA
k
j
j
j
j
k
k
=++++
eaea
L
1
1
1
. (4)
Умножим равенство (3) на
e
и вычтем результат из равенства (2). Тогда
(
)
(
)
bvAvA
k
j
j
j
j
k
k
=-++-
eaea
L
1
1
1
. (5)
Из соотношений (4), (5) следует, что при достаточно малом 0
>
e
имеют
место включения UvUv ÎÎ
+-
, . Кроме того,
2
-+
+
=
vv
v
и, значит,
-+
-+= vvv )1(
aa
,
()
1,0
2
1
Î=
a
.
По условию теоремы
v
– угловая точка множества U , поэтому
-+
= vv
.
Тогда
0
1
===
k
aa
L
,
что противоречит сделанному предположению. Таким образом, набор
столбцов
k
jj
AA ,,
1
L
линейно независим и rk
£
.
Если rk
=
, то необходимость уже доказана. В качестве номеров
r
jj ,,
1
L
следует взять номера столбцов
k
jj
AA ,,
1
L
( rk
=
). Если rk
<
, то к столбцам 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                  jp
                                        ìïv j p + e × a p , p = 1, L, k ,
                             v   +     =í
                                         ïî0, p = k + 1, L, n

              æ v 1- ö
              ç ÷
и точку v - = ç L ÷ с координатами
              ç n÷
              è v- ø

                                  jp
                                        ìïv j p - e × a p , p = 1,L , k ,
                             v   -     =í
                                         ïî0, p = k + 1,L , n .

     Умножим равенство (3) на e и сложим результат с равенством (2).
Получим

                             (               )                 (
                          A j1 v j1 + ea1 + L + A jk v jk + ea k = b .    )      (4)

     Умножим равенство (3) на e и вычтем результат из равенства (2). Тогда

                             (               )                 (
                          A j1 v j1 - ea1 + L + A j k v jk - ea k = b .   )      (5)

     Из соотношений (4), (5) следует, что при достаточно малом e > 0 имеют
место включения v - Î U , v + Î U . Кроме того,

                                                      v + + v-
                                                 v=
                                                          2

     и, значит,

                                                                   1
                            v = av + + (1 - a )v - , a =             Î (0,1) .
                                                                   2

     По условию теоремы v – угловая точка множества U , поэтому v + = v- .
Тогда

                                           a1 = L = a k = 0 ,

что противоречит сделанному предположению. Таким образом, набор
столбцов A j ,L, A j линейно независим и k £ r .
            1      k




     Если k = r , то необходимость уже доказана. В качестве номеров j1 ,L, j r
следует взять номера столбцов A j ,L, A j ( k = r ). Если k < r , то к столбцам
                                                 1         k




                                                      63

Страницы