KNOW INTUIT, Лекция, Метод на пълно изключване
1. Метод на пълно изключване
Алгоритъмът на симплексния метод, разгледан по-горе, е неудобен за програмиране и решаване на проблеми на компютър. Необходима е рационализация както във формата на представяне на информацията, така и в метода на организиране на изчисленията, за да стане подходяща за внедряване на компютър. За тази цел е разработена таблична версия на симплексния метод. Основава се на метода на Йордан-Гаус за пълно елиминиране.
Нека е дадена система от линейни алгебрични уравнения
В матрична форма тази система има следния вид:
Матрицата Ap=[A, A0] се нарича разширена матрица. Методът на пълно елиминиране на Джордан-Гаус се състои от краен брой итерации от един и същи тип и се състои в редуциране на матрицата до една форма. Методът се основава на две операции:
- един от редовете на разширената матрица се умножава по фактор, различен от нула;
- един ред, умножен по някакво число, се изважда от всеки ред на разширената матрица.
Всяка от тези елементарни трансформации (наречена трансформация на Гаус) води до нова система от линейни уравнения, която е еквивалентна на оригиналната система.
Първа итерация на метода за пълно елиминиране.
- Измежду елементите на A се избира произволен елемент, различен от нула. Нарича се ръководство за итерация. Редът и колоната, съдържащи водача, се наричат водачи.
- Всички елементи на водещата линия на разширената матрица са разделени на водещ елемент. Резултатът е водеща линия с водещ елемент, равен на единица. След това, от елементите на всеки ред на матрицата A, елементите на новияводещ ред, умножен по елементите, които се намират в пресечната точка на дадения ред и водещата колона.
Означава се матрицата, в която е преобразувана разширената матрица Ap след първата итерация. В него всички елементи на направляващата колона, с изключение на водещия елемент (равен на 1), станаха нула. Наборът от елементи на първите n колони на матрицата Ap , лежащи извън водещия ред и колоната на предишната (предишната) итерация, се нарича основна част на матрицата .
Втората и следващите итерации на метода се извършват подобно на първата и доколкото е възможно да се избере водещ елемент.
Ако след k -тата итерация основната част на матрицата A_p^ не съдържа елементи или съдържа само нули, тогава процесът приключва.
Нека процесът приключи след итерация 1. Да предположим първо, че сред редовете на матрицата A (l) има такива, които не са били водещи в нито една от предишните итерации, например номер на ред i. Тогава е очевидно