Теоретические основы решения ЗЛП (продолжение)

Как мы увидели в предыдущем пункте, при решении ЗЛП аналитическим методом имеются определённые признаки, по которым можно определить, является ли данное опорное решение оптимальным. Конечно, те признаки, которыми мы пользовались, чисто интуитивные. Мы приведём здесь научные признаки.

Пусть X ₁ - некоторое опорное решение ЗЛП (1.6), причём в (1.6) базисные переменные уже выражены через свободные, то есть в этой системе базисные переменные уже исключены из всех уравнений, кроме одного, в который она входит с коэффициентом 1. Например, если в X ₁ базисными являются x ₁, x ₂, …, x_n, то (1.6) имеет вид

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®max(min)

(1.7)

Обозначим через I_б =(i ₁, i ₂, …, i_m) вектор индексов переменных, входящих в базис, а через C_б =(, , …, ) - вектор коэффициентов целевой функции при базисных переменных. Например, если мы имеем ситуацию (1.7), то I_б =(1, 2, …, m), C_б =(c ₁, c ₂, …, c_m).

Величина D _k = C_бA_k - c_k = - c_k называется оценкой разложения вектора условий A_k по базису опорного решения.

Так в ситуации (1.7) имеем D _k = - c_k. Ясно, что если k Î I_б (то есть если переменная x_k - базисная), то D _k =0.

Пусть опорное решение X ₂ получено из X ₁ переводом некоторой переменной x_k из свободных в базисные. Введём обозначение q_k = Можно доказать, что тогда

3.5.1. CX ₂- CX ₁=- q_k D _k. Другими словами, при переходе от опорного решения X ₁ к опорному решению X ₂ включением в число базисных переменных x_k значение целевой функции меняется на - q_k D _k.

Отсюда получаем, что

3.5.2. Для получения более высокого значения целевой функции (при решении задачи на максимум) необходимо включить в число базисных переменных переменную x_k такую, что D _k <0. Для получения более низкого значения целевой функции (при решении задачи на минимум) необходимо включить в число базисных переменных переменную x_k такую, что D _k >0.

3.5.3. Если в опорном решении X для всех свободных переменных x_k имеет место оценка D _k ≥0, то на X достигается максимум целевой функции, а если D _k ≤0, то - минимум.

Условия D _k ≥0 для максимума и D _k ≤0 для минимума называются достаточными условиями решения задачи. Если они не выполняются или для всех свободных переменных x_k имеет место a_ik ≤0 при любом i Î I_б, то ЗЛП не имеет решений.

 

 

Симплекс-метод решения ЗЛП

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

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

1. Привести задачу к каноническому виду.

2. С помощью метода Жордана-Гаусса найти очередное опорное решение.

3. Проверить на оптимальность очередное опорное решение. Если оно оптимальное, то задача решена. В противном случае перейти к пункту 2.

Опорное решение, полученное на первом шаге, называется первоначальным опорным планом.

Для нахождения первоначального опорного плана (после приведения задачи к каноническому виду) поступаем следующим образом:

1. Из векторов условий A ₁, A ₂, …, A_n включаем в базис те, которые являются стандартными единичными (то есть те, у которых все координаты нулевые, кроме одной, которая равна 1; среди них обязательно окажутся те, которые соответствуют дополнительным переменным с положительным знаком). Соответствующие переменные будут включены в базис. Если число таких векторов условий равно m, то первоначальный опорный план построен: им является решение системы ограничений, полученное приравниванием свободных переменных к 0. В противном случае идём к пункту 2.

2. Допустим, переменная x_k пока не вошла в базис. Тогда выбираем уравнение, в котором отношение (где a_ik >0) будет минимальным. Это (i -е) уравнение будет ведущим: разделив его на коэффициент a_ik при x_k, добиваемся, чтобы коэффициент при x_k стал равным 1, а из остальных уравнений x_k исключаем (применяем метод Жордана-Гаусса). Процесс продолжаем до тех пор, пока базис не будет содержать m переменных.

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

Пример 1. Найти первоначальный опорный план задачи:

-3 x ₁+ x ₂+2 x ₃®max(min)

