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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
80
1
1
1
11
1
buauaw
n
n
+---=
L
…………………………… (2)
mn
mnm
m
buauaw +---=
L
1
1
4. Выполнить пункты 2-8 алгоритма, описанного в п.4. В результате
будет найдена угловая точка
mnmn
RwRvR
w
v
z ÎÎÎ
÷
÷
ø
ö
ç
ç
è
æ
=
**
+
*
*
*
,, допустимого
множества вспомогательной задачи.
5. Провести анализ величины
(
)
0
1
³
*
zI : если
(
)
0
1
>
*
zI , то допустимое
множество исходной задачи линейного программирование пусто, и эта задача
не имеет решения. В противном случае сделать переход на следующий пункт
данного алгоритма.
6. Обратиться к последней симплекс-таблице решения вспомогательной
задачи (рис. 8), то есть симплекс-таблице точки
÷
÷
ø
ö
ç
ç
è
æ
=
*
*
0
v
z , и провести анализ
структуры базиса угловой точки
*
z .
Таблица 6
1 2 3 4 5 6 7 8 9 10
1+r
u
…
k
u
…
n
u
1+-rm
w
…
m
w
Св. ч.
1
u
11 +r
g
…
k1
g
…
n1
g
11 +-rm
g
…
m1
g
1
*
v
… … …
… … … … … … …
j
u
1+rj
g
…
kj
g
…
nj
g
1+-rmj
g
…
mj
g
j
v
*
… … …
… … … … … … …
r
u
1+rr
g
…
kr
g
…
nr
g
1+-rmr
g
…
mr
g
r
v
*
1
w
11 ++ rr
g
…
kr 1+
g
…
nr 1+
g
11 +-+ rmr
g
…
mr 1+
g
0
… … …
… … … … … … … 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                          w1 = -a11u1 - L - a1nu n + b1

                                     ……………………………                                                                 (2)

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

      4. Выполнить пункты 2-8 алгоритма, описанного в п.4. В результате
                                                          æv ö
будет     найдена          угловая       точка      z* = çç * ÷÷ Î R n + m , v* Î R n , w* Î R m        допустимого
                                                          è w* ø

множества вспомогательной задачи.

      5. Провести анализ величины I1 (z* ) ³ 0 : если I1 (z* ) > 0 , то допустимое
множество исходной задачи линейного программирование пусто, и эта задача
не имеет решения. В противном случае сделать переход на следующий пункт
данного алгоритма.

    6. Обратиться к последней симплекс-таблице решения вспомогательной
                                                                                      æv ö
задачи (рис. 8), то есть симплекс-таблице точки z * = çç * ÷÷ , и провести анализ
                                                       è0ø
структуры базиса угловой точки z* .

    Таблица 6

     1       2              3    4            5     6           7                 8          9          10

             u r +1         … uk              …      un         w m -r +1         …          wm         Св. ч.

     u1      g 1 r +1       … g1k             …      g 1n       g 1 m - r +1      …          g 1m        v *1

     …       …              … …               …     …           …                 …          …          …

     uj      g   j r +1     … g jk            …      g jn       g j m -r +1       …          g jm        v *j

     …       …              … …               …     …           …                 …          …          …

     ur      g r r +1       … grk             …      grn        g r m -r +1       …          grm         v *r

     w1      g r +1 r +1    … g r +1 k        …      g r +1 n   g r +1 m - r +1   …          g r +1 m   0

     …       …              … …               …     …           …                 …          …          …


                                                        80

Страницы