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

Пусть δ₁, δ₂, … , δ_n – оценки системы векторов условий, приведенных к некоторому базису опорного решения а0ю Если вектор β =( l₁, … , l_j, … , l_n) является произвольным допустимым решением КЗЛП, то по Лемме о целевой функции имеем: f(β)=f(a) - ∑ⁿ_j=1 δ_j l_j . Так как для любых j=1, 2, … , n по условию δj≤0, а вектор β =( l₁, … , l_j, … , l_n) – произвольное допустимое решение данной задачи, то есть lj≥0 для всех j=1, 2, … , n, то f(β)≥f(a⁰). Следовательно, по определению вектор а⁰ является оптимальным решением задачи (1) – (3) на минимум.

23. Условия неограниченности целевой функции КЗЛП на минимум.

Пусть симплекс таблица привидена к некоторому базису опорного решения α

Если при этом существует единственное δ_s >0 S=1,……n, а остальные элементы s-го неположительные, т.е. а_is ≤ i=1….n, то целевая функция КЗЛП неограниченна снизу на интервале допустимых значений.

Задача не имеет решения.

25. Допустимое базисное решение называется невырожденным, если значения всех базисных переменных положительны (  ).

            Задача ЛП называется невырожденной, если допустимые базисные решения всех эквивалентных ей задач невырождены.

Теорема

            Для невырожденной задачи ЛП симплекс-метод завершается через конечное число итераций.

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

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

            Итак надо показать, что в невырожденном случае допустимые базисные решения не повторяются.

            Пусть х и х' - допустимые базисные решения для старой и новой симплекс-таблиц. Так как базисные решения невырождены, то 

            

            Поэтому 

                        

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

Теорема доказана.

26. Теорема о разрешимости кзлп.

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

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

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

27. основные свойства искусственной задачи ЛП. Допустимое множество решений задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник. Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение. Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечно много точек максимума или минимума).

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

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

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

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

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

5. ∑ⁿ_j=1 Е_j x_j + E₁ x_n+1 + E₂ x_n+2 + … + E_m x_n+m = B,

6. x_j≥0, j=1, 2, … , n, n+1, n+2, … , n+m, где Е_j – единичный вектор (j=1, 2, … , m), a x_n+1 , x_n+2 , … ,x_n+m – искусственные переменные.

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

1. Если a_n+1 = a_n+2 = … = a_n+m=0, то вектор а=(а₁, а₂, … , а_n) является опорным решением исходной КЗЛП (1) – (3);

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