49. Число опорных решений кзлп.

На основании предыдущего свойства можно найти все опорные решения канонической задачи линейного программирования, выполнив следующие действия:

• найти все базисы системы векторов условий данной задачи

• по каждому из найденных базисов разложить вектор ограничений B и выбрать среди них разложение с неотрицательными коэффицентами

• для каждого выбранного разложения вектора B с неотрицательныи коэффицентами выписать опорное решение исходной задачи

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

Условие. Любому опорному решению КЗЛП соответствует хотя бы один базис системы векторов условий этой задачи.

Доказательство. Пусть вектор α=(0,...0,α_i1,0….)является опорным решением КЗЛП

(1)F(x) =

(2)

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

По определению в системе векторов условий задачи (1) – (3) векторы A_i1, A_i2, …, A_il, соответствующие ненулевым координатам данного опорного решения, образуют линейно независимую систему векторов условий данной задачи. Пусть этим базисом будет система векторов A_i1,A_i2…A_il..A_il+1... A_jr. Тогда небазисным векторам из системы векторов условий задачи 1-3 соответствуют нулевые координаты опорного решения и по определению векторы A_i1,A_i2…A_jr образуют базис опорного решения α.

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

51.Теорема об оптимальных решениях кзлп

Теорема: Если КЗЛП имеет оптимальные решения, то одно из них является опорным решением этой задачи.

Док-во: Рассмотрим КЗЛП

(1)F=(x)=

(2)

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

Рассмотрим оптимальное решение задачи 1-3 с наименьшим числом нулевых координат. Пусть таким решением будет вектор и докажем что он является опорным решением задачи 1-3.

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

+ +… =θ

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

+ + =B

Получаем ( )+ ( )…=B

Отсюда следует, что по определению решения системы уравнений векторы α’=( + …, + ) и α’’=( - ,…, - ) являются решениям СЛУ(2).Еcли же число δ выбрать так, что оно удовлетворяет арифмитической лемме, то координаты векторов α’ и α’’ будут удовлетворять условию (3) и при этом хотя бы у одного из этих векторов число ненулевых координат будет меньше, чем l.Пусть этот вектор α’,тогда он не будет являться оптимальным решением. Для векторов α’ и α’’ должна выполняться система неравенств:

Отсюда противоречивая система:

Таким образом, вектор α^0 является опорным решением задачи 1-3.

52) Свойства симплекс таблицы: структура вектора ограничений, оценки базисных векторов и значение целевой функции.

(1) f(X) =

(2)

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

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

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

(6) А_i1 α_{i1 +} А_i2 α_{i2 + … +} А_ir = B.

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

(7) А_i1 α_i1^’ ₊ А_i2 α_i2^’ _{+ … +} А_ir α_ir^’ = B.

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

(8) А_i1 (α_i1 - α_i1^’ ) + А_i2 (α_i2 - α₂^’) + … + А_ir (α_ir - α_r^’) = ϴ.

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

2⁰. Оценки базисных векторов опорного решения всегда равны нулю, то есть, если векторы А_i1, А_i2, … , А_ir являются базисом некоторого опорного решения задачи (1) – (3), то δ_i1 = δ_i2 = …, = δ_ir

▲ Доказательство следует из построения строки оценок системы векторов условий, приведенных к базису опорного решения. ■

3⁰. Если симплекс таблица приведена к базису опорного решения α, то δ₀ = ƒ(α).

▲ Из построения строки оценок для системы векторов условий задачи (1) – (3), приведенной к базису А_i1, А_i2, … , А_ir , и с учетом того, что α_i1 = α_i1^’, α_i2 = α₂^’, …, α_ir = α_r^’ следует: δ₀ = γ₀ + γ_i1 α_i1 + γ_i2 α_i2 + … γ_ir α_ir = f(α). ■

▲ Приведем систему векторов условий данной задачи к базису А₁, А₃ опорного решения α = (1,0,1)

<=> <=> δ

В полученной симплекс таблице имеем строку оценок δ = (0,-13, 0) системы векторов условий, приведенных к базису А₁, А₃ опорного решения α = (1, 0, 1), а δ₀ = 2 соответствует значению целевой функции на этом опорном решении f(α) =3*1+4*0–1*1=2, следовательно, δ₀ = f(α). ■