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

Рассмотрим n-мерное пространство, точки которого задаются координатами .

Определение 1. Гиперплоскостью в n-мерном пространстве называется совокупность точек М, координаты которых удовлетворяют уравнению

,

где хотя бы одно из чисел отлично от нуля. При n = 3 это плоскость в трехмерном пространстве, при n = 2 - прямая на плоскости.

По отношению к гиперплоскости все n-мерное пространство разбивается на две части: область, в которой выполняется неравенство

и область, в которой справедливо неравенство

.

Данные области называются полупространствами.

Определение 2. Выпуклой линейной оболочкой точек линейного пространства называется множество точек вида

,

где числа удовлетворяют условиям , ;

.

Выпуклой линейной оболочкой двух точек и является множество точек отрезка .

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

Определение 4. Пересечение конечного числа полупространств называется многогранником (если область ограничена) или многогранной областью (если область не ограничена).

Теорема 1. Решение системы m линейных неравенств с n неизвестными

есть выпуклый многогранник или выпуклая многогранная область n-мерного пространства (или Æ), получающаяся в результате пересечения всех полупространств, отвечающих неравенствам данной системы.

Теорема 2. Любой выпуклый многогранник совпадает с выпуклой оболочкой некоторой конечной системы точек. Эти точки называются вершинами (или угловыми точками) данного многогранника.