Системы линейных неравенств и выпуклые множества точек
Понятие системы линейных неравенств
Неравенство - это два числа или математических выражения, соединённых одним из знаков: > (больше, в случае строгих неравенств), < (меньше, в случае строгих неравенств), ≥ (больше или равно, в случае нестрогих неравенств), ≤ (меньше или равно, в случае нестрогих неравенств).
Неравенство является линейным при тех же условиях, что и уравнение: оно содержит переменные только в первой степени и не содержит произведений переменных.
Решение линейных неравенств и систем линейных неравенств неразрывно связано с их геометрическим смыслом: решением линейного неравенства является некоторая полуплоскость, на которые всю плоскость делит прямая, уравнением которой задано линейное неравенство. Эту полуплоскость, а в случае системы линейных неравенств - часть плоскости, ограниченную несколькими прямыми, требуется найти на чертеже.
К решению систем линейных неравенств с большим числом переменных сводятся многие экономические задачи, в частности, задачи линейного программирования, в которых требуется найти максимум или минимум функции.
Решение систем линейных неравенств с любым числом неизвестных
Сначала разберём линейные неравенства на плоскости. Рассмотрим одно
неравенство с двумя переменными 
и
:
,
где 
-
коэффициенты при переменных (некоторые числа),
- свободный
член (также некоторое число).
Одно неравенство с двумя неизвестными, так же как и уравнение, имеет
бесчисленное множество решений. Решением данного неравенства назовём пару чисел
,
удовлетворяющих этому неравенству. Геометрически множество решений неравенства изображается
в виде полуплоскости, ограниченной прямой
,
которую назовём граничной прямой.
Шаг 1. Построить прямую, ограничивающую множество решений линейного неравенства
Для этого надо знать какие-либо две точки этой прямой. Найдём точки пересечения с осями координат. Ордината точки пересечения A равна нулю (рисунок 1). Числовые значения на осях на этом рисунке относятся к примеру 1, который разберём сразу после этого теретического экскурса.
Абсциссу найдём, решая как систему уравнение прямой с уравнением оси 
.
Найдём пересечение с осью :
Подставляя значение 
в первое уравнение, получаем
,
откуда 
.
Таким образом, нашли абсциссу точки A 
.
Найдём координаты точки пересечения с осью 
.
Абсцисса точки B равна нулю. Решим уравнение граничной прямой с уравнением оси координат:
Решение:
,
следовательно, координаты точки B: 
.
Шаг 2. Начертить прямую, ограничивающую множество решений неравенства. Зная точки A и B пересечения граничной прямой с осями координат, можем начертить эту прямую. Прямая (снова рисунок 1) делит всю плоскость на две части, лежащие справа и слева (выше и ниже) от этой прямой.
Шаг 3. Установить, которая из полуплоскостей является решением данного неравенства. Для этого нужно в это неравенство подставить начало координат (0; 0). Если координаты начала удовлетворяют неравенству, то решением неравенства является полуплоскость, в которой находится начало координат. Если же координаты не удовлетворяют неравенству, то решением неравенства является полуплоскость, которая не содержит начала координат. Полуплоскость решения неравенства будем обозначать штрихами от прямой внутрь полуплоскости, как на рисунке 1.
Если решаем систему линейных неравенств, то каждый шаг выполняется для каждого из неравенств системы.
Пример 1. Решить неравенство
Решение. Начертим прямую
Подставив в уравнение прямой 
,
получим 
, а
подставив 
,
получим 
.
Следовательно, координаты точек пересечения с осями будут A(3; 0),
B(0; 2). Через эти точки проведём прямую (опять рисунок 1).
Выберем полуплоскость решений неравенства. Для этого в неравенство подставим координаты начала (0; 0):
,
получим 
,
т. е. координаты начала удовлетворяют данному неравенству. Следовательно, решением неравенства
является полуплоскость, содержащая в себе начало координат, т. е. левая (она же нижняя) полуплоскость.
Если бы данное неравенство было строгим, то есть имело бы вид
,
то точки граничной прямой не являлись бы решением, так как они не удовлетворяют неравенству.
Теперь рассмотрим систему линейных неравенств с двумя неизвестными:
Каждое из неравенств этой системы на плоскости определяет полуплоскость.
Система линейных неравенств называется совместной, если она имеет хотя бы одно решение, и
несовместной, если она не имеет решений. Решением системы линейных неравенств называется
любая пара чисел (),
удовлетворяющая всем неравенствам данной системы.
Геометрически решением системы линейных неравенств является множество точек, удовлетворяющих всем неравенствам системы, то есть, общая часть получаемых полуплоскостей. Поэтому геометрически в общем случае решение может быть изображено в виде некоторого многоугольника, в частном случае - может быть линия, отрезок и даже точка. Если система линейных неравенств несовместна, то на плоскости не существует ни одной точки, удовлетворяющей всем неравенствам системы.
Пример 2. Решить систему линейных неравенств
Решение. Итак, требуется найти многоугольник решений этой системы неравенств.
Построим граничную прямую для первого неравенства, то есть прямую 
,
и граничную прямую для второго неравенства, то есть прямую 
.
Делаем это пошагово, как было показано в теоретической справке и в примере 1, тем более, что в примере 1 строили граничную прямую для неравенства, которое является первым в данной системе.
Полуплоскости решений, соответствующие неравенствам данной системы, на рисунке 2 заштрихованы вовнутрь. Общая часть полуплоскостей решений представляет собой открытый угол ABC. Это означает, что множество точек плоскости, составляющих открытый угол ABC, является решением как первого, так и второго неравенства системы, то есть, является решением системы двух линейных неравенств. Иначе говоря, кординаты любой точки из этого множества удовлетворяют обоим неравенствам системы.
Пример 3. Решить систему линейных неравенств
Решение. Построим граничные прямые, соответствующие неравенствам системы. Делаем это, выполняя шаги, данные в теоретической справке, для каждого неравенства. Теперь определим полуплоскости решений для каждого неравенства (рисунок 3).
Полуплоскости решений, соответствующие неравенствам данной системы, заштрихованы вовнутрь. Пересечение полуплоскостей решений изображается, как показано на рисунке, в виде четырёхугольника ABCE. Получили, что многоугольник решений системы линейных неравенств с двумя переменными является четырёхугольником ABCE.
Всё описанное выше о системах линейных неравенств с двумя неизвестными
относится и к системе неравенств с любым числом неизвестных, с той лишь разницей, что решением
неравенства с n неизвестными будет совокупность n чисел (
),
удовлетворяющих всем неравенствам, а вместо граничной прямой будет граничная гиперплоскость
n-мерного пространства. Решением будет многогранник решений (симплекс), ограниченный
гиперплоскостями.
Так же, как и в двухмерном пространстве (на плоскости), каждое из неравенств системы определяет n-мерное полупространство. Пересечение всех этих полупространств образует многогранник решений. Но изобразить этот многогранник (называемый симплексом) геометрически невозможно. Лишь в случае, когда число неизвестных не больше трёх, то есть в действительном пространстве, многогранник решений можно изобразить геометрически.
Множество решений линейных неравенств геометрически составляет выпуклый многогранник или выпуклое множество точек.
Выпуклые множества точек
Как уже отмечалось, системы линейных неравенств играют важную роль в линейном программировании. Теоремы линейного программирования содержат такие понятия, как выпуклые множества и крайние точки. Разберёмся бегло, о чём речь.
Множество точек называется выпуклым, если вместе с его любыми двумя точками ему принадлежит и весь отрезок, соединяющий их. Если же существует хотя бы такая пара точек множества, что отрезок, соединяющий эти точки, не принадлежит целиком этому множеству, то такое множество называется невыпуклым. На рисунке 4 слева изображено выпуклое множество, а справа - невыпуклое.
Выпуклые множества обладают важным свойством, которое устанавливается следующей теоремой.
Теорема. Пересечение двух выпуклых множеств - также выпуклое множество.
Через любую внутреннюю точку выпуклого множества можно провести отрезок, для которого она является внутренней, а сам отрезок целиком принадлежит этому множеству. Но есть точки (для выпуклого многоугольника это его вершины), для которых такое построение выполнить нельзя: нет ни одного отрезка, для которого вершина являлась бы внутренней, а отрезок целиком бы принадлежал мноргоугольнику.
Точка выпуклого множества называется угловой (или крайней), если через неё нельзя провести ни одного отрезка, состоящего только из точек данного множества и для которого она была бы внутренней.
| Назад<<< | Листать | Вперёд>>> |
Поделиться с друзьями
