Симплекс метод в общем виде

Требуется найти максимум целевой функции:

(1)

При ограничениях:

(2)

И условиях неотрицательности:

x_i ≥ 0, i=1, 2,..., n (3)

Из системы (2) видно, что если за свободные неизвестные принять х₁, х₂ и положить их равными нулю, то базисные неизвестные х₃, х₄, х₅ будут равны правым частям системы. в результате получаем план:

х₁=0, х₂=0, х₃=b₁, x₄=b₂, x₅=b₃ (4)

Для которого целевая функция равна

(5)

Выразим из (2) базисные неизвестные х₃, х₄, х₅ через свободные х₁, х₂:

(6)

Подставим (6) в целевую функцию (1) и после приведения подобных членов будем иметь:

f = (c 1– c 3 a 11– c 4 a 21– c 5 a 31) x 1 + (c 2– c 3 a 12– c 4 a 22– c 5 a 32) x 2 + c 3 b 1 + c 4 b 2 + c 5 b 3. (7)

Если коэффициенты перед х₁, х₂ в (7) окажутся отрицательными, то целевую функцию нельзя увеличить, переводя эти свободные неизвестные в базисные, то есть давая им какие-то положительное значения. Отрицательность коэффициентов перед неизвестными в (7) есть признак того, что найдено оптимальное решение. Коэффициенты перед свободными неизвестными в выражении для целевой функции принято называть оценками. Введем обозначения:

Z 1 = c 3 a 11 + c 4 a 21 + c 5 a 31, Z 2 = c 3 a 12 + c 4 a 22 + c 5 a 32. (8)

В этих обозначениях условия максимальности запишутся:

c 1 – Z 1 < 0, c 2 – Z 2 < 0, (9)

Пусть условии оптимальности (9) не выполнены, а именно пусть, для определенности, коэффициент перед х₁ в (7) положителен, тогда, увеличивая х₁, мы увеличим целевую функцию по сравнению с ее значением (5). Посмотрим, насколько может быть увеличена переменная х₁по сравнению с нулем, при условии, что х₂ остается свободной, то есть будет иметь неизменное значение х₂=0. Из (6) видно, что увеличение х₁ будет вести к уменьшению х₃, х₄, х₅, если коэффициенты перед х₁ в (6) отрицательны. Увеличивать х₁ можно лишь до значения, при котором первая из неизвестных х₃, х₄, х₅ обратится в нуль. Положив нулю левые части (6), получим три уравнения:

0 = b 1 – a 11 x 1, 0 = b 2 – a 21 x 1, 0 = b 3 – a 31 x 1.

Если положить:

(10)

то только одна неизвестная из х₃, х₄, х₅ обратится в нуль, то есть станет свободной, а остальные останутся положительными. Предположим, что это будет х₃, тогда будем иметь в качестве свободных неизвестных х₂, х₃ и в качестве базисных х₁, х₄, х₅.

Для удобства дальнейших вычислений желательно преобразовать систему ограничений к виду (2), который характерен тем, что столбцы коэффициентов при базисных неизвестных образуют единичную матрицу. Так как старая базисная переменная х₃ заменяется новой базисной переменной х₁, то в первом уравнении коэффициент перед х₁ должен быть равен 1. Это достигается делением первого уравнения на a₁₁. Далее следует исключить неизвестную х₁ из второго и третьего уравнений. Для этого преобразованное первое уравнение умножим сначала на а₂₁ и вычтем из второго, затем на а₃₁ и вычтем из третьего. В результате этих преобразований система (2) примет вид:

(11)

Здесь через a¹_ij обозначены новые значения коэффициентов. Заметим, что подобные преобразования выполняются в методе Гаусса при решении систем линейных уравнений.

Описание выше действия по работе с системой ограничений (2) следует повторить для системы (11) и т.д., до тех пор, пока не будет выполнены условия оптимальности.

Для удобства и компактности вычислений по симлекс-методу применяются симплексные таблицы.