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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
62
{
}
0, ³=Î= ubAuRuU
n
.
Здесь
A
– матрица размера
,
n
m
´
n
m
£
,
{
}
mrArang ,,1
L
Î= . Символом
{
}
njA
j
,,1,
L
Î обозначим
й
j
-
столбец матрицы
A
и заметим, что равенство
bAu
=
эквивалентно равенству
buAuA
n
n
=++
L
1
1
. (1)
Теорема 1. Для того чтобы точка
U
v
Î
была угловой точкой множества
U , необходимо и достаточно существование номеров
{
}
njj
r
,,1,,
1
L
L
Î , таких,
что
1) столбцы
r
jj
AA ,,
1
L
матрицы А линейно независимы;
2) 0=
j
v , если
{
}
r
jjj ,,
1
L
Ï .
Доказательство. Необходимость. Пусть
U
v
Î
– угловая точка. Сначала
предположим, что 0
=
v . Ранг матрицы
A
равен
r
, поэтому существует набор
линейно независимых столбцов
r
jj
AA ,,
1
L
этой матрицы. Номера
r
jj ,,
1
L
удовлетворяют условиям теоремы. Для случая 0
=
v теорема доказана.
Пусть теперь 0
¹
v и
k
j
j
vv ,,
1
L
– все положительные координаты точки
v
(остальные равны нулю). Тогда из равенства
bAv
=
, записанного в форме (1),
следует
bvAvAAv
k
k
j
j
j
j
=×++×=
L
1
1
. (2)
Покажем, что столбцы
k
jj
AA ,,
1
L
линейно независимы. От противного
приходим к существованию ненулевого набора чисел
1
1
,, R
k
Î
aa
L
, для которых
имеет место равенство
0
1
1
=++
k
jkj
AA
aa
L
. (3)
Построим точку
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
+
+
+
n
v
v
v L
1
с координатами 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                            U = {u Î R n Au = b, u ³ 0}.

      Здесь A – матрица размера m ´ n, m £ n , rang[A] = r Î {1,L, m} . Символом
A j , j Î {1,L , n} обозначим j - й столбец матрицы A и заметим, что равенство

Au = b эквивалентно равенству

                                        A1u 1 + L + An u n = b .                                       (1)

      Теорема 1. Для того чтобы точка v ÎU была угловой точкой множества
U , необходимо и достаточно существование номеров j1 ,L, j r Î {1,L , n} , таких,

что

      1) столбцы A j ,L, A j матрицы А линейно независимы;
                          1       r




      2) v j = 0 , если j Ï { j1 , L, j r }.

      Доказательство. Необходимость. Пусть v ÎU – угловая точка. Сначала
предположим, что v = 0 . Ранг матрицы A равен r , поэтому существует набор
линейно независимых столбцов A j ,L , A j                    1        r
                                                                          этой матрицы. Номера   j1 , L, j r

удовлетворяют условиям теоремы. Для случая v = 0 теорема доказана.

      Пусть теперь v ¹ 0 и v j ,L, v j – все положительные координаты точки v
                                        1            k




(остальные равны нулю). Тогда из равенства Av = b , записанного в форме (1),
следует

                                        Av = A j1 × v j1 + L + A jk × v jk = b .                       (2)

      Покажем, что столбцы A j ,L, A j линейно независимы. От противного
                                                 1               k



приходим к существованию ненулевого набора чисел a1 ,L ,a k Î R1 , для которых
имеет место равенство

                                                a1 A j + L + a k A j = 0 .
                                                         1                k
                                                                                                       (3)

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



                                                                 62

Страницы