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

 

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

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; ; ).