Унимодулярность матрицы в задаче линейного программирования

[re3burn]

Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

[Sonic86]

re3burn в сообщении #482121 писал(а):

Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

Вообще говоря, не является: матрица задачи ЛП необязательно квадратная, у неквадратных матриц и определителя-то нету Если же рассматривать квадратные матрицы, то ограничения задачи ЛП не меняются, если их умножать на коэффициент ($ax+by \leqslant c \Leftrightarrow (\forall k)kax+kby \leqslant kc$), в то время как определитель при это преобразовании умножается на $k$, значит, можно подобрать такое $k$, что ....
В общем - неестественная какая-то задача.

[re3burn]

Sonic86 в сообщении #482157 писал(а):

re3burn в сообщении #482121 писал(а):

Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

Вообще говоря, не является: матрица задачи ЛП необязательно квадратная, у неквадратных матриц и определителя-то нету Если же рассматривать квадратные матрицы, то ограничения задачи ЛП не меняются, если их умножать на коэффициент ($ax+by \leqslant c \Leftrightarrow (\forall k)kax+kby \leqslant kc$), в то время как определитель при это преобразовании умножается на $k$, значит, можно подобрать такое $k$, что ....
В общем - неестественная какая-то задача.

Нашел ответ в книге "Новые направления в линейном программировании" (Гольштейн Е.Г.):
Теорема. Для целочисленности всех многогранных множеств M(B), где B - произвольный m-мерный вектор с целыми состовляющими, необходимо и достаточно, чтобы любой минор порядка m матрицы A был равен либо 0, либо +/-1.