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

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

Цикл начинается с анализа базисных переменных. Если все переменные неотрицательны, вычисления завершаются. Иначе выбирается направляющая сторока k по минимальной базисной переменной. Вычисляются значения q: для ά_kj< 0

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

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

Пример: Пусть заготовки вырезаются из прямоугольных листов размером 5´10. Необходимо наилучшим образом выполнить заказ, включающий два вида прямоугольных заготовок: 650 штук размером 2´2.5 и 1300 – размером 3´4. В качестве критерия возьмем расход материала (листов), а за переменные x_j примем количество листов, раскраиваемых j- мспособом. Все возможные карты раскроя показаны на рис. Каждой карте соответствует своя переменная и количество получаемых заготовок (в скобках).

Модель задачи:

L=x ₁ +x ₂ +x ₃ +x ₄® min

10 x ₁ + 7 x ₂+5 x ₃+ x ₄³ 650;

x ₂ + 2 x ₃+3 x ₄³ 1300;

Таблица 0
Csi	Базис	A0	A 1	A 2	A 3	A 4	A 5	A 6
	x 5	-650	-10	-7	-5	-1
	x 6	-1300		-1	-2	-3
L, Δj		-1	-1	-1	-1
Zj
q	--	--		1/2	1/3	--	--

" x_j ³ 0.

Канонический вид (умножен на –1):

-10 x ₁-7 x ₂- 5 x ₃- x ₄+ x ₅ = - 650;

- x ₂- 2 x ₃ - 3 x ₄+ x ₆ = -1300.

Как видно из таблицы, начальное базисное решение является недопустимым (отрицательным), но удовлетворяет условиям оптимальности (" Δ_j £ 0). Поэтому последующие действия будут направлены на достижение доп. решения при сохранении условий оптимальности.

Таблица 1
Csi	Базис	A0	A 1	A 2	A 3	A 4	A 5	A 6
	x 5	-650/3	-10	-20/3	-13/3			-1/3
	x 4	1300/3		1/3	2/3			-1/3
L, Δj	1300/3	-1	-2/3	-1/3			-1/3
q	--	1/10	1/10	1/13	--	--

В качестве направляющей берем строку с минимальной базисной переменной (x ₆= -1300). Вычисляем значения q, минимальное из которых определяет направляющий столбец. Тем самым определен и направляющий элемент. Выполнив симплекс-преобразование, получаем новое базисное решение.

Таблица 2
Csi	Базис	A0	A 1	A 2	A 3	A 4	A 5	A 6
	x 3		30/13	20/13			-3/13	1/13
	x 4		-20/13	-9/13			2/13	-5/13
L, Δj		-3/13	-2/13			-1/13	-4/13

Так как в этом решении есть отрицательная переменная, проводим следующую итерацию.

Здесь базисные переменные положительны, значит, решение допустимое. Условия оптимальности, как и в предыдущих решениях, выполняются. Таким образом, в табл. 2 имеем оптимальное решение задачи раскроя: