WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Линейное неравенство — это неравенство, вовлекающее линейные функции. Линейное неравенство содержит одно из символов неравенства[1]

  • < — меньше
  • > — больше
  •  — меньше либо равно
  •  — больше либо равно
  •  — не равно

а также (формально)

  • = — равно

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

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

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

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

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

и

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

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

Линейные неравенства в пространствах более высокой размерности

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

или

где f — линейная форма, , а b — постоянная вещественная величина.

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

или

Здесь называются неизвестными, а называются коэффициентами.

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

или

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

То есть

или

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

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

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

Здесь  — переменные,  — коэффициенты системы, а  — константные члены.

Кратко это можно записать как матричное неравенство

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

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

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

Приложения

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

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

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

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

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

Обобщение

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

Примечания

  1. Miller, Heeren, 1986, с. 355.
  2. Технически, такое утверждение корректно, когда a и b одновременно нулю не равны. В случае равенства нулю решением является пустое множество, либо вся плоскость.
  3. Angel, Porter, 1989, с. 310.
  4. В случае 2-мерного пространства как линейная форма, так и аффинная функция исторически называются линейными функциями поскольку их графики — прямые линии. В других размерностях ни одна из этих функций не имеет прямую в качестве графика, так что обобщение линейной функции в более высокие размерности делается в смысле алгебраических свойств и это приводит к разделению на два вида функций. Однако, разница в этих функциях — просто добавленная константа.
  5. Angel, Porter, 1989, с. 373.

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии