Симплексные таблицы

Практические расчеты при решении реальных задач симплексным методом выполняются в настоящее время с помощью компьютеров. Однако если расчеты осуществляются без ЭВМ, то удобно использовать так называемые симплексные таблицы. Рассмотрим алгоритм их составления при решении задачи на максимум.

1. После введения добавочных переменных систему равнений и ЦФ записываем в виде, который называется расширенной системой:

2. Исходную расширенную систему заносим в симплексную таблицу. Последняя строка таблицы, в которой дано уравнение для ЦФ, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком. В левом столбце таблицы записываются основные переменные (базис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце – свободные члены расширенной системы. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы заносятся коэффициенты при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

3. Проверяем выполнение критерия оптимальности при решении задачи на максимум – наличие в последней строке отрицательных коэффициентов. Если таких нет, то решение оптимально.

4. Если критерий оптимальности не выполнено, то наибольший по модулю отрицательных коэффициент в последней строке определяет разрешающий столбец s.

Составляем ограничения каждой строки по следующим правилам:

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

5. Переходим к следующей таблице по правилам:

· В левом столбце записывает новый базис;

· В столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 – против своей основной переменной, 0 – против чужой основной переменной, 0 – в последней стоке для всех основных переменных;

· Новую строку с номером q получаем из старой делением на разрешающий элемент

· Все остальные элементы вычисляем по следующим формулам:

Далее переходим к пункту 3.

Пример. Рассмотрим решение предыдущей задачи с помощью симплекс таблиц.