一个基于离散填充函数的整数线性规划方法.pdfVIP

第18卷第1期 运 筹 与 管 理 V01．18．No．1 OPERATIONSANDMANAGEMENTSCIENCE Feb．2009 2009年2月 RESEARCH 一个基于离散填充函数的整数线性规划方法 陈克东1， 荆明娥2 (1．复旦大学管理学院，上海200433；2．复旦大学专用集成电路与系统国家重点实验室201203) 摘要：本文提出了一个有效的解决整数线性规划的新算法。如果离散化的局部有哪些信誉好的足球投注网站过程陷入局部最优解，则 构造相应的离散填充函数，引导有哪些信誉好的足球投注网站过程跳出局部最优解并得到更好的解。该方法是在离散空间中进行优化 的，无需增加新的约束，且一直保持整数可行性，收敛的速度非常快。该方法也为一般整数规划提出了一种新的 途径。数值实例表明，与现有的方法相比，该算法能够较快的找到最优解。 关键词：NP完全问题；填充函数；局部最优解；整数线性规划 中图分类号：0221．4 文章标识码：A 文章编号：1007—3221(2009)Ol·0021·04 ANewMethodfor Linear Based Integer Programming onDiscreteFilledFunctionMethod CHEN 1，JING Ke．dong Ming．e2 (1．ManagementSchool，FudanUniversity，Shanghai200433，China；2．StateKeyLaboratoryofASICSys· 201 tern，FudanUnwearyShanghai203，China) newmethodforILPis inthis search is intoa Abstract：A proposedpaper．Ifunfortunately，theprocesstrapped local filledfunctionisconstructedatthis thesearch outof10- optimalsoltution，a solution，whichguides process andfind areaddedtothe cal solution anotherbettersolution．Noadditionalconstraints optimal originalprogram— thescaleofthe constant．Ontheother method anew for ruing，so problemkeeps hand，this supplieswaygeneral thatthenewmethodhasanattractiveeffect． show integerprogramming．Severalexamples linear Keywords：NP—completefunction；localoptimalsolution；integerprograming problem；filled 0引言 整数线性规划在很多的工程科学上都是一个非常好的建模和解决离