Целочислени полиедрични множества
Унимодулни проблеми на целочисленото програмиране.
Дефиниция на унимодуларен целочислен програмен проблем.
Дефиниция 3.1. Матрица A, чиито всички минори са 0 или , се наричаунимодуларнаматрица.
Целочислени полиедрични множества.
В този раздел се разглеждат целочислени полиедрични множества, т.е. многостенни множества, чиито върхове са цели числа. Важността на изучаването на тези множества се дължи на факта, че директният симплексен метод, подобно на други методи за крайно линейно програмиране, определя точно основното оптимално решение (ако проблемът има решение). Следователно, ако всички основни решения на някакъв проблем с линейно програмиране са цели числа, тогава алгоритмите за линейно програмиране позволяват намирането на оптимално (базово) решение, което също така удовлетворява изискването за цяло число и също е оптималното решение на съответния целочислен проблем с линейно програмиране.
Многостенно множество се наричацяло число, ако всички негови върхове (съответстващи на основни решения) са цели числа (т.е. всички техни компоненти са цели числа).
Помислете за многостенно множество:
Следната теорема е вярна.
Теорема 3.1.[1] Нека е матрица с фиксиран ранг с цели елементи. За да бъде едно многостенно множество цяло число, е необходимо и достатъчно всеки минор от порядъка на матрицата да бъде 0 или .