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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
66
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
--
-=
1
2
11
,
2
1
9
,
1
1
2
,
2
4
1
,
2
1
3
,
1
2
1
,
21221
11412
92131
54321
bAAAAAA
.
Ранг матрицы А равен трем. Например, вектора
421
,, AAA линейно
независимы, так как
08
121
112
231
¹=
--
- .
Точка
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
0
2
0
2
1
1
v является угловой для множества
U
. Действительно, для
нее
4,2,1
321
=== jjj
. Условие 1) теоремы 1 для этих номеров установлено
выше, а равенство bAv =
1
проверяется следующими вычислениями:
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
×+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-×+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
×
1
2
11
1
1
2
2
2
1
3
2
1
2
1
1 .
Заметим, что угловая точка
1
v – невырожденная.
Точка
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
1
1
0
0
0
2
v также угловая. Равенство bAv =
2
проверяется
непосредственно. Эта угловая точка вырожденная. Ее базис не единственен,
так как, по крайней мере, можно указать два ее базиса:
{
}
{
}
543541
,,,,, AAAAAA .
Действительно,
063
212
114
921
,016
211
112
921
¹-=
-
¹-=
--
. 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


       æ1   3 1 2 9ö          æ1ö          æ 3ö          æ1ö          æ 2ö         æ 9ö        æ11ö
       ç             ÷        ç ÷          ç ÷           ç ÷          ç ÷          ç ÷         ç ÷
   A = ç 2 - 1 4 1 1 ÷ , A1 = ç 2 ÷ , A2 = ç - 1÷ , A3 = ç 4 ÷ , A4 = ç 1 ÷ , A5 = ç 1 ÷ , b = ç 2 ÷ .
       ç -1 2 2 -1 2÷         ç - 1÷       ç 2÷          ç 2÷         ç - 1÷       ç 2÷        ç1÷
       è             ø        è ø          è ø           è ø          è ø          è ø         è ø

     Ранг матрицы А равен трем. Например, вектора A1 , A2 , A4 линейно
независимы, так как

                                           1     3     2
                                           2     -1    1 =8¹0.
                                          -1     2    -1

                æ1ö
                ç ÷
                ç2÷
     Точка v1 = ç 0 ÷ является угловой для множества U . Действительно, для
                ç ÷
                ç2÷
                ç0÷
                è ø
нее j1 = 1, j 2 = 2, j 3 = 4 . Условие 1) теоремы 1 для этих номеров установлено
выше, а равенство Av1 = b проверяется следующими вычислениями:

                                     æ 1 ö       æ 3ö         æ 2 ö æ11ö
                                     ç ÷         ç ÷          ç ÷ ç ÷
                                 1 × ç 2 ÷ + 2 × ç - 1÷ + 2 × ç 1 ÷ = ç 2 ÷ .
                                     ç - 1÷      ç 2÷         ç - 1÷ ç 1 ÷
                                     è ø         è ø          è ø è ø

     Заметим, что угловая точка v1 – невырожденная.
                     æ0ö
                     ç ÷
                     ç0÷
     Точка      v2 = ç 0 ÷    также            угловая.      Равенство          Av 2 = b   проверяется
                     ç ÷
                     ç1÷
                     ç1÷
                     è ø
непосредственно. Эта угловая точка вырожденная. Ее базис не единственен,
так как, по крайней мере, можно указать два ее базиса: {A1 , A4 , A5 }, {A3 , A4 , A5 } .
Действительно,

                             1    2    9            1        2     9
                             2    1    1 = -16 ¹ 0, 4        1     1 = -63 ¹ 0 .
                             -1 -1 2                       2 -1 2




                                                      66

Страницы