2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Унимодулярность матрицы в задаче линейного программирования
Сообщение10.09.2011, 20:24 
Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

 
 
 
 Re: Унимодулярность
Сообщение11.09.2011, 06:24 
re3burn в сообщении #482121 писал(а):
Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

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

 
 
 
 Re: Унимодулярность
Сообщение11.09.2011, 10:31 
Sonic86 в сообщении #482157 писал(а):
re3burn в сообщении #482121 писал(а):
Является ли свойство унимодулярности матрицы в задаче линейного программирования необходимым условием для того, чтобы вершины полиэдра имели целочисленные координаты?

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

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group