Докажите теорему о разрешимости задачи линейного программирования на минимум.

Теорема. (о разрешимости задачи линейного программирования на минимум)

Если каноническая задача линейного программирования на минимум имеет допустимое решение, а целевая функция на множестве допустимых решений ограничена снизу, то эта задача имеет оптимальное решение.

▲ В теореме о существовании опорного решения было доказано, что если каноническая задача линейного программирования имеет допустимое решение, то эта задача имеет и опорное решение. Принимаем это опорное решение за начальное опорное решение и решаем задачу симплекс методом. Так как целевая функция ограничена снизу на множестве допустимых решений, то через конечное число шагов симплекс метода будет найдено оптимальное решение данной задачи. ■

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

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

(6) f(X) = γ_j x_j + γ₀,

(7) А_j x_j =B,

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

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

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

(9) A₁ k₁ + A₂ k₂ + … + A k = Ө.

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

(10) A₁ α ₁ + A₂ α ₂ + … + A α = В.

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

А₁( α₁ δ k₁) + А₂ ( α₂ δ k₂ ) + … + А ( α δ k ) = B.

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

39.Теорема (об оптимальном решении).

Если каноническая задача линейного программирования (1) – (3) имеет оптимальные решения, то одно из них является опорным решением этой задачи.

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

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

A₁ k₁ + A₂ k₂ + … + A k = Ө.

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

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

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

А₁( α₁ δ k₁) + А₂ ( α₂ δ k₂ ) + … + А ( α δ k ) = B.

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

f(α⁰) < f(α^’),

f(α⁰) ≤ f(α^’’),

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

γ_j α_j + γ₀ < γ_j (α_j + δk_j) + γ₀,

γ_j α_j + γ₀ ≤ γ_j (α_j  δk_j) + γ₀.

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

0 < δ γ_j k_j,

0 ≤ – δ γ_j k_j.

Таким образом, предположение о том, что вектор α⁰ не является опорным решением не верно. Следовательно, вектор α⁰ является опорным решением задачи (1) – (3). ■

Поиск по сайту: