Симплексным методом

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

В зависимости от вида ограничений различают две формы общей модели ЗЛП: каноническую и стандартную.

ЗЛП называется канонической, если ограничения представлены в виде равенств:

z = c₁x₁ + c₂x₂ + … + c_nx_n

x_j ³ 0, j = 1, 2,…, n, m < n.

Эти соотношения можно записать в векторной форме:

x_j ³ 0; i = 1, 2,…, m; j = 1, 2,…, n; m < n.

ЗЛП называется стандартной, если ограничения представлены в виде неравенств, содержащих знаки ≤ или ≥. В векторной форме эти соотношения имеют вид:

;

или ;

x_j ³ 0, i = 1, 2,…, m, j = 1, 2,…, n, m < n.

Необходимо найти такие значения x₁, x₂, … , x_n, которые обращают в максимум целевую функцию.

Любая стандартная ЗЛП может быть приведена к ЗЛП в каноническом виде с помощью введения неотрицательных переменных x_n+i, которые называют дополнительными. В целевую функцию они входят с нулевыми коэффициентами. В ограничения, содержащие знаки ≤ , дополнительные переменные входят с коэффициентом «1», а в ограничения, содержащие знаки ≥, дополнительные переменные входят с коэффициентом «–1»:

i = 1, 2, …, m ;

или

i = 1, 2, …, m.

При сведении стандартной ЗЛП, имеющей ограничения со знаком ≤, к ЗЛП в каноническом виде, коэффициенты при переменных x_n+i образуют систему m линейно независимых векторов, представляющую базис.

Переменные x_n+1, x_n+2, …, x_n+m называются базисными переменными, а остальные – свободными.

Замечание: Если в системе ограничений из коэффициентов при m переменных x_n+1, x_n+2, …, x_n+m невозможно составить единичную матрицу m-го порядка, то необходимо выбрать базис и найти разложение всех векторов по этому базису.

Из математической модели ЗЛП следует, что в допустимом решении X₀ базисные переменные равны правым частям соответствующих ограничений, а свободные переменные равны нулю: X₀ = (0, 0, …, 0, b₁, b₂, …, b_m).

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

Симплекс-методом ЗЛП решается за конечное число шагов (итераций). На первом шаге отыскивается исходный опорный план, содержащий не более m ненулевых компонент, где m – число строк. На каждом последующем шаге осуществляется нахождение нового опорного плана со значением целевой функции не хуже, чем на предыдущем шаге.

Условия задачи, а также все вычисления при решении ЗЛП симплекс-методом будем оформлять в виде симплекс-таблиц (таблица 1).

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

В клетке оценочной строки, соответствующей свободным членам, записывается значение целевой функции z₀ при первоначальном опорном плане.