16-5. Формализованная симплекс-таблица

Обычно процедура отыскания экстремума с помощью симплекс-метода оформляется в виде специальной таблицы. Разберем эту таблицу на примере. Для этого преобразуем рассмотренную выше задачу к такому виду, чтобы можно было применить симплекс-метод. С этой целью введем дополнительные переменные x_n+i:

Пример 16-2. Пусть система ограничений с введением слабых переменных задана в виде равенств (16-9), т. е.

Минимизируем L=-4x₁+x₂ при x_i≥0j = 1, 2,..., 6. Очевидно, что решение x₁ = 0, x₂ = 0, х₃ = 2, х₄= -8, x₅ = 10, x₆ = - 2 удовлетворяет уравнениям (16-9), но не удовлетворяет условию x_j≥ 0 и поэтому не является базисным. Очевидно, что выбираемые не базисные переменные образуют косоугольную систему координат в ранее рассмотренной геометрической интерпретации.

Будем считать, что x₃ и x₄ - не базисные переменные, и выразим через них базисные переменные и величину L:

Посмотрим, не достигла ли L своего минимального значения. Коэффициент при х₄ отрицательный, следовательно, возрастание х₄ приведет к дальнейшему уменьшению L. Однако при этом необходимо следить, чтобы x₁, x₂, x₅, x₆, которые зависят от х₄ не стали отрицательными, т. е. не вышли из допустимой области. Так как увеличение х₄ приводит к увеличению x₁, x₂, x₆, то для этих переменных такой опасности не существует. Рассматривая переменную x₅, убеждаемся, что максимально допустимое значение х₄ может быть x₄ = 10. При этом

Поэтому за новый базис могут быть приняты переменные x₁, x₂, x₄, x₆, т. е. мы перешли к вершине x₃ = 0, x₅ = 0. Для того чтобы приступить к следующему шагу, необходимо выразить эти базисные переменные и L через не

базисные (или, иначе, через координаты новой косоугольной системы координат). В итоге получим;

Совершенно очевидно, что как бы мы ни увеличивали x₃ и x₅, уменьшить L не удается. Следовательно, достигнуто окончательное решение, при котором

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

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

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

Таблица 16-1 Симплекс-таблица для первого шага

Таблица 16-2 Симплекс-таблица для второго шага

Симплекс-таблица для третьего шага

На каждом шаге в базис включается одна из не базисных переменных, для которой положителен (или отрицателен в случае максимизации линейной формы) элемент, находящийся в самой нижней строке таблицы. Благодаря этому выбирается та переменная, увеличение которой приводит к уменьшению линейной формы (например, на втором шаге переменная х₄). При этом надо помнить, что числа в самой нижней строке симплекс-таблицы равны коэффициентам при соответствующих не базисных переменных в линейной форме, взятых с обратным знаком. Одновременно вычеркиваем из базисных переменных ту, которая дает наименьшее отношение свободного члена к коэффициенту в столбце, при соответствующей выбранной не базисной переменной в ограничениях, причем отрицательные отношения не учитываются, так как соответствующие переменные не могут стать отрицательными. Например, для табл. 16-2 отрицательное отношение свободного члена во второй строке к коэффициенту при переменной х₄, которую рассматриваем на предмет возможности включения в базис, равно 1/ - 1/6 = -6. Это указывает на то, что за счет увеличения переменной ч₄ переменная х₂, которую предполагаем исключить из базиса, не обращается в нуль, что и соответствует уравнению

[см. формулу (16-10)]. Поэтому ее исключать не следует. Геометрически это означает, что с включением переменной х₂ и исключением переменной х₄ вершина многогранника не будет достигнута. Для второго шага остается одна возможность - исключить х₅, при этом следующая вершина многогранника будет достигнута.

На пересечении строки вводимой в базис переменной и столбца удаляемой переменной находится элемент, называемый центральным или опорным, который отмечается звездочкой.

Напомним, что симплекс-таблица строилась для случая минимизации линейной формы.