Matlab 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Matlab
标  题: 整数线性规划问题和算法简介
发信站: 哈工大紫丁香 (Wed Mar 31 10:16:14 2004), 站内信件

整数线性规划(integer linear programming)通常简称整数规划(integer programming)

，它比普通的线性规划（即无整数约束的线性规划）无论在理论上还是实践中都要难得

多．相对于整数规划，前述线性规划可称为普通线性规划(ordinary linear programmi

ng)

***************************************************************************

注意：关于整数规划比普通的线性规划要难得多这一点，许多人感到并非是用直觉就易

于理解的。其实，变量只能取整数，这相当于加上了一类很强的约束条件，因此通常使

求解的难度大大增加了（而不是难度减小！），整数规划是组合问题(combinatorial p

roblems)，两者都属于所谓“NP一完全问题”（NP－Complete Problem），即未找到多

项式时间算法的问题，并且人们相信对此类问题根本不存在多项式时间算法，计算量将

随问题规模（变量数、约束数等）按指数增长

***************************************************************************

    整数线性规划的困难在于当问题的维数（变量与约束的个数）增加时，计算量将爆

炸性（即按指数规律）增加．下面是一些常用求解方法．

    l）穷举法：变量维数(n)高时不可行．

    2）舍人凑整法：与非整数最优点相邻的整数数为 个，故此时等效于求一个0-l规划

的穷举法，变量维数(n)高时同样不可行．

    3）分支定界法：比较可行．

    4）割平面法：比较可行．

***************************************************************************

  提示：在实践中，不必把整数规划与普通规划界限划得太清．因为在许  多实际问题

中，模型的建立本身就包含了一些不确定因素，同时常常也允许近似的或粗略的结果．

不必太在意严格和完美，笔者发现舍入凑整法在实践中经常是有用的！

***************************************************************************




--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]