Единственность базиса у невырожденного опорного решения КЗЛП

Свойство (базисов опорного решения). Невырожденному опорному решению канонической ЗЛП (1)-(3) может соответствовать только один базис системы векторов условий данной задачи.

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

 

Билет №15

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

Свойство (базисов опорного решения). Один и тот же базис системы векторов условий канонической задачи линейного программирования (1)-(3) не может являться базисом двух различных опорных решений этой задачи.

Доказательство: Предположим, что базис А₁,..., А_г системы векторов условий КЗЛП (1) - (3) является базисом опорного решения: а’ =(а'₁,..., а_г, а’_r+1,… а’_n) и опорного решения а” =(a"₁,..., а”_r, а"_г+ь..., а” _п), у которых a’_r+1= 0,..., а’_n = 0 и a”_r+1 = 0,..., а”_n = 0. Следовательно, a’ =(a'₁,..., a_r, 0,..., 0) и a” =(a"₁,..., a” _r, 0,..., 0). По определению опорного решения векторы a’ =(a'₁,..., a’_r, 0,..., 0) и a” =(a"₁,..., a” _r, 0,..., 0)являются допустимыми решениями КЗЛП (1) - (3) и, следовательно, являются решением системы линейных уравнений (2). Поэтому, подставляя указанные векторы в систему линейных уравнений (2), получаем: A₁ а’₁ + A₂ а’₂ +...+ А_г а'_г = В и A₁ а”₁ + A₂ а”₂ +...+ А_г а”_г = В.

