Алгоритм решения ЗЛП с помощью симплексных таблиц

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

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

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

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

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

1. Сли ∞, если b_i и а_is имеют разные знаки;

2. ∞, если b_i=0 и а_is<0;

3. ∞, если а_is=0;

4. 0, если b_i=0 и а_is>0;

5. , если а_i0 и а_is имеют одинаковые знаки.

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

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

a. В левом столбце записываем новый базис: вместо основной переменной x_q – переменную x_s;

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

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

d. Все основные элементы вычисляем по правилу прямоугольника:

Пример 4.1. Решить ЗЛП с использованием симплексной таблицы.

От системы неравенств перейдем к системе уравнений, вводя новые переменные

Линейную функцию представим в виде F-x₁-x₂=0

I. Заполним первую симплексную таблицу, в которой переменные x₃ и x₄- основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

В соответствии с пунктом III алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (в нашем случае эти коэффициенты равны, можно выбрать любой, например первый коэффициент -1); следовательно, первый столбец разрешающий, переменная x₁ перейдет в основные (этот столбец отмечен стрелкой). В соответствии с пунктом IV алгоритма находим оценочные отношения и x₁=min{30/1;20/2}=20/2=10. Вторая строка является разрешающей (отмечена горизонтальной стрелкой). На пересечении разрешающих строки и столбца стоит разрешающий элемент a₂₁=2.

I. Строим таблицу 2 по правилам п. V алгоритма:

а) в новом базисе основные переменные x₃ и x₁;

б) расставляем нули и единицы, например, в клетке, соответствующей основной переменной x₃ по столбцу и строке ставим 1, а в клетке, соответствующей основной переменной x₃ по строке, а основной переменной x₂– по столбцу, ставим 0 и т.п. в последней строке против всех основных переменных ставим 0. Первая строка получается делением на разрешающий элемент a₂₁=2 той же строки в таблице 1. Остальные ячейки заполняем по правилу прямоугольника:

в₁=30-20·1/2=20, a₁₂=3-1·1/2=5/2, a₁₄=0-1·1/2=-1/2, в₃=0-(-1)·20/2=10,

a₃₂=-1-(-1)·1/2=-1/2, a₃₄=0-1·(-1)/2=1/2

Критерий оптимальности вновь не выполнен. Теперь второй столбец разрешающий, x₂ переходит в основные, min{20/(3/2);10/(1/2)}=8; первая строка разрешающая, а₁₂=3/2 – разрешающий элемент. Переходим к следующей симплексной таблице.

II. Строим третью симплексную таблицу по правилам п.V алгоритма

Критерий оптимальности выполнен, значит F_max=14, оптимальное базисное решение (6;8;0;0).

Ответ. F_max=14.