Решение систем линейных уравнений методом Жордана Гаусса

 

Так как y1 = -2 < 0 и y3 = -1 < 0, то точка (x,y)0 = (0; 0; - 2; +4; - 1), определяемая данной таблицей, соответствует недопустимому решению. Поэтому необходимо произвести переход к другой точке с помощью модифицированного жорданова исключения. Разрешающий элемент выбираем по ПРАВИЛУ 1. а именно: в первой строке (так как b1 = -2 по абсолютной величине больше b3 = -1) отыскиваем любой отрицательный коэффициент, например, a12 = -1, поэтому 2-ой столбец объявляем разрешающим. Теперь рассчитаем неотрицательные симплексные отношения: b1 : a12 = (-2) : (-1) = 2 > 0, b2 : a22 = 4 : 1 = 4 > 0, b3 : a32 = (-1) : (-1) = 1 > 0. минимальное из них соответствует 3-ей строке, а, следовательно, 3-я строка объявляется разрешающей. При этом элемент a32 будет разрешающим элементом.

Переходим к следующей 2-ой итерации.

Итерация 2	- x1	- y3	1	Пометки	Расчет симплексных отношений
y1 =	- 2	- 1 Разреш элемент	- 1	Наибольшее нарушение ← Разршающая строка	-1	= 1
					-1
y2 =	1	1	3		4	= 4
					1
x2 =	0	- 1	1		-1	= 1
					-1
Z' =	-5	- 1	1
		↑ Разреш. столбец

 

Эта таблица определяет точку (x, y)1 = (0; 1; -1; 3; 0) (или точку x1 = (0;1) ). Эта точка соответствует решению, которое также является недопустимым, так как y1 = -1 < 0. Поэтому переходим к следующей точке, т.е. к следующей таблице. Разрешающий элемент a12 = - 1.

Эта таблица определяет точку (x, y)2 = (0; 2; 0; 2; 1) (или точку x2 = (0;2) ). Полученная точка соответствует допустимому решению, так как в соответствующей таблице все свободные члены bi положительны.

Итерация 3	- x1	- y1	1
y3 =	2	-1	1
y2 =	-1	1	2
x2 =	2	- 1	2
Z' =	-3	- 1	2

 

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

Описание второго этапа симплекс-метода

Пусть в результате выполнения первого этапа симплекс-метода получена следующая таблица:

	x1	…	xk	ys+1	…	ym
y1 =	α11	…	α1 k	α 1, s+1	…	α1 n	β1
…			…
ys =	α s1	…	α sk	α s, s+1	…	α sn	βs
xk+1	α k+1, 1		α k+1, k	α k+1, s+1		α k+1, n	βk+1
…			…
xn =	α m1	…	α mk	α m, s+1	…	α m n	βm
Z =	q1		qk	qs+1		qn	Q

 

После нескольких шагов жордановых исключений на верх таблицы перешло (m-l) зависимых переменных yi , а слева от таблицы появилось (n-k) переменных xj; очевидно, что m-l = n-k. Так как первый этап симплекс-метода выполнен, все коэффициенты bi неотрицательны.

Пусть в таблице все коэффициенты qi также неотрицательны. Тогда исходная задача ЛП решена, причем max Z = Q. Оптимальным решением при этом является опорное допустимое решение, определяемое данной таблицей, а именно: x1 = … = xs = 0 = y s+1 = … = ym, а y 1 = β1, … , ys = βs, xk+1= βk+1 , … , xn = βm .

Пусть среди коэффициентов Z-строки есть отрицательные, например, пусть qs < 0. В этом случае нельзя утверждать, что опорное решение, определяемое этой таблицей, является оптимальным. Симплекс-метод для отыскания оптимального решения означает специальное правило перехода от полученной точки Pk (вершины выпуклого многогранника D) к другой соседней вершине этого многогранника, в которой значение Z не меньше Q. Этот процесс продолжается, пока не будет найдена вершина, в которой значение Z максимально, т.е. для которой все коэффициенты Z-строки будут неотрицательны или пока не будет установлено, что функция Z неограничена сверху.

Чтобы осуществить такой переход от данной вершины к соседней, делаем один шаг модифицированного жорданова исключения с ПРАВИЛО 2 выбора разрешающего элемента.

ПРАВИЛО 2 выбора разрешающего элемента

1. В качестве разрешающего  выбираем столбец, содержащий отрицательный  элемент Z- строки, например, столбец s, так как qs < 0. Обычно разрешающим  выбирают столбец, содержащий наибольший  по абсолютной величине отрицательный  коэффициент Z-строки.

2. Если в этом (s-ом) столбце  нет положительных коэффициентов, то это означает, что целевая  функция Z не ограничена сверху  на множестве допустимых решений, т.е. исходная задача не имеет  решений.

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

Пример 2.1 (продолжение)

Рассмотрим таблицу, соответствующую итерации 3 примера 2.1, полученную выше.

