Метод Гауса-Жордана рішення систем лінійних рівнянь

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

 

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ

 

Лабораторна робота №3

 

Метод Гауса-Жордана рішення систем лінійних рівнянь

 

Виповнив: -----------()

Перевірив: Тижненко О. Г.

 

 

Харків, 2012

 

 
 

Лабораторна робота №3

Метод Гауса – Жордана рішення систем лінійних рівнянь

Мета роботи– практичнезастосування функцій та надбудовExcelдля розв’язання систем лінійних алгебраїчних рівнянь методом Гауса - Жордана.

 

Змістовна постановка задачі та її математична модель

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

Прикладом застосування систем лінійних алгебраїчних рівнянь до розв’язання реальних економічних задач є визначення прогнозних значень виробництва продукції за відомими запасами сировини. Так, наприклад, підприємство виробляє видів продукції, використовуючи сировину типів. Необхідні характеристики виробництва (норми витрат сировини за видами продукції) представлено матрицею , де . Запас сировини задано у вигляді вектору .

Необхідно визначити оптимальний обсяг виробництва продукції кожного виду за умовою використання існуючих запасів сировини.

Така задача є типовою при прогнозуванні та оцінці функціонування підприємств, а також в плануванні мікроекономічних показників їх діяльності.

Позначимо невідомі обсяги виробництва продукції через . Тоді, за умовою повного використання запасів сировини кожного типу, можна записати балансові співвідношення, які створюють систему рівнянь із невідомими: , де – матриця системи, загальний елемент якої - представляє собою витрати одиниць сировини го виду на виробництво однієї одиниці продукції го виду, де (); – стовпчик невідомих; – стовпчик вільнихчленів.

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

Серед відомих методів розв'язку систем лінійних алгебраічних рівнянь слід відзначити метод виключення Гауса та його модифікації, зокрема метод повного виключення Жордана-Гауса. Сутність методу полягає в тому, що за допомогою елементарних перетворювань (перестановка рівнянь, множення рівняння на число, що не дорівнює нулю, додаток рівнянь системи) від початкової системи переходять до системи з трикутною або трапецієвидноюматрицею. Якщо внаслідок перетворень система рівнянь має трикутну матрицю, то вона має єдиний розв'язок. У випадку трапецєвидної матриці - система сумісна, але неозначена. Якщо при виключенні невідомих одержано суперечне рівняння, система несу­місна. Слід відзначити, що дослідження системи проводиться паралельно з виключенням невідомих.

Необхідно зауважити, що елементарні перетворення системи зруч­но проводити за допомогою таблиці (схема Гауса) з одночасним контролюванням обчислень. Для цього вводиться у перетворення ще один стовпчик з контрольними сумами, елементами якого є суми елементів відповідних рядків. Над контрольними сумами у кожному рядку виконуються ті ж операції, що над усіма інши­ми елементами цього рядку. При відсутністі помилок обчислювання елементи стовпчика «Контрольна сума» дорівнюють сумам елементів відповідних перетворе­них рядків.

Завдання

Розв’язати систему лінійних алгребраічних рівнянь за методом Жордана - Гауса в середовищі Excel.

 

Приклад виконання лабораторної роботи № 2

Для демонстрації розв’язання маємо наступну систему рівнянь:

 

 

Наведена система відображає загальну постановку завдання планування обсягів виробництва трьох видів продукції - за умовою використання трьох типів сировини, запаси якої відповідно 240, 220 та 270 одиниць.

Для розв’язання завдання побудуємо таблицю Excel, що відповідає умовам задачі. Заповнюємо вихідні дані (рис. 1.1, рядки 4–6), а далі за методом Жордана-Гаусса здійснюємо ітераційні перетворення, що наведено на рис. 1.1 (рядки 7–15).

 
 

 

Рис. 1.1. Вигляд таблиці розв’язання системи лінійних алгебраічних рівнянь за методом Жордана-Гаусса

В стовпчику «Коментарій» представлено пояснення обчислень, що проводяться у відповідному рядку (в квадратних дужках вводиться номер рядку).

У рядках 13–15 останньої ітерації (в стовпчику b) отримуємо розв’язок завдання – визначені прогнозні обсяги виробництва продукції кожного виду:

.

