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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

85
Пусть
rS
a
– направляющий элемент. Сделаем шаг обыкновенного жорда-
нова исключения (отличие от модифицированного состоит в том, что элементы в
разрешающей строке меняют знаки, а в столбце знаки сохраняются; в остальном
преобразование остается тем же):
1
v
=
…
r
u
=
…
=
W
1
u
11
b
…
1S
a
…
1n
b
1, 1n
b
…
…
…
…
…
…
…
1r
a
…
1
…
rn
a
…
…
…
…
…
…
…
m
u
1m
b
…
mS
a
…
mn
b
,1mn
b
1
1,1m
b
…
S
p
…
1,mn
b
1, 1mn
b

Здесь
ij ij rS rj iS
b a a a a
и всю данную таблицу также следует разделить
еще на
rS
a
.
Замечание: Не следует забывать при преобразованиях, что в данном слу-
чае у нас таблица развернута.
Таким образом, нетрудно заметить, что шаг модифицированного жордано-
ва исключения над симплексной таблицей прямой задачи соответствует шагу
обыкновенного жорданова исключения над симплексной таблицей двойственной
задачи. Эти взаимно двойственные задачи можно совместить в одной симплекс-
ной таблице:
1
v
=
1
x
…
=
S
x
…
=
n
x
W
1
1
u
1
y
=
11
a
…
1S
a
…
1n
a
1
b
…
…
…
…
…
…
…
r
u
r
y
=
1r
a
…
rS
a
…
rn
a
…
…
…
…
…
…
…
m
u
m
y
=
1m
a
…
mS
a
…
mn
a
m
b
1
Qx
=
1
p
…
S
p
…
n
p
0
Можно показать, что, решая основную задачу линейного программирова-
ния, решаем и двойственную к ней. И наоборот. Причем,
max minQW
.
Теоремы двойственности
Основная теорема двойственности линейного программирования
Пусть рассматривается пара двойственных задач:
max,
,
0,
Q x p x
A x b
x

(7.1)

Страницы