Лінійні нерівності
Нехай у рівнянні прямий (4) знак рівності замінений знаком нерівності ³ або £; відповідне безліч точок M(x;y) називаєтьсянапівплощиною.
Наприклад, лінійна нерівністьy³ 2x+ 3 описує напівплощину, що складається
з усіх точокнаабовище(лівіше) прямийy= 2x+ 3 . Аналогічно,x³ 0 – це
нерівність для напівплощини, що складається з точокнаабоправішеосі Oy .
Системи лінійних нерівностей знаходять застосування у так званих завданнях лінійного програмування. Розглянемо конкретний (двовимірний) приклад.
Приклад.Нехай деяка безліч складається з усіх точок на площині, координати яких задовольняють системі лінійних нерівностей (10.а) – (10.д).
Усі точки площини, що задовольняють цій системі нерівностей, називаються планами . Крім того, задана лінійна функціяz= 2x+ 3y, званацільовою функцією. Завдання ставиться так: знайти найбільше значення (максимум) цільової функції на безлічі планів. Також слід вказатиоптимальний планM0 (x0;y0), на якому цільова функція приймає максимум. ( Аналогічно формулюється завданнямінімумцільової функції.)
Рішення задачі графічним методом.Безліч всіх планів складається з точок, що задовольняють відразу всім 5 умовам: ці точки розташовані(a)наабонижчепрямийy-x=2,(б)наабонижчепрямий3 y+x=14,(в)наабовищепрямийy- 3x=-12,(г)наабоправішепрямийx=0,(д)наабовищепрямийy= =0. Звідси випливає, що безліч планів є опуклий 5-кутник OA1A2A3A4. Кожна його вершина знаходиться на перетині пари прямих, що обмежують 5-кутник. Наприклад, на перетині прямихy-x= 2,x= 0 знаходиться вершина A1; на перетині прямихy-x= 2, 3y+x= 14 знаходиться вершина A2. Аналогічно визначаються вершини A3, A4, O.
Безліч точок M(x;y), на яких цільова функція набуває деякого постійного значення, називаєтьсялінією рівнядляz. Всі лінії рівня є паралельними прямими, що задаються рівняннями 2x+3y=c.
Розглянемо одну з цих прямих 2x+ 3y =0 (тутc=0,цільова функціяz
також дорівнює 0). Це пряма LO з кутовим коефіцієнтомk= - 2 / 3. Інші лінії рівня виходять паралельним переміщенням прямої LO. Цей зсув прямий можна робити за допомогою лінійки. При зрушенні лінійки праворуч (або вгору) значенняcцільової функції збільшується. Наприклад, пряма L1 – лінія рівня, що проходить через вершину A1. Лінійку можна зрушувати вправо (або вгору) доти, доки на відповідній лінії рівня знаходяться точки 5-кутника. У результаті досягається крайня точка, яка буде оптимальним планом. Це - вершина 5-кутника, що характеризується тим, що лінія рівня, що проходить через неї, не має спільних точок із начинкою 5-кутника. В даному випадку, як видно з малюнка, ця вершина є A3(5; 3), координати якоїx3 = 5,y3 = 3 знаходяться із системи рівнянь 3y + x= 14,y- 3x= -12. Значення цільової функції цього плану єz= 2x3+3y3=2 × 5 + 3 × 3 = 19.Відповідь:zmax = 19, оптимальний план M0 (5; 3).
Правило перевірки.Існує простий числовий метод, який дозволяє підібрати оптимальний план або проконтролювати правильність підібраного оптимального плану. Розглянемо більш загальну цільову функціюz=a1x+a2y, для якої потрібно знайти максимум . За знаками чиселa1 ,a2 можна вказати ті частини межі багатокутника, де слід шукати оптимальний план.
оптимальний план. Якщоk12³k³k23, то вершина A2 -оптимальний план. Якщоk23?k, то вершина A3 – оптимальний план.
Для першої ситуації «правило перевірки» можна сформулювати так. Нехай
лінія рівня проходить через оптимальний план (одну з вершин верхньої частини кордону). Запишемо кутові коефіцієнти сторін верхньої частини кордону та лінії рівня в тому порядку, як проходяться ці сторони і вершина оптимального плану при обході верхньої частини кордону зліва направо. Якщо отримані числа розташувалися у спадному порядку (загально: у монотонно не зростаючому порядку), то вершина оптимального плану обрана правильно.
2-я ситуація.Нехай коефіцієнт у цільовій функціїa1 > 0 тоді оптимальний план є вершиною на правій частині межі багатокутника планів. У розглянутому прикладі права частина кордону – це ламана лінія A1A2A3, опукла праворуч. Зворотні кутові коефіцієнти сторін ламаної лінії зменшується при обході правої межі знизу нагору. Якщо зворотний кутовий коефіцієнт 1/k= -a2 /a1 такий, що 1/k³ 1/k34, то вершина A4 - оптимальний план. Якщо 1/k34 ³ 1/k³ 1/k23, то A3 - оптимальний план. Якщо 1 /kBC ³ 1/k, то A2 -оптимальний план.