Методичка_ММИО_2006

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

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

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

задачи линейного программирования, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм 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

-1

-3

-2

k=1

l=2

3/2

1/2

3/2

-1/2

1/2

4/3

10/3

-1/2

3/2

k=2

l=1

4/3

10/3

2/3

-1/3

-1

-2/3

-1/3

2/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				2	1	0	0
0	1 2	3 4	0 0	10 40	1 1	-1 0	1 0	0 1	10 40
	3				-2	-1	0	0
1	1 2	1 4	2 0	10 30	1 0	-1 1	1 -1	0 1	- 30
	3				0	-3	2	0
2	1 2	1 2	2 1	40 30	1 0	0 1	0 -1	1 1	- -
	3				0	0	-1	3

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

Итак, .

Содержание