Базис Гильберта (линейное программирование)
- Базис Гильберта выпуклого конуса C — минимальный набор целочисленных векторов, представляющих собой конические комбинации векторов с целыми коэффициентами.
- Рассматривается моноид C ∩ L, порожденный решеткой L ⊂ Zd.
- Согласно лемме Гордана, моноид C ∩ L конечно порожден и существует конечный набор точек решетки, представляющих собой целочисленные конические комбинации этих точек.
- Конус С называется заостренным, если x, −x ∈ C подразумевает x = 0.
- В этом случае существует уникальный минимальный порождающий набор моноида C ∩ L — гильбертов базис C.
- Гильбертов базис задается набором неприводимых точек решетки, которые нельзя записать в виде суммы двух ненулевых элементов.
Полный текст статьи: