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

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

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

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

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

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

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

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

Шаг 3. Если a_ik ^{( S -1)} , , то ЗЛП не имеет конечного решения, иначе находим номер l из условия

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

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

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

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

(2.71)

Х₁+2Х₂ 6

2Х₁+Х₂ 8

-Х₁+Х₂ 1 (2.72)

Х₂ 2

Х₁ 0 Х₂ 0.

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

Х₁+2Х₂+S₁=6

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

-Х₁+Х₂+S₃=1

Х₂+S₄=2

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

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

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

, , .

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

Таблица 2.2.

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, все , следовательно, опорный план

,

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

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

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

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

X₁-X₂ 10

X₁ 40 (2.75)

X_{1, 2} 0

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

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

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

X₁+ S₂=40

.

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

Таблица 2.3

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

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

Итак, .