Следствие из леммы 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 име­ются положительные.

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

.

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

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

причем

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

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

,

причем ■