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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
92
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ
4.1. Двойственная задача к общей задаче линейного
программирования. В общей задаче линейного программирования,
описанной в пункте 2.1, рассмотрим отдельно случаи минимизации и
максимизации целевой функции.
Задача 1.
(),min,,
n
IucuuR
=®Î
Aub
**
£
,
Aub
³
,
Aub
=
,
0,.
u
³
%
Задача 2.
(),max,,
n
IucuuR
=®Î
Aub
**
£
,
Aub
³
,
Aub
=
,
0,.
u
³
%
Вводя дополнительные обозначения
111
,,
mk
mks
vvv
vvv
vvv
++
***
æöæöæö
÷÷÷
ççç
÷÷÷
ççç
÷÷÷
ççç
÷÷÷
===
ççç
÷÷÷
ççç
÷÷÷
ççç
÷÷÷
ççç
÷÷÷
÷÷÷
ççç
÷÷÷
ççç
èøèøèø
LLL
,
поставим задачам 1, 2 в соответствие следующие задачи линейного
программирования.
Задача 3.
()
,max
Д
bv
Ivbv
bv
**
****
æöæö
-
÷÷
çç
÷÷
çç
÷÷
çç
÷÷
=®
çç
÷÷
çç
÷÷
çç
÷÷
çç÷÷
÷÷
-çç
÷÷
çç
èøèø
,
(
)
{
}
,1,,
i
TTT
i
AvAvAvcil
******
-+³-ÎL,
(
)
{
}
,1,,
i
TTT
i
AvAvAvciln
******
-+-=Î+L . 
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


       4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
                         ПРОГРАММИРОВАНИИ


     4.1.   Двойственная               задача                 к       общей        задаче   линейного
программирования.        В       общей           задаче             линейного       программирования,
описанной в пункте 2.1, рассмотрим отдельно случаи минимизации и
максимизации целевой функции.

     Задача 1.

                                I (u ) = c, u ® min , u Î R n ,

                        A*u £ b* , A**u ³ b** , Au = b , u% ³ 0, .

     Задача 2.

                                I (u ) = c, u ® max, u Î R n ,

                        A*u £ b* , A**u ³ b** , Au = b , u% ³ 0, .

     Вводя дополнительные обозначения

                                  æ v1 ö÷         æv m+1 ÷ö         æ k +1 ö
                                  çç ÷            çç     ÷       ççv ÷÷
                                         ÷               ÷                 ÷
                           v* = ççç L÷÷ , v** = ççç L ÷÷ , v = ççç L ÷÷ ,
                                         ÷
                                   çç m ÷÷               ÷
                                                   çç k ÷÷        çç s ÷÷÷
                                    èçv ø÷          èç v ÷ø        çè v ÷ø

    поставим задачам 1, 2 в соответствие следующие задачи линейного
программирования.

     Задача 3.

                                         æ-b* ö÷             æ v* ö÷
                                         çç        ÷÷          çç ÷
                             I Д (v) = ççç b** ÷÷ ,             ççv** ÷÷ ® max ,
                                          çç        ÷÷           çç ÷÷÷
                                           èç -b ÷ø÷         èçç v ø÷÷


                      ( A*T v* - A**T v** + AT v ) ³ -ci , i Î {1,L, l} ,
                                                         i




                    (- A*T v* + A**T v** - AT v ) = ci , i Î {l +1, L, n} .
                                                         i




                                                    92

Страницы