ВУЗ:
Составители:
Рубрика:
17. Системы линейных неравенств и многогранники 157
Пересечением этих замкнутых полупространств, согласно определению, является неко-
торый многогранник. Координаты точек, принадлежащих этому многограннику, удо-
влетворяют системе неравенств
a
1
1
x
1
+ . . . + a
1
n
x
n
− b
1
6 0,
. . . . . . . . . . . . . . . . . . . . . , (17.13)
a
k
1
x
1
+ . . . + a
k
n
x
n
− b
k
6 0,
т.е. множество решений этой системы линейных неравенств можно интерпретировать
как некоторый замкнутый многогранник.
♦ Знаки неравенства в (17.13) при необходимости всегда можно поменять на про-
тивоположные умножением его коэффициентов на −1.
Многогранник называется n-мерным параллелепипедом в аффинном простран-
стве A
n
, если он задается неравенствами
x
(0)
i
6 x
i
6 x
(1)
i
, i = 1, n, (17.14)
по каждой координатной прямой (17.1). Если числа x
(0)
i
= 0, x
(1)
i
= 1, т.е.
0 6 x
i
6 1, i = 1, n, (17.15)
то он называется параллелепипедом, построенным на базисных векторах ~e
1
, . . . , ~e
n
,
исходящих из начала координат — точки O.
♦ С помощью преобразований репера A
n
параллелепипед (17.14) всегда можно
привести к виду (17.15).
С точки зрения определения (17.14), отрезок является одномерным параллелепи-
педом, параллелограмм — двумерным параллелепипедом и т.д.
Часть параллелепипеда (17.15), лежащая в какой-либо координатной плоскости
x
i
= 0 или гиперплоскости x
i
= 1, сама является (n −1)-мерным параллелепипедом и
называется (n − 1)-мерной гранью параллелепипеда (17.15) .
Аналогично можно рассматривать грани этих (n−1)-мерных граней, грани их гра-
ней и т.д. Такой подход приводит к набору k-мерных (n−1 6 k 6 1) параллелепипедов.
Одномерные грани называются ребрами, а их концы — вершинами параллелепипеда.
Очевидно, что вершины параллелепипеда являются его угловыми точками, посколь-
ку вершины — это только те точки, у которых каждая координата равна либо нулю,
либо единице.
Множество точек аффинного пространства A
n
, координаты которых удовлетво-
ряют неравенствам
|x
i
| 6 M,
называется ограниченным.
Очевидно, что множество ограничено только в том случае, если оно целиком содер-
жится в некотором параллелепипеде (17.14). Ограниченные многоугольники показаны
на рис. 12,а и в.
Пример 17.1. На рис. 13,a изображено невыпуклое множество G, ограниченное ло-
маной ABCDEA. Показать, что это множество не является пересечением конечного
числа полуплоскостей. Построить выпуклый многогранник, содержащий в себе исход-
ное невыпуклое множество G.
Решение. Для наглядности будем штриховать край полуплоскости так, чтобы линии
штриховки принадлежали полуплоскости (см. рис. 13). После этого сразу становится
видно, что пересечением полуплоскостей могут быть многогранники AA
′
CB, DD
′
BC
или EDBCA
′
— все они являются выпуклыми. Множество G, ограниченное ломаной
ABCDEA, не является пересечением всех исходных полуплоскостей, поскольку мно-
гогранники AED
′
и DEA не могут одновременно принадлежать пересечениям всех
изображенных полуплоскостей.
Страницы
- « первая
- ‹ предыдущая
- …
- 155
- 156
- 157
- 158
- 159
- …
- следующая ›
- последняя »
