Имплекс-метод. Решение задач линейного программирования.

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

1. обобщенный симплекс-метод;

2. симплекс-метод в виде таблиц

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

Алгоритм симплекс-метода с помощью симплекс таблиц.

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

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

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

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

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

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

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

Замечание: Для того чтобы решать ЗЛП с помощью симплекс таблиц, необходимо её представить в канонической форме.

Пример: Найти минимум целевой функции F = x₄ – x₅ → min, если система ограничений имеет вид

Решение:

x₄, x₅ – свободные переменные

x₁, x₂, x₃ – базисные переменные (зависят от свободных)

Для составления симплекс таблиц систему ограничений и функцию F необходимо представить в следующем виде:

F – x₄ + x₅ = 0

	Базисные переменные	Свободный член	X1	X2	X3	X4	X5	Симпл отнош
	X1						-2	-
	X2					-2
	X3							3
	F					-1		-

*2 *(-1)

	Базисные переменные	Свободный член	X1	X2	X3	X4	X5	Симпл отнош
	X1					-3		-
	X5					-2		-
	X3			-1				1/5
	F	-2		-1				-

*1/5 3/5 2/5 (-1/5)

	Базисные переменные	Свободный член	X1	X2	X3	X4	X5	Симпл отнош
	X1	28/5		7/5	3/5
	X5	12/5		3/5	2/5
	X4	1/5		-1/5	1/5
	F	-11/5		-4/5	-1/5

Ответ: F_min = ; x = ( ; 0; 0; ; ).