Симлекс-метод (стр. 3 из 4)

Ax=A0.

Матрица Ap=[A, A0] называется расширенной матрицей. Метод полного исключения Жордана - Гаусса состоит из конечного числа однотипных итераций и заключается в сведении матрицы к единичному виду. Метод основывается на двух операциях:

1) одну из строк расширенной матрицы умножают на множитель, отличный от нуля;

2) из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.

Каждое из таких элементарных преобразований ( называемых преобразованием Гаусса) приводит к новой системе линейных уравнений, которая эквивалентна начальной системе.

Первая итерация метода полного исключения.

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

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

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

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

Если после k-й итерации главная часть матрицы Ap(k) не содержит ни одного элемента или содержит только нули, то процесс заканчивается.

Пусть процесс оборвался после итерации 1. Предположим вначале, что среди строк матрицы A(l) есть такие, которые не были направляющими ни в одной из предыдущих итераций, например, строка с номером i. Тогда очевидно,

aij = 0; j = 1, 2, ., n.

Поскольку для любой строки справедливо

A(i)x = ai0 , (2.2.9)

то уравнение для і-й строки имеет вид

0x1+0x2+.+0xn=ai0(l). (2.2.10)

Если ai0(l)≠0, то уравнение (2.2.10) противоречиво, и данная система уравнений неразрешима.

Если ai0(l)=0, то уравнение (2.2.10) представляет собой тождество и

i-я строка может быть отброшена.

Перебрав одну за другой все строки матрицы A(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.

Таким образом, в системе окажется равно l уравнений. Примем для определенности, что это первые по порядку l уравнений. Тогда полученную систему уравнений можно записать в виде

i=1, 2, .,l. (2.2.11)

Пусть i-й направляющей строке соответствует i-й направляющий столбец вследствие соответствующего выбора направляющего элемента. Тогда

aij(l)=

i=1, 2, ., l. (2.2.12)

Следовательно, (2.2.11) можно записать в виде:

xi = ai0(l) -

i=1, 2, ., l, (2...2.13)

причем переменные xi ( i =1, ., l) являются базисными, а переменные xj

( j=l+1, ., n) - небазисными.

При xj = 0 ( j=l+1, ., n) получим одно из базисных решений системы уравнений

xi = ai0(l), i =1, 2, ., l, xj=0; j=l+1,.,n.

Задавая для xj произвольные значения

, получим полное множество решений.

Если xi - i-я компонента этого решения, то

(2.2.14)

Обозначим

x0= (a10, a20,., al0,0,.,0 )

xj= (-a1j, -a2j,., -aij, 0 ,., 0, 1, 0 ,.,0 ), 1 £ j £ n.

Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (2.2.14):

x общ = x0 +

(2.2.15)

где x0- базисное решение начальной системы уравнений;

- полное решение соответствующей однородной системы уравнений (то есть при A0=0).

Обозначим расширенную матрицу системы уравнений после k-й итерации через

Ap(k)=[ai0(k), ai1(k),.,ain(k)],i=1,2,.,m.

Пусть aij(k)- направляющий элемент преобразования на (k + 1)-й итерации. Тогда в результате (k + 1)-й итерации метода полного исключения Гаусса получим матрицу Ap(k+1), элементы которой определяются следующими соотношениями:

1) для всех элементов направляющей строки

l=1, 2,.,n; (2...2.16)

2) для элементов направляющего столбца

arj(k+1)=0; r=1,.,n, причем r¹и; aij(k+1)=1; (2.2.17)

3) для всех остальных элементов матрицы

(2.2.18)

Пример 2.3. Применим метод полного исключения Гаусса для исследования системы уравнений

x1 + 2x2 + x3 + x4 = 3;

2x1 + x2 + x3 + 3x4 = 3;

4x1 + 5x2 + 3x3 + 5x4 = 9.

Расширенная матрица имеет вид:

Первая итерация. В качестве первого направляющего элемента возьмем a11= 1 , умножим первую строку матрицы А на 2 и на 4 , затем вычитая результаты из второй и третьей строк, получим

Вторая итерация. Поскольку главная часть матрицы Ap(1) содержит ненулевые элементы, продолжим процесс исключения. Выберем элемент a22(1)=-3.

После аналогичных преобразований получим

Как видим, главная часть матрицы Ap(2), состоящая из элементов a33(2) и a34(2) , содержит только нули. Следовательно, процесс исключения заканчивается.

Исследуем матрицу A(2). Поскольку третья строка содержит лишь нулевые элементы, то она может быть отброшена. Тогда эквивалентная матрица системы уравнений будет иметь вид

Соответственно формулам (2.2.13), (2.2.14) имеем базисное решение

x1*=1; x2*=1; x3=0; x4=0.

Общее решение данной системы имеет такой вид:

X1=1-

X2=1- X3= X4=

где a3, a4- произвольные скаляры.

3. Табличный симплекс метод.

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

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

A1x1+.+Anxn+e1xn+e1xn+1+.+emxn+m=A0=[ai0],

где

. - единичный базис, ai0³0

для всех i = 1, 2,., n.

Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ., An, e1, ., em, A0].

Пусть aij- направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (3.3.18) получим новые значения свободных членов:

. (3.3.19)

Исследуем выражения (3.3.19). и выясним условия, при которых al0(k+1)>0 для всех l, то есть новое базисное решение будет также допустимым.

По предположению al0(k)>0; l=1,.,m,

aij(k)>0,

тогда

Если alj(k)<0, тогда al0(k+1) > 0, поскольку ai0(k) > 0 , aij(k) > 0.

Если alj(k)>0, то

будет больше нуля при всех l=1, 3. ..., m тогда и только тогда, когда

(3.3.20)

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение

было минимально при условии, что aij>0.

При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов Dj:

(3.3.21)

где Iб - множество индексов базисных векторов; xij- определяют из условия

(3.3.22)

Величины {Dj } равны симплекс-разницам для переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть

.

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 3.3.

Таблица 3.3.

c	c1	c2	c3	.	cj	.	cn
Bx	a00	A1	A2	A3	.	Aj	.	An
c1	x1	a1o	a11	a12	a13	.	a1j	.	a1n
c2	x2	a2o	a21	a22	a23	.	a2j	.	a2n
.	.	.	.	.	.	.	.	.	.
ci	xi	aio	ai1	ai2	ai3	.	aij	.	ain
.	.	.	.	.	.	.	.	.	.
cm	xm	amo	am1	am2	am3	.	amj	.	amn
D	D1	D2	D3	.	Dj	.	Dn

Последняя сторока таблицы - индексная -служит для определения направляющего столбца. Ее элементы Dj определяют по формуле (3.3.21). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки Dи=a0и=0.