 |
 |
 |
 |
|
 |
 |
33
Ax=b. Тем самым доказано, что иb
?
сх.
Замечание. Теорема 1.4, разумеется, верна и для оптимальных планов взаимно двойственных задач:
f(x*)
? f*(u*)
, где х* и u*—любые оптимальные планы задач (D, f) и (D*,f*). На самом деле, как будет
видно из дальнейшего, справедливо равенство f(x*) = f*(u*).
Теорема 1.5. Если для некоторых допустимых планов
x
~
и
u
~
взаимно двойственных задач (D, f) и
(D*,f*) выполняется равенство f(
x
~
)=f*(
u
~
), то
x
~
и
u
~
являются оптимальными планами для этих
задач.
Доказательство.
Согласно теореме 1.4, для всех допустимых планов х задачи (D, f) справедливо неравенство сх <
u
~
b.
По условию теоремы f(
x
~
)=f(
u
~
)
или, что то же самое, с
x
~
=
u
~
b. Следовательно, верно утверждение: для
любого x
D с
x
~
>сх, т. е. х является оптимальным планом для задачи (D, f).
Рассуждения, доказывающие оптимальность плана
u
~
для задачи (D*,f*), проводятся аналогично.
Теорема 1.6. Если целевая функция f в задаче (D, f) не ограничена сверху, то двойственная к
ней задача (D*,f*) не имеет допустимых планов.
Доказательство.
Если предположить, что у двойственной задачи (D*,f*) существует хотя бы один допустимый план ??,
то, согласно теореме 1.4, для любого допустимого плана х задачи (D, f) справедливо неравенство f(x)
?
f*(
u
~
) ?
<+
. Последнее означает, что целевая функция f задачи (D, f) ограничена сверху. Поскольку это
противоречит условию теоремы, предположение о существовании допустимых планов двойственной
задачи (D*,f*) неверно.
Следующее утверждение, известное как теорема равновесия, используется при проверке
оптимальности планов ЗЛП.
Теорема 1.7. Пусть х* и u* — оптимальные планы канонической задачи (D, f) и двойственной по
отношению к ней задачи (D*,f*). Если j-я компонента плана х* строго положительна (x
j
*
>0), то
соответствующее j-e ограничение двойственной задачи выполняется как равенство: а
1,j
u1*
+...+а
m,j
u
m
*= с
j
; если же j-й компонент плана х* имеет нулевое значение (х
j
* =0), то j-e ограничение
двойственной задачи выполняется как неравенство: а
1,j
u1* +...+а
m,j
u
m
*
?
с
j
.
Доказательство.
Векторы х* и и*, будучи допустимыми планами соответствующих задач, удовлетворяют условиям:
Ах* = b, х* > 0 и и*А-с ? 0. Найдем скалярное произведение
Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных
задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0 . Однако скалярное произведение
двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про-
изведения их соответствующих координат равны нулю. Следовательно, если
x
j
* > 0, то u*а
j
–
с
j
= 0,
если же x
j
= 0, то возможно u*а
j
– с
j
?
0 , что и утверждается в теореме.
Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс
решения основной задачи на решение двойственной, которое в определенных случаях может оказаться
более простым. Например, задача, область допустимых значений которой описывается двумя
уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим
методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая
имеет только две переменные.
Еще раз вернемся к таблице Т2
(q)
(рис. 1.8), получаемой на финальной итерации процедуры
модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы
?
-1
(?
(q)
),
для которой было введено обозначение
?
0
(?
(q)
). Поэлементно она может быть записана в следующем
виде:
Введем вектор
u
~
=
(?
0,1
(?
(q)
), ?
0,2
(?
(q)
),..., ?
0,m
(?
(q)
)). Нетрудно проверить, что строка оценок a
0
(?
(q)
)
может быть представлена следующим образом: