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

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

▲Любое опорное решение имеет хотя бы один базис причем один и тот же базис не может быть одновременно базисом двух различных опорных решений =>,число опорных решений не превосходит число базисов системы векторов условий КЗЛП. В то же время известно, что число базисов любой системы из n n-мерных векторов конечно и не превосходит число сочетаний

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

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

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

▲Необх. A_i1,…,A_ir – базис сис-мы вект КЗЛП(1)-(3) явл базисом опорн реш α=( α₁,…, α_n) по опр базиса опорн реш => для любого i=(i₁,...,i_r) выполн α_i=0

Из опр опорн реш => оно явл допустим реш задачи по опр доп реш =>α удов огранич (3), т.е. α_i1≥0,…, α_ir≥0 и явл реш сист лин уравн (2), т.е. A_i1α_i1+…+A_irα_ir=B=> В линейном выражении через вект базиса A_i1,…,A_ir с неотр коэф

Достаточность: A_i1,…,A_ir – набор базисных векторов сис-мы условий КЗЛП(1)-(3) и A_i1α_i1+…+A_irα_ir=B, где α_i1≥0,…, α_ir≥0

Рассмотрим α=(0,…,0, α_i1,0,…,0, α_i2,0,…,0, α_ir, 0, …,0) – этот вектор удов (3) и явл решением СЛУ(2) => α является доп. Решением КЗЛП(1)-(3)

Ненулевым координатам α соотв вектора из набора базисных векторов из A_i1,…,A_ir. При

Этом может случиться, что среди координат α₁,…, α_r, кот =0. В этом случае остальным координатам вектора α будут соотв вектора не всего базисного набора. Однако любая часть ЛНЗ системы векторов также ЛЗ. Т.о. вектор α по опр явл опорн реш КЗЛП(1)-(3). Кроме того вектора векторы условий данной ЗЛП не попавшие в набор базисн. вект., соотв нулевым координатам вектора α (по построению) => по опр базиса опорн решения набор базисн векторов A_i1,…,A_ir, сист векторов условий КЗЛП(1)-(3) является базисом опорного решения α. ■

Замечание: На основании свойства (4) можно найти все опорные решения КЗЛП. Для этого необходимо:

1) Найти все базисы сист вект условий данной задачи

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

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

19. Теорема об оптимальном решении канонической задачи линейного программирования.

1. Дана КЗЛП F(X) = ∑ⁿ_i=1 γ_j x_j + γ₀,

2. ∑ⁿ_i=1 A_j x_j = B,

3. x_j≥0, j=1, 2, … , n

Замечание: Задача (1)-(3) – может иметь ни одного оптимального решения. При этом имеется след теорема: если КЗЛП(1)-(3) имеет оптимальное решение то хотя бы одно из них является опорным решением этой задчи.

▲Рассмотрим оптим реш КЗЛП(1)-(3) с наим числом ненул коорд. Пусть это α⁰=( α₁, α₂,…, α_l,0,0…), где α₁>0,…, α_l>0. Покажем, что α⁰ – опорное решение КЗЛП(1)-(3) от противного. Предположим, что вектор α⁰ не является оптимальным решением. Тогда по опр опорного решения A_i1,…,A_ir будут ЛЗ => по опр ЛЗ найдется ненулевой набор чисел k₁,…,k_ℓ, такой что выраж будет усл A₁k₁+…+A_ℓk_ℓ=0 (4). Т.к. α⁰ является оптим решен=> по опр α⁰ явл дополнит решением (1)-(3)=> α⁰ – решение СЛУ(2)=> A_i1α_i1 +…+A_iℓα_iℓ=B (5)

Вывод: δ>0 удовл лемме: Умножим соотношение (4) на ±δ и сложим с (5)

A₁(α₁±δk₁)+…+A_ℓ(α_ℓ±δk_ℓ)=B

Из этого соотношения => α^/=( α₁+δk₁+…+α_ℓ+δk_ℓ) α^//=( α₁- δk₁,…, α_ℓ-δk_ℓ)

В силу арифметич леммы α_j± δk≥0, j=1,…,ℓ, причем хотя бы одно из них=0, поэтому одно из доп решений α^/ и α^//, содерж ненулев координат меньше, чем 2, пусть это α^/=> α^/ не явл оптимальн, т.к. был выбран оптим вектор α⁰ с наим числом ненулевкоорд, равных ℓ

Поэтому выполняется:

- противоречивая сист=> предположение о том, что α⁰ не явл опорн решением неверно => α⁰ – опорное решение. ■

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

Замечание: на практике такой способ (перебор опорн реш КЗЛП) не годен. Это связано с тем, что задача может иметь много разных опорных решений и для их перебора потребуется большое кол-во времени, поэтому разработали методы целенаправ выбора опорн решений, в кот значение целевой ф-ции на кажд выбр опорн реш меньше, чем на предыд опорное реш. Таким методом является симплекс.

20. 1) Если СТ приведена к базису A_i1,…,A_ir опорн реш α, то в столбце B^/ находятся координаты опорного решения α, соответствующие векторам базиса A_i1,…,A_ir, т.е. α₁^/= α_i1,…, α_r^//= α_ir

▲Если α=(0,…,0, α_i1,0,…,0, α_in ,0,…,0, α_ir, 0, …,0) опорное решение КЗЛП(1)-(3) по опр => α – дополнительное решение этой задачи => α является реш СЛУ(2) =>по опр => A_i1α_i1+ A_i2α_i2+…+A_irα_ir=B (6). Отметим, что решением (5) является вектор α^/=(0,…,0, α_i^/,0,…,0, α^/₂,0,…,0, α^/_r, 0, …,0). Т.к. система (5) получена из (4) методом Гаусса, то => (5)(4)=> α^/ - реш (4).

A_i1α_i^/+ A_i2α^/₂+…+A_ir α^/_r =B (7), вычитаем из (6) (7) =>

(6)-(7)= A_i1(α_i1-α₁^/)+ A_i2(α_i2-α2^/)+…+A_ir(α_ir-α_r^/)=0 (8). Т.к. A_i1,А_i2,…,A_ir обр базис системы уравнений(1)-(3), то A_i1,…,A_ir – ЛНЗ => по опр соотн (8) возможно, если α_i1=α₁,…, α_ir=α_r^/ => α_i1=α₁^/,…, α_ir=α_r^/.■

2)Оценки базисных векторов всегда =0, т.е. если A_i1,А_i2,…,A_ir – базис опорнонго решения α, то δ_i=δ_i2=δ_ir=0

▲Из постр δ_i, δ_i2,…, δ_ir. ■

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

▲Из постр строки оценок в т.(5) базиса при базисе A_i1,А_i2,…,A_ir, с учетом св-ва (1) α_i1=α₁^/, α_i2= α^/₂, α_ir=α_r^/, имеем S_γ=γ₀+γ_i1α_i1+γ₂α_i2+…+γ₂α_ir.

21. Лемма (о целевой функции). (стр. 65):

1. F(X) = ∑ⁿ_i=1 γ_j x_j + γ₀,

2. ∑ⁿ_i=1 A_j x_j = B,

3. x_j≥0, j=1, 2, … , n.

Пусть δ₁, … , δ_j, … , δ_n – оценки векторов условий задачи (1) – (3), приведенные к базису опорного решения а. Если вектор β=( l₁, … , l_j, … , l_n) является допустимым решением данной задачи, то f(β)=f(a) - ∑ⁿ_j=1 δ_j l_j.

22. (стр. 66) Теорема (достаточное условие оптимальности опорного решения):

1. F(X) = ∑ⁿ_i=1 γ_j x_j + γ₀,

2. ∑ⁿ_i=1 A_j x_j = B,

3. x_j≥0, j=1, 2, … , n.

Если для опорного решения а⁰ КЗЛП (1) – (3) на минимум найдётся базис, для которого все оценки неположительные, то есть δ_j≤0 для всех j=1, 2, … , n, то вектор а⁰ является оптимальным решением данной задачи.