Лінійна нерівність

Графік лінійної нерівності: x + 3y <9

Двовимірні лінійні нерівності — це вирази вигляду:

${\displaystyle ax+by<c}$ і ${\displaystyle ax+by\geqslant c,}$

де нерівності можуть бути строгими або не строгими. Множину розв'язків такої нерівності можна графічно подати як півплощину (всі точки з «одного боку» від фіксованої прямої) евклідової площини[2]. Пряма, що визначає півплощину (ax + by = c) не включається до розв'язку, якщо нерівність строга. Проста процедура визначення, яка з півплощин є розв'язком — обчислення значення функції ax + by у точці (x_0, y₀)_, розташованій поза прямою, і перевірка, чи задовольняє ця точка нерівності.

Наприклад[3], щоб намалювати розв'язок x + 3y <9, спочатку проводимо пряму з рівнянням x + 3y = 9 (пунктирна лінія), щоб показати, що пряма не належить області розв'язків, оскільки нерівність строга. Потім вибираємо зручну точку не на прямій, наприклад, (0,0). Оскільки 0 + 3(0) = 0 <9, то ця точка належить множині розв'язків нерівності і півплощина, що містить цю точку, (півплощина «нижче» прямої) є множиною розв'язків лінійної нерівності.

У просторі Rⁿ лінійні нерівності — це вирази, які можна записати у вигляді

${\displaystyle f({\bar {x}})<b}$ або ${\displaystyle f({\bar {x}})\leqslant b,}$

де f — лінійна форма, ${\displaystyle {\bar {x}}=(x_{1},x_{2},\ldots ,x_{n})}$, А b — стала дійсна величина.

Конкретніше, це можна записати як

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}<b}$

або

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leqslant b.}$

тут ${\displaystyle x_{1},x_{2},...,x_{n}}$ називають невідомими, а ${\displaystyle a_{1},a_{2},...,a_{n}}$ називають коефіцієнтами.

Альтернативно, те саме можна записати як

${\displaystyle g(x)<0\,}$ або ${\displaystyle g(x)\leqslant 0,}$

де g — афінна функція[4]

Тобто

${\displaystyle a_{0}+a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}<0}$

або

${\displaystyle a_{0}+a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leqslant 0.}$

Зауважимо, що будь-яку нерівність, що містить знаки «більше» чи «більше або дорівнює» можна переписати на нерівність зі знаками «менше» чи «менше або дорівнює», так що немає потреби визначати лінійні нерівності з цими знаками.

Система лінійних нерівностей — це набір нерівностей з одними і тими самими змінними:

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leqslant \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leqslant \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leqslant \;&&&b_{m}\\\end{alignedat}}}$

тут ${\displaystyle x_{1},\ x_{2},...,x_{n}}$ — змінні, ${\displaystyle a_{11},\ a_{12},...,\ a_{mn}}$ — коефіцієнти системи, а ${\displaystyle b_{1},\ b_{2},...,b_{m}}$ — сталі члени.

Коротко це можна записати як матричну нерівність

${\displaystyle Ax\leqslant b,}$

де A — матриця m × n, x — n × 1 вектор-стовпець змінних, а b — m × 1 вектор-стовпець констант.

В описаних вище системах можуть використовуватися як строгі, так і нестрогі нерівності.

Не всі системи лінійних нерівностей мають рішення.

Множина розв'язків дійсної нерівності утворює півпростір n-вимірного дійсного простору, один із двох півпросторів, визначених відповідним лінійним рівнянням.

Множина розв'язків системи лінійних нерівностей відповідає перетину півпросторів, визначених окремими нерівностями. Вона є опуклою множиною, оскільки півпростори є опуклими множинами, а перетин множини опуклих множин є також опуклою множиною. В невироджених випадках ця опукла множина є опуклим багатогранником (можливо, необмеженим, наприклад, півпростір, пластина між двома паралельними півпросторами або опуклий конус). Вона може бути також порожньою або опуклим багатогранником меншої розмірності, обмеженим афінним підпростором n-вимірного простору R^n.

Задача лінійного програмування шукає оптимум (найбільше або найменше значення) функції (званої цільовою функцією) за деякого набору обмежень на змінні, які, в загальному випадку, є лінійними нерівностями[5]. Список цих обмежень є системою лінійних нерівностей.