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

Неравенство, включающее линейную функцию

В математике линейное неравенство — это неравенство , в котором участвует линейная функция . Линейное неравенство содержит один из символов неравенства: ^[1]

• < меньше чем
• > больше чем
• ≤ меньше или равно
• ≥ больше или равно
• ≠ не равно

Линейное неравенство выглядит точно так же, как линейное уравнение , только знак неравенства заменяет знак равенства .

Линейные неравенства действительных чисел

Двумерные линейные неравенства

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

Двумерные линейные неравенства представляют собой выражения с двумя переменными вида:

${\displaystyle ax+by<c{\text{ and }}ax+by\geq c,}$

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

Например, ^[3] для того, чтобы нарисовать множество решений x + 3 y < 9, сначала рисуется линия с уравнением x + 3 y = 9 в виде пунктирной линии, чтобы указать, что линия не входит в множество решений, поскольку неравенство строгое. Затем выбирается удобная точка не на линии, например (0,0). Поскольку 0 + 3(0) = 0 < 9, эта точка находится в множестве решений, поэтому полуплоскость, содержащая эту точку (полуплоскость «ниже» линии), является множеством решений этого линейного неравенства.

Линейные неравенства в общих измерениях

В R ⁿ линейные неравенства — это выражения, которые можно записать в виде

${\displaystyle f({\bar {x}})<b}$или ${\displaystyle f({\bar {x}})\leq b,}$

где f — линейная форма (также называемая линейным функционалом ), а b — постоянное действительное число. ${\displaystyle {\bar {x}}=(x_{1},x_{2},\ldots ,x_{n})}$

Более конкретно это можно записать как

${\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}\leq b.}$

Здесь называются неизвестными, а называются коэффициентами. ${\displaystyle x_{1},x_{2},...,x_{n}}$ ${\displaystyle a_{1},a_{2},...,a_{n}}$

В качестве альтернативы их можно записать как

${\displaystyle g(x)<0\,}$или ${\displaystyle g(x)\leq 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}\leq 0.}$

Обратите внимание, что любое неравенство, содержащее знак «больше» или «больше или равно», можно переписать со знаком «меньше» или «меньше или равно», поэтому нет необходимости определять линейные неравенства с использованием этих знаков.

Системы линейных неравенств

Система линейных неравенств — это набор линейных неравенств относительно одних и тех же переменных:

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&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\leq b,}$

где A — матрица размером m × n , x — вектор-столбец размером n × 1 переменных, а b — вектор-столбец размером m × 1 констант. ^{[ необходима ссылка ]}

В приведенных выше системах могут использоваться как строгие, так и нестрогие неравенства.

• Не все системы линейных неравенств имеют решения.

Переменные можно исключить из систем линейных неравенств, используя метод исключения Фурье–Моцкина . ^[5]

Приложения

Многогранники

Множество решений действительного линейного неравенства образует полупространство n -мерного действительного пространства, одно из двух, определяемых соответствующим линейным уравнением.

Множество решений системы линейных неравенств соответствует пересечению полупространств, определяемых отдельными неравенствами. Это выпуклое множество , поскольку полупространства являются выпуклыми множествами, а пересечение множества выпуклых множеств также выпукло. В невырожденных случаях это выпуклое множество является выпуклым многогранником (возможно, неограниченным, например, полупространством, плитой между двумя параллельными полупространствами или многогранным конусом ). Оно также может быть пустым или выпуклым многогранником меньшей размерности, ограниченным аффинным подпространством n -мерного пространства R ⁿ .

Линейное программирование

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

Обобщение

Приведенное выше определение требует четко определенных операций сложения , умножения и сравнения ; поэтому понятие линейного неравенства может быть распространено на упорядоченные кольца и, в частности, на упорядоченные поля .

Ссылки

1. Миллер и Хирен 1986, стр. 355
2. Технически, чтобы это утверждение было верным, a и b не могут одновременно быть равны нулю. В этой ситуации множество решений либо пусто, либо представляет собой всю плоскость.
3. Энджел и Портер 1989, стр. 310
4. В двумерном случае и линейные формы, и аффинные функции исторически называются линейными функциями, поскольку их графики являются линиями. В других измерениях ни один из типов функций не имеет графика, который является линией, поэтому обобщение линейной функции в двух измерениях на более высокие измерения выполняется с помощью алгебраических свойств, и это приводит к разделению на два типа функций. Однако разница между аффинными функциями и линейными формами заключается лишь в добавлении константы.
5. Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8.
6. Энджел и Портер 1989, стр. 373

Источники

• Энджел, Аллен Р.; Портер, Стюарт Р. (1989), Обзор математики и ее приложений (3-е изд.), Addison-Wesley, ISBN 0-201-13696-1
• Миллер, Чарльз Д.; Хирен, Верн Э. (1986), Математические идеи (5-е изд.), Скотт, Форесман, ISBN 0-673-18276-2

Внешние ссылки

• Khan Academy: Линейные неравенства, бесплатные онлайн-микролекции