Билет №11

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

Билет №12

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

Лемма (арифметическая). Пусть а₁, а₂, …., a_l некоторые положительные числа, а k₁, k₂, … k_l ненулевой набор чисел, т.е. найдется номер j такой, что k_j ≠ 0, j = 1, 2, … l. Тогда найдется положительное число δ такое, что: a_j ± δ k_j ≥ 0 для всех j = 1, 2, … l, а одно из чисел { a_j ± δ k_j } обязательно равны 0.

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

:

(1)f(X) = (2)

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

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

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

(4) А₁ k₁ + A₂ k₂ + … + A_l k_l= θ

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

(5) А₁ α ₁ + A₂ α ₂ + … + A_l α _l= В

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

А₁ (α ₁ ± δ k₁) + A₂ (α ₂ ± δ k₂) … + A_l (α _l ± δ k_l) = В

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

Допустимое решение α = (α₁, α₂, α_j…,α_n) канонической задачи линейного программирования. (1)-(3) называется опорным решением, если векторы условий А_i1,А_i2,…,А_ik, соответствующие нулевым координатам вектора α = (α₁, α₂, α_j…,α_n) образуют линейно независимую систему векторов

Замечание. Чтобы выяснить, является ли вектор α = (α₁, α₂, α_j…,α_n) опорным решением (1)-(3), необходимо:

1. Проверить, является ли вектор α решением системы линейных уравнений (2),

2. Проверить, удовлетворяет ли вектор α ограничением (3),

3. Выписать номера всех ненулевых координат вектора α и показать, что векторы условий рассматриваемой задачи с этими номерами образуют линейно независимую систему векторов.