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

Теоретическая часть:

Симплекс-метод в отличие от геометрического, является полностью аналитическим, что позволяет использовать его в задачах с практически любым конечным числом переменных. Для его использования все ограничения задачи должны представлять собой равенства. Ограничения задачи могут иметь вид: В случае ( ) вводятся дополнительные переменные u_i: ;в случае ( ) вводятся фиктивные переменные w_i: ; в случае ( ) одновременно вводятся дополнительные переменные u_i и фиктивные переменные w_i; .Целевая функция дополняется членами ,содержащими w_i c большим по модулю отрицательным коэффициентом .Симплекс-метод состоит в процедуре последовательных переходов от одного опорного решения к другому, причем на каждом шаге значение целевой функции должно увеличиваться. Процедура заканчивается тогда, когда переход к новым опорным решениям не приводит к увеличению целевой функции

Практическая часть:

Записываем симплекс – таблицу

Табл.№ 2

Базисные переменные	Свободные члены						Свободные члены
	20	2	1	1	0	0	20
	12	1	1	0	1	0	12
	30	1	3	0	0	1	10
	0	-40	-50	0	0	0

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

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

Новые эл-ты = старые эл-ты -

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

1) Если в индексной строке найдется хотя бы один отрицательный элемент и

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

2) Если все элементы индексной строки неотрицательны, то достигнуто оптимальное решение.

Это и есть достаточные условия существования оптимального плана решения.

В нашем случае разрешающий столбец 4, строка 2, разрешающее число 3. (см. табл. 2)

Решение не является оптимальным, т.к. в индексной строке есть отрицательные элементы. Продолжаем действие симплекс – преобразование.

Новая симплекс – строка – это старая строка, делимая на разделяющее число.

Далее делаем преобразования по правилу (смотри выше).

Получаем новую таблицу, введя в базис вместо .

Табл. №3