Решение. Решим задачу вначале «вручную».

1. Приведём задачу к каноническому виду. Для этого сначала умножим второе неравенство системы ограничений на (-1) (добиваемся, чтобы правые части всех нетривиальных ограничений имели знак «+»). Получаем систему ограничений

Теперь добавляем во второе и третье неравенства системы дополнительные переменные x ₄ и x ₅:

Таким образом, получаем канонический вид исходной задачи:

-3 x ₁+ x ₂+2 x ₃®max(min)

2. С помощью метода Жордана-Гаусса найдём первоначальный опорный план. Прежде всего замечаем, что дополнительная переменная x ₄ входит только во второе уравнение. И она уже в базисе. Так как для x ₂ min =2 достигается в первом уравнении (при определении этого min второе уравнение не участвует, так как коэффициент при x ₂ в нём равен 0), то x ₂ включаем в базис, исключив его из третьего уравнения (для этого первое уравнение вычитаем из третьего):

Две базисные переменные из первого и второго уравнений выбраны. Осталось выбрать третью базисную переменную из третьего уравнения. Переменные x ₃ и x ₅ для этого не годятся, так как коэффициенты при них отрицательны. Остаётся только x ₁. Для того, чтобы её ввести в базис необходимо, чтобы минимум отношений свободных членов к положительным коэффициентам достигался в третьем уравнении. Так оно и есть: min =2 достигается в третьем уравнении. Поэтому третье уравнение делим на 2, затем прибавляем его к первому и вычитаем из второго:

Таким образом, при x ₃=0, x ₅=0 имеем x ₁=2, x ₂=4, x ₄=2 и X ₁=(2; 4; 0; 2; 0) - первоначальный опорный план.

Ответ: X ₁=(2; 4; 0; 2; 0) - первоначальный опорный план.

Проверка опорного плана на оптимальность проводится по следующей схеме:

1. Находятся оценки D _k = C_бA_k - c_k = - c_k для всех k =0, 1, …, n. При этом D₀ - это значение целевой функции при данном опорном плане, и D _k =0 для всех базисных переменных x_k (то есть последние вычислять необязательно, а достаточно сразу положить D _k =0).

2. Если условие оптимальности опорного плана выполнено (D _k ³0 для всех k =1, …, n при поиске максимума, D _k £0 для всех k =1, …, n при поиске минимума), то задача решена. В противном случае переходят к другому опорному плану.

Переход к другому опорному плану проводится по следующей схеме:

1. Для всех D _k, для которых нарушается условие оптимальности задачи, вычисляются q_k = , а по ним - величины - q_k D _k.

2. Выбирается x_k такой, что |- q_k D _k | является максимальным. Эту x_k и вводим в базис, выводя из него x_i, в которой достигается минимальное q_k, по методу Жордана-Гаусса.

Пример 2. Решить задачу предыдущего примера (найти экстремумы).

Решение. При решении предыдущего примера канонический вид задачи и её первоначальный опорный план найдены.

Проверим на оптимальность решение X ₁. Для этого необходимо вычислить D _k = C_бA_k - c_k для k - индексов свободных переменных. При k =3 имеем

D₃= C_бA ₃- c ₃=(1, 0, -3)× -2=1× +0× +(-3)× -2=1,

то есть D₃=1≥0. В частности, в X ₁ минимум не достигается.

D₅= C_бA ₅- c ₅=(1, 0, -3)× -0=1× +0× +(-3)× =1,

то есть D₅=1≥0. Так как D _k ≥0 для всех k =1, 2, 3, 4, 5, то в X ₁ достигается максимум целевой функции, который равен D₀= CX =-3×2+4+2×0=-2. Минимум в этой точке не достигается.

Перейдём к другому опорному плану. Для D₃ и D₅, для которых нарушается условие оптимальности, вычислим q ₃ и q ₅, а по ним - величины - q ₃D₃ и - q ₅D₅:

q ₃= = = = (достигается при x ₄),

- q ₃D₃=- ×1=- ,

q ₅= = =4, (достигается снова при x ₄, то есть в любом случае x ₄ будем выводить из базиса),

