Численные методы оптимизации. Рейзлин В.И. - 89 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

89
7.4. Метод последовательного уточнения оценок
Этот метод иногда называют еще двойственным симплекс-методом. Ранее
говорилось, что одновременно с решением прямой задачи решается и двой-
ственная задача. Если проследить за получающимися преобразованиями двой-
ственной таблицы и переменных
i
u
и
j
x
и записать таблицу для двойственной
задачи в обычном виде, то получим описание нового метода – метода последова-
тельного уточнения оценок.
Пусть дана задача:
11
1 11 1 1 1 1
11
... ... min,
... ... 0,
......................................................................
... ... 0,
.......................
r r m m
r r m m
s s rs r ms m r
W u b u b u b u
v a u a u a u p
v a u a u a u p
1 1 2 ,
...............................................
... ... 0,
0.
n n rn m n m n
v a u a u a u p
v
Симплексая таблица, построенная для данной задачи, будет иметь вид:
1
u
….
r
u
….
1
1
v
=
11
a
….
1r
a
….
1m
a
1
p
….
….
….
….
….
….
….
s
v
=
1s
a
….
sr
a
….
sm
a
s
p
….
….
….
….
….
….
….
n
v
=
1n
a
….
nr
a
….
nm
a
n
p
W
=
1
b
….
….
m
b
0
В методе последовательного уточнения оценок сначала избавляются от
отрицательности в
W
-строке (получают псевдоплан), а затем, перебирая псевдо-
планы, ищут оптимальный план (первый найденный опорный).
Правило выбора разрешающего элемента для избавления от отрица-
тельности в W-строке:
1) Если все коэффициенты W-строки неотрицательны, то 0 является
оценкой снизу для целевой функции
W
и можно переходить к отысканию опти-
мального решения. Иначе выбираем некоторый
0
r
b
и рассматриваем
r
-й
столбец.
2) Находим в
r
-м столбце какой-нибудь из отрицательных элементов,
например,
0
rs
a
. Тогда строку с номером
s
, содержащую
rs
a
, выбираем в ка-
честве разрешающей строки. Если все коэффициенты
r
-го столбца неотрица-
тельны, то либо W неограничена снизу (
W 
), либо система ограничений
противоречива. (Из противоречивости двойственной не следует неограничен-
ность прямой задачи).

Страницы