Введение в линейное программирование. Палий И.А. - 34 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

6.3.3. ),),(),(
2121
yxyxyxx
+
=+ .
6.3.4. Если векторы
x
и y неотрицательны,
x
≥ 0, y ≥ 0, то ),( y
x
≥
0.
6.3.5. ),(),( xyAyxA
T
= , где
A
− квадратная матрица с n строками.
6.4. Теоремы двойственности
6.4.1. Теорема 1 (основное неравенство теории двойственности).
Если
),,,(
21 n
xxxx L=
и
),,,(
21 m
yyyy L
=
− произвольные
допустимые решения пары двойственных задач
(6.3), (6.4), то
),(
x
c
Z
= ≤ ).,(
0
yAW = (6.5)
Доказательство опирается на свойства скалярного произведения.
Допустимость векторов
x
и y означает справедливость следующих
соотношений:
x
≥ 0,
0
AxA = ,
cyA
T
≥
(
0≥− cyA
T
), ),(),(),(
0
yAxyxAyA
T
== =
),( xyA
T
= . Поэтому
Z
W − = ),(
0
yA − ),(
x
c
),( xyA
T
=
− ),(
x
c =
),( xcyA
T
−=
≥ 0, так как
0≥− cyA
T
и
x
≥ 0.
Следствие 1. Если допустимые решения
),,,(
21 n
xxxx L
=
и
),,,(
21 m
yyyy L=
пары двойственных задач (6.3) и (6.4) таковы, что
),(
x
c = ).,(
0
yA , то
x
и y − оптимальные решения этих задач.
Действительно, если
),,,(
21 m
yyyy L=
− не оптимальное решение
задачи (6.4), то существует такое допустимое решение задачи (6.4), вектор
),,,(
211 m
yyyy
′
′′
=
L , на котором целевая функция меньше, чем на векторе
y
: ),(),(),(
010
xcyAyA =< . Получено противоречие с основным
неравенством.
Следствие 2. Если целевая функция Z задачи (6.3) не ограничена сверху
на допустимом множестве задачи
(6.3), то у задачи (6.4) нет ни одного
допустимого решения. Если целевая функция W задачи
(6.4) не ограничена
снизу на допустимом множестве задачи
(6.4), то у задачи (6.3) нет ни
одного допустимого решения.
Пусть, например, целевая функция Z не ограничена сверху, а у задачи
(6.4) есть допустимые решения и
),,,(
21 m
yyyy L
=
− одно из них.
Обозначим через
0
W значение целевой функции W на векторе y . В силу

Страницы