Билет №13

Существование базиса опорного решения КЗЛП

(1)f(X) = (2)

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

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

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

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

Билет №14

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

Рангом системы векторов называется число векторов в любом базисе системы, т.е. рангом системы векторов является максимальное число линейно независимых векторов системы.

Число ненулевых составляющих опорного плана не превышает числа m ограничений (не превзойти имеющихся объёмов ресурсов):

Опорный план, содержащий ровно m положительных компонент, называется невырожденным, и в противном случае - вырожденным.

Билет №15

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

Свойство (базисов опорного решения). Невырожденному опорному решению канонической ЗЛП (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 могут образовывать только единственный базис, соответствующий рассматриваемому опорному решению.

Билет №16

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

Свойство (базисов опорного решения). Один и тот же базис системы векторов условий канонической задачи линейного программирования (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) является базисом только одного опорного решения, т.к. а' = а"