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

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

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

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

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

· все ограничения преобразовываются в равенства с неотрицательной правой частью;

· все переменные неотрицательные;

· целевую функцию нужно либо максимизировать либо минимизировать.

Преобразование неравенства в равенства

Неравенства любого типа можно преобразовать в равенства путем добавления в левую часть дополнительных переменных – остаточных либо избыточных.

Пример 1:

- остаточная переменная

Пример 2:

Преобразование свободных переменных в неотрицательные:

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

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

Редимикс

Задачу ЛП в стандартной форме можно представить в виде следующей таблицы (симплекс таблицы)

Базис								Решения
		-5	-4
		-1							-1

Для решения задачи симплекс методом лежит 2 условия

Условие оптимальности – вводимой переменной в задачи максимизации (минимизации является небазисная переменная имеющая наибольший отряд (положительный) коэффициент в z – строке.

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

Оптимальное решение достигнуто, когда в z строке все коэффициенты при небазисных переменных будут неотрицательны (неположительны).

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

Если базисных переменных с такими свойствами несколько, то выбирается один из них произвольно:

Базис								Решения
		-5	-4
	0/6		2/3	1/5
	-	-	-	-	-	-	-	-
	-	-	-	-	-	-	-	-
	-	-	-	-	-	-	-	-

Базис								Решения
			-2/3	5/6
			2/3	1/6
			4/3	-1/6
	-		5/3	-	-	-	-
	-		-	-	-	-	-	-

Базис								Решения
		-5	-4						-
		-1							-1

вводим в базис выводим

Базис								Решения
			-2/3	5/6					-
			2/3	1/6
			4/3	-1/6					3/2
			5/3	1/6

Опять выбираем ведущую строку, теперь это

Базис								Решения
				9/12	1/2
				¼	-1/2
				-1/8	5/4			3/2
				9/24	-5/4			5/2
				1/8	-3/4			½

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