Системи лінійних нерівностей
Задача знаходження розв'язку системи лінійних нерівностей відіграє важливу роль у розв'язуванні багатьох задач математичного програмування, а не лише лінійного. Ця задача має і самостійний інтерес.
Розглянемо спочатку такий приклад. Нехай дано систему нерівностей:
(2)
Геометрично кожну нерівність системи (2) можна тлумачити як деяку півплощину, обмежену прямою, рівняння якої можна дістати з відповідної нерівності, змінивши знак нерівності знаком рівності. Через di(x1, x2) (і =1, 2, ..., 6) позначено відхилення довільної точки з координатами x1, x2 від відповідної прямої. Так, відхилення точки з координатами х1=3, х2 = 8 від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 становить d1(3, 8) = -1*3 - 1*8 + 11 = 0, тобто точка (3; 8) лежить на цій прямій; аналогічно знаходимо відхилення точки (3; 8) від прямої d2(x1, x2), яке становить -3; від прямої d3(x1, x2) становить 15 і т.д.
У точці з координатами (x1; x2) нерівність, наприклад, d1(x1, x2) = -1х1 - 1х2 + 11 = 0, виконується, якщо відхилення такої точки від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 невід'ємне.
Рис.6.
На Рис. 6 зображено множину точок W (її заштриховано), у кожній точці якої винонуються всі нерівності системи (2). Отже, множина W є множиною розв'язків системи нерівностей (2). Якщо точка х належить множині W розв'язків системи нерівностей (2), то відхилення цієї точки від усіх прямих, які обмежують множину W, будуть невід'ємними. А якщо точка не належить W, то принаймі одна з нерівностей не справджуватиметься і координати цієї точки не задовольнятимуть систему нерівностей, які визначають множину W. Очевидно, W є опуклим многокутником.
Отже, якщо всі відхилення деякої точки від прямих, що обмежують множину W, невід'ємні, то набір координат такої точки є одним із розв'язків даної системи нерівностей. Такий розв'язок називатимемо допустимим. Точку, що відповідає допустимому розв'язку, називатимемо допустимою.
Як бачимо, у двовимірному просторі задачу можна розв'язати графічним способом, побудувавши множину розв'язків для кожної нерівності і взявши переріз таких множин. Якщо цим перерізом є порожня множина, то система нерівностей несумісна.
Зауважимо, що в n-вимірному (навіть в тривимірному) просторі графічно розв'язати довільну систему нерівностей вже неможливо. Проте за допомогою жорданових виключень досить легко розв'язати таку задачу.
Нехай задано систему лінійних нерівностей
di(x) * (ai, x) + bi = 0 (i =1, 2, ..., m), (3)
де x = (x1; x2; ...; xn) ( Rn, ai = (ai1; ai2; ...; ain) ( Rn, bi - дійсні числа.
Розв'язком системи неріностей (3) називається будь-яка точка x ( Rn, яка задовольняє всі нерівності (3). У геометричному тлумаченні розв'язком системи (3) є будь-яка точка x( Rn , що має невід'ємні відхилення від усіх m площин di(x) = 0.
Припустимо спочатку, що ранг матриці кеофіцієнтів системи (3) дорівнює n.
Запишемо систему (3) у вигляді таблиці.
Таблиця 1

x1
x2
...
xn
1

d1
a11
a12
...
a1n
b1

d2
a21
a22
...
a2n
b2

...
...
...
...
...
...

dm
am1
am2
...
amn
bm


Очевидно, що коли всі bi = 0, то x=(0; 0; ...; 0) є розв'язком системи нерівностей. Припустимо, що серед чисел bi є від'ємні. Нехай, наприклад, b1 < 0. За допомогою кроку жорданового виключення замість якоїсь із змінних xj введемо до числа незалажних змінну d1. Нехай після кроку жорданового виключення дістанемо таблицю
Таблиця 2
d1
x2
...
xn
1

x1


...



d2


...



...
...
...
...
...
...

dm


...




Якщо серед чисел b(1)i немає від'ємних, то, поклавши d1 = 0, x2 = 0, ..., xn = 0, дістанемо: x1 = b(1)1, d2 = b(1)2, ..., dm = b(1)m. Точка x = (b(1)1; 0; ...; 0), очевидно, буде розв'язком системи (3), бо в цій точці d1 = 0, d2 = 0, ..., dm = 0. Нехай серед чисел b(1)i є від'ємні, наприклад, b(1)2 < 0. Тоді замість якоїсь з решти зміних xj вводимо змінну d2. Якщо таким чином вдається виключити всі змінні xj, то через n кроків жорданових виключень дістанемо таблицю.
Таблиця 3
d1
d2
...
dn
1

x1


...



...
...
...
...
...
...

xn


...



dn+1


...



...
...
...
...
...
...

dm


...




Поклавши d1 = 0, d2 = 0, ..., dn = 0, дістанемо: x1= b(n)1; x2 = b(n)2; ...; xn = b(n)n; xn+1 = b(n)n+1 ; ...; xm = b(n)m.
Вирази для змінниx xi надалі з розрахункових таблиць можна вилучити. Визначивши потрібні значення змінних d1, d2, ..., dn, можна легко знайти відповідні значення змінних x1, x2, ..., хn за таблицею 3.
Якщо серед чисел b(n)n+1, ..., b(n)m немає від'ємних, то точка x = (b(n)1; b(n)2; ...; b(n)n) є розв'язком системи нерівностей (3). Ця точка належить до площин d1(х) = 0, d2(х)= 0 ,..., dn(х) = 0, оскільки має нульові відхилення від цих площин. Від площин dn+1(х) = 0, ..., dm(х) = 0 точка x = (b(n)1; b(n)2; ...; b(n)n) має відповідно невід'ємні відхилення b(n)n+1 = 0, ..., b(n)m = 0. Нехай серед вільних членів b(n)n+1, ..., b(n)m є від'ємні, наприклад, b(n)n+1 < 0. Серед коефіцієнтів d-рядка з від'ємним вільним членом знайдемо додатній. Якщо додатніх коефіцієнтів в d-рядку з від'ємним вільним членом немає, то система нерівності (3) несумісна, а тому і вся система (3) не має розв'язку.
На Рис. 7 показано сумісні системи нерівностей для двовимірного (Рис. 7, в) та тривимірного (Рис. 7, г) випадків і несумісні системи для двовимірного (Рис. 7, а) та тривимірного (Рис. 7, б) випадку.

Рис. 7.
Нехай серед коефіцієнтів d-рядка з від'ємним вільним членом є додатні, наприклад b(n)n+1 < 0, a(n)n+1,1 > 0. Тоді, збільшуючи відхилення d1(x), тобто віддаляючись від площини d1(x) = 0 в напрямі збільшення d1(x), збільшуватимемо і від'ємне відхилення dn+1(x) за умови, що при цьому відбуватиметься рух по ребру d2(x) = 0, ..., dn(x) = 0 у напрямі збільшення d1(x) i dn+1(x). По ребру d2(x) = 0, ..., dn(x) = 0 рухатимeмось у вказаному напрямі до найпершої із площин dn+1(x) = 0, dn+2(x) = 0, ..., dm(x) = 0. Якщо d2(x) = 0, ..., dn(x) = 0, точка х досягне площини dn+1(x) = 0 за умови, що dn+1(x) = a(n)n+1,1 * d1(x) + b(n)n+1 = 0, тобто коли d1(x) набуде значення - b(n)n+1 / a(n)n+1,1 , очевидно, додатнього.
Площини dm(x) = 0 точка x, рухаючись по ребру d2(x) = 0, ..., dm(x) = 0, досягне при умові dm(x) = a(n)m1 * d1(x) + b(n)m = 0, тобто при d1(x) = - b(n)m / a(n)m1. Зауважимо, що коли відношення b(n)i / a(n)i1 > 0 для деякого i ( {n+1, ..., m}, то площини di(x) = 0 із збільшенням d1(x) досягти неможливо. Справді, якщо b(n)i > 0 і a(n)i1 > 0, то із збільшенням d1(x) значення di(x) = a(n)i1 d1(x) + b(n)i збільшується, тобто із збільшенням d1(x) відповідна точка х не наближатиметься до площини di(x) = 0, а, навпаки, віддалятиметься. А коли b(n)i < 0 і a(n)i1 < 0, то із збільшенням d1(x) значення di(x) = a(n)i1 d1(x) + b(n)i лише зменшується (від'ємне й збільшується за модулем), відповідна точка x знову віддалятиметься від площини d1(x) = 0.
Отже, рухаючись по ребру d2(x) = 0, ..., dn(x) = 0 в напрямі збільшення d1(x), точка x може досягти лише тих площин dі(x) = 0 (і=n+1, ..., m), для яких b(n)i / a(n)i1 < 0. При цьому d1(x) набуватиме значень відповідно d1(x) = - b(n)i / a(n)i1 > 0. Першрю серед площин dn+1(x) = 0, ..., dm(x) = 0, очевидно, буде досягнуто ту площину, для якої відношення b(n)i / a(n)i1 за модулем буде найменше. Нехай таке найменше відношення досягнеться при i = n+1. Тоді дістанемо dn+1(x) = 0, d1(x) = - b(n)n+1 / a(n)n+1,1. Виключемо змінну d1 із незалежних, ввівши замість неї змінну dn+1. Після кроку жорданового виключення матимемо таблицю:
Таблиця 4
d1
d2
...
dn
1

x1


...



...
...
...
...
...
...

xn


...



d1


...



dn+1


...



...
...
...
...
...
...

dm


...




Точка x = (b(n+1)1; b(n+1)2; ...; b(n+1)n) тепер уже належить площинам dn+1(x) = 0, d2(x) = 0, d3(x) = 0, ..., dn(x) = 0. Точку x ( Rn, яка належить деяким n площинам di1(x) = 0, ..., din(x) = 0, i,j ( {1, 2, ..., m}, називатимемо вершиною. Площини di(x) = 0, яким належить вершина, називатимемо базовими. Вершину, яка є розв'язком системи (3), називатимемо допустимою.
Переходячи за допомогою жорданових виключень від однієї вершини до іншої, за скінченну кількість кроків знайдемо допустиму вершину або з'ясуємо, що система (3) несумісна.
Отже, можна сформулювати правила знаходження допустимої вершини системи нерівностей (3):
1. Виключаємо всі змінні xj (j = 1, 2, ..., n) з незалежних.
2. Якщо всі вільні члени d-рядків невід'ємні, то точка х, що належить базовим площинам di(x) = 0, допустима.
3. Якщо серед вільних членів d-рядків є від'ємні і є d-рядок з від'ємним вільним членом, де всі коефіцієнти недодатні, то система нерівностей (3) несумісна.
4. Якщо в кожному d-рядку з від'ємним вільним членом є принаймні один додатний коефіцієнт, то, вибравши будь-який з таких коефіцієнтів, візьмемо стовпчик, в якому міститься цей коефіцієнт, за основний.
5. Знайдемо від'ємні відношення вільних членів, d-рядків до відповідних коефіцієнтів основного стовпчика. Рядок, на який припадає найменше за модулем відношення, візьмемо за основний.
6. З визначеним таким чином основним елементом виконаємо крок жорданового виключення. Діставши нову таблицю, знову повернемось до правила 2.
Слід зазначити, що коли є стовпчик, всі елементи d-рядків у якому додатні, відповідну незалежну змінну d можна необмежено збільшувати, в результаті чого зрештою всі залежні змінні d стануть додатними. Множина розв'язків у цьому випадку виявляється необмеженою.
Зауваження. Коли найменше відношення, визначене в п. 5, дорівнює нулю, то ми не виходимо з попередньої точки х, оскільки крок вздовж відповідного ребра буде нульовим. При цьому змінюється лише набір базових площин. У такому разі можливе так зване зациклювання, коли через певну кількість кроків повторюватимуться ті самі таблиці. Є спеціальні засоби, щоб подолати зациклювання, на яких ми тут не зупиняємося.
У наведених щойно міркуваннях ми припускали, що ранг матриці (aij) {і = 1, 2, ..., n; j = 1, 2, ..., m) дорівнює n. Якщо ранг цієї матриці менший за n, то виключити всі xj (j = 1, 2, ..., n) з незалежних не вдається.
Нехай ранг матриці (aij) (і = 1, … ,m; j = 1, …, n) дорівнює s (s < n), тоді через s кроків жорданових виключень дістанемо таблицю 5.
Таблиця 5
d1
...
ds
xs+1
...
xn
1

x1

...


...



...
...
...
...
...
...
...
...

xs

...


...



ds+1

...

0
...
0


...
...
...
...
...
...
...
...

dm

...

0
...
0



Змінним xj (j = s+1, ..., n), що залишається серед незалежних, можна надавати довільних значень. Якщо при цьому незалежні змінні di (i = 1, … , s) покласти рівними нулю, то всі залежні змінні di (i = s+1, ..., m) не змінюватимуться при зміні незалежних змінних xj (j = s+1, ..., n). Змінюватимуться лише залежні змінні x1, ..., xs. При цьому відбуватиметься рух по (n-s)-вимірному "ребру", тобто по множині точок, що належать одночасно площинам d1(х) = 0, ..., ds(x) = 0. Площини ds+1(x) = 0, ..., dm(x) = 0 виявляються паралельними такому "ребру".
Правила розв'язування системи (3) при цьому залишаться назмінними. Геометричне тлумачення таке саме з тією лише відмінністю, що тепер зручно перейти до s-вимірного підпростору Rn, оскільки в усіх перерізах, ортогональних до згаданого s-вимірного підпростору, картина залишається однаковою. Отже, фактично задача лише спрощується.
Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Шукана область (простір) розв’язків задачі прикладу 1.1. показана на рис. 2.1. Умови невід’ємності змінних обмежують область їх допустимих значень першим квадрантом координатної площини (частина площини над віссю x1 і справа від осі x2). Інші межі простору розв’язків зображені прямими лініями, побудованими по рівняннях, що отримані заміною знака “?” знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності ( в нашому випадку - нерівності із знаком “?”), указуються стрілками, спрямованими вбік допустимих значень змінних. Отриманий простір розв’язків задачі - багатокутник АВСDЕF (рис. 2.1). У кожній точці, що належить внутрішній області або межам багатокутника розв’язків АВСDЕF, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед нескінечного числа таких точок можна знайти точку оптимальнного розв’язку, якщо з'ясувати, в якому напрямку зростає цільова функція.  

 
Рис. 2.1. Простір допустимих розв’язків задачі “про фарби”.
На рис. 2.2   показано, як здійснюється така операція. 
 

 
Рис. 2.2. Знаходження оптимального розв’язку ЗЛП графічним методом.
На графік наносять лінію рівня цільової функції c1*x1+c2*x2=z0, де z0 - довільне значення z. Будують вектор N (c1, c2), що є нормальним до ліній рівня цільової функції й визначає напрямок оптимізації z. Лінію рівня зрушують паралельно самій собі вздовж вектора N доти, поки вона не вийде за межі області допустимих розв’язків. Остання точка цієї області й буде точкою оптимуму. 
Індивідуальне завдання
(для визначення числових значень коефіцієнтів використовується N – порядковий номер студента в групі)
Розглянемо діяльність деякого виробничого об’єкта. Нехай у його розпорядженні є 5 типів сировинних ресурсів у розмірі bj =N+j*5 (bj – число одиниць ресурсу j = 1, …, 5). З цих ресурсів виробничий об’єкт виготовляє k видів продукції у ціні ci=(-1)N*(N+i) за одиницю, і = 1, …, k. Задано матрицю A з елементами aij - число одиниць ресурсу j необхідних для виготовлення однієї одиниці продукції і, aij = N*2+(-1)i(i*j). Визначити оптимальний план виробництва. Число k будується з номера групи так: якщо номер групи n=10l + m , то k =l - m.