Симплексные таблицы. 
Исследование операций в экономике

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

I. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены: в противном случае используем так называемый М-метод, который будет рассмотрен ниже.

II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком:? = -с (•. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы — все переменные (отмечая при этом основные), во втором столбце — свободные члены расширенной системы bvbv …, bm. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты а~ при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности при решении задачи на максимум — наличие в последней строке отрицательных коэффициентов bj 0). Если таких нет, го решение оптимально, достигнут шах F = с () (в левом нижнем углу таблицы), основные переменные принимают значения aj0 (второй столбец), неосновные переменные равны нулю, т. е. получаем оптимальное базисное решение.

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

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

• 1) ?, если и аы имеют разные знаки;
• 2) ?, если Ь. = 0 и а. <0;
• 3) ?, если ак = 0;
• 4) 0, если bi = 0 и ajs > 0;
• 5) , если аю и аы имеют одинаковые знаки.

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

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

• а) в левом столбце записываем новый базис: вместо основной переменной дг — переменную .г,;
• 6) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 — против «своей» основной переменной, 0 — против «чужой» основной переменной, 0 — в последней строке для всех основных переменных;
• в) новую строку с номером q получаем из старой делением на разрешающий элемент aq',
• г) все остальные элементы а^ вычисляем по правилу прямоугольника (рис. 5.4):

Рис. 5.4.

Далее переходим к ?. III алгоритма.

5.10. Решить задачу об использовании ресурсов, приведенную в параграфе 1.2, с помощью симплексных таблиц^[1].

Решение. Расширенная система задачи имеет вид.

Линейную функцию представим в виде F-2х, — Зх2 =0.

Заполняем первую симплексную таблицу (табл. 5.1), в которой переменные, г3, х4, х5, х6 основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

Таблица 5.1

!!!

В соответствии с ?. III алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (-3); второй столбец разрешающий, переменная х2 перейдет в основные (этот столбец отмечен стрелкой). В соответствии с ?. IV находим оценочные отношения и х2 = min {18/3; 16; 5; ?} = 5. Третья строка является разрешающей (отмечена горизонтальными стрелками). На пересечении разрешающих строки и столбца стоит разрешающий элемент egg = 1.

Строим табл. 5.2 по правилам ?. V алгоритма:

• а) в новом базисе основные переменные: .г3,, г4, х2, хс;
• б) расставляем нули и единицы; например, в клетке, соответствующей основной переменной х3 по столбцу и строке, ставим 1, а в клетке, соответствующей основной переменной х3 по строке и основной переменной х2 по столбцу, ставим О и т. п. В последней строке против всех основных переменных ставим 0. Третья строка получается делением на разрешающий элемент? = 1. Остальные клетки заполняем по правилу прямоугольника. Например: ,

и т. д.

Получим вторую симплексную таблицу (табл. 5.2).

Таблица 5.2

Критерий оптимальности вновь не выполнен. Теперь первый столбец разрешающий; х, переходит в основные, min {3/1; 11/2; °°; 7} = 3; первая строка разрешающая, — разрешающий элемент.

Новая симплексная таблица примет вид табл. 5.3.

Таблица 5.3.

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, а25 = 5 — разрешающий элемент.

Переходим к табл. 5.4.

Таблица 5.4

Критерий оптимальности выполнен, значит, Епт - 24, оптимальное базисное решение (6; 4; 0; 0; 1; 3) совпадает с ранее полученным (см. решение задачи 5.1 симплексным методом). >

• [1] Эта задача уже решена геометрически в 4.1, а в 5.1 — симплексным методом без использования таблиц.