4. Нахождение нового опорного плана.

Новый опорный план получается в результате пересчета по обычным правилам симплексного метода.

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

Если на некотором шаге окажется, что в i–й строке симплекс–таблицы в столбце вектора В стоит отрицательное число b_i, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Задача. Найти максимальное значение функции при условиях

Решение. Систему ограничений исходной задачи требуется привести к системе неравенств вида « ». Для этого обе части второго и третьего неравенств вида « » необходимо умножить на (-1).

Запишем исходную задачу линейного программирования в канонической форме:

Составим симплексную таблицу для исходной задачи, выбрав в качестве базисных векторов , т.к. эти векторы единичные и независимые.

Базис	Сb	b	с1=1	с2=1	с3=2	с4=0	с5=0
			A1	A2	A3	A4	A5
a3	2	8	1	1	1	0	0
a4	0	-4	-1	1	0	1	0
a5	0	-6	-1	-2	0	0	1
		16	1	1	0	0	0

Среди значений свободных членов есть отрицательные, поэтому будем решать задачу двойственным симплексным методом.

Из этой таблицы видим, что псевдопланом исходной задачи является . При этом плане значение целевой функции . Так как в столбце вектора В имеются два отрицательных числа (–4 и –6), а в индексной строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. В данном случае это можно сделать, так как в строках векторов а₄ и а₅ имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима.

Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора В. В данном случае это число –6. Следовательно, из базиса исключаем вектор а₅. Чтобы определить, какой вектор необходимо ввести в базис, находим , где . В нашем случае: .

Значит, в базис будем вводить вектор а₂, при этом направляющим элементом является число –2. Переходим к новой симплекс–таблице.

Базис	Сb	B	с1=1	с2=1	с3=2	с4=0	с5=0
			а1	а2	а3	а4	а5
а3	2	5	1/2	0	1	0	1/2
а4	0	–7	–3/2	0	0	1	1/2
а2	1	3	1/2	1	0	0	–1/2
		13	1/2	0	0	0	1/2

Из этой таблицы видно, что получен новый псевдоплан . При этом плане значение целевой функции .

Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного псевдоплана к другому.

Так как в столбце вектора В стоит одно отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное – 3/2, следовательно, направляющей вектор - строкой является a₄. Направляющим элементом в этой таблице является число – 3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице.

Базис	Сb	B	С1=1	С2=1	С3=2	С4=0	С5=0
			а1	а2	а3	а4	а5
а3	2	8/9	0	0	1	1/3	2/3
а1	1	14/3	1	0	0	-2/3	-1/3
а2	1	2/3	0	1	0	1/3	-1/3
		32/3	0	0	0	1/3	2/3

Видно, что найден оптимальный план исходной задачи. Ими является вектор . При этом плане значение целевой функции .