Методы определения целочисленных решений.

Теряется св-во выпуклости области определения, на чем основаны все предыдущие методы. Их округление может привести к недопустимости. Даже если можно округлить, будет ли оно оптимальным. При особых свойствах целочисленной задачи решение ее как непрерывной всегда дает целочисленный результат. Такой исход имеет место, если все вершины допустимого множества целочисленные. Многогранное множество, обладающее этим свойством, называется целочисленным. Определим условия, при которых множество оказывается целочисленным. Возьмем многогранное множество M (B):

; (1) (2) где все a_ij – фиксированные целые числа, B = (b ₁, b ₂, …, b_m)^Т и m< n (ранг матрицы [ a_ij ] равен m.) Для него справедлива следующая теорема.

Теорема. Для того чтобы все вершины многогранного множества M(B) при любом целочисленном векторе B были целочисленными, необходимо и достаточно, чтобы каждый минор порядка m матрицы условий [ a_ij ] был равен либо 0, либо +1 или –1.

Если вместо равенств (1) множество задается неравенствами, указанные в теореме значения относятся ко всем минорам матрицы [ a_ij ].