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

I. После введения добавочных переменных, система уравнений записывается в виде, который называется расширенной системой (11). Предполагается, что все добавочные переменные имеют тот же знак, что и свободные члены.

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

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

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

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

1) , если и имеют разные знаки;

2) , если и ;

3) ли ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

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

VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):

1) В левом столбце записываем новый базис: вместо основной переменной - переменную ,

2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.

3) Новую строку получаем из старой делением на разрешающий элемент .

4) Все остальные элементы вычисляем по правилу прямоугольника:

(12)

Далее переходим к шагу III.

Пример.Решить задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде

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

Заполняем первую симплекс-таблицу:

Базис	Свободный	Переменные	Оценочные
	член							отношения
								18/3
		-2	-3

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

Находим оценочные отношения и выбираем из них минимальное (5). Следовательно, , переменная является вводимой в базис, а соответствующая ей строка - разрешающей.

Переходим к новой симплекс-таблице:

а) в новом базисе основные переменные ;

б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной ставим 1, а остальные элементы столбца равны 0 и т.д. Третья строка получается делением на разрешающий элемент . Остальные клетки таблицы заполняем по формулам (12). Например:

Получаем вторую симплекс-таблицу:

Базис	Свободный	Переменные	Оценочные
	член							отношения
						-3
						-1		11/2
		-2

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и - вводимая переменная. Считаем оценочные отношения и находим разрешающую строку - первая и выводимую из базиса переменную - .Разрешающий элемент .

Переходим к новой симплекс-таблице:

Базис	Свободный	Переменные	Оценочные
	член							отношения
						-3
				-2				5/5
								5/1
				-3				12/9
						-3

и на этот раз критерий оптимальности не выполнен.

Выводимая переменная ; вводимая переменная- . Переходим к новой таблице.

Базис	Свободный	Переменные	Оценочные
	член							отношения
				-1/5	3/5
				-2/5	1/5
				2/5	-1/5
				3/5	-9/5
				4/5	3/5

Критерий оптимальности выполнен. Следовательно, Оптимальное решение

Поиск по сайту: