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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
67
3.3 Обоснование симплекс-метода. Рассмотрим каноническую задачу
линейного программирования на минимум, опишем и обоснуем метод ее
решения, который обычно называется симплекс-методом.
Задача 2.
min,)( ®= ucuI ,
{
}
bAuuRuUu
n
=³Î=Î ;0 .
Здесь А – матрица размера
[
]
rArangnm =´ , . Предполагается, что
Æ
¹
=
Umr , и множество U имеет хотя бы одну угловую точку
v
.
Покоординатно равенство bAu
=
может быть представлено так
1
1
1
11
buaua
n
n
=++
L
,
..........
..........
..........
(1)
rn
rnr
buaua =++
L
1
1
.
Перенумеровав переменные, можно считать, что столбцы
r
AA ,,
1
L
матрицы А являются базисом точки
v
.
Определение 4. Переменные
r
uu ,,
1
L
будем называть базисными
переменными, а переменные
nr
uu ,,
1
L
+
– внебазисными, для угловой точки
v
.
Придадим задаче 2 новую форму, выразив базисные переменные через
внебазисные. Обозначим
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
r
u
u
u L
1
,
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
r
v
v
v L
1
,
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
r
c
c
c L
1
,
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
jr
j
j
a
a
A L
1
, nj ,,1
L
=
,
(
)
r
AAB
L
1
= .
Тогда
buAuAuBuAuAuAuA
n
n
r
r
n
n
r
r
r
r
=+++=+++++
+
+
+
+
L
L
L
1
1
1
1
1
1
. (2)
Из линейной независимости столбцов
r
AA ,,
1
L
следует существование
матрицы
1-
B
. Точка
v
– угловая с базисом
r
AA ,,
1
L
, поэтому
÷
÷
ø
ö
ç
ç
è
æ
=
0
v
v . Из
равенства (2) вытекает, что 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


      3.3 Обоснование симплекс-метода. Рассмотрим каноническую задачу
линейного программирования на минимум, опишем и обоснуем метод ее
решения, который обычно называется симплекс-методом.

    Задача 2.

                        I (u ) = c, u ® min , u ÎU = {u Î R n u ³ 0; Au = b}.

    Здесь А –            матрица размера                m ´ n, rang [ A] = r .   Предполагается, что
r = m, U ¹ Æ и множество U имеет хотя бы одну угловую точку v .

      Покоординатно равенство Au = b может быть представлено так

                                            a11u 1 + L + a1n u n = b1 ,

                                             .................................                           (1)

                                            a r1u 1 + L + a rn u n = b r .

    Перенумеровав переменные, можно считать, что столбцы                                          A1 ,L, Ar
матрицы А являются базисом точки v .

    Определение 4. Переменные                         u 1 ,L , u r     будем называть базисными

переменными, а переменные u r +1 ,L, u n – внебазисными, для угловой точки v .

    Придадим задаче 2 новую форму, выразив базисные переменные через
внебазисные. Обозначим

             æ u1 ö      æ v1 ö      æ c1 ö       æ a j1 ö
             ç ÷         ç ÷         ç ÷          ç ÷
         u = ç L ÷ , v = ç L ÷ , c = çL ÷ , A j = ç L ÷ , j = 1, L, n , B = ( A1 L Ar ) .
             ç r÷        ç r÷        çc ÷         ça ÷
             èu ø        èv ø        è rø         è jr ø

    Тогда

            A1u 1 + L + Ar u r + Ar +1u r +1 + L + An u n = Bu + Ar +1u r +1 + L + An u n = b .          (2)

    Из линейной независимости столбцов A1 ,L, Ar следует существование
                                                                                                  æv ö
матрицы B -1 . Точка v – угловая с базисом A1 ,L , Ar , поэтому v = çç ÷÷ . Из
                                                                     è 0ø
равенства (2) вытекает, что
                                                      67

Страницы