[求助]咨询几个清华运筹学教程线性规划和整数规划的问题

sdeven95

[这个贴子最后由sdeven95在 2012/03/13 11:55am 第 1 次编辑]

各位好，有几个运筹学课本问题想咨询下。
我是学管理的，运筹学不是很好，去年给学生讲了一次运筹学，反响不好，领导也批，但是感觉里面的算法的确挺有意思的（用的清华的绿皮教程），就编程试了一下，发现了一些问题，大家帮我看看。
（1）线性规划在使用两阶段法求解的时候，辅助线性规划最后的求解结果有时出现一种特殊情况，最优值为0但仍有人工变量为基变量的情况（当然对应最优解为0），课本上好像没说这种情况如何处理，我用的是对偶单纯形法中的旋转思路，将人工变量旋转出去，这样处理到底有没有问题？（我在模拟测试中好像没有发现问题）
（2）单纯形法是不是不是一种有效算法，好像还听说过一种什么kamarkar算法，这是一种什么算法？它的编程实现能不能找到？
（3）指派问题的匈牙利算法是不是有问题啊？当中提到一点细节说如果划线数大于划圈数的话说明不合理，需要回去重新测试，在程序中如果这样做的话不确定性就太强了，如果不考虑这一点有些问题又会出现死循环。我查了下资料最后使用了图论上增广路调整和饱和路变换的思路进行了编程，方法很简单，效率也很高，万阶成本矩阵（1亿变量）在我的机器（E5200）上可在1秒内完成计算。那么对于指派问题教程上是否可以考虑不再讲那个绕来绕去的匈牙利法，直接讲增广路调整和饱和路变换方法多好？（复杂度理论上最坏n^3，实际上感觉远远达不到）
（4）割平面法是不是个陷阱啊？我用来编程之后，发现很多2变量*2约束的问题它都会出现收敛很慢的情况，实际上从图形上直观看就知道，这种操作会使顶点越割越多。我觉得是不是应该从教程上把这种方法去掉啊？可是教程上提到一句“如果与其他方法结合也是有效地”，到底怎么结合啊？
（5）混合型整数规划怎么这么难求解？我用分支定界法很慢，基本上到15变量*10约束条件的情况下，有些问题就需要几十秒才能完成。我觉得问题的关键在于减少搜索的分支，由于分支存在不存在有效算法，减少分支可以从两个思路，一是通过其他方法先搜索一个尽量大的整数解下界，二是在运算过程中想办法减少分支的数目，我从两个角度想了不下10种方法及其组合来改进，但效果都不太理想，相对基本分支定界法效率也就提高20-30%。奇怪的是使用择向下降变量代换的思路居然能将效率提高50%，搞不清为甚么？
     现在到底有没有混合整数规划的有效算法啊？我看到lingo文档上说它的变量个数可以达到1万个，mathmatica文档上说它使用了一种缩减矩阵的搜索方法，它们到底是如何实现的啊？[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
又发现一个问题，bland规则是否正确，针对任何情况都能避免循环？（希望正确，否则我的线性规划程序要想办法改写了）能否推广到对偶单纯形法？是不是不能啊，我在超平面下降法求整数规划满意解的测试下发现一个对偶单纯形法死循环的例子，即使使用有些资料上说的推广的bland规则也没用。[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
是不是我搞错了，对偶单纯形法不存在退化，因此不使用bland法则，我用了反而出现了死循环？[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
无论用还是不用都有死循环的情况出现[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
由于问题特殊，死循环的情况通过一些方法解决了。可以开始进行一些测试了，现在看来还是择向下降法比较好，规模稍微大点（20变量以上），求解时间就可以缩短为普通分支定界法的百分之几，如果规模再大，也许会缩减到百分之一以内[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
有没有人有规模大些的线性规划的例子，我需要进行一些测试。最好100变量左右的，我的模拟方法好像有问题，在100变量*80约束条件生成的线性规划都是无解的（30变量以下好像可以生成30-50%有解的），两个多小时了还没发现一个可解的。这些无解的，择向下降法找最优解耗时大概在2—10分钟之间。如果有例子请发到我的邮箱272995135@qq.com。看来需要做好长期测试的准备了，要打持久战了。[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
补充一下，我使用了“有理+大数”精确运算形式，为了避免误差放大问题（但感觉可能使求解时间数十倍甚至百倍增加），提供的数据最好是有理数形式。[br][br]-=-=-=-=- 以下内容由 sdeven95 在 时添加 -=-=-=-=-
在完全退化的情况下，即使使用了bland规则，单纯形法也很容易出现循环，因此bland规则应该是有条件的，即不会出现完全退化的情况。单纯形法本质上无法避免穷枚举本质带来的各种问题

EhomeS

运筹学～～～