Алгоритм однократного заміщення Жордана-Гауса

Розглянемо систему лінійних рівнянь з невідомими:

Будь-які m невідомих системи звуться основними (базисними), якщо визначник матриці їхніх коефіцієнтів відрізняється від 0. Тоді інші невідомих звуться неосновними (вільними). Базисним (опорним) розв’язком зветься розв’язок системи, у якому всі вільні невідомі дорівнюють 0. Сумісна система має нескінчену кількість розв’язків, серед них базисних скінчена кількість, що не перебільшує . Розв’язок зветься допустимим, якщо він містить тільки невід’ємні компоненти.

Розглянемо приклад 4.

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

Базисні невідомі завжди можна виразити через вільні. При цьому вільні коефіцієнти у правих частинах рівностей будуть дорівнювати значенням відповідних базисних невідомих у базисному розв’язку. В нашому прикладі виразимо через :

Підкресленням виділені вільні коефіцієнти. Виразивши через , отримаємо

звідки одразу бачимо значення базисних невідомих у відповідному базисному розв’язку.

Для отримання виразу базисних невідомих через вільні необхідно проводити перетворення рівнянь системи – виражати одну невідому через інші з одного рівняння і підставляти в інші рівняння. Цей процес – алгоритм Жордана-Гауса – можна виконувати певною стандартною послідовністю дій, для скорочення запису використовуючи таблицю.

Складемо таблицю для коефіцієнтів виразу базисних невідомих через вільні:



		–2

Відмітимо, що для подальшої зручності вільні невідомі беруться з протилежним знаком (це позначено знаком «–» в заголовку стовпчика). В останньому стовпчику маємо значення базисних невідомих у відповідному базисному розв’язку. Для переходу до іншого набору базисних змінних використовуємо алгоритм Жордана-Гауса:

1. Обираємо в таблиці розв’язуючий елемент, що відрізняється від 0. Він знаходиться на перетині стовпчика, що відповідає новому базисному невідомому, і рядка, що відповідає новому вільному невідомому. Рядок і стовпчик, у яких знаходиться розв’язуючий елемент, теж називаються розв’язуючими.

2. Міняємо місцями заголовки розв’язуючих рядка і стовпчика. Заголовки інших рядків і стовпчиків переписуємо без змін.

3. На місці розв’язуючого елементу записуємо 1.

4. Інші елементи розв’язуючого рядка переписуємо без змін.

5. Інші елементи розв’язуючого стовпчика переписуємо з протилежним знаком.

6. Інші елементи таблиці знаходимо за «правилом прямокутника»: креслимо уявний прямокутник з вершинами у розв’язуючому елементі і тій клітині таблиці, яку треба заповнити; від добутку елементів у вершинах прямокутника на діагоналі з розв’язуючим елементом віднімаємо добуток двох інших кутових елементів.

7. Усі елементи отриманої таблиці ділимо на величину розв’язуючого елементу.

В результаті таких перетворень маємо нову таблицю, що відповідає вибору вільної змінної та базисних змінних , .


	1/2	3/2
	–1/2	–7/2

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Зведення ЗЛП до канонічної форми	\|	Симплексний метод

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.