Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №4, Москва, 1992
Авторы: Шевченко В.Н.
Верхние оценки числа крайних точек в целочисленном программировании
Аннотация:
В этой статье используется подход, применявшийся автором ранее, для оценки числа крайних точек выпуклой оболочки множества М целочисленных решений системы линейных уравнений. Рассмотрены свойства крайних точек, когда М описано системой линейных уравнений и сравнений, получены различные варианты оценок их числа, то же самое сделано для случая, когда М описано системой линейных неравенств. При фиксированной размерности все оценки полиномиальны и не зависят от правых частей систем, описывающих М. Показано, как аналогичные вопросы решать для частично целочисленного случая.
Ключевые слова:
целочисленное программирование, выпуклая оболочка, система линейных уравнений, система линейных неравенств, крайние точки
Язык публикации: русский, страниц: 8 (с. 65-72)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Шевченко Валерий Николаевич,  ,  ННГУ им. Н. И. Лобачевского, факультет вычислительной математики и кибернетики