Опорні рішення системи лінійних рівнянь

Розглянемо систему з m лінійних рівнянь з n невідомими, причому m

Базисом системи лінійних рівнянь називається максимальна кількість лінійно незалежних векторів системи. Для даної системи це кількість дорівнює m. Скористаємося методом послідовних виключень невідомих і виділимо в системі якийсь вихідний одиничний базис:

В отриманій системі одиничні вектори називаються базисними. а вектора - вільними.

Про п р е д е л е н і е 5.Базіснимі рішеннями називаються рішення системи, одержувані при прирівнювання вільних невідомих нулю.

Про п р е д е л е н і е 6. Базове рішення називається невироджених. якщо всі базисні змінні отриманого рішення ненульові, в іншому випадку базисне рішення називається виродженим.

Очевидно, що базисні рішення простіше знаходити, якщо система приведена до одиничного базису, тому відшукання всіх базисних рішень зводиться до послідовного перетворення системи до всіляких одиничним базисам. Цього можна досягти шляхом послідовних перетворень одноразового заміщення.

Для виконання одного перетворення однократного заміщення потрібно вибрати серед не одиничних стовпців коефіцієнтів відмінний від нуля дозволяє елемент Aqp і провести одне перетворення схеми послідовних виключень. Тоді що дозволяє (p- й) стовпчик коефіцієнтів перетвориться в одиничний, а, навпаки, одиничний стовпець, що має координату 1 в дозвільному q -м рівнянні, стане не поодиноким. Це відповідає переходу в число базисних невідомого xp і, навпаки, виведення з числа базисних невідомого, щодо якого було дозволено q- е рівняння.

При цьому потрібно стежити за тим, щоб в процесі перетворень не повторювався раніше зустрічався базис. Для цього необхідно систематизувати розрахунки.

Важливо також запам'ятати, що якщо r - кількість базисів, які можуть бути виділені з даної системи, то. Причому рівність досягається тільки в тому випадку, якщо жоден з векторів ні при якому з базисів не є вироджених комбінацією.

Про п р е д е л е н і е 7.Опорнимі рішеннями системи називаються ті базисні рішення, які мають всі невід'ємні значення невідомих.

Звичайно, їх можна виділити, якщо знайдені всі базисні рішення, але такий шлях веде до надзвичайно складним розрахунками. Якщо ж вибирати дозволяє елемент з додаткових умов, то ті ж перетворення однократного заміщення забезпечать перехід не просто до базисних, а до опорних рішень. Ці додаткові умови полягають в наступному:

1) дозволяє стовпець (номер p) вибирається так, щоб в ньому виявився хоча б один позитивний елемент Aip> 0;

2) роздільна рядок (номер q) вибирається з умови, щоб відношення було найменшим із значень при Aip> 0.

Після вибору який дозволить елемента подальші обчислення ведуться відповідно до звичайних правил перетворень одноразового заміщення.

Як і при визначенні базисних рішень, тут також необхідно стежити, щоб на будь-якої ітерації не повернуться до раніше знайденому опорного рішення. Ця умова додатково обмежує вибір дозволяє елемента.

П р и м і р 3. За допомогою перетворень одноразового заміщення знайти всі базиси і опорні рішення наступної системи рівнянь:

Р і ш е н і е. Кількість опорних варіантів розв'язання системи лінійних рівнянь.