Следствие из леммы 2 и признака оптимальности
Задача А. Максимизировать линейную функцию
![]() ![]() ![]() ![]() | Задача А*.Минимизировать линейную функцию
![]() ![]() ![]() |
Теорема. Если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и
оптимальные соответственно в задачах А и А*.
Доказательство.Пусть К – допустимое и двойственно базисное множество. Это значит, что вектора и
- допустимые. На основании леммы 2
, а это достаточно для того, чтобы вектор
был оптимальным и вместе с ним и вектор
(см. краткую форму достаточного признака оптимальности)▄
Лемма 3
Дано:
допустимое базисное множество К, х (К) =(х1, х2, . . ., хп).
для некоторого известны коэффициенты gk в разложении вектора
посоответствующим базисным векторам:
=
.
Тогда вектор
= (
) с компонентами
,
,
,
,
,
удовлетворяет условию , причем
, где величина
определяется из системы
,
.
Лемма 3
Доказательство. Поскольку – д.б.м., то отвечающий ему вектор
– допустимый в задаче А. Он будет оптимальным, если выполняется признак оптимальности:
,
,
.
Возможны случаи:
а) все
– оптимальный вектор.
б)
для некоторого
признак оптимальности нарушен и нужно найти другой вектор
= (
), который должен быть допустимым, т.е. удовлетворять условиям:
1)
2)
3) – т.к. задача на
, то целевая функция должна увеличиться
Лемма 3
Доказательство (продолжение). Покажем, что выполнено 2). Разобьем сумму в условии 2) на несколько сумм:
Учитывая, что ,
и
Имеем:
(1)
(первая скобка равна 0, т.к.
– старый допустимый вектор)
т.к.
=
, то получим в (1): (0)+
(0)=0
вектор
удовлетворяет условию 2).
Покажем, что выполнено условие 1):
Возможны два случая:
а) все коэффициенты gk≤0 в выражении .
б) среди коэффициентов gk имеются положительные.
Рассмотрим случай а).
Т.к. gk≤0, то
![]() |
Если имеет место случай а),то векторы , определяемые в лемме 3, являются допустимыми в задаче А при всех
, а линейная функция
на множестве таких векторов не ограничена сверху.
По теореме двойственности в двойственной задаче допустимый вектор не существует, следовательно, вектор х не оптимальный.
Рассмотрим случай б), когда среди коэффициентов gk имеются положительные.
Пусть, например, ;
.
Тогда . Для того, чтобы эти неравенства выполнялись одновременно, находят
Следовательно,
, если
причем
, т.е.
ограничена сверху и по теореме двойственности вектор х – оптимальный.
Если имеет место случай б),то векторы являются допустимыми в задаче А лишь при
, где
,
причем
■