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