Наведений приклад вирішений в наступному листі Excel:


Рис. 1. 2 Лист Excel для рішення системи 3-го порядку методом Гауса-Жордана..

 

Наведена задача має єдиний розв’язок. Однак, на практиці досить часто постають питання альтернативних рішень або визначення їх варіантів. Так, не завжди кількість видів продукції дорівнює кількості типів сировини або витрати і запаси одного типу сировини є пропорційними до витрат і запасів іншого типу (тобто система рівнянь може мати кількість невідомих змінних, що перевищує кількість рівнянь). В такому випадку задача або не має розв’язків, або має їх безліч. Тоді, в разі існування безлічі розв’язків необхідно визначити всі опорні розв’язки.

Змінимо умови представленої вище задачі. Запаси сировини та кількість її типів залишається, а додатково потребується виробництво нового виду продукції (в кількості ), що потребує використання існуючих запасів сировини.

Модель зміненої задачі перетворюється у наступну систему рівнянь:

 

 

Отже, кількість рівнянь системи менш ніж кількість невідомих змінних. Позначимо як вільну змінну, тоді – базисні змінні. Застосовуючи метод Жордана-Гаусса отримуємо перший загальний розв’язок задачі (рис. 1.2). У рядках 13–15 останньої ітерації отримуємо загальний розв’язок – обсяги продукції перших трьох видів, що визначені через обсяг виробництва продукції четвертого виду:

 

.

 
 

Рис. 1.2. Вигляд таблиці розв’язання системи лінійних алгебраічних рівнянь за методом Жордана-Гаусса

Якщо вільна змінна , то отримуємо перший опорний розв’язок .

Наступний розв’язок можна побудувати шляхом введення змінної до базису. Оголошуючи змінну вільною та здійснюючи перетворення за методом Жордана-Гаусса, маємо такий загальний розв’язок – обсяги продукції другого, третього та четвертого видів, що визначені через обсяг виробництва продукції першого виду:

 

 
 

(рис. 1.3).

Рис. 1.3. Пошук альтернативного загального розв’язку

 

Якщо вільна змінна , то отримуємо другий опорний розв’язок

 

.

 

Аналогічні міркування (оголошення наступної вільної змінної) приводять до іншого розв’язку. При цьому, слід мати на увазі, що розв’язок є опорним, якщо за умовою відсутності вільної змінної він не містить від’ємних значень (саме такі обмеження існують в реальній економіці).

Отже, пошук опорних рішень передбачає попередній аналіз про доцільність призначення відповідної вільної змінної. Так, на етапі ітерації рядків 16–18 (рис. 1.3) в представленій до розгляду задачі не має сенсу оголошувати змінну вільною. Інакше для цього знадобиться ввести до базису і рядок 17 поділити на від’ємне число (), що приведе до від’ємного значення в стовпчику b, яке надалі стає основною складовою величини .

Аналогічно, на етапі ітерації рядків 13–15 (рис. 1.3) не має сенсу оголошувати змінну вільною. Для цього знадобиться ввести до базису і рядок 15 поділити на від’ємне число (), що приведе до від’ємного значення в стовпчику b, яке надалі стає основною складовою величини .

Таким чином, поставлена задача має два опорних розв’язки – альтернативні варіанти прогнозування обсягів виробництва продукції:

1-ий план виробництва –

 

;

2-ий план – .

 

Остаточний вибір варіанту передбачає додатковий аналіз ринкового попиту та ринкової вартості.

Завдання для самостійної роботи

  1)   2)   3)     4)   …  

Контрольні запитання

1. Моделювання економічних процесів та явищ.

2. Детерміновані та імовірнісні моделі складних систем.

3. Які методи застосовуються для розв’язання систем лінійних рівнянь?

4. Що таке ранг матриці системи лінійних рівнянь? Чи можна визначити ранг матриці системи лінійних рівнянь за методом Жордана-Гаусса?

5. Що означає «розвязковий елемент» та «керований рядок»?

6. Яким чином можна встановити існування єдиного розв’язку задачі?

7. Що визначає відсутність розв’язку?

8. В яких випадках система лінійних рівнянь має безліч рішень?

9. Що таке опорний розв’язок? Як можна його отримати?

10. Пояснити поняття «базисні вектори».