Прикладзнаходження базисних розв’язків системи лінійних рівнянь методом перетворення жорданових таблиць

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

Завдання

1. Розв’язати систему лінійних рівнянь методом перетворень Жордана-Гаусса.

2. Записати загальний та базисний розв’язки задачі.

3. Знайти розв’язок системи лінійних рівнянь матричним методом.

Теоретичні відомості

1. Система лінійних нерівностей обмежень задачі лінійного програмування, зведена до канонічної форми, представляє собою систему лінійних рівнянь, а отже, як система лінійних рівнянь, може бути розв’язана методом Жордана-Гаусса. Суть методу – перетворення записаних у таблицях коефіцієнтів невідомих та вільних членів системи рівнянь. За кожний крок перетворень записують нову таблицю, у якій певне невідоме виключають з усіх рівнянь, крім одного. Кроків перетворень виконують стільки, скільки рівнянь у системі, і таким чином, кожне рівняння матиме свою змінну, яку називають базисною. Інші змінні, які називають вільними, входять в усі рівняння перетвореної системи. Якщо кожне рівняння записати як вираз, що визначає свою базисну змінну, то така система рівнянь буде представляти собою загальний розв’язок задачі. Якщо вільні невідомі, через які у загальному розв’язку виражають базисні змінні, прирівняти до нуля, то матимемо один із базисних розв’язків системи.

Жорданові перетворення являють собою багатокроковий процес, за кожний крок якого базисною невідомою стає одна змінна. Щоб розпочати жорданові перетворення, вибирають рівняння і невідому, яку мають ввести у базис за даний крок перетворень. Коефіцієнт цієї невідомої називають розрахунковим елементом. Суть одного кроку перетворень полягає у такому:

· елементи (коефіцієнти та вільний член рівняння) рядка, що належить розрахунковому елементу, перетворюються простим діленням на розрахунковий елемент:

a_il*=a_il/a_ij;

· усі інші елементи жорданової таблиці перетворюють за формулою:

або ,

де a_kl – елемент, що підлягає перетворенню, a_ij– елемент, щодо якого виконують перетворення (розрахунковий елемент), a_ila_kj– відповідні елементи таблиці, які використовують для перетворень, – нове значення перетвореного елемента;

· кроків перетворень стільки, скільки невідомих можна ввести у базис, тобто скільки незалежних лінійних рівнянь входить у систему.

2. Ту саму задачу можна розв’язати іншим методом, а саме матричним. Сутність матричного методу розв’язку системи лінійних рівнянь пов’язана з двома процедурами:

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

· друга процедура – знаходження добутку матриці-оператора на початкову розширену матрицю системи рівнянь. Отримана матриця представляє собою загальний розв’язок системи лінійних рівнянь. Коефіцієнти базисних змінних у цій прямокутній матриці утворюють одиничну матрицю.

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

Зміст завдань

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

1. Розв’язати систему рівнянь методом жорданових перетворень. Для цього:

· звести систему нерівностей до канонічного виду та записати відповідну еквівалентну систему лінійних рівнянь;

· шляхом жорданових перетворень, зробивши два кроки перетворень таблиці, ввести у базис основні невідомі задачі х₁ та х₂;

· розглянути отриманий базисний розв’язок задачі і, в разі наявності від’ємних значень будь-якої змінної, проводити введення у базисі інших із неосновних змінних доти, поки не отримаємо опорного розв’язку задачі (додатного базисного розв’язку);

· записати загальний та базисний розв’язок системи рівнянь.

2. Розв’язати систему лінійних рівнянь матричним методом. Для цього:

· вибрати невідомі, які бажано мати за базисні у кінцевому розв’язку задачі. (Для цієї практичної роботи за базисні спочатку краще вибрати невідомі опорного розв’язку задачі, отриманого у методі Йордана-Гауса);

· записати матрицю D коефіцієнтів вибраних невідомих такою, якою вона записана у початковій формі лінійних рівнянь першої жорданової таблиці;

· обчислити матрицю D^-1, обернену до матриці D;

· записати розширену матрицю А коефіцієнтів невідомих та вільних членів системи рівнянь. Помножити зліва матрицю D^-1 на матрицю
А (D^-1×А=А*);

· вислідна матриця А* буде являтиме собою такий самий розв’язок задачі, як і в попередньому методі.

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

· Взяти з попередньої практичної роботи результати обчислень координати вершин багатокутника розв’язків;

· замінюючи у матриці D стовпчики коефіцієнтів для різних можливих комбінацій неосновних змінних (х₃; х₄; х₅; х₆), отримати відповідні різні варіанти оберненої матриці D^-1. Записати їх;

· помноживши зліва відповідні варіанти матриці D^-1 на розширену матрицю задачі А, отримати та записати різні варіанти базисних розв’язків задачі;

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

Прикладзнаходження базисних розв’язків системи лінійних рівнянь методом перетворення жорданових таблиць

Маємо систему нерівностей обмежень (приклад 1, попередньої роботи):

Зведемо систему обмежень до канонічного виду та запишемо еквівалентну системі нерівностей задачі систему рівнянь:

Скориставшись програмою Microsoft Excel, запишемо першу таблицю для цих обмежень та виконаємо два кроки жорданових перетворень. При цьому введемо у базис х₁ та х₂.

Виберемо за розрахунковий елемент коефіцієнт при х₁, виконаємо щодо нього перетворення першої таблиці та запишемо результат цих перетворень у другу таблицю. Для цього у клітинку «В7» (перший стовпець, перший рядок) другої таблиці запишемо формулу: «=B3/$B$3» та скопіюємо її на всі клітинки цього рядка. Далі візьмемо будь-яку клітинку іншого стовпця та іншого рядка другої таблиці, наприклад, «С8» та запишемо у ній формулу: «C4-C$3*$B4/$B$3».Скопіюємо цю формулу на всі інші клітинки другої таблиці та отримаємо результат обчислень чисел цієї таблиці.

Виконавши аналогічні перетворення щодо розрахункового елемента – коефіцієнта при х₂, клітинка «С8», яку знайдемо у другому рядку другому стовпці другої таблиці, отримаємо значення елементів третьої таблиці.

Фрагмент сторінки Microsoft Excel, що відповідає наведеному прикладу, наведено на рисунку 2.1.

Рис. 2.1. Фрагмент сторінки Microsoft Excel, що відповідає наведеному прикладу

В останній третій таблиці читаємо результат: Х (–5; 6; 0; 0; –12; 19). Цей результат відображає базисний розв’язок задачі, але він не є опорним, бо дві з чотирьох базисних змінних – від’ємні, це змінні х₁ = –5 та х₃= –12. Тому виконуємо ще один крок жорданових перетворень, взявши за розрахунковий елемент коефіцієнт при х₃ «1,400», який знайдемо у третьому рядку третього стовпця третьої таблиці (клітинка «D13»).

Таблиця 2.1

Як бачимо, у четвертій таблиці після третього кроку перетворень маємо опорний розв’язок системи лінійних рівнянь: Х(3,571; 2,571; 8,571; 0; 0; 3,571).

Можемо записати загальний розв’язок системи рівнянь:

Базисний розв’язок отримаємо, коли приймемо, що х₄=х₅=0, тоді маємо:

Основні невідомі, серед них х₁ та х₂.