Так как все свободные члены в этой таблице неотрицательны, то, как уже говорилось, определяемое ею решение x2 = (0;2) является допустимым, но, так как коэффициенты Z- строки отрицательны (q1 = - 3 < 0 и q2 = - 1 < 0), то это решение не является оптимальным.

Итерация 3	- x1	- y1	1	Пометки	Расчет симплексных отношений
y3 =	2 Рареш. элмент	-1	1	← Разрешающая строка	1	= 0,5
					2
y2 =	- 1	1	2		2	< 0
					-1
x2 =	2	- 1	2		2	= 1
					2
Z' =	-3	- 1	2
	↑ Разреш. столбец

 

Переходим к следующей вершине, предварительно выбрав разрешающий элемент. Разрешающий столбец здесь – первый, так q1 по модулю больше q2. Разрешающая строка тоже первая, так как ей соответствует минимальное симплексное отношение, равное 0,5. Разрешающий элемент a 11 = 2. Построим новую таблицу.

Итерация 4	- y3	- y1	1	Пометки	Расчет симплексных отношений
x1 =	0,5	-0,5	0,5		0,5	< 0
					-0,5
y2 =	0,5	0,5 Рареш. элмент	2,5	← Разрешающая строка	2,5	5
					0,5
x2 =	-1	0	1		1	+¥
					0
Z' =	1,5	- 2,5	3,5
		↑ Рареш. столбец

 

Таблице, полученной на 4-ой итерации, соответствует допустимое опорное решение x3 = (0,5; 1). Но это решение также не является оптимальным, так как q2 = - 2,5 < 0. Соответственно второй столбец выбираем разрешающим. Разрешающая строка – третья, так как ей соответствует единственное неотрицательное симплексное отношении. Следовательно, разрешающий элемент a22 = 0,5. Переходим к следующей таблице.

Итерация 5	- y3	- y2	1
x1 =	1	1	3
y3 =	1	2	5
x2 =	1	0	1
Z' =	4	5	16

 

Решение, определяемое данной таблицей (x,y) 4 = (3; 1; 5; 0; 0) или x4 = (3; 1). Это опорное решение допустимое и оптимальное, так как qj > 0 , j = 1,2. Таким образом, x4 = x* , т.е. оптимально. Значение целевой функции для этого решения, т.е. Z'(x4), в таблице определяется величиной Q. Следовательно, Z' (x*) = 16, а Z (x*) = - Z' (x*) = - 16. Убедиться в правильности полученного значения можно, подставив координаты оптимальной точки в выражение для целевой функции, т.е. Z (x*) = -5x1*- x2* = (-5)*3- 1*1 = -16.

Ответ исходной задачи Примера 2.1: x* = (3; 1), Z (x*) = -16.

Проанализируем полученный результат. Из таблицы, соответствующей итерации № 5, видно, что y1* = 5, y2* = 0, y3* = 0, Это означает, что второе и третье неравенства исходной задачи для оптимального решения выполняются как тождества, т.е. точка x* лежит на пересечении гиперплоскостей, соответствующих второму и третьему неравенствам.

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

Геометрическая иллюстрация решения задачи ЛП

 

 

 

 

 

§5. Метод Жордана-Гаусса решение систем линейных уравнений.

Определение. Система m уравнений с n неизвестными называется системой с базисом, если в ней имеются какие – то m неизвестных, каждое из которых входит только в одно уравнение с коэффициентом единица и не входит в остальные уравнения.

Система с базисом может быть записана, например, так:

x1 +      a1. m+1  xm+1  + ... +a1n xn  =   a10,

    x2 +  a2. m+1 xm+1   + ... +a2n xn  =  a20,

...............................................................

    xm + am. m+1  xm+1  + ... +amn xn =   am0.

Для того, чтобы произвольную систему m уравнений с n неизвестными привести к системе с базисом, воспользуемся методом Жордана – Гаусса. Рассмотрим систему

a11x1 + a12x2 + ... + a1kxk + ... + a1pxp + ... + a1n xn =  a10,

a21x1 + a22x2 + ... + a2kx k + ... + a2pxp + ... + a2nxn  = a20,

.......................................................................................

ai1x1 + ai2x2  + ... + aikxk  + ... + aipxp  + ... + ainxn  =  ai0,

......................................................................................

as1x1 + as2x2 + ...  + aspxp  + ... + aspxp + ... + asnxn  = as0,

......................................................................................

am1x1 + am2x2 + ... + amkxk + ... + ampxp + ... + amnxn = am0.

 

Составим таблицу Жордана – Гаусса .

x1	x2		xk		xp		xn	ai0
a11	a12	.....	a1k	.....	a1p	.....	a1n	a10
a21	a22	.....	a2k	.....	a2p	.....	a2n	a20
.....	.....	.....	.....	.....	.....	.....	.....	.....
ai1	ai2	.....	aik	.....	aip	.....	ain	ai0
.....	.....	.....	.....	.....	.....	.....	.....	.....
as1	as2	.....	asp	.....	asp	.....	asn	as0
.....	.....	.....	.....	.....	.....	.....	.....	.....
am1	am2	.....	amk	.....	amp	.....	amn	am0