Сформулируйте теорему о существовании опорного решения.

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

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

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

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

(2) А_j x_j =B,

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

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

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

(1)A₁ k₁ + A₂ k₂ + … + A k = Ө.

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

(2)A₁ α ₁ + A₂ α ₂ + … + A α = В.

Прибавив к соотношению (5) соотношение (4), умноженное на δ, получим

А₁( α₁ δ k₁) + А₂ ( α₂ δ k₂ ) + … + А ( α δ k ) = B.

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

Сколько базисов системы векторов условий КЗЛП может соответствовать одному опорному решению?

Любому опорному решению канонической задачи линейного программирования соответствует, по крайне мере, один базис системы векторов условий этой задачи.

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

Пусть вектор α = ( 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 образуют базис опорного решения α.

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