Алгоритм симплекс-метода

Будем считать, что известна исходная К-матрица К⁽⁰⁾ задачи линейного программирования, определяющая исходный опорный план

В симплексном методе последовательно строят К-матрицы

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

Шаг 1. Вычисляем для столбцов матрицы симплекс-разности и находим номер К из условия .

Шаг 2. Если , то опорный план

является оптимальным, а

есть оптимальное значение линейной формы , иначе переходим к шагу 3.

Шаг 3. Если , , то ЗЛП не имеет конечного решения, иначе находим номер l из условия

Направляющий элемент на S-й итерации метода есть элемент

Шаг 4. Вычисляем компоненты вектора :

Шаг 5. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Присваиваем переменной S алгоритма значение S+1 и переходим к шагу 1.

Пример 3.3 Симплекс-методом решить ЗЛП:

(3.57)

Х₁+2Х₂ 6

2Х₁+Х₂ 8

-Х₁+Х₂ 1

Х₂ 2 (3.58)

Х₁ 0 Х₂ 0.

Приводим систему линейных неравенств (3.58) к каноническому виду, вводя в каждое неравенство дополнительную переменную , где . Получим систему линейных уравнений:

Х₁+2Х₂+S₁=6

2Х₁+Х₂+S₂=8 (3.59)

-Х₁+Х₂+S₃=1

Х₂+S₄=2

Целевая функция будет иметь вид =3X₁+2X₂+0 S₁+0 S₂+0 S₃+0 S₄

Расширенная матрица

системы линейных уравнений (3.59) является исходной К-матрицей К⁽⁰⁾ ЗЛП, которая определяет исходный опорный план:

, , .

Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплексной таблицы.

Таблица 3.1

S	i
					-1						- -
					-3	-2					k=1 l=2
						3/2 1/2 3/2		-1/2 1/2 1/2			4/3 10/3
						-1/2		3/2			k=2 l=1
				4/3 10/3 2/3			2/3 -1/3 -1 -2/3	-1/3 2/3 1/3
							1/3	4/3

На второй итерации S=2, все , следовательно, опорный план

,

определяемый К-матрицей К⁽²⁾, оптимальный,

Оптимальное значение линейной формы равно:

Пример 3.4 Симплекс-методом решить ЗЛП:

max (2X₁+X₂) (3.60)

X₁-X₂ 10

X₁ 40 (3.61)

X_1,2 0

Приводим ЗЛП к каноническому виду

max (2X₁+X₂+0 S₁+0S₂)

X₁-X₂+ S₁=10 (3.62)

X₁+ S₂=40

.

Результаты последовательных итераций записываем в симплекс-таблицу.

Таблица 3.2

S	i
						-1
					-2	-1
						-1	-1		-
						-3
							-1		- -
							-1

Из симплекс-таблицы при S=2 следует, что согласно шагу 3 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны.

Итак, .