Файл: В. А.МАТВЕЕВ.pdf

x1 , x2 , x3 Rn и их выпуклую линейную комбинацию

треугольником с вершинами в точках x1 , x2 , x3 Rn . Эти же

точки являются угловыми для треугольника. Более того, треугольник и есть выпуклая линейная комбинация угловых точек, вершин треугольника. Примеры отрезка (7.1), треугольника (7.3) позволяют дать

Определение 7. 3. Выпуклым многогранником в векторном пространстве Rn называется выпуклая линейная комбинация k

точек x1 , x2 , …, xk Rn . Угловые точки этого множества

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

Выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя вершинами (7.1), треугольник – тремя вершинами (7.3), n – угольник – n вершинами (7.2).

Выпуклая оболочка из k точек может быть обобщена на более широкое понятие – выпуклая оболочка множества в

векторном пространстве. Пусть задано множество M Rn

(конечное или бесконечное) Существует бесконечное число выпуклых множеств в векторном пространстве, содержащих M. Рассмотрим пересечение этих выпуклых множеств. Во – первых, по теореме о пересечение такое множество выпукло, во – вторых, оно содержит данное множество M. Это пересечение является наименьшим множеством с указанными двумя свойствами и оно определяется по M однозначно. Это пересечение называется

выпуклой оболочкой множества M в векторном пространстве Rn

и обозначается co (M). Отметим, что выпуклая оболочка множества совпадает с множеством всех выпуклых комбинаций точек из M, как это определено в (7.2). В этом случае можно ограничиться и конечным числом точек из множества M. Всё это представлено в

57

Теорема (Каратеодори). Пусть M множество в Rn . Тогда co(M ) ={x R n x =α1 x1 +... +αk x k , k ≤ n +1, x1,..., x k M ,

В этом случае говорят, что каждая точка их co(M) представима в виде линейной комбинации не более чем n+1 точки из M. Если множество М компакт, то и множество co(M) также является компактом.

Выпуклые множества и многогранники используются при изучении решений систем линейных неравенств. Рассмотрим линейное уравнение

Множество его решений называется гиперплоскостью в векторном

пространстве Rn . В частном случае при n = 2 гиперплоскость в (7.5) геометрически представляется прямой на плоскости. При n = 3 эта гиперплоскость есть плоскость в пространстве.

Рассмотрим линейное неравенство, соответствующее (7.5)

Множество точек, удовлетворяющее (7.6), называется полупространством, на которое делится всё пространство гиперплоскостью (7.5), включая и эту гиперплоскость. Отметим, что гиперплоскость и полупространство являются выпуклыми множествами.

Перейдём к системе m линейных неравенств a11 x1 +... +a1n xn ≤ b1 ,

Решение каждого неравенства в (7.7) является полупространством, т.е. выпуклым множеством. Тогда, согласно теореме о пересечении выпуклых множеств, множество решений такой системы также выпукло. Если это решение ограничено, то оно является многогранником и выпуклой оболочкой конечной системы угловых точек.

58

Пример 7.1. Решить графически систему неравенств. Найти угловыерешения. Еслимножестворешенийограничено, тоуказать общеерешение

3x1 + 4x2 ≥12,

3x1 +8x2 ≤ 24,

2x1 + x2 ≤ 8,

− x1 + 2x2 ≤ 2, x2 ≤ 5, xi ≥ 0,i =1,2.

На плоскости каждому неравенству соответствует полуплоскость, её граница – прямая линия. Для построения полуплоскостей запишем уравнения прямых в отрезках

(m) : x41 + x32 =1;

(n) : x81 + x32 =1; ( p) : x41 + x82 =1;

Соответствующие прямые – границы построены на рисунке 7.2. Для каждой из них штриховкой выделена полуплоскость, являющаяся решением соответствующего неравенства. Решение системы неравенств есть выпуклое множество - пересечение полуплоскостей. Из рисунка видно, что пересечение пяти полуплоскостей является выпуклый четырёхугольник АВСD.

59

Найдёмкоординатыеговершин. Ониопределяются, какпересечения сторон

− x1 + 2x2 = 2.

Согласно результатам параграфа множество всех решений системы неравенств является четырёхугольник АВСD.

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

x 2

8

5

(r)

(p)

Рис. 7.2.

60