- q ₅D₅=-4×1=-4.

Так как |- q ₅D₅|=|-4|>|- |=|- q ₃D₃|, то в базис будем вводить x ₅ вместо x ₄. Для этого второе уравнение прибавляем к первому и третьему, и умножаем его на 2:

Получили новый опорный план X ₂=(4; 6; 0; 0; 4), который проверяем на оптимальность:

D₃= C_бA ₃- c ₃=(1, 0, -3)× -2=1×3+0×3+(-3)×1-2=-2,

D₄= C_бA ₄- c ₄=(1, 0, -3)× -0=1×1+0×2+(-3)×1-0=-2.

Таким образом, D₃=-2<0, D₄=-2<0, то есть D _k ≤0 для всех k =1, 2, 3, 4, 5. Значит, X ₂ - оптимальное решение задачи с точки зрения минимизации. В нём CX =-3×4+6+2×0=-6.

Ответ: F _min=-6, минимум достигается в точке X ₂=(4; 6; 0);

F _max=-2, максимум достигается в точке X ₁=(2; 4; 0).

 

Симплекс-таблицы.

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

 

№№ ур-й	Своб. члены	A 1	A 2	…	An	qk
	b 1	a 11	a 12	…	a 1 n	b 1/ a 1 k (a 1 k >0)
	b 2	a 21	a 22	…	a 2 n	b 2/ a 2 k (a 2 k >0)
…	…	…	…	…	…	…
m	bm	am 1	am 2	…	amn	bm / amk (amk >0)

производятся преобразования Жордана-Гаусса. Затем составляется симплекс-таблица вида

Базис	Сб	Своб. члены	c 1	c 2	…	cn	q 1	q 2	…	qn
A 1	A 2	…	An
		b 1	a 11	a 12	…	a 1 n			…
		b 2	a 21	a 22	…	a 2 n			…
…	…	…	…	…	…	…	…	…	…	…
		bm	am 1	am 2	…	amn			…
D k	D1	D1	D2	…	D n	- q 1D1	- q 2D2	…	- qn D n

в которой D _k =0 сразу проставляются для всех базисных векторов условий и D _k = C_бA_k - c_k для небазисных, столбцы q_k вычисляются только для свободных переменных x_k, наконец, для тех из них, для которых не выполнено условие оптимальности, вычисляются - q_k D _k, и из них выбирается наибольший по абсолютной величине. Тот x_k, для которого достигается этот максимум, вводится в базис.

Продемонстрируем применение таблиц при решении нашего предыдущего примера.

I этап. Нахождение первоначального опорного плана:

Табл.1	№№ ур-й	Своб. члены	x 1	x 2	x 3	x 4	x 5	qk
			-1					2/1	min, k =2
								-
							-1	6/1
Табл.2			-1					-
								4/1
					-1		-1	4/2	min, k =1
Табл.3					3/2		-1/2
					3/2		1/2
					-1/2		-1/2

Напоминаем, что в базис включаем x ₂. Имеем, что минимум min =2 отношений свободных членов системы к положительным коэффициентам достигается в первой строке. При переходе к Табл.2 первые две строки Табл.1 перенесли в Табл.2. Третью строку табл.2 получили, вычтя из третьей строки (Табл.1) первую строку.

В Табл.3 в базис включаем x ₁. Имеем min =2 в третьей строке. Третью строку Табл.2 делим на 2 - получаем третью строку Табл.3. Затем третью строку прибавляем к первой строке и вычитаем из второй строки Табл.2. Получаем первую и вторую строки Табл.3.

II этап. Применение симплекс-метода.

Базис	Сб	Своб. члены	-3					q 1	q 2	q 3	q 4	q 5
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2	-	-	8/3	-	-
x 4					3/2		1/2	-	-	4/3	-
x 1	-3				-1/2		-1/2	-	-	-	-	-
D k	-2						-	-	-4/3	-	-4
x 2
x 5
x 1	-3
D k	-6			-2	-2

Комментарии опустим, предложив читателю восстановить применение метода к таблицам.

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

 

Метод искусственного базиса