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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
77
(
)
1- . В пространстве переменных
mn
m
n
R
w
w
u
u
z
+
Î
÷
÷
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
ç
ç
è
æ
=
L
L
1
1
рассмотрим следующую
каноническую задачу линейного программирования:
Задача 3.
min,)(
1
1
®++=
m
wwzI
L
()
þ
ý
ü
î
í
ì
³=Î
÷
÷
ø
ö
ç
ç
è
æ
==Î
+
0,, zbzEAR
w
u
zZz
mn
.
Сформулированную задачу 3 будем называть вспомогательной задачей
по отношению к задаче 2. В координатной форме ограничения
вспомогательной задачи запишутся в виде
11
1
1
11
bwuaua
n
n
=+++
L
,
……………………………
mmn
mnm
bwuaua =+++
L
1
1
,
0,,0,0,,0
11
³³³³
mn
wwuu
L
L
.
Заметим, что для задачи 3 выполнены условия
()
[]
,
100
001
,
1
111
m
aa
aa
rangEArang
mnm
n
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
LL
MMMMMMM
LL
Æ
¹
Z , Z
b
z Î
÷
÷
ø
ö
ç
ç
è
æ
=
0
0
,
точка
0
z
– угловая для множества
Z
, и последние
m
ее координат – базисные.
В силу неравенства
(
)
0
1
³zI для всех
Z
z
Î
(случай -¥=
*1
I невозможен) за
конечное число итераций симплекс-метод приведет к решению задачи 3. Пусть
÷
÷
ø
ö
ç
ç
è
æ
=
*
*
*
w
v
z
– решение этой задачи. Заметим, что точка
*
z – угловая для множества
Z
. Имеются две возможности: либо 0)(
1
>
*
zI , либо 0)(
1
=
*
zI . 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                                          æ u1 ö
                                                          ç    ÷
                                                          çL÷
                                                          ç n÷
                                                            u
(- 1) . В пространстве переменных                     z = ç 1 ÷ Î R n+m     рассмотрим следующую
                                                          çw ÷
                                                          ç    ÷
                                                          çL÷
                                                          ç wm ÷
                                                          è    ø

каноническую задачу линейного программирования:

     Задача 3.

                                     I 1 ( z ) = w1 + L + w m ® min,

                                    ì      æuö                                 ü
                            z Î Z = í z = çç ÷÷ Î R n + m ( A, E )z = b, z ³ 0 ý .
                                    î      è wø                                þ

      Сформулированную задачу 3 будем называть вспомогательной задачей
по   отношению          к    задаче        2.     В        координатной              форме   ограничения
вспомогательной задачи запишутся в виде

                                      a11u1 + L + a1n u n + w1 = b1 ,

                                   ……………………………

                                     am1u1 + L + amnu n + wm = b m ,

                                u 1 ³ 0, L, u n ³ 0, w 1 ³ 0,L , w m ³ 0 .

     Заметим, что для задачи 3 выполнены условия

                                éæ a11 L a1n      1 0 L 0 öù
                                êç                         ÷ú                    æ 0ö
         rang [( A, E )] = rang êç M    M  M      M M M M ÷ú = m, Z ¹ Æ , z 0 = çç ÷÷ Î Z ,
                                  ç
                                êëè am1 L amn     0 0 L 1 ÷øúû                   èbø


точка z 0 – угловая для множества Z , и последние m ее координат – базисные.

      В силу неравенства I 1 (z ) ³ 0 для всех z Î Z (случай I 1* = -¥ невозможен) за
конечное число итераций симплекс-метод приведет к решению задачи 3. Пусть
       æv ö
z * = çç * ÷÷ – решение этой задачи. Заметим, что точка z * – угловая для множества
       è w* ø

Z . Имеются две возможности: либо I 1 ( z * ) > 0 , либо I 1 ( z * ) = 0 .

                                                      77

Страницы