нахождение целочисленной точки в симплексе

evor

симплекс задаётся системой из n неравенств с n переменными
задача заключается в поиске в нём точки с целочисленными координатами или же получения ответа, что её нет
является ли такая задача NP-полной(трудной есть ли частные случаи (какие-нибудь ограничения на матрицу) в которых она становится разрешимой за полиномиальное время?
буду благодарен все пинкам в этом направлении)
PS: кто скачает книжку Схрейвера http://lib.mexmat.ru/books/66321 буду очень признателен

vsjshnikova

Является NP-полной, к ней сводится общая задача целочисленного линейного программирования. (Добиваем количество переменных или неравенств с помощью несущественных, находим ограничение на решение, бинарным поиском двигаем плоскость, соответствующую функционалу цены, пока целочисленные точки не перестанут существовать)
Я в этой области не сильно специалист, из полиномиально разрешимых вариантов могу вспомнить ЦЛП с вполне унимодулярной матрицей ограничений.
http://free-books.dontexist.com/search?req=%D0%A1%D1%85%D1%8...

evor


чото я не въехал в последние 3 строчки, как они это делают?)

vsjshnikova

чото я не въехал в последние 3 строчки, как они это делают?)
[math]$Ax\leqslant b \Leftrightarrow A(x'-x'')\leqslant b, x',x''\geqslant 0$[/math] - заменяем произвольное целое $x$ на разность двух положительных, любое $x$ можно так представить
[math]$A(x'-x'')\leqslant b \Leftrightarrow A(x'-x'') + x''' = b, x'''\geqslant 0$[/math] - обозначаем $x'''$ недостаток в неравенстве, он положительный.

evor

и почему это получится частный случай (2)?)

vsjshnikova

и почему это получится частный случай (2)?)
Это будет (2 если матрица [A|-A|E], а вектор цены [c|-c|0]
Оставить комментарий
Имя или ник:
Комментарий: