Лекція 10 Тема: Принцип граничних розв’язків системи лінійних нерівностей План:

1. Означення граничного розв’язку системи лінійних нерівностей.

2. Вузлові розв’язки системи. Крайні підсистеми системи лінійних нерівностей.

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

4. Вершини многогранника розв’язків.

5. Алгоритм знаходження мінімальних граней многогранника.

Короткий зміст лекції.

Нехай задана система лінійних нерівностей:

(1)

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

Граничний розв’язок системи (1) рангу r>0 називається крайнім розв’язком системи (1), якщо він перетворює в рівність r її нерівностей з лінійно незалежними формами .

Підсистема системи (1) рангу k з k нерівностей називається крайньою підсистемою системи (1), якщо існує такий розв’язок системи (1), який перетворює в рівність всі нерівності цієї підсистеми.

Крайня підсистема, кількість нерівностей якої співпадає з рангом системи (1), називається вузловою.

Будь-яка сумісна система (1) рангу r>0 має хоч би один граничний розв’язок.

Будь-яка сумісна система (1) рангу r>0 має хоч би одну крайню підсистему.

Будь-яка сумісна система (1) рангу r>0 має хоч би одну вузлову підсистему, отже, має хоча би один граничний розв’язок.

Якщо сумісна система (1) має ранг r>0, то серед її нерівностей можна виділити r таких нерівностей з лінійно незалежними формами, що всі граничні розв’язки для відхиленої системи нерівностей задовольняють системі (1).

Множина тих розв’язків системи (1) рангу r>0, які перетворюють в рівність деякі її r нерівностей з лінійно незалежними формами, називається мінімальною гранню многогранника системи (1).

Многогранник розв’язків сумісної системи лінійних нерівностей рангу r>0 має хоча би одну мінімальну грань.

Вершиною многогранника М розв’язків сумісної системи (1) називається такий її розв’язок, який не міститься в якості внутрішнього елемента в жодному відрізку многогранника М.

Мінімальні грані многогранника М розв’язків сумісної системи (1) рангу r = n, і тільки вони, є його вершинами.

Якщо сумісна система (1) має ранг r = n, то многогранник розв’язків має хоча би одну вершину.

Алгоритм знаходження мінімальних граней многогранника:

1. Визначаємо ранг системи (1), нехай він дорівнює r>0.

2. Виписуємо з системи (1) рангу r>0 всі лінійно незалежні підсистеми лінійних нерівностей рангу r і замінюємо їх системами рівнянь, змінивши знак нерівності на знак рівності.

3. Розв’язуємо одержані системи лінійних рівнянь рангу r.

4. Розв’язки системи лінійних рівнянь, які задовольняють системі лінійних нерівностей (1) є мінімальними гранями многогранника розв’язків системи (1).

Проілюструємо на прикладі основні положення лекції.

1. Для сумісної системи лінійних нерівностей знайти граничні розв’язки, вузловий розв’язок, мінімальні грані.

Розв’язання.

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

Наприклад, точка перетворює першу нерівність системи в рівність.

Вершини многогранника є вузловими розв’язками, оскільки розв’язки (1,0,0), (0,1,0), (0,0,1), (0,0,0) перетворюють в рівність підсистеми:

а) б)

в) г)

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

Ранг r системи дорівнює 3, кількість невідомих n = 3, отже, r = n.

Виписуємо всі підсистеми рангу 3:

а) б)

в) г)

Всі ці підсистеми мають по одному розв’язку (r = n = 3), а саме (1,0,0), (0,1,0), (0,0,1), (0,0,0).

Ці розв’язки є розв’язками заданої системи нерівностей, а тому є вершинами многогранника розв’язків.

Контрольні питання для самоперевірки:

1. Дайте означення граничного розв’язку системи лінійних нерівностей.

2. Який граничний розв’язок називається вузловим?

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

4. Яка крайня підсистема називається вузловою?

5. Дайте означення мінімальної грані многогранника розв’язків.

6. Що називається вершиною многогранника розв’язків?

7. В якому випадку многогранник розв’язків системи лінійних нерівностей має хоча б одну вершину?

8. Як знайти граничний розв’язок системи лінійних нерівностей?

9. Як знайти вузловий розв’язок?

10. Наведіть алгоритм знаходження мінімальних граней.

11. Для наступних сумісних нерівностей знайти:

а) будь-який граничний розв’язок;

б) будь-який вузловий розв’язок;

в) мінімальні грані многогранника розв’язків;

г) побудувати многогранника розв’язків:

1) 2)

3) 4)

Література:

1. С.Г.Колесник, В. В.Цыбуленко. Алгебра и теория чисел, ч. І. – Х., ХГПУ, 1998. – Гл. V, §1,4.