Многогранник [polihedron] — выпуклое ограниченное множество точек, удовлетворяющих одновременно конечному числу неравенств типа:
a11x1 + … + a1nxn ≤ b1
………………..
am1x1 + … + amnxn ≤ bm
или в матричной записи
M = {x∈En | Ax ≤ B}.
М. имеет конечное число крайних точек, называемых его вершинами, экстремальными точками (это такие точки, которые не могут лежать внутри отрезка, соединяющего две точки выпуклого множества, а могут быть только одной из концевых точек этого отрезка).
Понятие М. используется в геометрической интерпретации задач линейного программирования: множество допустимых решений задачи является выпуклым М., базисное решение или опорный план — одной из его вершин. (См. Вершина допустимого многогранника).