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

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

 

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

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

z = c1x1 + c2x2 + … + cnxn

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

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

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

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

;

или ;

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

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

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

i = 1, 2, …, m ;

или

i = 1, 2, …, m.

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

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

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

Из математической модели ЗЛП следует, что в допустимом решении X0 базисные переменные равны правым частям соответствующих ограничений, а свободные переменные равны нулю: X0 = (0, 0, …, 0, b1, b2, …, bm).

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

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

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

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

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