Свойства множества допустимых решений ЗЛП

Многогранные множества, многогранники, вершины

def. Множество точек пространства , координаты которых удовлетворяют уравнению

, где , называется гиперплоскостью H_ab.

Или H_ab =

def. Множества

, , (2)

порождаемые этой гиперплоскостью, называются (закрытыми) полупространствами.

def. Вектор a называется нормалью к гиперплоскости H_ab, к ней ортогонален и направлен в сторону пространства H⁺_ab

Если в соотношениях (2) знаки “³ ”, ”£ ” заменить на “> ”, ”< ”, получим открытые полупространства.

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

1) записать множество Х в виде

Х = {x Î Rⁿ | x удовлетворяют условиям S};

2) предположить, что точки (для них выполняются условия S);

3) показать, что выпуклая линейная комбинация этих двух точек

принадлежит Х,

то есть, используя тот факт, что точки удовлетворяют условиям S показать, что и их линейная выпуклая комбинация удовлетворяет тем же условиям.