Реферат: Симлекс-метод

4. Вычисляем новый ДБР.

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

x1*=200; x2*=300.

Метод полного исключения

Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана - Гаусса.

Пусть задана система линейных алгебраических уравнений

j=1, 2, ., m.

В матричной форме данная система имеет следующий вид:

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), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.