Учебное пособие: Практикум по решению линейных задач математического программирования

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

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

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

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент .

Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.

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

max

Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.

max

2) Определяем базисные переменные – это .

3) Заполняем первую таблицу

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0
	0	16	2	1	0	1	0	0
	0	5	0	1	0	0	1	0
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0

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