Многогранник

Многогранник [polihedron] — выпуклое ограниченное множество точек, удовлетворяющих одновременно конечному числу неравенств типа:

a11x1 + … + a1nxn ≤ b1

………………..

am1x1 + … + amnxn ≤ bm

или в матричной записи

M = {xEn | AxB}.

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

Понятие М. используется в геометрической интерпретации задач линейного программирования: множество допустимых решений задачи является выпуклым М., базисное решение или опорный план — одной из его вершин. (См. Вершина допустимого многогранника).