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

Как уже известно, прежде чем решать задачу линейного программирования симплекс-методом, ее необходимо привести к канонической форме (см. § 5.7). После этого выделяют переменные, которые присутствуют только в одном уравнении с коэффициентом единица и принимают их в качестве базисных. Если в ограничении такую переменную выделить нельзя, то вводят искусственную базисную переменную. Затем определяется исходный базисный план и значение целевой функции для этого плана (см. § 5.8). Далее выполняется описанная ниже последовательность шагов.

Шаг 1. Строим и заполняем исходную симплексную таблицу по следующей схеме (табл. 3):

Таблица 3

	-1	0		...	cj	...
	C	B		...	xj	...
...
xi	ci	bi			aij
		f		...	j	...

В столбце "Базис" записываются базисные переменные, в столбце "С" - коэффициенты при базисных переменных в целевой функции (c_i), в столбце "В" - свободные члены ограничений (b_i), т.е. значения базисных переменных. В столбцах x_j (небазисные переменные) отражаются коэффициенты при небазисных переменных в ограничениях (a_ij), над переменными x_j - коэффициенты при этих переменных в целевой функции (c_j). Строка "" в столбце "В" содержит значение целевой функции, которое рассчитывается по формуле:

(22)

а столбцы x_j этой же строки - значения относительных оценок (_j), рассчитываемых по формуле:

.

(23)

Относительными эти оценки называются потому, что их значение зависит от выбора базисного плана.

Условие оптимальности плана задачи линейного программирования (для задачи на max). Если для некоторого базисного плана относительные оценки , то этот план является оптимальным.

Рассмотренное условие является достаточным условием оптимальности базисного плана задачи.

Числа (-1) и 0, записываемые соответственно над столбцами "С" и "В", неизменно присутствуют в каждой симплексной таблице и носят вспомогательный характер, чтобы при расчете оценок _j по таблице не забывать о вычислении c_j.

При определении значения f фактически нужно найти сумму произведений элементов столбца "С" на соответствующие элементы столбца "В", что равносильно подстановке базисного плана в целевую функцию, а при определении значения относительной оценки _j - сумму произведений элементов столбца "С", включая (-1), на соответствующие элементы того столбца x_j, для которого она рассчитывается.

Шаг 2. Проверим полученный базисный план на оптимальность по условию оптимальности.

2.1. Если , то полученный базисный план не является оптимальным и необходимо переходить к другому базисному плану. Идти на шаг 3.

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

Идти на шаг 7.

2.3. Если в оптимальном плане , то это говорит о том, что задача имеет бесконечное число планов (см. пример 3 в §5.10).

Идти на шаг 7.

2.4. Если все0, то план является оптимальным и единственным. Решение найдено. Идти на шаг 7.

Шаг 3. Для перехода к новому базисному плану в первую очередь из числа небазисных переменных с отрицательными оценками _j выбирается переменная, которая вводится в базис. Введем в новый базис переменную x_k, которой соответствует наибольшая по абсолютной величине отрицательная оценка _j:

.

(24)

Столбец, отвечающий переменной x_k, назовем главным. Элементы главного столбца обозначаются через a_ik. Выбранная переменная будет вводиться в базис.

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

Шаг 4. Выбираем переменную, которая выводится из базиса. Ее индекс r находится из соотношения:

(25)

по всем i, для которых a_ik>0.

Строку таблицы, в которой получено наименьшее отношение элемента столбца "В" к соответствующему положительному элементу главного столбца, назовем главной. Элементы главной строки обозначаются через a_rj. Выбранная переменная x_r будет выводиться из базиса.

Если окажется несколько одинаковых наименьших значений отношений, то выбирается любая из соответствующих им переменных. Это может произойти в вырожденной задаче.

Элемент, стоящий на пересечении главной строки и главного столбца, назовем главным (обозначается через a_rk или  ).

В случае отсутствия значений a_ik>0 задача неразрешима, так как ее целевая функция не ограничена на множестве планов задачи сверху.

Шаг 5. Преобразование симплексной таблицы. Для определения нового базисного плана производим перерасчет элементов таблицы и результаты заносим в новую симплексную таблицу. Выбранные переменные в новой таблице меняются местами вместе со своими коэффициентами в целевой функции. Остальные переменные переписываются без изменений со своими коэффициентами.

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

• разрешающий элемент  заменяется на обратную величину 1/;

• разрешающая строка делится на разрешающий элемент;

• разрешающий столбец делится на разрешающий элемент с противоположным знаком;

• все остальные элементы таблицы преобразуются по правилу прямоугольника:

новый элемент	=	старый элемент		разрешающий элемент	-	элемент разрешающей строки		элемент разрешающего столбца
		разрешающий элемент

Некоторые практические советы:

1) если в главном столбце пересчитываемой таблицы стоит нуль, то соответствующая ему строка переписывается в новую симплексную таблицу без изменений;

2) если в главной строке пересчитываемой таблицы стоит нуль, то соответствующий ему столбец переходит в новую таблицу без изменений;

3) если из числа базисных исключается искусственная переменная, то соответствующий ей столбец в новую симплексную таблицу не включается и, следовательно, не пересчитывается. Как указывалось ранее, искусственные переменные вводятся только для получения исходного базисного плана. Впоследствии они выводятся из базиса и в число базисных больше не попадут. Данный прием не ускоряет процесса получения оптимального плана, однако уменьшает объем вычислений.

Шаг 6. Проверяем правильность расчета значений целевой функции f и оценок _j по формулам (22), (23). Переходим к шагу 2.

Шаг 7. Расчет закончен.