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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
50
,,1,,,,,1,,
iiii
ii
vbauimvbauimk
****
=-==-+=+
LL
.
Покажем теперь, что любая задача линейного программирования (задача
1) может быть сведена к стандартной задаче. В пространстве переменных
()
1
1
2
1
l
l
nnl
nl
n
l
n
u
u
v
RR
v
w
w
+
+-
-
+
æö
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç÷
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
Î=
֍
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
÷
ç
ç
÷
èø
ç
÷
÷
ç
÷
L
L
L
рассмотрим задачу линейного программирования в стандартной форме
Задача 4.
)
)
111
11
min,
lllnn
lln
cucucwvcwv
++
+
+++-++-®
LL
)
)
1111
111111
lllnn
lln
auauawvawvb
++
+
+++-++-£
LL,
……………………………………………………………………
)
)
111
11
lllnnm
mmlmlmn
auauawvawvb
++
+
+++-++-£
LL
,
)
)
1111
111111
lllnnm
mmlmlmn
auauawvawvb
+++
+++++
+++-++-³
LL
,
……………………………………………………………………
)
)
111
11
lllnnk
kklklkn
auauawvawvb
++
+
+++-++-³
LL
,
)
)
1111
111111
lllnnk
kklklkn
auauawvawvb
+++
+++++
+++-++-£
LL
)
)
1111
111111
lllnnk
kklklkn
auauawvawvb
+++
+++++
+++-++-³
LL
……………………………………………………………………..
)
)
111
11
lllnns
sslslsn
auauawvawvb
++
+
+++-++-£
LL,
)
)
111
11
lllnns
sslslsn
auauawvawvb
++
+
+++-++-³
LL 
2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                v*i = bi - ai , u* , i = 1,L, m, v*i = -bi + ai , u* , i = m + 1, L, k .

    Покажем теперь, что любая задача линейного программирования (задача
1) может быть сведена к стандартной задаче. В пространстве переменных

                                         æ u1 ÷ö
                                         çç                     ÷
                                          çç L ÷÷
                                           çç                   ÷÷
                                            çç u l ÷÷÷
                                             çç l +1 ÷÷
                                              çç v ÷÷
                                               çç                ÷÷
                                                çç L ÷÷÷ Î R
                                                                      n +(n-l )
                                                                                = R 2 n-l
                                                 çç n ÷           ÷
                                                  çç v ÷÷
                                                   çç wl +1 ÷÷÷
                                                    çç            ÷
                                                     çç L ÷÷÷
                                                      çç          ÷÷
                                                       çèç wn ÷÷÷ø
                                                         ç         ÷÷

рассмотрим задачу линейного программирования в стандартной форме

    Задача 4.

                  c1u1 + L + cl u l + cl +1 ( wl +1 - v l +1 ) + L + cn ( wn - v n ) ® min,

                  a11u1 + L + a1l u l + a1l +1 ( wl +1 - v l +1 ) + L + a1n ( wn - v n ) £ b1 ,

            ……………………………………………………………………

                 am1u1 + L + aml u l + aml +1 ( wl +1 - vl +1 ) + L + amn ( wn - v n ) £ b m ,


          am +11u1 + L + am+1l u l + am +1l +1 ( wl +1 - v l +1 ) + L + am +1n ( wn - v n ) ³ b m+1 ,

            ……………………………………………………………………

                  ak 1u1 + L + akl u l + akl +1 ( wl +1 - v l +1 ) + L + akn ( wn - v n ) ³ b k ,


           ak +11u1 + L + ak +1l u l + ak +1l +1 ( wl +1 - v l +1 ) + L + ak +1n ( wn - v n ) £ b k +1

           ak +11u1 + L + ak +1l u l + ak +1l +1 ( wl +1 - v l +1 ) + L + ak +1n ( wn - v n ) ³ b k +1

           ……………………………………………………………………..

                  as1u1 + L + asl u l + asl +1 ( wl +1 - vl +1 ) + L + asn ( wn - v n ) £ b s ,

                  as1u1 + L + asl u l + asl +1 ( wl +1 - vl +1 ) + L + asn ( wn - v n ) ³ b s

                                                               50

Страницы