欢迎来到天天文库
浏览记录
ID:46530637
大小:879.27 KB
页数:8页
时间:2019-11-24
《用于求解0-1型整数规划问题的新算法研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、第21卷第5期运筹与管理Vol.21,No.52012年10月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEOct.2012用于求解0-1型整数规划问题的新算法研究赵宁, 宓为建, 王东胜(上海海事大学,上海201306)摘要:本文针对0-1型整数规划问题的求解算法进行研究,在分析了常用典型算法的求解原理和过程的基础上,提出了一种新的算法———Cards-flipping算法。该算法在此类问题的计算上具有通用性,其可靠性与精度等效于枚举法,求解过程中无需遍历各中间解的目标值即可按照最优顺序
2、依次检验中间解,找到的第一个可行解即为最优解,因此求解效率较高。通过对该算法的数学证明以及大量的算例分析,证明了算法的有效性和实用性。关键词:运筹学;Cards-flipping算法;翻牌序列;0-1型整数规划中图分类号:O221.4 文章标识码:A文章编号:1007-3221(2012)05-0107-08ANewAlgorithmforZero-oneIntegerLinearProgrammingZHAONing,MIWei-jian,WANGDong-sheng(LogisticsEngineeringSc
3、hool,ShanghaiMaritimeUniversity,Shanghai201306,China)Abstract:Thispaperdiscussestheproblemofsolvingzero-oneintegerlinearprogrammingmodels.Basedontheanalysisofdifferentcommonlyusedalgorithms,weputforwardanewalgorithmnamedcards-flippingalgorithmwhichdemonstratesre
4、liabilityandaccuracyequivalenttoenumerationmethods.Thecorrectnessandthepractica-bilityofthemethodareverifiedwithmathematicalproofsandagreatdealofexamples.Keywords:operationresearch;cards-flippingalgorithm;flipserialnumber;zero-oneintegerlinearprogramming0 引言0-1规
5、划在整数规划中占有重要地位,一方面因为许多实际问题,例如指派问题、选地问题、送货问[1]题都可归结为此类规划。0-1变量作为逻辑变量常被用来表示系统是否处于某个待定状态,或者决策时是否取某个待定方案。求解0-1规划的常用方法是分支定界法,对各种特殊问题还有一些特殊方法,例如求解指派问题用匈牙利方法就比较方便。然而实际应用中决策模型求解规模都比较大,所以像分支[2!~4]定界法、目标排序法等传统的算法往往无法满足企业对求解速度的要求,因此,不少学者通过增加辅助决策变量和辅助约束等手段改造模型并编写专用算法求解模型,然而这
6、类算法往往只能得到较优解,其可靠性有待实际检验。本文提出了一种求解0-1型整数规划模型的新算法———Cards-flipping算法(简称CFAlgorithm),其可靠性等效于枚举法,且求解效率相对较高。1 求解0-1型整数规划的常用算法分析0-1型整数规划的数学模型可表示如下:收稿日期:2011-12-12基金项目:国家863计划重点项目(2009AA043001);上海市教委项目(J50604&09ZZ163)作者简介:赵宁(1981-),男,讲师,博士研究生。108运筹与管理 2012年第2
7、1卷n目标函数:max(ormin)Z=∑aixi(1)i=1约束条件:n∑cjixi≤bj, (j=1,2,⋯,m)i=1xi=0or1, (j=1,2,⋯,n)(2)对于任意一个0-1问题,若其决策变量有n个,那么其解的个数就是2的n次方个,如图1所示。如果按照这些解的目标函数值从最优到最差排序,假设最优解出现在第i个,对于任意一种算法,为保证第i个解的最优性,则必须遍历目标更优的前i-1个解是不可行解。关键问题在于中间解的优越序列是未知的,因此传统算法在迭代过程中大量地检验第i个后面的非最优图1 n个决策变量对应
8、的解空间示意图解,导致计算规模极大,各算法的计算量分析如下:n(1)穷举法显然是要计算所有2个解的目标函数值,并一一进行约束检验,其计算量是最大的。[5](2)过滤隐枚举法是以穷举法为基础,通过建立过滤条件而减少计算工作量。该算法首先用试算法找到一个可行解,求得初始目标函数Z0,接着使用建立辅助约束条件,若是求最大化则令目标函数方
此文档下载收益归作者所有