4. Теоретическая часть

4.1. Двойственный симплекс-метод

Двойственный симплекс-метод представляет собой итерационный метод решения задач ЛП, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное», решение (в обычном симплекс-методе сначала находится допустимое, но неоптимальное решение). Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

Вычислительная схема двойственного симплекс-метода похожа на вычислительную схему обычного симплекс-метода. На каждой итерации также проверяется условие оптимальности решения и в случае его невыполнения – условие разрешимости задачи. При выполнении условия разрешимости осуществляется переход к следующей итерации. Аналогичны и формы симплекс-таблиц.

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

Условие оптимальности базисного решения формулируется следующим образом: все компоненты базисного решения являются неотрицательными.

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

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

После выбора исключаемой из базиса и включаемой в базис переменных для получения следующего базисного решения осуществляется обычная операция преобразования строк симплекс-таблицы.

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

1. Новое ограничение при полученном решении выполняется, поэтому решение остаётся неизменным.

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

Пример. Дана задача ЛП:

Найдём её решение с помощью симплекс-метода. Для этого преобразуем задачу к канонической форме, вводя дополнительные переменные x₃ и x₄:

Итоговая симплекс-таблица представлена табл. 1.

Таблица 1

Базис	Св. член	x1	x2	x3	x4
x1	1	1	0	4/5	-1/5
x2	3	0	1	-3/5	2/5
f	4	0	0	1/5	1/5

Таким образом, задача ЛП имеет решение x^*=(1, 3), при этом f(x^*)=4.

Пусть к предыдущей задаче добавлено ограничение

x₁ +2x₂≤4.

Новое ограничение при полученном решении не выполняется (x₁^*+2x₂^*=7>4), поэтому найдём новое решение.

Добавляем в новое ограничение дополнительную переменную x₅, которую затем введём в базис:

x₁ +2x₂+x₅ =4, x₅≥0.

Используя итоговую симплекс-таблицу исходной задачи, выражаем базисные переменные, содержащиеся в новом ограничении, через свободные переменные:

и подставляем полученные выражения в новое ограничение:

В качестве базисных выбираем переменные x₁, x₂, x₅. Таким образом, Б₀={x₁, x₂, x₅}. В результате получаем табл. 2.

Таблица 2

						↓
	Базис	Св. член	x1	x2	x3	x4	x5
	x1	1	1	0	4/5	-1/5	0
	x2	3	0	1	-3/5	2/5	0
→	x5	-3	0	0	2/5	-3/5	1
	f	4	0	0	1/5	1/5	0
						1/3

Из табл. 2 следует, что начальное базисное решение имеет вид БР₀={x₁=1, x₂=3, x₅= 3}. БР₀ не является допустимым, поскольку в столбце свободных членов есть отрицательный коэффициент Задача разрешима, поскольку в строке x₅ есть отрицательный коэффициент. Находим Б₁: