资源描述：
《一种混合整数双层线性规划的全局优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2005年7月系统工程理论与实践第7期 文章编号:100026788(2005)0720113204一种混合整数双层线性规划的全局优化方法1,21赵茂先,高自友(11北京交通大学系统科学研究所,北京100044;21山东科技大学应用数学系,山东泰安271019)摘要:通过求得下层问题的对偶问题可行域上的极点,将上层所有变量为021型变量和下层所有变量为连续型变量的双层线性规划转化为有限个混合整数线性规划问题,从而用求解混合整数线性规划的方法获得问题的全局最优解.由于下层问题的对偶问题可行域只有有限个极点,所提出的方法具有全局收敛性.关键词:混合整数双层线性规划;混合整数
2、线性规划;对偶问题;极点中图分类号:O221.1;O221.4文献标识码:AAGlobalConvergentAlgorithmforSolvingtheMixedIntegerBilevelLinearProgrammingProblemZHAOMao2xian,GAOZi2you(11InstituteofSystemSciences,BeijingJiaotongUniversity,Beijing100044,China;21DepartmentofAppliedMathematics,ShandongUniversityofScienceandTechnolo
3、gy,Tai’an271019,China)Abstract:Themixedintegerbilevellinearprogrammingproblem(MIBLPP),wheretheupper2leveldecisionmakercontrolsallzero2onevariableandthelower2leveldecisionmakercontrolsallcontinuousvariables,isdiscussed.Bysolvingtheextremepointsofthefollower’sdualproblem,theMIBLPPisdecompo
4、sedintoaseriesofmixedintegerlinearprogramproblems.Usingmixedintegerlinearprogrammethods,aglobaloptimalsolutiontotheMIBLPPcanbeobtained.Keywords:mixedintegerbilevellinearprogramming;mixedintegerlinearprogram;dualproblem;extremepoint对于大系统和复杂系统,层次性是系统的主要特征之一.多层规划正是为了研究系统层次性而产生的,并正逐渐形成一个新的运筹
5、学分支.在多层规划应用中,以双层规划最为常见,这是因为现实中的决策系统大都可看作双层决策系统,并且任何多层决策系统都是一系列双层决策系统的复合.双层规划问题是由非合作且有序的两个优化问题组成,上层首先给下层一定信息,下层在这些信息下按自己的利益做出反应,上层再根据下层的反应作出符合全局利益的决策.在许多双层优化问题中,要求某些变量只能取整数,例如企业人力资源规划问题、生产设备分配问题以及城市交通网络设计问题等.变量的离散性使得问题变得复杂,即使对较简单的混合整数双层线性规划,也可能导致问题无解.Moore和[1]Bard对上、下层都有离散变量的混合整数双层线性规划问题进
6、行了讨论,并给出了一种分支定界求解算[2]法,该算法只有在上层无连续变量的情况下,才能保证收敛.Bard和Moore对上、下层所有变量都为021型变量的混合整数双层线性规划问题加以了研究,通过对构造出的参数整数规划不断进行求解,提出了一种分支定界方法.本文将讨论上层所有变量为021型变量和下层所有变量为连续型变量的双层线性规划问题,通过求得下层问题的对偶问题可行域上的极点,将问题转化为有限个含021型变量的混合整数线性规划问题,从而用混合整数线性规划的方法求得问题的全局最优解.1 模型与定义设x为021型变量组成的n维列向量,y为连续变量组成的m维列向量,本文讨论的混合
7、整数双层收稿日期:2004206201资助项目:国家杰出青年科学基金(70225005);教育部高等学校优秀青年教师教学科研奖励计划(2001)作者简介:赵茂先(1966-),男,江苏江都人,副教授,在职博士,主研方向为最优化理论与算法.©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.114系统工程理论与实践2005年7月线性规划问题(MIBLPP)一般形式可以写为:(P1)minF(x,y)=c1x+d1yxs.t.A1x+B1y≤b1xj=0或1(1≤j≤n
