Симплекс-алгоритм.

Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования (ЛП), перестает быть пригодной для этой цели при числе свободных переменных n – m >= 3.

Идея симплекс-метода относительно проста. Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n – m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n – m переменных x₁ , x₂ , … x_k , а остальные m выражены через них:

x_k+1 = a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,kx_k + b_k+1

x_k+2 = a_k+2,1x₁ + a_k+2,2x₂ + … + a_k+2,kx_k + b_k+2

… (1)

x_n = a_n,1x₁ + a_n,2x₂ + … + a_n,kx_k + b_n Если положить все свободные переменные x₁ , x₂ , … x_k равными нулю, то мы получим решение: x₁ = 0, x₂ = 0, … x_k = 0, x_k+1 = b_k+1, x_k+2 = b_k+2, … , x_n = b_n, которое называется базисным.

z = c₁x₁ + c₂x₂ + … + c_nx_n , (2)

которую требуется минимизировать, через свободные переменные x₁ , x₂ , … x_k:

z = d₀ + d₁x₁ + … + d_kx_k , (3)

Для этого надо в (2) подставить (1), выражение базисных переменных через свободные и привести подобные члены. Очевидно, что при x₁ = 0, x₂ = 0, … x_k = 0 z = d₀ , т.е. d₀ – это значение целевой функции при допустимом базисном решении. Посмотрим, не можем ли мы улучшить решение, т.е. уменьшить целевую функцию z, увеличивая какие-нибудь из переменных x₁, x₂, … x_k (уменьшать их мы не можем, т.к. все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты d₁, d₂ , … d_k в формуле (3) положительны, то, увеличивая какие-то из переменных x₁, x₂ , … x_k сверх нуля, мы не сможем уменьшить целевую функцию z; следовательно, найденное нами допустимое базисное решение является оптимальным. Если же среди коэффициентов d₁, d₂ , … d_k в формуле (3) есть отрицательные, то, увеличивая некоторые из переменных x₁, x₂ , … x_k , а именно – те, коэффициенты при которых отрицательны, мы можем улучшить решение, т.е.

Пусть, например, коэффициент d₁ в формуле (3) отрицателен. Значит, есть смысл увеличить х₁, т.е. перейти от данного допустимого базисного решения (опорного решения) к другому, где переменная х₁ не равна нулю, а вместо нее равна нулю какая-то другая, т.е. перейти от одной вершины ОДР к другой вершине. Увеличение х₁ “полезно” для целевой функции z, делает меньше. Однако увеличивать х₁ надо осторожно, так чтобы не стали отрицательными другие переменные x_k+1, x_k+2 , … , x_n , выраженные через свободные переменные, в частности, через х₁ формулами (1). Так как остальные свободные переменные x₂ , … x_k остаются равными нулю, то изменения базисных переменных x_k+1, x_k+2 , … , x_n от увеличения х₁ выражаются формулами:

x_k+1 = a_k+1,1x₁ + b₁

x_k+2 = a_k+2,1x₁ + b₂

… (4)

x_n = a_n,1 x₁ + b_n Посмотрим, опасно ли для переменных x_k+1, x_k+2 , … , x_n увеличение х₁ , т.е. может ли оно делать их отрицательными? Да, опасно, если коэффициент при х₁ в соответствующем уравнении отрицателен. Если среди уравнений (4) нет уравнения с отрицательным коэффициентом при х₁ , то величину х₁ можно увеличивать беспредельно, а, значит, целевая функция z не ограничена снизу и оптимального решения задачи ЛП не существует. Допустим, что это не так и что среди уравнений (4) есть такие, в которых коэффициент при х₁ отрицателен. Для переменных, стоящих в левых частях уравнений, увеличение х₁ опасно – оно может сделать их отрицательными. Возьмем одну из таких переменных х_l и посмотрим, до какой степени можно все же увеличить х₁, пока переменная х_l не станет отрицательной? Выпишем l–ое уравнение из системы (4)

x_l = a_l,1x₁ + b_l

Здесь свободный член b_l >= 0, а коэффициент a_l,1 отрицателен.

Выберем ту из переменных x_k+1, x_k+2 , … , x_n , которая раньше всех обратиться в нуль при увеличении х₁ , т.е. ту, для которой величина - b_l / a_l,1 меньше всего. Пусть этой переменной будет х_r . Тогда имеет смысл “пере разрешить” систему уравнений (1) относительно базисных переменных, выведя из числа свободных переменных х₁ и переведя вместо нее в группу свободных переменных х_r . Действительно, мы хотим перейти от допустимого базисного решения, задаваемого равенствами x₁ = 0, x₂ = 0, … x_k = 0, к допустимому базисному решению, в котором уже x₁ 0, а x₂ = 0, … x_k = 0,х_r = 0. Первое допустимое базисное решение мы получили, если обратим в нуль все новые свободные переменные x₁, x₂, … x_k ; второе мы получим, если обратим в нуль прежние переменные x₂, … x_k, х_r . Базисными переменными при этом будут x₁,x_k+1 , … ,х_r-1, х_r+1, … , х_n .

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

Изложенное выше является содержанием симплекс-алгоритма. Суть симплекс-алгоритма состоит в установлении для имеющегося допустимого базисного решения является ли оно оптимальным. Если нет, то в указании как перейти к новому допустимому базисному решению, в котором значение целевой функции будет не больше, чем в предыдущем решении.

1.