Линейное неравенство

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

Двумерные линейные неравенства — это выражения вида:

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

где неравенства могут быть строгими или не строгими. Множество решений такого неравенства можно графически представить как полуплоскость (все точки с «одной стороны» от фиксированной прямой) евклидовой плоскости[2]. Прямая, определяющая полуплоскость (ax + by = c) не включается в решение, если неравенство строгое. Простая процедура определения, какая из полуплоскостей является решением — вычисление значения функции ax + by в точке (x₀, 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ⁿ.

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