Руководство по решению задач по курсу "Вариационное исчисление и методы оптимизации". Шарапов В.Г. - 18 стр.

UptoLike

ВУЗ: 

ВолГУ | Волгоград

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

Рубрика: 

18
2) Составляем симплекс-таблицу
x
1
x
2
…
x
n
s
1
s
2
…
s
m
a
11
a
12
… a
1n
1 0 … 0 b
1
a
21
a
22
… a
2n
0 1 … 0 b
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
…
a
mn
0 0 … 1
b
m
c
1
c
2
…
c
n
0 0 … 0
z
В системе уравнений (3) можно считать
mis
i
,1, = базисными пе-
ременными, а
x
1
, …, x
n
− свободными.
Будем считать сначала, что все
mib
i
,1,0 =≥ . Тогда при свобод-
ных переменных, равных нулю,
s
i
= b
i
, z = c
1
x
1
+ … + c
n
x
n
+ 0⋅s
1
+ … + 0⋅s
m
= 0.
Числа, стоящие в последней строчке таблицы (кроме
z), называются
индикаторами. Если все они не положительны,
c
1
≤ 0, то z = 0 есть мак-
симальное значение, т.е. решение задачи.
Если имеются положительные индикаторы, то выбирается какой-
нибудь столбец с положительным индикатором, скажем,
k-й и в этом
столбце выбирается центральный элемент, скажем,
a
jk
, такой что a
jk
≥ 0 и
отношение
jkj
ab было бы минимальным для всех
iki
ab с положи-
тельными
a
ik
. Отмечаем в таблице
jk
a .
3) Делим всю
k-ю строку на a
jk
, чтобы вместо
jk
a
получить 1.
4) Из каждой из остальных (кроме
j-ой), скажем, i-ой строки, надо
вычесть
j-ю, умноженную на a
ik
(чтобы все элементы k-го столбца, кроме
a
jk
, стали нулями, в том числе и индикатор). При этом z заменится на
kj
cbz − . 0=−
kj
cbz , откуда 0>
=
kj
cbz .
Если после этого остались положительные индикаторы, то опять
выбираем столбец с положительным индикатором, центральный элемент и
т.д., как описано выше, превращаем центральный элемент в
1, а остальные
элементы столбца в
0. Таким образом действуем до тех пор, пока не будет
положительных индикаторов. Как только положительные индикаторы ис-
чезнут, то задача решена. 
          2) Составляем симплекс-таблицу
x1    x2     …     xn    s1   s2    …      sm
a11   a12    …     a1n   1    0     …      0    b1
a21   a22    …     a2n   0    1     …      0    b2
.     .      .     .     .    .            .    .
.     .      .     .     .    .            .    .
.     .      .     .     .    .            .    .
am1 am2 …          amn 0      0     …      1    bm
c1 c2 …            cn 0       0     …      0    z

      В системе уравнений (3) можно считать si , i = 1, m базисными пе-
ременными, а x1, …, xn − свободными.
      Будем считать сначала, что все bi ≥ 0, i = 1, m . Тогда при свобод-
ных переменных, равных нулю,
      si = bi, z = c1x1 + … + cnxn + 0⋅s1 + … + 0⋅sm = 0.
      Числа, стоящие в последней строчке таблицы (кроме z), называются
индикаторами. Если все они не положительны, c1 ≤ 0, то z = 0 есть мак-
симальное значение, т.е. решение задачи.
      Если имеются положительные индикаторы, то выбирается какой-
нибудь столбец с положительным индикатором, скажем, k-й и в этом
столбце выбирается центральный элемент, скажем, ajk, такой что ajk ≥ 0 и
отношение b j a jk было бы минимальным для всех bi aik с положи-
тельными aik. Отмечаем в таблице a jk .

      3) Делим всю k-ю строку на ajk, чтобы вместо a jk получить 1 .

       4) Из каждой из остальных (кроме j-ой), скажем, i-ой строки, надо
вычесть j-ю, умноженную на aik (чтобы все элементы k-го столбца, кроме
ajk, стали нулями, в том числе и индикатор). При этом z заменится на
z − b j ck . z − b j ck = 0 , откуда z = b j ck > 0 .
        Если после этого остались положительные индикаторы, то опять
выбираем столбец с положительным индикатором, центральный элемент и
т.д., как описано выше, превращаем центральный элемент в 1, а остальные
элементы столбца в 0. Таким образом действуем до тех пор, пока не будет
положительных индикаторов. Как только положительные индикаторы ис-
чезнут, то задача решена.


                                    18

Страницы