Допустимое базисное множество

Для каждого базисного множества система линейных уравнений

относительно переменных x_k, , имеет единственное решение, отвечающее единственному разложению вектора — по соответствующим базисным векторам. Это решение можно дополнить до вектора х = (х₁, х₂,..., х_n), удовлетворя­ющего условию , положив , .

Получаемый таким образом вектор х = (х₁, х₂,..., х_n) будет обозначать­ся через х (К).

Т.е. система

(17)

имеет единственное решение.

Если компоненты , то вектор является допустимым вектором в задаче А.

В этом случае К называют допустимым базисным множеством (ДБМ),

=(х₁, х₂,..., х_m, 0,…,0).

Двойственно допустимое базисное множество

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

Для любого базисного множестваК единственное решение у (К) имеет система: , Если вектор у (К) является допустимым в двойствен­ной задаче А* (т. е. удовлетворяет условию2), то множе­ство К называется двойственно допустимым базисным мно­жеством (ДДБМ). Обозначим через , . Если , , то у (К) удовлетворяет условию2), то есть является допустимым вектором в двойственной задаче А*.

 

Двойственно допустимое базисное множество

Итак, базисное множество является двойственно допустимым, если величины

, , (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

Пусть задано некоторое базисное множество К и от­вечающий ему вектор

х (К) = (х₁, х₂,..., х_п). Кроме того, для некоторого известны коэффициенты g_k в разложении вектора посоответствующим базисным векторам:

= .

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

, , , , ,

удовлетворяет условию , причем значение линейной функции на этом векторе может быть вычислено по формуле

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

Лемма 3

Доказательство. Имеем: = (23)

После умножения соотношения (18) на и переноса всех его членов в левую часть получаем равенство: (24)

Имеем: (25)

Складывая (19) и (20), получаем

. (26)

Следовательно, интересующий нас вектор удовлетворяет требуемому условию . Далее, для вектора выполнены равенства (в силу того, что , , , , и (22))

(27) ▄

Следствие 1 из леммы 3

Вектор должен удовлетворять условию неотрицательности, т.е. .

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

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

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

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

Действительно,

 

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

 

 

Следствие 2 из леммы 3

Вектор должен удовлетворять условию неотрицательности, т.е. .

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

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

,

причем

.

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