Общая теория

Замечание 7: В линейном программировании для решения систем линейных уравнений используется метод Жордана-Гаусса. Алгоритм нахождения решений системы линейных уравнений данного метода основывается на том, что от заданной системы при помощи эквивалентных преобразований переходят к эквивалентной системе, которая решается «проще». Напомним, что эквивалентными преобразованиями являются:

1) перемена местами двух (и более) уравнений в системе;

2) умножение какого-либо уравнения системы на действительное число с¹0;

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

Замечание 8: Система линейных уравнений может быть противоречивой, т.е. не иметь решений, например, в том случае, если исходная система или любая эквивалентная ей система содержит уравнение вида:

0_*х₁+0_*х₂+0_*х₃+...+0_*х_n = b, где b ¹ 0.

Замечание 9: При условии, что все уравнения системы линейно-независимы, система линейных уравнений имеет:

1) одно решение, если число неизвестных совпадает с числом переменных;

2) бесконечное множество решений, если число неизвестных больше числа уравнений.

Определение 7: Переменная х_j называется выделенной (или базисной) в i-ом уравнении системы, если в этом уравнении коэффициент перед х_j равен единице (а_ij = 1), а в остальных – нулю.

Определение 8: Если каждое уравнение системы содержит выделенную переменную, то такая система называется системой с выделенными переменными.

Например, система с выделенными первыми m переменными выглядит следующим образом:

(_*)

Замечание 10: Если небазисные переменные приравнять к нулю, то базисные переменные будут равны свободным членам. Очевидно, что такое решение будет являться частным решением системы. Полученное таким образом частное решение системы принято называть базисным.

Например, базисное решение системы (_*) имеет вид:

(х₁, х₂, х₃,…х_m, х_m+1,…х_n) = (b₁, b₂, b₃,…b_m,0,…0)

Определение 9: Если все переменные в решении системы принимают неотрицательные значения, то такое решение называется неотрицательным.

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

Например, система следующего вида не имеет неотрицательных решений:

Так как в первом уравнении коэффициенты а₁₁= -1 £ 0 и а₁₂ = -3£ 0, а свободный член в₁=2>0.

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

Теорема 2 (Критерий неограниченности значений целевой функции): Пусть в З.Л.П. (на максимум) с выделенными переменными некоторый коэффициент в целевой функции с_к >0 при переменной х_к, и пусть в системе ограничений перед переменной х_к все коэффициенты а^’_iк £ 0. Тогда значения целевой функции не ограничены на максимум (f _max (x)=¥).

Теорема 3 (О возможности перехода от одного базисного решения к другому с не меньшим значением целевой функции): Пусть в З.Л.П. (на максимум) с выделенными переменными в целевой функции некоторый коэффициент с_к >0 при переменной х_к, и в системе ограничений среди коэффициентов перед этой переменной есть положительные (а^’_iк >0). Тогда можно перейти от данного базисного решения к другому, с не меньшим значением целевой функции.

Изложенные выше основные теоретические положения позволяют сформулировать алгоритм симплекс-метода для решения З.Л.П.