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

целочисленное программирование, выпуклая оболочка, система линейных уравнений, система линейных неравенств, крайние точки

Математические вопросы и теория численных методов