Симплекс-метод

Его называет еще методом последовательного улучшения плана. Метод предназначен для решения общей задачи линейного программирования.

Введение в симплекс-метод

Пусть имеем следующую задачу:

,                          (1)

с системой ограничений следующего вида:

.                              (2)

Разрешим эту систему относительно переменных :

.                                (3)

Векторы условий, соответствующие , образуют базис. Перемен­ные   назовем базисными переменными. Остальные переменные задачи – небазисные.

Целевую функцию можно выразить через небазисные переменные:

.

Если приравнять небазисные переменные нулю

,

то соответствующие базисные переменные примут значения

.

Вектор с такими компонентами представляет собой угловую точку многогранника решений (допустимую) при условии, что (опорный план).

Теперь необходимо перейти к другой угловой точке с меньшим значением целевой функции. Для этого следует выбрать некоторые небазисную и базисную переменные так, чтобы после того, как мы “поменяем их местами”, значение целевой функции уменьшится. Такой направленный перебор в конце концов приведет нас к решению задачи.

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

Формализованный алгоритм симплекс метода состоит из двух основных этапов: 1) построение опорного плана; 2) построение оптимального плана.

Проиллюстрируем алгоритм на рассмотренном ранее примере:

.

.

В случае базисных переменных начальная симплексная таблица для данного примера будет выглядеть следующим образом:

			1
=	1	–2	1
=	–2	1	2
=	3	1	3
=	–1	1	0

Она уже соответствует опорному плану (столбец сво­бодных членов).

Построение оптимального плана. Для того чтобы опорный план был оптимален при минимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неположительными (в случае максимизации – неотрицательными). То есть, при поиске минимума мы должны освободиться от положительных коэффициентов в строке .

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

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

.

– разрешающий (направляющий) элемент, строка – разрешающая.

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

Если в разрешающем столбце нет положительных коэффициентов, то целевая функция неограничена снизу (при максимизации – неограничена сверху).

Шаг модифицированного жорданова исключения над симплексной таблицей:

1. На месте разрешающего элемента ставится 1 и делится на разрешающий элемент.

2. Остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент.

3. Остальные элементы разрешающей строки делятся на разрешающий элемент.

4. Все остальные элементы симплексной таблицы вычисляются по следующей формуле:

.

			1		Разрешающий элемент, соответствующий замене базисной переменной на небазисную переменную .
	1	–2	1
	–2	1	2
	3	1	3
	-1	1	0

			1		Разрешающий элемент, соответствующий замене базисной переменной на небазисную переменную .
	–3	2	5
	–2	1	2
	5	–1	1
	1	–1	–2

			1		Все коэффициенты в строке целевой функции отрицательны, т.е. мы нашли оптимальное решение.
	3/5	7/5	28/5
	2/5	3/5	12/5
	1/5	–1/5	1/5
	–1/5	–4/5	–11/5

Построение опорного плана. Пусть необходимо решить задачу:

.

Введем дополнительные переменные, чтобы преобразовать ограничения-неравенства к равенствам. В ограничениях-равенствах дополнительные переменные должны быть нулевыми. Тогда система ограничений принимает вид:

,

где  .

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

			….		.…		1
0			….		….
….	….	.…	….	.…	.…	.…	.…
0			….		….
			….		….
….	….	….	….	….	….	….	…
			….		….
			….		….		0

Правила выбора разрешающего элемента при поиске опорного плана:

1. При условии отсутствия “0-строк” (ограничений-равенств) и “сво­бодных” перемен­ных (т.е. переменных, на которые не наложено требование неотри­цатель­ности).

• Если в столбце свободных членов симплексной таблицы нет отрицательных элементов, то опорный план найден.

• Есть отрицательные элементы в столбце свободных членов, например . В такой строке ищем отрицательный коэф­фициент , и этим самым определяем разрешающий столбец . Если не найдем отри­цательный , то система ограничений несовместна (противо­речива).

• В качестве разрешающей выбираем строку, которой соответствует минимальное отношение:

,

где - номер разрешающей строки. Таким образом, - разрешающий элемент.

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

2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.

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

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