4. Свойства решений задач линейного

программирования

Одним из основных понятий в теории ЛП является многогранник в

- мерном пространстве и угловая точка. Перейдём к их определению.

4.1. Отрезок в . Понятие выпуклого множества. Гиперплоскость и полупространство, их выпуклость

Пусть две произвольные (различные) точки пространства .

Определение 4.1.1. Отрезком называется множество всех точек из вида , где . Точки и называются концами отрезка, остальные точки называются внутренними.

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

Теорема 4.1.1. Пересечение выпуклых множеств есть выпуклое множество.

Доказать самостоятельно.

Определение 4.1.3. Гиперплоскостью в пространстве _{называется совокупность точек , удовлетворяющих уравнению}

, (4.1.1)

где хотя бы один из коэффициентов отличен от нуля.

Определение 4.1.4. Полупространством в _{называется множество точек}

_{, удовлетворяющих неравенству}

(4.1.2)

или неравенству

. (4.1.3)

Ясно, что гиперплоскость (4.1.1) есть пересечение полупространств (4.1.2) и (4.1.3). Обозначая через А вектор , мы получим краткую запись гиперплоскости (4.1.1): AX=B и полупространств , . _{Теперь легко доказать следующую теорему:}

Теорема 4.1.2. Всякое полупространство в является выпуклым множеством.

_{Доказательство. Рассмотрим} . Пусть _{и пусть для произвольного любая точка отрезка .}

.

Следствие. Всякая гиперплоскость в является выпуклым множеством.

4.2. Понятие многогранной области и многогранника. Понятие угловой точки. Представление любой точки многогранника через угловые точки

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

Определение 4.2.2. Ограниченная многогранная область называется многогранником.

Определение 4.2.3. Выпуклой линейной комбинацией векторов , , …, называется всякий вектор , допускающий представление , где и .

Определение 4.2.4. Точка множества называется угловой точкой, если она не является внутренней точкой отрезка, целиком принадлежащего .

Угловые точки многогранника называются его вершинами.

Теорема 4.2.1. Любая точка многогранника является выпуклой линейной комбинацией его угловых точек.

Доказательство проведём только для случая

Пусть точка Х – внутренняя точка многоугольника с вершинами , , , , . Тогда если точка Х – внутренняя точка отрезка , то , , такое, что

. (4.2.1)

Также , , такое, что . Подставив последнее выражение в (4.2.1), получим .

Обозначим , , , запишем

.

Здесь , , и .

Следовательно, точка является выпуклой линейной комбинацией угловых точек , , , ч.т.д.