Если для опорного решения α0 канонической задачи линейного программирования на минимум (1) – (3) найдется базис, для которого все оценки неположительные, то есть δj≤0 для всех j = 1, 2, …, n, то вектор α0 является оптимальным решением данной задачи.
Доказательство
Пусть δ1, δ2, …, δn – оценки системы векторов условий, приведенных к некоторому базису опорного решения α0. Если вектор β=(1, …, j, …, n ) является произвольным допустимым решением канонической задачи линейного программирования (1) – (3), то по доказанной лемме имеем: f(β)=f(α) – δjj.
Так как, для любых j=1, 2, …, n по условию δj≤0 , а вектор β=(1, …, j, …, n ) произвольное допустимое решение данной задачи, т.е. j≥0 для всех j=1, 2, …, n , то f(β)≥f(α0). Следовательно, по определению вектор α0 является оптимальным решением задачи (1) – (3) на минимум
Сформулируйте теорему о неограниченности целевой функции КЗЛП.
Теорема ( о неограниченности целевой функции).
Пусть симплекс таблица приведена к некоторому базису опорного решения α канонической задачи линейного программирования (1) – (3) на минимум. Если при этом существует столбец Аs с положительной оценкой, т.е. δs > 0, где s=1, 2, …, n , а все остальные элементы этого столбца неположительные, т.е, αis ≤ 0, i=1, 2, …, r , то целевая функция данной задачи неограниченна на множестве допустимых решений, и, следовательно, задача не имеет оптимального решения.
Доказательство
Пусть симплекс таблица приведена к базису А1, А2, …, Аr опорного решения α=(α1, α2, …, αr, 0, 0, …, 0) и имеет вид:
A’1
A’2
…
A’r
A’r+1
…
A’s
…
A’n
B’
…
a/1,r+1
…
a'1s
…
a'1n
α1
…
a'2,r+1
…
a'2s
…
a'2n
α2
…
…
…
…
…
…
…
…
…
a'r,r+1
…
a'rs
…
a'rn
αr
δr+1
…
δs
…
δn
δ0
Следовательно, вектор ограничений В’, а также вектор условий А’s можно представить в виде линейной комбинации базисных векторов, а именно,
Помножив соотношение (13) на переменную t > 0 и вычтя его из соотношения (12), получим:
А’1 ( α1 – t a’1s ) + А’2 ( α2 – t a’2s ) + … + А’r (αr – t a’rs) + A’s t = B’.
Из последнего соотношения и с учетом того, что a’is ≤ 0, следует, что вектор
Αt = (α1 – t a’1s , α2 – t a’2s , …, αr – t a’rs , 0, …, 0, t, 0, …, 0 )
является допустимым решением задачи (1) – (3). По лемме о целевой функции для допустимого решения αе имеем
f(αt) = f(α) – δ1 ( α1 – t a’1s ) – δ2 ( α2 – t a’2s ) – …– δr ( αr – t a’rs ) – δs t .
С учетом того, что оценки базисных векторов равны нулю, т.е., δ1= δ2= …= δr=0, значение целевой функции можно записать в виде: f(αt) = f(α) – δs t. Так, как δs > 0 , то при t→ + целевая функция неограниченно уменьшается, т.е., f(αt) → – , и, следовательно, задача не имеет оптимального решения