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