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

Базисное множество

Вторая каноническая форма задачи ЛП в векторной форме

Введем в рассмотрение m-мерные векторы:

Тогда задачи 3 и 3* запишутся в следующей форме:

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

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

Пусть – m-мерное подмножество множества J.

Множество К называют базисным множеством, если отвечающие ему векторы являются линейно не­зависимыми, т.е. образуют базис в пространстве R^m. Число векторов в базисном множестве К равно числу m уравнений в условии 2 задачи А:

→max

на множестве n-мерных векторов

х = (х₁, х₂, . . ., х_n),

удовлетворяющих условиям

1 ., ,

2.

Пример. Векторы - линейно независимые, т.к. , К={1,2}.

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

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

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

Т.е. система

(17)

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

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

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

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