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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

86
min,
,
0.
W u b u
x
A x p
u

(7.2)
Если одна из этих задач обладает оптимальным решением, то и двойствен-
ная к ней задача также имеет оптимальное решение. Причем экстремальные зна-
чения соответствующих линейных форм равны:
max minQW
.
Если же у одной из этих задач линейная форма не ограничена, то двой-
ственная к ней задача противоречива.
Доказательство: Пусть основная задача (7.1) имеет конечное решение и
получена окончательная симплексная таблица:
1
u
=
s
u
=
1s
v
=
….
n
v
=
W
=
1
y
s
y
1s
x
….
n
x
1
1
v
1
x
=
1,1
b
1,s
b
1, 1s
b
….
1,n
b
1, 1n
b
….
….
….
….
….
….
….
….
s
v
s
x
=
,1s
b
,ss
b
,1ss
b
….
,sn
b
,1sn
b
1s
u
1s
y
=
1,1s
b
1,ss
b
1, 1ss
b

….
1,sn
b
1, 1sn
b

….
….
….
….
….
….
….
….
m
u
m
y
=
,1m
b
,ms
b
,1ms
b
….
,mn
b
,1mn
b
1
Q
=
1
q
s
q
1s
q
….
n
q
0
q
Так как данная таблица, по предположению, соответствует оптимальному
решению задачи (7.1), то
1, 1 , 1
0, ..., 0
n m n
bb


и
1
0, ..., 0
n
qq
. При этом
0
maxQq
достигается при
11
... ... 0
s s n
y y x x
.
Рассмотрим полученную таблицу двойственной задачи. Полагая значения
переменных слева (небазисных) равными нулю:
11
... ... 0
s s m
v v u u
,
найдем
11
0uq
, …,
0
ss
uq
,
11
0
ss
vq


, …,
0
nn
vq
.
Следовательно, получено опорное решение
11
uq
, …,
ss
uq
,
1
0
s
u
, …,
0
m
u
.
Из последнего столбца находим, что
1, 1 1 , 1 1, 1 1 , 1 0
... ...
n s n s s n s m n m
W b v b v b u b u q
и в точке
11
... ... 0
s s m
v v u u

Страницы