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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
93
0,0
vv
***
³³
.
Задача 4.
()
,min
Д
bv
Ivbv
bv
**
****
æöæö
÷÷
çç
÷÷
çç
÷÷
çç
÷÷
=-®
çç
÷÷
çç
÷÷
çç
÷÷
çç÷÷
÷÷
çç
÷÷
çç
èøèø
,
(
)
{
}
i
TTT
i
AvAvAvcil
******
-+³ÎL,
(
)
{
}
,1,,
i
TTT
i
AvAvAvciln
******
-+-=-Î+L .
0,0
vv
***
³³
.
Определение 1. Задачи 3, 4 называется двойственными по
отношению к задачам 1, 2 соответственно. Сами задачи 1, 2 при этом
называется прямыми.
Пример 1. Прямая задача линейного программирования на минимум
целевой функции имеет вид
12345
12345
12345
2354min
23468,
234510,
uuuuu
uuuuu
uuuuu
+-+-®
+-++£
-+-++£
12345
12345
12345
12345
123
24357,
24783,
46254,
35248,
0,0,0.
uuuuu
uuuuu
uuuuu
uuuuu
uuu
+-+-³-
-+++³-
-++-+=-
-++-=
³³³
Запишем для нее двойственную задачу (задача 3).
123456
123456
123456
123456
123456
123456
1234
8107348max,
222431,
2344652,
3437223,
45855,
6544,
0,0,0,0.
vvvvvv
vvvvvv
vvvvvv
vvvvvv
vvvvvv
vvvvvv
vvvv
----+-®
----+³-
+-++-³-
--+-++³
--+++-=
---+-+=-
³³³³
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


                                      v* ³ 0, v** ³ 0 .

     Задача 4.

                                    æ b* ö÷              æ v* ö÷
                                      çç       ÷÷        çç ÷
                         I Д (v ) = ççç-b** ÷÷ ,          ççv** ÷÷ ® min ,
                                       çç       ÷÷         çç ÷÷÷
                                        èç 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




                                      v* ³ 0, v** ³ 0 .

     Определение 1.        Задачи          3, 4              называется      двойственными   по
отношению к задачам 1, 2 соответственно. Сами задачи 1, 2 при этом
называется прямыми.

     Пример 1. Прямая задача линейного программирования на минимум
целевой функции имеет вид

                         u1 + 2u 2 - 3u 3 + 5u 4 - 4u 5 ® min
                         u1 + 2u 2 - 3u 3 + 4u 4 + 6u 5 £ 8,
                         -2u1 + 3u 2 - 4u 3 + u 4 + 5u 5 £ 10,

                         2u1 + 4u 2 - 3u 3 + 5u 4 - u 5 ³ -7,
                         2u1 - 4u 2 + 7u 3 + 8u 4 + u 5 ³-3,
                         -4u1 + 6u 2 + 2u 3 - 5u 4 + u 5 = -4,
                         3u1 - 5u 2 + 2u 3 + u 4 - 4u 5 = 8,
                         u1 ³ 0, u 2 ³ 0, u 3 ³ 0.

     Запишем для нее двойственную задачу (задача 3).

                    -8v1 -10v 2 - 7v3 - 3v 4 + 4v5 - 8v 6 ® max,
                    v1 - 2v 2 - 2v3 - 2v 4 - 4v5 + 3v6 ³ -1,
                    2v1 + 3v 2 - 4v 3 + 4v 4 + 6v 5 - 5v 6 ³ -2,
                    -3v1 - 4v 2 + 3v3 - 7v 4 + 2v5 + 2v 6 ³ 3,
                    -4v1 - v 2 + 5v3 + 8v 4 + 5v 5 - v6 = 5,
                    -6v1 - 5v 2 - v3 + v 4 - v5 + 4v6 = -4,
                    v1 ³ 0, v 2 ³ 0, v3 ³ 0, v 4 ³ 0.

                                               93

Страницы