34.Когда искусственная каноническая задача линейного программирования имеет оптимальное решение?

Задачи (4) – (6) имеет допустимые решение, одним из которых является, например, вектор β = (0, …, 0, b₁, b₂, …, b_m), так как опорное решение всегда является допустимым. Из (6) следует, что все искусственные переменные неотрицательны, т.е. х_n+i ≥ 0, i = 1, 2, …, m. Поэтому целевая функция (4) φ(X) = x_n+1 + x_n+2 + … +x_n+m ограничена снизу на множестве допустимых решений, т.е. φ(X) ≥ 0. Следовательно, по теореме о разрешимости канонической задачи линейного программирования, задачи (4) – (6) имеет оптимальное решение.■

Замечание. Так как у задачи (4) – (6) всегда известно начальное опорное решение, то ее можно решить симплекс методом, который через конечное число шагов приведет к оптимальному решению этой задачи.

1. φ(X) = x_n+1 + x_n+2 + … +x_n+m (min),

2. А_j x_j +E₁ x_n+1 + E₂ x_n+2 + … + E_m x_n+m =B,

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

где E_j – единичный вектор (j = 1, 2, …, m) , а x_n+1 , x_n+2 , … , x_n+m – искусственные переменные.

35.При каком решении искусственной кзлп исходная задача имеет опорное решение?

Теорема (о методе искусственного базиса)

Пусть вектор β = (α₁, α₂, …, α_n, α_n+1, α_n+2, …, α_n+m) является оптимальным решением искусственной задачи (4) –(6). Тогда:

Еесли α_n+1 = α_n+2 = …= α_n+m =0 , то вектор α = (α₁, α₂, …, α_n) является опорным решением исходной канонической задачи линейного программирования (1) – (3);

Доказательство

Докажем это утверждение. По условию вектор β = (α₁, α₂, …, α_n, α_n+1, α_n+2, …, α_n+m) является оптимальным решением искусственной задачи (4) – (6). Тогда вектор β является опорным решением этой задачи, а, следовательно, и допустимым решением и, по определению, является решением системы линейных уравнений (5), т. е. выполняется соотношение:

А₁ α ₁ +А₂ α ₂ +…+А_n α _n +E₁ α _n+1 + E₂ α _n+2 + … + E_m α _n+m =B,

Так как α_n+1 = α_n+2 = …= α_n+m =0 , то последнее равенство можно записать в виде А₁ α ₁ +А₂ α ₂ +…+А_n α _n =B.

Откуда, по определению, следует, что вектор α = (α₁, α₂, …, α_n) является допустимым решением исходной задачи (1) – (3).

Так как вектор β = (α₁, α₂, …, α_n, 0, 0, …, 0) является опорным решением искусственной задачи, то ненулевым координатам этого вектора соответствуют линейно независимые векторы условий этой задачи. Тогда некоторые из указанных линейно независимых векторов соответствуют ненулевым координатам вектора α = (α₁, α₂, …, α_n). Следовательно, вектор α является опорным решением исходной задачи (1) – (3).

36.При каком решении искусственной кзлп исходная задача не имеет решений?

Если среди чисел α_n+1, α_n+2, …, α_n+m , хотя бы одно отличается от нуля, т.е. найдется α_n+1>0 , i = 1, 2, …, m , то задача (1) – (3) не имеет ни одного допустимого решения, т.е. система ограничений канонической задачи линейного программирования (1) – (3) является несовместной.

Доказательство

Это утверждение теоремы о методе искусственного базиса

будем доказывать от противного, предположив, что существует число α_n+i>0 , i = 1, 2, …, m, но при этом исходная задача (1) – (3) имеет допустимое решение α = (k₁, k₂, …, k_n), которое удовлетворяет системе (2) и k_j ≥0, j =1, 2, …, n . Тогда по определению допустимого решения выполняется соотношение: А₁ k ₁ +А₂ k ₂ +…+А_n k _n = B, которое можно переписать в виде

А₁ k ₁ +А₂ k ₂ +…+А_n k _n +A_n+1 0 + A_n+2 0 + … + A_n+m 0 = B.

Откуда следует, что вектор β’ = (k₁, k₂, …, k_n, 0, 0, …, 0) является допустимым решением искусственной задачи (4) – (6).

Так как по условию вектор β = (α₁, α₂, …, α_n, α_n+1, α_n+2, …, α_n+m) является оптимальным решением искусственной задачи, то φ(β) ≤ φ(β’), что равносильно неравенству: α_n+1 + α_n+2 + …+ α_n+m ≤ 0 + 0 + … + 0. Однако, по предположению, существует α_n+1>0 , i = 1, 2, …, m, а, следовательно, α_n+1 + α_n+2 + …+ α_n+m> 0. Получено противоречие. Таким образом, предположение о существовании допустимого решения исходной задачи является неверным. Следовательно, система ограничений исходной задачи является несовместной.