Решение задачи линейного программирования симплекс – методом

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

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

f (x) = с₁x₁+с₂x₂ +с₃x₃+…+с_nx_n  max

x_j  0, j = 1,2,...n

где a_{ij ,} b_{i ,} с_j ( i = 1..m; j = 1..n) – заданные постоянные величины;

x_j ( j = 1..n) – неизвестные.

Замечание 6

З.Л.П. на определение минимума целевой функции необходимо заменить З.Л.П. на определение максимума целевой функции, пользуясь известным фактом:

min f(x) = max(- f (x))

Общая теория

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

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

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

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

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

0_*х₁+0_*х₂+0_*х₃+...+0_*х_n = , где   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). Тогда можно перейти от данного базисного решения к другому, с не меньшим значением целевой функции.

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