单纯形怎么解决整数规划啊。。

没法解决

Cu Ball

单纯性，好遥远的东西……

感觉我可能表达出现了错误。。
就比如说费用流之类的问题。。可以用单纯形把。。

orz

如果系数矩阵全都是+1或者-1 那么可以观察Simplex的执行过程发现，整个过程中系数总是+1或者-1，这种Linear Programming问题就可以解决了
Network Flow问题就是一个例子
像NOI2008 employee也是这种

神牛们全都冒出来了

网上搜一下割平面算法，貌似可以解决一般的整数线性规划，大致思想是 先搞出浮点解然后割平面限制可行域（就是增加一个不等式限制）然后继续 浮点解，一直到浮点解 就是整数解为止。。。

其实提的人也不懂。