Доказательство.

Пусть вектор а = (0, … , 0, а_i1, 0, … , a_i2, 0, … , 0, a_ir, 0, … , 0) – невырожденное опорное решение КЗЛП, у которого по определению a_i1 >0, a_i2>0, … , a_ir>0, где r=rang {A₁, … , A_n}, и в соответствующий ему базис системы условий КЗЛП должны входить векторы условий КЗЛП – А_i1, A_i2, … , A_ir. Так как ранг системы векторов условий КЗЛП совпадает с количеством ненулевых координат данного опорного решения, то векторы А_i1, A_i2, … , A_ir могут образовывать только единственный базис, соответствующий рассматриваемому опорному решению.

16. Среди базисов системы векторов А₁, … , А_j, … , A_n условий КЗЛП

4. F(X) = ∑ⁿ_i=1 γ_j x_j + γ₀,

5. ∑ⁿ_i=1 A_j x_j = B,

6. x_j≥0, j=1, 2, … , n.

имеются базисы, соответствующие опорным решениям данной задачи.

Определение: Базис А_i1, A_i2, … , A_ir системы векторов А₁, … , А_j, … , A_n условий задачи (1)-(3) называется базисом опорного решения а=(а₁, а₂, … , а_j, … , a_n), если а₁=0 для любых i не равных i₁, i₂, … , i_r.

Таким образом, базис А_i1, A_i2, … , A_ir системы векторов А₁, … , А_j, … , A_n условий задачи (1)-(3) называется базисом опорного решения а=(а₁, а₂, … , а_j, … , a_n), если небазисным векторам из системы векторов условий задачи (1)-(3) соответствуют нулевые координаты опорного решения.

Замечание. Т.к. векторы условий, соответствующие ненулевым координатам опорного решения а=(а₁, а₂, … , а_j, … , a_n), входят в каждый его базис, то это опорное решение может иметь не один базис.

Определение. Допустимое решение а=(а₁, а₂, … , а_j, … , a_n ) КЗЛП (1)-(3)называется опорным решением, если векторы условий А_i1, A_i2, … , A_{i k} , соответствующие ненулевым координатам вектора а=( а₁, … , а_j, … , а_n ), образуют линейно независимую систему векторов.

Замечание. Чтобы выяснить, является ли вектор а=( а₁, … , а_j, … , а_n ) опорным решением (1) – (3), необходимо:

-проверить, является ли вектор а решением системы линейных уравнений (2);

-проверить, удовлетворяет ли вектор а ограничениям (3);

-выписать номера всех ненулевых координат вектора а и показать, что векторы условий рассматриваемой задачи с этими номерами образуют линейно независимую систему векторов.

Теорема ( о существовании опорного решения ). Если КЗЛП имеет хотя бы одно допустимое решение, то эта задача имеет и опорное решение.

Доказательство.

Рассмотрим КЗЛП:

1. F(X) = ∑ⁿ_i=1 γ_j x_j + γ₀,

2. ∑ⁿ_i=1 A_j x_j = B,

3. x_j≥0, j=1, 2, … , n

которая имеет хотя бы одно допустимое решение. Из всех допустимых решений данной задачи выберем допустимое решение с наименьшим числом ненулевых координат. Пусть таким решением будет вектор а=( а₁ , … , a_l, 0, … , 0), где координаты а₁ > 0, … , a_l > 0, и докажем, что выбранный вектор является опорным решением задачи (1) – (3).

Предположим противное, а именно, что вектор а не является опорным решением. Тогда по определению опорного решения, векторы А₁, А₂ , … , А_l , соответствующие ненулевым координатам выбранного вектора а, образуют линейно независимую систему. Из определения линейно зависимой системы векторов следует, что найдётся ненулевой набор чисел k₁, k₂ , … , k_l такой, что будет выполняться соотношение

4. A₁ k₁ + A₂ k₂ + … + A_l k_l = Ө.

Так как вектор а является допустимым решением рассматриваемой задачи, то по определению, этот вектор является решением системы линейных уравнений (2). Тогда по определению решения системы уравнений должно выполняться соотношение

5. A₁ а₁ + A₂ а₂ + … + A_l а_l = В.

Прибавив к соотношению (5) соотношение (4), умноженное на ±δ, получим A₁ ( а₁ ±δ k_l ) + A₂ (а₂ ±δ k₂ ) + … + A_l (а_l ±δ k_l ) = B.

Из последнего соотношения следует, что векторы а’=(a₁ + δ k₁, a₂ + δ k₂, … , a_l + δ k_l, 0, …, 0) и a”=( a₁ - δ k₁, a₂ - δ k₂, … , a_l - δ k_l, 0, …, 0) являются решениями системы линейных уравнений (2). Если же число δ выбрать так, что оно удовлетворяет арифметической лемме , то координаты векторов а’ и a” будут удовлетворять условию (3), а сами векторы будут являться допустимыми решениями задачи (1) – (3) и при этом, хотя бы у одного из этих векторов число ненулевых координат будет меньше, чем l. Это противоречит выбору допустимого вектора а. Следовательно, вектор а является опорным решением задачи (1) – (3). Ч. Т. д.