Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

• просматривается вторая строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов ) выбирается наибольшее отрицательное число при отыскании max, либо наибольшее положительное при задаче на min. Если такового (при отыскании max – отрицательного, а при отыскании min – положительного) нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту во второй строке - ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится, ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных;
• разрешающий элемент заменяем на :

;

• умножим каждый элемент ключевой строки (исключая разрешающий элемент) на и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы;
• умножим каждый элемент ключевого столбца (исключая разрешающий элемент) на и полученные значения запишем в столбец с измененной свободной переменной новой симплекс таблицы;
• столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же;
• строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же;
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

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

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

В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму.