Формулы пересчета при симплекс-методе

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

Для элементов разрешающей строки используются следующие формулы:

где s - номер разрешающей строки,

r - номер разрешающего столбца,

, - новые значения пересчитываемых элементов,

as_j, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.

Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид:

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 3. Пересчитаем элемент a₁₁ (в исходной симплекс-таблице его значение равно 4). В таблице 2.6 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

, т.е.

Аналогичным образом пересчитываются остальные элементы.

Построение начального базисного плана с помощью искусственных переменных.

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

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

Этап 1. Рассматривается искусственная целевая функция, равная сумме искусственных переменных, которая минимизируется при помощи симплекс-метода. Другими словами, производится исключение искусственных переменных. Если минимальное значение вспомогательной задачи равно нулю, то все искусственные переменные обращаются в нуль и получается допустимое базисное решение начальной задачи. Далее реализуется этап 2. Если минимальное значение вспомогательной задачи положительное, то по крайней мере одна из искусственных переменных также положительная, что свидетельствует о противоречивости начальной задачи, и вычисления прекращаются.

Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица 1 этапа превращается в начальную таблицу этапа 2 и изменяется целевая функция.