После вычитания второго соотношения из первого, получим: A₁ (а’₁ – а”₁) + A₂ (а’₂ – а”₂) +...+ А_г(а'_г – а”_r) = θ

Из этого соотношения с учетом линейной независимости базисных векторов A₁,..., А_г, имеем: а’₁ – а”₁= 0, а’₂ – а”₂= 0,..., a_r-a, = 0. то есть а’₁ = а”₁, а’₂ = a"₂,..., a’_r = а”_r. Следовательно, один и тот же базис системы условий КЗЛП (1) - (3) является базисом только одного опорного решения, т.к. а' = а"

Билет №16

Число опорных решений канонической задачи линейного программирования

КЗЛП имеет конечное число различных опорных решений.

Любому опорному решению задачи соответствует не менее одного базиса системы векторов условий задачи. Один и тот же базис системы векторов условий рассматриваемой задачи не может быть базисом двух различных опорных решений этой задачи. Следовательно, число опорных решений не превосходит числа базисов системы векторов условий задачи. В то же время, число базисов любой системы из n m-мерных векторов конечно и не превосходит числа сочетаний из n по m, то есть c=n!/(n-m)!m!.

Следовательно, число опорных решений КЗЛП тоже конечно.

 

 

Билет №17

Связь базиса системы векторов условий КЗЛП с базисом некоторого опорного решения этой задачи

Базис системы векторов условий КЗЛП (1)-(3) является базисом некоторого опорного решения этой задачи тогда и только тогда, когда вектор ограничений В СЛУ (2) линейно выражается через базисные векторы с неотрицательными коэффициентами.

Необходимость. Пусть Аі₁, Аі₂, …, Аіr базис системы векторов условий задачи (1)-(3) является базисом опорного решения α=(α₁,…,αј,…,αn) этой задачи. Из определения базиса опорного решения следует, что αі=0 для любых і≠і₁,і₂,…,іr.

По определению, опорное решение является допустимым решением задачи(1)-(3), то есть оно удовлетворяет ограничениям (3) αі₁≥0, αі₂≥0,…, αіr≥0 и является решением СЛУ (2),то есть обращает ее в точное числовое равенство вида Аі₁ αі₁+ Аі₂ αі₂+…+Аіr αіr=В. Следовательно, вектор ограничений В линейно выражается через базисные векторы Аі₁, Аі₂,…,Аіr с неотрицательными коэффициентами.

Достаточность. Пусть Аі₁, Аі₂,…,Аіr базис системы векторов условий задачи (1)-(3) и вектор ограничений В представим в виде Аі₁ αі₁+ Аі₂ αі₂+…+Аіr αіr=В,где αі₁≥0, αі₂≥0,…, αіr≥0. Рассмотрим вектор α=(0,…,0,αі₁,0,…,0,αі₂,0,…,0,αіr,0,…,0). Очевидно, что этот вектор удовлетворяет условию (3) и является решением СЛУ (2). Следовательно, вектор α является допустимым решением задачи(1)-(3), причем его ненулевым координатам соответствуют векторы из набора базисных векторов Аі₁, Аі₂,…,Аіr. Может случиться, что среди координат αі₁,αі₂,…,αіr окажутся такие, которые равны нулю(например, если вектор α является вырожденным). в этом случае остальным ненулевым координатам вектора будут соответствовать некоторая часть базисных векторов, которая будет линейно независимой. Таким образом, вектор α по определению является опорным решением задачи(1)-(3). Кроме того, векторы условий данной задачи, не попавшие в набор базисных векторов Аі₁, Аі₂,…,Аіr, будут соответствовать нулевым координатам рассматриваемого вектора α.

Следовательно, набор базисных векторов Аі₁, Аі₂,…,Аіr системы векторов условий задачи (1)-(3) является базисом опорного решения α.

 

Билет №18

Теорема об оптимальном решении КЗЛП

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

(4) f(X)=∑ γј*хј+γ₀,

(5) ∑ Ај*хј=В,

(6) хј≥0, ј=1,2,…,n.

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

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

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

А₁k₁+А₂k₂+…+А₁k₁=Ѳ.

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

А₁α₁+А₂α₂+…+А₁α₁=В.

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

А₁(α₁±δ*k₁)+А₂(α₂±δ*k₂)+…+ А₁(α₁±δ*k₁)=В.

Из последнего соотношения по определению решения системы уравнений следует, что векторы α΄=(α₁+δ*k₁, α₂+δ*k₂,…, α₁+δ*k₁) и α΄΄=(α₁-δ*k₁, α₂-δ*k₂,…, α₁-δ*k₁) являются решениями СЛУ(2). Если же число δ выбрать так, что оно удовлетворяет арифметической лемме, то координаты векторов α΄и α΄΄ будут удовлетворять условию (3), а сами векторы будут являться допустимыми решениями задачи(1)-(3) и при этом, хотя бы у одного из этих векторов число ненулевых координат будет меньше, чем 1. Пусть это будет вектор α΄. Тогда этот вектор не будет являться оптимальным решением, так как ранее был выбран оптимальный вектор α° с наименьшим числом 1 ненулевых координат. Поэтому для векторов α΄ и α΄΄ должна выполняться система неравенств:

{f(α°)<f(α΄),

{f(α°)≤f(α΄΄),

Которая равносильна системе:

{∑ γј*αј+γ₀<∑ γј(αј+δ*kј)+γ₀,

{∑ γј*αј+γ₀≤∑ γј(αј-δ*kј)+γ₀.

Откуда получаем противоречивую систему:

{0<δ∑γј*kј,

{0≤-δ∑γј*kј.

Таким образом, предположение о том, что вектор α° не является опорным решением неверно. Следовательно, вектор α° является опорным решением задачи.

Билет №19

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

1°. Если симплекс таблица приведена к базису Аі₁, Аі₂, …, Аіr опорного решения α, то в столбце В΄ находятся координаты опорного решения α, соответствующие векторам базиса Аі₁, Аі₂, …, Аіr, то есть α₁=αі₁, α₂=αі₂, …, αr=αіr.

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

(6) Аі₁ α₁+Аі₂ α₂+…+Аіr αr=В.

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

(7) Аі₁ αі₁+Аі₂ αі₂+…+Аіr αіr=В.

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

(8) Аі₁ (αі₁-α₁)+Аі₂ (αі₂-α₂)+…+Аіr (αіr-αr)=Ѳ.

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

Откуда,αі₁=α₁, αі₂=α₂,…,αіr=α₁.

2°. Оценки базисных векторов опорного решения всегда равны нулю, то есть, если векторы Аі₁, Аі₂,…,Аіr являются базисом некоторого опорного решения задачи (1)-(3), то δі₁=δі₂=…,=δіr.

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

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

Из построения строки оценок для системы векторов условий задачи (1)-(3), приведенной к базису Аі₁, Аі₂, …Аіr, и с учетом того, что α₁=αі₁, αі₂, …, α₁=αіr.

 

 

Билет №20

Лемма о целевой функции

Пусть δ₁,…,δј,…,δn оценки векторов условий задачи (1)-(3), приведенных к базису опорного решения α. Если вектор β=(l₁,…,lј,…,ln) является допустимым решением данной задачи, то f(β)=f(α)-∑ δј lј.

Пусть векторы А₁, А₂, …, Аr являются базисом опорного решения α=(α₁,α₂,…,αr,0,0,…,0). Тогда симплекс таблица системы векторов условий задачи(1)-(3), приведенных к данному базису будет иметь вид:

Где по правилу построения строки (δ₁,…,δј,…,δn), оценки примут следующие значения: δ₁=δ₂=…=δr=0 и

Так как для базисных векторов А₁, А₂, …, Аr оценки равны нулю, то есть δ₁=δ₂=…=δr=0, то значение целевой функции на векторе β можно записать в виде:

f(β)= γ₀+γ₁α₁+…+γr αr-δ r+₁ l r+₁- δ r+₂ l r+₂-…-δn ln=f(α)-∑ δј lј.

Билет №21