Такая система не имеет предпочтительного вида. В этом случае вводят искусственный базис путём перехода к M задаче

+ ограничение >=

- Ограничение <=

Min Z =-5x1+4*x2+3*x3+6*x4

-----

X1+21*x2+x3+2*x4<=3

-x1-14*x2-2*x3+3*x4>=2

-x1-6*x2+x3-x4>=1

------

-----

X1+21*x2+x3+2*x4+x5=3

-x1-14*x2-2*x3+3*x4-x6=2

-x1-6*x2+x3-x4-x7=1

------

-----

X1+21*x2+x3+2*x4+x5=3

-x1-14*x2-2*x3+3*x4-x6+W1=2

-x1-6*x2+x3-x4-x7+W2=1

------

Min Z =-5x1+4*x2+3*x3+6*x4+0*x5+0*x6+0*x7+M*W1+M*W2

Между оптимальными планами исходной задачи и М задачи имеется следующая связь- если в оптимальном плане М задачи все искусственные переменные Wi=0, то значения оставшихся координат дадут оптимальный план исходной задачи.

Симплексные таблицы

БП	С5	А0	Х1	Х2	Х3	…	Xn
Xn+1		B1
Xn+2		B2
…		Bm
Zj	Cj

Max Z = 18*x1+20*x2+32*x3

----

18*x1+15*x2+12*x3<=720

6+x1+4*x2+8x3<=384

5*x1+3*x2+12*x3<=360

---

----

18*x1+15*x2+12*x3+x4=720

6+x1+4*x2+8x3+x5=384

5*x1+3*x2+12*x3+x6=360

---

Max Z = 18*x1+20*x2+32*x3+0*x4+0*x5+0*x6

БП	С5	А0	Х1	Х2	Х3	X4	X5	X6
X4
X5
X6
Zj	Cj		-18	-20	-32

Рабочая область таблицы начиная с 3его столбца и 3й строки содержит элементы расширенной матрицы над которыми будут проводиться преобразования с целью получения оптимального плана. В последней строке таблицы записано нулевое уравнение эта строка называется индексной строкой или строкой оценок. Индексная строка заполняется по формуле:

J= Сб*Аj-Cj

0*18+0*6+0*5-18

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

Min Z = -6*x1+8*x2-x3+2*x4

----

-2*x1+x2+x3=8

3*x1-8*x2+x4=48

----

БП	С5	А0	Х1	Х2	Х3	X4
X3	-1		-6		-1
-2
X4				-8
Zj	Cj			-25

D0= -1*8+2*48=88

D1=-1*(-2)+2*3-(-6)=14

D2=-25

D3=0

D4=0

X0={0;0;8;48}

----

Х1+х2+х3=12

Х2+х4=2

2*x1+x2+x5=20

----

Max Z = 2*x1+4*x2+0*x3+0*x4+0*x5

БП	С5	А0	Х1	Х2	Х3	X4	X5
X3
X4
X5
Zj	Cj		-2	-4

БП	С5	А0	Х1	Х2	Х3	X4	X5
X3
			-1
X2
X5						-1
Zj	Cj		-2

X3A0(2)=(X3A0(1)* X4X2(1)-X2A0(1)*X3X2(1))/X4X2(1)

БП	С5	А0	Х1	Х2	Х3	X4	X5
X3
X2
X1						-1/2	1/2
Zj	Cj

X*- оптимальное значение

X*=(9;2;1;0;0)

Алгоритм симплекс методов:

-используя каноническую форму определяем начальный опорный план

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

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

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

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

-в задаче на максимум- максимальный по модулю отрицательный элемент

-в качестве разрешающей строки берём строку, к которой отношение элементов столбца свободных членов А0 к соответствующему элементу разрешающего столбца минимальной соответствующий элемент должен быть положительный

Min{ Bi/Aik}

-строим новую таблицу, в которой заменяем базисную переменную на переменную разрешающего столбца

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

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