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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
69
Таблица 1
Базисные
переменные
1+r
u
…
k
u
…
n
u
Свободный
член
1
u
11 +r
g
…
k1
g
…
n1
g
1
v
… … … … … … …
i
u
1+ir
g
…
ik
g
…
in
g
i
v
… … … … … …
r
u
1+rr
g
…
rk
g
…
rn
g
r
v
Целевая
функция
1+
D
r
…
k
D
…
n
D
)(vI
Определение 5. Формулы (4), (6) будем называть симплекс-разложением,
а таблицу 1– симплекс-таблицей, отвечающими угловой точке
v
.
Добавляя к формулам (4),(6) неравенства
niu
i
,,1,0
L
=³
, получим искомую
эквивалентную запись исходной задачи 2.
Укажем один способ построения точки
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
n
w
w
w L
1
из множества
U
.
Зададимся набором значений внебазисных переменных 0,,0
1
³==
*
+ kkr
uww
L
,
0, =
n
w
L
, а значения базисных переменных вычислим по формулам (4),
подставив в них выбранные значения внебазисных переменных. Тогда
k
rk
rrk
ik
iik
k
uvwuvwuvw
***
-=-=-=
ggg
,,,,
1
11
L
L
. (7)
Пусть оказалось, что
0,1,,
i
wirn
³=+
. Тогда цель достигнута. Заметим,
что если 0=
*
k
u , то
v
w
=
. 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


       Таблица 1

              Базисные                     u r +1   …       uk        …       un        Свободный
              переменные                                                                член

                         u1               g 1r +1   …       g 1k      …       g   1n            v1

                    …                     …         …       …         …       …                …

                    ui                    g ir+1 …          g ik      …       g in              vi

                    …                     …         …       …         …       …

                    ur                    g rr +1   …       g rk      …       g rn              vr

                    Целевая                D r +1   …        Dk       …       Dn                I (v)
              функция




     Определение 5. Формулы (4), (6) будем называть симплекс-разложением,
а таблицу 1– симплекс-таблицей, отвечающими угловой точке v .

     Добавляя к формулам (4),(6) неравенства u i ³ 0, i = 1, L, n , получим искомую
эквивалентную запись исходной задачи 2.

                                                                                  æ w1 ö
                                                                                  ç ÷
     Укажем один способ построения точки                                      w = çL÷          из множества U .
                                                                                  ç n÷
                                                                                  èw ø

Зададимся набором значений внебазисных переменных w r +1 = 0,L , w k = u*k ³ 0 ,
L , w n = 0 , а значения базисных переменных вычислим по формулам (4),

подставив в них выбранные значения внебазисных переменных. Тогда

                         w1 = v1 - g 1k u *k ,L , w i = v i - g ik u *k ,L, w r = v r - g rk u *k .         (7)

     Пусть оказалось, что wi ³ 0, i = r + 1,L, n . Тогда цель достигнута. Заметим,
что если u*k = 0 , то w = v .




                                                          69

Страницы