Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 76 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

76
Напомним, что неотрицательные векторы X и Y называются допустимыми, если
они соответственно удовлетворяют условиям прямой и двойственной задач.
Имеют место следующие теоремы.
Теорема 1
. Если векторы X и Y допустимы для сопряженных задач вида (2.2.34) —
(2.2.36) и (2.2.37) —(2.2.39), то
CX
≤
BY. (2.2.42)
Д о к а з а т е л ь с т в о. Умножая скалярно неравенство (2.2.36) на
неотрицательный вектор Y, получим
(AX)Y
≤
BY. (2.2.43)
Так же умножая неравенство (2.2.39) на неотрицательный вектор X, имеем
(A
T
Y)X
≥
CX. (2.2.44)
Проверкой можно убедиться, что
(АХ) Y = (A
т
Y) X =
∑
ji
ijij
yxa
,
. (2.2.45)
Сопоставление неравенств (2.2.43) и (2.2.44), с учетом равенства (2.2.45), дает
неравенство
СХ ≤ (A
Т
Y) X = (АХ) Y
≤
ВУ, (2.2.46)
и теорема доказана.
Таким образом, неравенство между значениями целевых функций для допустимых
решений взаимосопряженных задач имеет в точности тот же вид, что и неравенство в
условиях прямой задачи.
Теорема 2
(признак оптимальности). Если для некоторых допустимых решений X
0
и Y
0
прямой и двойственной стандартных задач выполняется равенство
CX
0
= BY
0
, (2.2.47)
то векторы Х
0
и Y
0
являются оптимальными решениями соответствующих задач.
Д о к а з а т е л ь с т в о. Пусть X произвольный другой допустимый вектор задачи
(2.2.34)—(2.2.36). Тогда, по теореме 1,
CX≤BY
0
, (2.2.48)
Учитывая равенство (2.2.47), получаем
СХ ≤ СХ
0
,
а это значит, что вектор Х
0
является оптимальным решением прямой задачи. Аналогично
доказывается оптимальность вектора Y
0
двойственной задачи. Теорема доказана.
Теорема 2 устанавливает достаточность условия (2.2.47) для оптимальности
допустимых векторов Х
0
и Y
0
, т. е. если для некоторых допустимых решений
взаимосопряженных задач их целевые функции совпадают по величине, то допустимые
решения являются оптимальными.
Можно доказать, но на этом мы останавливаться не будем, что условие (2.2.47)
является также и необходимым условием для оптимальности допустимых векторов Х
0
и
Y
0
, т. е. если допустимые векторы Х
0
и Y
0
оптимальны, то целевые функции для этих
векторов совпадают по величине.
Обратим внимание на неравенство (2.2.46). Если допустимые векторы X и Y
оптимальны, то неравенство (2.2.46) должно быть равенством. Обратно, если неравенство
(2.2.46) является равенством для некоторых допустимых векторов X и У взаимосо-
пряженных задач, то эти векторы оптимальны.
Итак, для оптимальности допустимых векторов X и Y необходимо и достаточно
выполнение условия
СX=(A
T
Y)X=(AX)Y=BY. (2.2.49)
Равенства (2.2.49) напишем еще в виде

Страницы