Вычислительные процедуры симплекс-метода

Симплекс-алгоритм состоит из следующих шагов.

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n - m (небазисных) переменных.

Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2.

Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое значение (стать небазисной) при введении в состав базисных новой переменной.

Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1.

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

W - 3х₁ - 2х₂ = 0 (целевая функция),

х~+2х, +з, =6~

2х"-+ х, ~~, =8

~ "+ "' '+ ~~- (ограничения). [ 3 х, +в,=2

Как отмечалось ранее, в качестве начального пробного решения используется решение системы уравнений, в которой две (=6 - 4) переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка х~=х~ - - 0 сразу же приводит к следующему результату: ~,=6, з,=8, з,=1 и з,=2 (т. е. решению, соответствующему точке А на рис. 3.2). Поэтому точку А можно использовать как начальное допустимое решение. Величина W в этой точке равна нулю, так как и х,, и х, имеют нулевое значение. Поэтому, преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться в том, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение. Это имеет место во всех случаях. когда начальный базис состоит из остаточных переменных.