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

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

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

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

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

Шаг 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) к каноническому виду, вводя в каждое неравенство дополнительную переменную S_i, где i = 1,4. Получим систему линейных уравнений:

Х₁ + 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 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны.

Итак, .

3.5. Двойственный симплекс-метод (Р-Метод)

Пример 3.5. Рассмотрим следующую ЗЛП:

min(2Х₁ + 4Х₂)

3 Х₁ + Х₂ 3

4 Х₁ + 3 Х₂ 6 (3.63)

Х₁ + 2 Х₂ 3

Х_1,2 0

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

max (-2 Х₁ -4 Х₂)

3 Х₁ + Х₂ - S₁ = 3

4 Х₁ + 3 Х₂ - S₂ = 6

Х₁ + 2 Х₂ - S₃ = 3

или

max (-2 Х₁ -4 Х₂)

- 3 Х₁ - Х₂ + S₁ = - 3

- 4 Х₁ - 3 Х₂ + S₂ = - 6 (3.64)

Х₁ + 2 Х₂+ S₃ = 3

Рассмотрим расширенную матрицу системы линейных уравнений (3.64):

.

Матрица содержит единичную подматрицу порядка 3 и, следовательно, определяет базисное решение

= (-3; -6; 3); = (3; 4; 5)

системы уравнений, причем = (0, 0, 0). Так как элементы (n + 1 = 6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы :

, .

Так как все симплекс-разности матрицы являются неотрицательными, то базисное решение = (-3; -6; 3), не являющееся допустимым решением ЗЛП, является «лучшим», чем оптимальное решение.

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

Дата добавления: 2014-12-29