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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

87
значение W будет минимальным в силу того, что
,1
0
in
b
,
1,...,im
. Следова-
тельно,
max minQW
.
Пусть теперь линейная форма прямой задачи неограничена, т.е. для неко-
торой верхней переменной, например,
s
y
, соответствующий коэффициент
0
s
q
, а все коэффициенты этого столбца симплексной таблицы неположитель-
ны:
1,
0
s
b
,
2,
0
s
b
, …,
,
0
ms
b
. Тогда из таблицы для двойственной задачи:
,
то есть система ограничений двойственной задачи противоречива. Так как из не-
отрицательности
11
, ..., , , ...,
s s m
v v u u
следует неположительность
s
u
(нельзя сде-
лать ее положительной), то есть система несовместна.
Теорема доказана.
Вторая теорема двойственности:
Если хотя бы одно оптимальное решение одной из двойственных задач об-
ращает
i
-е ограничение этой задачи в строгое неравенство, то
i
-я компонента
(т.е.
i
x
или
i
u
) каждого оптимального решения второй двойственной задачи рав-
на нулю.
Если же
i
-я компонента хотя бы одного оптимального решения одной из
двойственных задач положительна, то каждое оптимальное решение другой
двойственной задачи обращает
i
-е ограничение в строгое равенство.
Иначе говоря, оптимальные решения
*
x
и
*
u
пары двойственных задач
удовлетворяют условиям
1
0, 1, ,
m
j ij i j
i
x a u p j n




(7.3)
1
0, 1, .
n
i ij j i
j
u a x b i m





(7.4)
Доказательство:
Пусть
*
x
и
*
u
– оптимальные решения пары двойственных задач. Тогда
для
1
max
n
jj
j
Q x p x

,
1
min
m
ii
i
W u bu

они удовлетворяют следующим ограничениям:

Страницы