2.2 Алгебраїчні перетворення систем лінійних рівнянь

 

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

                                                 (2.3)

Початковий вибір вільних і базисних змінних може бути довільним. Однак структура системи (2.3) така, що в якості базисних змінних зручно прийняти змінні х₃, х₄ і х₅, а в якості вільних – змінні х₁ і х₂. У цьому випадку відразу ж одержуємо деякий вихідний розв’язок системи (2.3):

‑ вільні змінні  х₁ =0, х₂ =0;

‑ базисні змінні  x₃=b₁, x₄=b₂, x₅=b₃;

Кожна базисна змінна входить тільки в одне рівняння системи й має коефіцієнт, який дорівнює одиниці. Тому кількість базисних змінних дорівнює кількості обмежень. Інші змінні вільні.

Запишемо вихідну систему (2.3) у більш докладному вигляді, а базисні змінні й коефіцієнти при них виділимо жирним шрифтом:

                     (2.4)

Припустимо, що вільну змінну х₁ варто перевести в розряд базисних, а базисну змінну х₃ ‑ у розряд вільних. Ця процедура досить проста й неодноразово використовувалася при розв’язку систем лінійних рівнянь у шкільному курсі алгебри.

Суть процедури полягає в наступному: з першого рівняння системи виражається змінна х₁ і підставляється в друге й третє рівняння системи. У результаті такого перетворення вільна змінна х₁ стає базисною, а базисна змінна х₃ стає вільною.

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

 .                          (2.5)

Виразимо із цього рівняння змінну х₁:

Підставляючи значення х₁ у друге й третє рівняння системи (2.4), після нескладних перетворень одержимо разом з рівнянням (2.5) нову перетворену систему рівнянь:

   (2.6)

Коефіцієнти перетвореної системи (2.6) позначимо штрихом і запишемо цю систему в більш простому вигляді:

                     (2.7)

У цій системі вільними будуть змінні х₂ і х₃, а базисними ‑ змінні х₁, х₄ і х₅. Новий розв’язок:

‑  вільні змінні: х₂=0, х₃=0;

‑  базисні змінні: х₁=b'₁, х₄=b'₂, х₅=b'₃.

Змінна х₁ стала базисною, а змінна х₃ ‑ вільною. В системах (2.6) і (2.7) базисні змінні й коефіцієнти при них виділені жирним шрифтом.

Аналіз систем (2.6) і (2.7) дозволяє сформулювати три правила перерахування коефіцієнтів при переміщенні однієї з базисних змінних у розряд вільних, а однієї з вільних змінних у розряд базисних:

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

                                                                         (2.8)

де  ‑ коефіцієнт, що лежить на перетині -го рядка  й j-го стовпця; ‑ нове перераховане значення коефіцієнта ; ‑ розв’язуючий елемент; ‑ коефіцієнт, що лежить на перетині -го рядка й розв’язуючого стовпця; ‑ коефіцієнт, що лежить на перетині розв'язуючого рядка і j-го стовпця.

2. Всі коефіцієнти розв'язуючого рядка діляться на розв'язуючий коефіцієнт . Розв'язуючий коефіцієнт при цьому стає рівним одиниці .

3. Всі коефіцієнти розв'язуючого стовпця, крім розв'язуючого елемента, замінюються нулями. Таким чином, перехід від одного розв’язку до іншого полягає в перерахуванні коефіцієнтів системи рівнянь за правилом 1, 2 і 3, викладеним вище.

При розв’язку реальних оптимізаційних задач зручно користуватися табличною формою запису систем рівнянь. Запишемо вихідну систему (2.4) у вигляді табл. 2.1, виділивши розв'язуючий рядок і стовпець.

Таблиця 2.1

 

Перерахувавши за правилами 1, 2 і 3 коефіцієнти цієї таблиці, одержимо нову таблицю 2.2, що відповідає перетвореній системі (2.7).

 

Таблиця 2.2

 

У таблицях 2.1 і 2.2 базисні змінні і їх коефіцієнти виділені жирним шрифтом.