Сколько ненулевых координат может иметь опорное решение?

Число ненулевых координат у любого опорного решения α канонической задачи линейного программирования не превышает r = rang{ A₁, …, A_n } – ранга системы векторов условий этой задачи.

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

Пусть вектор α = ( 0, …,0, α _i1 , 0,…, 0, α_i2 , 0, …, 0, α_il, 0, …, 0 ) является опорным решением канонической задачи линейного программирования

(1)f(X) = γ_j x_j + γ₀,

(2) А_j x_j =B,

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

где α _i1>0 , α_i2>0, …, α_i > 0. Тогда по определению в системе векторов условий задачи (1) – (3) векторы A_i1, A_i2, …, A_i , соответствующие ненулевым координатам данного опорного решения, образуют линейно независимую систему векторов, которую можно дополнить до базиса всей системы векторов условий данной задачи. Пусть этим базисом будет система из векторов A_i1, A_i2, … A_i A_{i +1}, , …, A_ir . Тогда небазисным векторам из системы векторов условий задачи (1) – (3) соответствуют нулевые координаты опорного решения и по определению векторы A_i1, A_i2, …, A_ir образуют базис опорного решения α.

Выше было доказано, что любому опорному решению КЗЛП соответствует хотя бы один базис системы векторов условий КЗЛП. Число векторов в любом базисе системы векторов условий КЗЛП совпадает с рангом этой системы. По определению базиса опорного решения, все координаты опорного решения α, соответствующие не базисным векторам системы векторов условий КЗЛП , равны нулю. Следовательно, ненулевых координат у опорного решения α не более, чем r.

Чему соответствуют элементы столбца ограничений В симплекс-таблицы, приведенной к базису опорного решения?

Если симплекс таблица приведенна к базису А_i1. А_i2, … , А_ir опорного решения α, то в столбце В^’ находятся координаты опорного решения α, соответствующие векторам базиса А_i1. А_i2, … , А_ir , то есть α₁^’ = α_i1, α₂^’ = α_i2, …, α_r^’ = α_ir,

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

Так как вектор α = ( 0, 0, …, 0, α_i1, 0, 0, …, 0, α_i2, 0, 0, …, 0, α_ir, 0, 0, .., 0) является опорным решением задачи (1) – (3), то он является и допустимым решением этой задачи, а следовательно, является решением системы линейных уравнений (2), то есть выполняется соотношение: (6) А_i1 α_i1+ A_i2 α_i2+…+ A_ir α_ir = B.

Решением системы (5) является вектор α^’ = ( 0, 0, …, 0, α₁^’, 0, 0, …, 0, α₂^’, 0, 0, … , 0, α_r^’, 0, 0, .., 0). Системы (5) и (4) равносильны, так как получены одна из другой методом Гаусса. Поэтому вектор α^’ является решением системы (4), и, следовательно, выполняться соотношение: (7) А_i1 α₁^’+ A_i2 α₂^’+…+ A_ir α_r^’ = B.

Вычитая из соотношения (6) соотношение (7), получаем соотношение:

(8)А_i1 (α_i1 – α₁^’ )+ A_i2 (α_i2 – α₂^’ )+…+ A_ir (α_ir – α_r^’ ) = Ө.

Так как векторы А_i1. А_i2, … , А_ir являются базисом системы векторов условий задачи (1) – (3), то они линейно независимы. Следовательно, соотношение (8) возможно, при α_i1 – α₁^’ = 0, α_i2 – α₂^’ = 0, …, α_ir – α₁^’ = 0. Откуда α_i1 =α₁^’, α_i2 = α₂^’, …, α_ir = α₁^’

Поиск по сайту: