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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

90
3) Находим неотрицательное отношение коэффициента W-строки к ко-
эффициентам разрешающей (s-й) строки. В качестве разрешающего берем тот
элемент разрешающей s-й строки, для которого это отношение положительно и
минимально, т.е. выбираем некоторый коэффициент
sk
a
, для которого
min 0
jj
k
j
sk sj sj
bb
b
a a a






.
Выбрав разрешающий элемент, делаем шаг обыкновенного жорданова ис-
ключения. Указанная последовательность действий выполняется до тех пор, по-
ка все коэффициенты W-строки не станут неотрицательными. Например, будет
получена следующая таблица
1
v
….
s
v
….
m
u
1
1
u
=
11
b
….
1s
b
1,1s
b
….
1m
b
1
q
….
….
….
….
….
….
….
….
s
u
=
1s
b
….
ss
b
1,ss
b
….
ms
b
s
q
1s
v
=
1, 1s
b
….
,1ss
b
1, 1ss
b

….
,1ms
b
….
….
….
….
….
….
….
….
n
v
=
1,n
b
….
,sn
b
1,sn
b
….
mn
b
n
q
W
=
1
b
….
s
b
1s
b
….
m
b
0
q
Если все
1
,...,
n
qq
неотрицательны, то таблица соответствует оптимально-
му решению и
0
minqW
, иначе,
0
q
– оценка снизу для W.
Правило выбора разрешающего элемента при поиске оптимального
решения:
1) В качестве разрешающей строки берем строку, содержащую отрица-
тельный коэффициент, например,
0
s
q
, и строка с номером
s
будет разреша-
ющей.
2) В качестве разрешающего выбираем тот положительный коэффици-
ент
ks
b
строки
s
, для которого
min 0
jj
k
j
sk sj sj
bb
b
b b b






.
Если в строке с номером
s
нет положительных коэффициентов, то ограни-
чения задачи противоречивы.
После выбора разрешающего элемента делаем шаг обыкновенного жорда-
нова исключения.
После конечного числа шагов либо найдем оптимальное решение, либо
можно убедимся в противоречивости ограничений задачи.
Замечание: Если в симплекс-методе мы приближаемся к оптимальному
решению при поиске минимума сверху, передвигаясь по опорным планам, то в
методе последовательного уточнения оценок при поиске минимума к оптималь-
ному решению снизу, причем промежуточные планы (псевдопланы) не являются

Страницы