Следствие из леммы 2 и признака оптимальности

Задача А. Максимизировать линейную функцию на множестве n -мерных векторов х = (х1, х2,..., хn), удовлетворяющих условиям 1. , , 2.

Задача А*.Минимизировать линейную функцию на множестве m-мерных векторов y = (y1, y2,..., ym), удовлетворяющих системе линейных неравенств 1. - 2. , .

Теорема. Если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и оптимальные соответственно в задачах А и А*.

Доказательство. Пусть К – допустимое и двойственно базисное множество. Это значит, что вектора и - допустимые. На основании леммы 2 , а это достаточно для того, чтобы вектор был оптимальным и вместе с ним и вектор (см. краткую форму достаточного признака оптимальности)▄

Лемма 3

Дано:

допустимое базисное множество К, х (К) =(х₁, х₂,..., х_п).

для некоторого известны коэффициенты g_k в разложении вектора посоответствующим базисным векторам:

= .

Тогда вектор = () с компонентами

, , , , ,

удовлетворяет условию , причем

, где величина определяется из системы , .

Лемма 3

Доказательство. Поскольку – д.б.м., то отвечающий ему вектор – допустимый в задаче А. Он будет оптимальным, если выполняется признак оптимальности:

, , .

Возможны случаи:

а) все – оптимальный вектор.

б) для некоторого признак оптимальности нарушен и нужно найти другой вектор = (), который должен быть допустимым, т.е. удовлетворять условиям:

1)

2)

3) – т.к. задача на , то целевая функция должна увеличиться

 

Лемма 3

Доказательство (продолжение). Покажем, что выполнено 2). Разобьем сумму в условии 2) на несколько сумм:

 

Учитывая, что , и

 

Имеем:

 

(1) (первая скобка равна 0, т.к. – старый допустимый вектор)

т.к. = , то получим в (1): (0)+ (0)=0

вектор удовлетворяет условию 2).

Покажем, что выполнено условие 1):

Возможны два случая:

а) все коэффициенты g_k≤ 0 в выражении .

б) среди коэффициентов g_k име­ются положительные.

 

Рассмотрим случай а).

Т.к. g_k≤ 0, то

 

Если имеет место случай а),то векторы , опреде­ляемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функ­ция на множестве таких векторов не ограничена сверху.

По теореме двойственности в двойственной задаче допустимый вектор не существует, следовательно, вектор х не оптимальный.

Рассмотрим случай б), когда среди коэффициентов g_k име­ются положительные.

Пусть, например, ;

.

Тогда . Для того, чтобы эти неравенства выполнялись одновременно, находят

Следовательно, , если

причем

, т.е. ограничена сверху и по теореме двойственности вектор х – оптимальный.

Если имеет место случай б),то векторы являются допустимыми в задаче А лишь при , где

,

причем ■