Итак, базисное множество является двойственно допустимым, если величины
, , (18)
удовлетворяют неравенствам
, (19)
Отметим, что величины (18) тесно связаны с коэффициентами разложения соответствующих векторов по рассматриваемым базисным векторам, а именно:
, , (20)
где - коэффициенты разложения векторов по рассматриваемому базису, т. е. . (21)
Действительно, учитывая (18), (21), , и свойства скалярного произведения, получаем
. (22)
Лемма 2
Каково бы ни было базисное множество K, для соответствующих векторов х (К) и у (К) имеет место равенство
.
Доказательство. Так как , , , , получаем
,
что и требовалось показать.▄
Следствие из леммы 2 и признака оптимальности
Задача А. Максимизировать линейную функцию на множестве n -мерных векторов х = (х1, х2,..., хn), удовлетворяющих условиям 1. , , 2. | Задача А*.Минимизировать линейную функцию на множестве m-мерных векторов y = (y1, y2,..., ym), удовлетворяющих системе линейных неравенств 1. - 2. , . |
Теорема. Если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и оптимальные соответственно в задачах А и А*.
Доказательство. Пусть К – допустимое базисное множество и двойственно допустимое базисное множество. Это значит, что вектора и - допустимые. На основании леммы 2 , а это достаточно для того, чтобы вектор был оптимальным и вместе с ним и вектор (см. краткую форму достаточного признака оптимальности)▄
Лемма 3
Пусть задано некоторое базисное множество К и отвечающий ему вектор
х (К) = (х1, х2,..., хп). Кроме того, для некоторого известны коэффициенты gk в разложении вектора посоответствующим базисным векторам:
= .
Тогда при любом вектор = () с компонентами
, , , , ,
удовлетворяет условию , причем значение линейной функции на этом векторе может быть вычислено по формуле
,где величина определяется из системы , .
Лемма 3
Доказательство. Имеем: = (23)
После умножения соотношения (18) на и переноса всех его членов в левую часть получаем равенство: (24)
Имеем: (25)
Складывая (19) и (20), получаем
. (26)
Следовательно, интересующий нас вектор удовлетворяет требуемому условию . Далее, для вектора выполнены равенства (в силу того, что , , , , и (22))
(27) ▄
Следствие 1 из леммы 3
Вектор должен удовлетворять условию неотрицательности, т.е. .
Возможны два случая:
а). Все коэффициенты gk≤ 0 в
б) среди коэффициентов gk имеются положительные
Следствие 1. Если имеет место случай а),то векторы , определяемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функция на множестве таких векторов не ограничена сверху.
Действительно,
По теореме двойственности (слайд 42) в двойственной задаче допустимый вектор не существует, следовательно, вектор х не оптимальный ▄
Следствие 2 из леммы 3
Вектор должен удовлетворять условию неотрицательности, т.е. .
Случай б) среди коэффициентов gk имеются положительные
Следствие 2. Если имеет место случай б),то векторы являются допустимыми в задаче А лишь при , где
,
причем
.
Пусть ; выполняется всегда; . Тогда , чтобы эти неравенства выполнялись одновременно, находят