Решение ЗЛП при помощи симплекс-таблиц

В предыдущем параграфе был рассмотрен симплекс-метод решения ЗЛП. Алгоритм симплекс-метода основан на последовательном улучшении (минимизации) целевой функции и построении базисного (опорного) решения (плана). Оптимальное решение достигается последовательным улучшением начального опорного плана за определенное число этапов (итераций). Переход к следующему опорному решению проводится на основе метода Жордана–Гаусса для систем линейных алгебраических уравнений. Направление перехода от одного базисного решения к другому выбирается на основе двух теорем (принципов оптимальности ЗЛП, теорема 5.1, теорема 5.2). Полученный опорный план на каждом шаге симплекс-метода проверяется на оптимальность. Процесс оканчивается за конечное число шагов. Причем на последнем шаге либо получается оптимальный опорный план и соответствующее ему оптимальное значение целевой функции (теорема 5.1), либо выявляется неразрешимость задачи (конечного оптимума нет).

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

Как и в предыдущем параграфе, рассмотрим ЗЛП в допустимом виде

(6.1)

где базисные переменные выражены через свободные переменные , причем . Целевая функция имеет вид

. (6.2)

Приведем ЗЛП (6.1) – (6.2) к каноническому виду

(6.3)

. (6.4)

Рассмотрим алгоритм решения ЗЛП, используя результаты предыдущего параграфа (теоремы 5.1, 5.2). В целях наглядности рассмотрим ЗЛП

(6.3′)

, (6.4′)

в которой три базисные переменные и три свободные переменные , причем .

Составим начальную симплекс-таблицу (табл. 6.1). В столбце БП выписываем базисные переменные , в столбце СЧ – коэффициенты в правой части системы ограничений (6.3′). В следующих столбцах выписываются коэффициенты при переменных в левой части системы (6.3′). Последняя строка таблицы составляется по коэффициентам при переменных в целевой функции (6.4′).

Табл. 6.1

БП	СЧ

 

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

Проверим построенное базисное решение на оптимальность. Возникают три случая:

Случай 1. Пусть в последней строке симплекс-таблицы все коэффициенты при свободных переменных неположительны:

.

Это условие равносильно тому, что . Тогда согласно теореме 5.1 базисное решение является оптимальным:

, .

Случай 2. Пусть в последней строке симплекс-таблицы среди коэффициентов есть положительный коэффициент (предположим для определенности: ), а все коэффициенты при соответствующей свободной переменной отрицательные (в нашем случае все коэффициенты , , при соответствующей свободной переменной отрицательны). Это условие равносильно тому, что

, .

Тогда согласно теореме 5.2, ЗЛП не имеет оптимального решения.

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

,

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

Табл. 6.2

БП	СЧ							Преобразования

Согласно симплекс-методу, необходимо изменить базис переменных: переменную вывести из базиса, а ввести в базис. Для этого составляется новая симплекс-таблица (табл. 6.3) по следующему правилу:

1) Базисными переменными являются , свободными – переменные (переменная сменила переменную в базисе);

2) Разрешающая строка (в данном случае строка коэффициентов при переменной ) делится на разрешающий элемент (в нашем случае на ). Полученная строка записывается в строку соответствующей новой базисной переменной;

3) В разрешающем столбце таблицы 6.2 (в столбце коэффициентов при ) необходимо получить нули. Для этого применяем элементарные преобразования над строками таблицы 6.2. Полученные результаты записываем в соответствующие строки табл. 6.3.

Табл. 6.3

БП	СЧ

Покажем, что в табл. 6.3 коэффициенты , , неотрицательны. Действительно, (так как по , ).

Далее, если даже коэффициент отрицательный, то в силу того, что :

.

Если же коэффициент положительный, то в силу выбора разрешающего элемента имеем

.

Итак, в любом случае коэффициент неотрицательный. Аналогично показывается, что коэффициент неотрицательный.

Это показывает, что вектор-столбец , полученный при нулевых значениях свободных переменных, является допустимым решением ЗЛП.

Значение целевой функции на базисном решении равно

.

Так как по условию , , , то , а значит,

,

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

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

Пример 6.1. Решить ЗЛП при помощи симплекс-таблиц.

,

Решение. 1) Приведем ЗЛП к каноническому виду. Введем в систему ограничений балансовые переменные . Так как , то введем функцию

,

сведя задачу к поиску минимума функции : .

Получили следующую ЗЛП канонического вида

,

2) Для полученной ЗЛП базис переменных . Составим базисное решение , . Получаем симплекс-таблицу (табл. 6.4).

Табл. 6.4

БП	СЧ							Преобразования
				–1
		–2	–1
			–3
	– 5		–3

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

,

откуда следует, что число 1 – знаменатель первой (наименьшей) дроби является разрешающим элементом (он выделен в табл. 6.4 в прямоугольнике, строка коэффициентов при переменной является разрешающей строкой). Производим смену базиса: .

3) Составляем следующую симплекс-таблицу. Для этого делим -строку табл. 6.4 на разрешающий элемент и при помощи элементарных преобразований обнуляем элементы, стоящие под разрешающим элементом. Получаем табл. 6.5.

Табл. 6.5

БП	СЧ							Преобразования
				– 1
				– 1
			– 5		– 1
	– 17		– 7		– 2

 

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

4) Проверим базисное решение на оптимальность. Как видно из табл. 6.5, разрешающим столбцом является -столбец, разрешающим элементом – элемент 5. Происходит смена базиса: . В результате шага симплекс-метода получаем таблицу 6.6.

Табл. 6.6

БП	СЧ
			– 1		–
	–		– 4		–

Базисное решение . При этом . Проверяя решение на оптимальность, замечаем, что в последней строке табл. 6.6, нет ни одного положительного числа. Согласно критерию оптимальности, базисное решение является оптимальным:

, .

Возвращаясь к исходной задаче, записываем ответ:

, .