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

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

(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 = (c1–c3a11–c4a21–c5a31)x1 + (c2–c3a12–c4a22–c5a32)x2 + c3b1 + c4b2 + c5b3. (7)

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

Z1 = c3a11 + c4a21 + c5a31, Z2 = c3a12 + c4a22 + c5a32. (8)

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

c1 – Z1 < 0, c2 – Z2 < 0, (9)

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

0 = b1 – a11x1, 0 = b2 – a21x1, 0 = b3 – a31x1.

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

(10)

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

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

(11)

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

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

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