2023年8月1日发(作者:)
2004年上海大学硕士学位论文摘要非线性背包问题是一类特殊的非线性整数规划问题.由于在管理,经济以及工业生产的最优化模型中的广泛应用,它在非线性整数规划中担当着十分重要的角色.一个非线性背包问题可描述如下:maxm)=∑厶(q)j=1nsc.口(。)=∑9j(q)sb,j=l。∈X=扛10Sxj≤uj,xjinteger}其中疗,毋为定义在吣,q】上的连续实函数,b和邯分别是变量唧的下界和上界.不失一般性,设ff,uj为整数,这里J—l….,n.本文研究的主要问题是两类非线性背包问题一凸背包问题和凹背包问题.根据这两类背包问题的单调性和凸性,本文给出了0-1线性化方法.凸背包问题可以直接转化成一个等价的0-1线性背包问题,然后通过隐枚举法或动态规划法解这个o.1线性背包问题就可以得到原凸背包问题的最优解.本文把这种o.1线性化方法同Pegging方法以及拉格朗匿对偶和区域割方法做丁数值比较,数值结果充分体现了o_1线性化算法的有效性和优越性.丽对于凹背包问题,首先用一个线性函数逼近目标函数,约束条件不变,这样就得到了一个目标函数是线性函数的凸背包问题,接下来就可以把得到的这个凸背包问题转化成一个等价的o-l线性背包问题,同样可用隐枚举法求解这个0-1线性背包问题.为了保证收敛性,我们利用函数的单调性和区域割技巧丢掉一些整数箱子,然后把保留下来的区域分割成一些整数箱子的并集.本文共由五章组成.第一章是前言部分,对非线性背包同题作了简单的介绍,并给出了几个非线性背包问题的模型;第二章介绍了求解非线性背包问题的现有算法;第三章绘出了凸背包问题的o_1线性化方法和数值结果,以及解0-1线性背包问题的几个常用算法,并与Pegging方法。拉格朗日对偶和区域割方法做了数值结果比较;第四章着重介绍了凹背包问题的0_1线性化分支定界算法;第五章是本文工作的总结以及对未来的研究2004年上海大学硕士学位论文展望.n关键询:非线性背包问题,线性逼近,0-1线性化,动态规划法,隐枚举法,Lagrangian对偶,分支定界算法.2004年上海大学硕士学位论文IIIAbstractNonlinearknapsackproblemis8specialclassofnonlinearintegerprogram-mingproblems.Becauseofitswideapplicationsinoptimizationmodelsincludingmanagement,economicsandindustry,thenonlinearknapsackproblemplaysanimportantroleinnonlinearintegerprogramming.Ageneralnonlinearknapsackcanbedescribedasfollows:nrnaxm)=∑乃(q)』=lst.9(。)=∑鲫(≈)56,j=1£∈X=(zf0Sz,≤%,≈integer},andg{arecontinuousreal-valuedfunctionsoll\},、‰{、。band弘jarethelossofgenerality,bandqaleassumedtobeintegers,Thegoalofthisthesisjstostudytwospecialclassesofnoulhiearknapsackknapsackproblemsandconcaveknapsackproblems.Usingtheandtheconvex/tyofthesetwokindsofknapsackproblems,wepro-a0-1linearizationmethod.Aconvexknapsackproblemcanbetransformedanequivalent0-ilinearknapsackproblemThesolutionoftheprimaryknapsackproblemcanbeobtainedbysolvingtheresulting0-ilinearproblembytheimplicitenumerationmethodorthedynamicprogram—method.Wecomparetheproposed0-1linearizationmethodwithPeggingandLagrangianandDomainCutmethod.Thecomputationalresultsthee最ciencyandtheadvantageoftheproposedalgorithm.Thesecondofthisthesisinvestigatestheconcaveknapsackproblems.First,theobjec-functionisreplacedbyalinearestimationfunctiontogetaconvexknapsackwithalinearobjectivefunction.ThentheresultingconvexknapsackissolvedbYtheimplicitenumerationmethodafterbeingtransformedanequivalent0-1linearknapsackproblemToensuretheconvergence,mono—pr曲lemwhere|ilowerboundandtheupperboundoftheargument%respectivelyforj=l,…,n.Withoutproblems:convexmonotonic/typoseintoconvexknapsackmingmethodshowparttireproblemprobleminto2004年上海大学硕士学位论文tonicityanddomaincuttechniqueareusedtoremovecertainintegerboxesandthereviseddomainarepartitionedintoaunionofintegerboxes.Thisthesisisorganizedasfollows.InChapter1,wegivesomebriefintro-ductionofnonlinearknapsackproblemsandillustratesomeexamplesofitsappli—cationsInChapter2.mintroducesomemethodsintheliteraturesforsolvingthenonlinearknapsackproblems.InChapter3,wepresentthe0-1llnearizationmethodfortheconvexknapsackproblemsandreportsystematiccomputationalresults.Wealsocomparethe0-1linearizationmethodwiththePeggingmethodandtheLagrangianandDomainCutmethod.Chapter4focusesonsolvingtheconcaveknapsackproblems.A0-1linearizationmethodandbranch-and-boundmethodisproposedfortheconcaveknapsackproblems.Finally,wesuumlarizethethesisinChapter5andsuggestsomefutureresearchdirections.Keywords:Nonlinearknapsackproblem,linearestimation,0-Ilinearization—dynamicprogrammingmethod,implicitenumeration,Lagrangiandualmethod,brandl一and.boundmethod.rvY上海大学678043本论文经答辩委员会全体委员审查,确认符合上海大学硕士学位论文质量要求。委员(工作单位、职称)答主辩任:,链移广名飚琴』p争毗;擎炙委员●■上大,)泛、n.磁■燃一儿几,n导师●●锶塍舭荚弓兕垫攻答辩日期:≯邸牛.S原创性声明本人声明:所呈交的论文是本人在导师指导下进行的研究工作。除了文中特别加以标注和致谢的地方外,论文中不包含其他人己发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名:釜丑塞日期塑业.点≥7本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定,即:学校有权保留论文及送交论文复印件,允许论文被套阅和借阅;学校可以公布论文的全部或部分内容。(保密的论文在解密后应遵守此规定)签名:盏丑基导师签名:盈:!缝日{}目=芝纽乡第一章前言§1.1问题的提出和定义一个徒步旅行者带了一个背包,他要用背包装入尽可能多的物品而不能超过这个背包的容量.如果有几种不同的物品可以装进背包,且每种物品都有一定的价值和体积.下面的问题就产生了:如何从这几种物品中选择才能使得放入背包的物品的价值最大.这就是著名的背包问题(KnapsackProblem).令b表示背包的最大容量,整数1,2,…,n表示n种可以选择的物品,聊,q分别表示第J种物品的价值和体积.背包问题的数学公式可以表示为:n暇P)m“∑pjxjJ=ls.t.∑ajxj≤b,j=txj≥0,qinteger,J=l。…,nt其中xj代表第J种物品被选择的数目.当xj∈{o,1}时,同题(KP)就是我们所熟悉的0-1线性背包问题.线性背包问题之所以得到了深入的研究,是因为很多实际问题都可以表示为线性背包问题.而在很多情况下,在经济管理与工业生产中,许多问豚的数学模型却是非线性的,由此产生的最优化问题就是非线性背包问题.非线性背包问题应用广泛,其中包括生产计划,资金预算,网络系统可靠性等.尽管非线性背包问题有着重要的应用,由于问题的困难性。这类问题在文献中并没有受到足够的重视,缺乏有效的算法或算法的实现经验.非线性背包问题的一般形式可表示为:(NKP)maxm)=∑,j(q)j=lst.g(z)=∑.qAxj)≤b,fJ≤qSuj,xjinteger,J=1,...,n.本文将用到一些概念,下面加以简单的说明2004年上海大学硕士学位论文2定义1.1.1某个数学规划限制全部或部分决策变量取整数值,称为整数规划;如果限制全部决策变量都取整数值,就称其为纯整数规划;如果仅限制部分决策变量取整数值,则称其为混合整数规划;如果所有决策变量取值仅限于0或者』,则称为0.i规划,这种决策变量称为止』变量.定义1.1.2若规划中目标函数及约束函数都是线性函数,称它为线性规划;否则,若其中至少有一个是非线性函数,则称它为非线性规划.特别地,若目标函数为二次函数,且约束函数是线性函数,这种非线性规划为二次规划.定义1.1.3如果一个函数可以写成若干十一元函数和的形式,则称其为可分的.即若,知1,x2,…,。。)=,l啊1)+12(z?)+…+^(z。),则称函数,是可分的.定义1.1.4假设函数,是定义在集合D上的函数,如果对VXl,z2∈D且zlS2;2都有,(z1)≤,(。2),则称函数,在D上是非减的.定义1.1.5称Dc酞”是一凸集是指如果对V.TI,x2∈D和A∈爬,0SA≤1,有^01+(1一A)z2∈D定义1.1.6如果DcR,-为一凸集,,:D—R为凸r凹J函数是指如果对V:gl,。2∈D和A∈R,0≤^≤1,有,(A。l+(1一A)。2)≤(≥)A,(z1)+(1一A),(z2)我们这里讨论的目标函数以及约束函数都具有单调性,所以这个问韪可以称为单调规划问题.根据目标函数的凸性,我们可以将此类问题分为两类:定义1.1.7在本文的问题rⅣK列中,如果目标函数是凹函数,则称此规划为凸背包问题;否则,如果目标函数是凸函数,则称此规划为凹背包问题.定义1.1.8【。J是小于等于z的最大的整数,而fz]则是大干等于z的最小的整数.§1.2非线性背包问题的模型非线性背包问题有着广泛的应用,主要包括资金预算(CapitalBudgeting)([33]),生产计划(ProductionPlanning)(f31】),市场生产(Marketing)([321),分层抽样(Strati—fledsampling)([35]),网络中系统可靠性(SystemReliability)([34][13][9]),制造业中容量计划(Capacityplanninginmanufacturingnetworks)(f13】)等,本节介绍三个模型.2(X)4年上海大学硕士学位论文31.2.1.制造业中容量计划问题许多制造业系统都可以看作是一个排队的阿络模型.其中,网络中的一个结点代表一台机器或者一个工作站,制造业容量计划问题就是给定一个总的费用约柬值,使得工作站的服务耗用最小.这个问题可描述成下面的样子;(MCP)rain∑fj(zj)j=lst.∑毋(q)<6,j=l0兰≈≤“J.。jinteger,J=1,..,n,这里我们记;n:网络中工作站的个数;筇第J个工作站的服务率(即决策变量);矗(q):第j个工作站达到容量q所需要的费用(凸函数);gj(xi)=幻岛(≈):第J个工作站工作需要的平均投入费用;6一:第J个工作站完成每个工作需要的平均投入费用;Lj(zj):第j个工作站需要完成工作的均值,具体的函数形式在下面i6:整个工作过程中网络所允许的总投入费用;%:第J个工作站顾客的到来率(对V^∞>o);∞,:第J个工作站等待顾客的时间方差的平方项系数;csj:第j个工作站服务时间方差的平方项系数;BitranandTirupati([38])用下面的函数来近似Lj(xj),并证明了岛(q)是q的凸函数:Lj(xj)=∞/q+((。q+c5J)督/(2q(勺一∞)))^(∞,q,cat,c勺)其中味^p一2竹勺∞cq)(。J一7j)/37j(caj+csi))ifcaj≤1JC勺ff,otherwise1.2.2.分层抽样中的最优样本配置我们来考虑如何估计人口中值p的值F.一个解决此问题的方法就是把人口分成n类,从每类中抽样,人口中值就可以描述为这n类中抽样平均值的加权和.2004年上海大学硕士学位论文4从每类中抽取样本的数量问题就可以形成一个非线性背包问题的模型,其中整数决策变量表示每类中样本的规模.这类问题可以表述为在给定的抽样费用预算下使得估算值§的方差最小.抽样费用函数可以为线性函数也可以为非线性函数(【39】【35】).我们这里考虑约束函数为线性函数的情况.(SAMP)miny(F)ns.t.∑bjxj≤b,j=llj≤qS2b,xjinteger.J=1,...,n,这里我们记:n:分成类的数目;%:每类中样本的大小即决策变量(J=1,…,n);Nj:第J类中抽样单元的数目;Ⅳ:所有类中抽样单元的数目(N=∑譬1%);脚:第J类的实际中值大小;一,:第J类的标准方差;矾:第J类的样本中值;“:人口中值;6:所有可用的抽样费用;bj:在第J类中调查一个单元所需的费用.Cochr∞([35])指出,p的无偏估计量萝可以由所有类的样本中值的加权来计算,也就是可=∑饕lN/F/N.方差估计由下面的公式给出:y(口)=(1/N2)∑孵霹(屿一q)/(^。q).j=l令吗=(Njaj/N)2,D=∑裟i由/坼,问题(SAMP)可以写成:(SAMP’)min∑djlzJ—Dj=ls.t.∑bqsb,j=l0≤叶≤“j,qinteger,J=1,...,n-注意到在(SAMP’)中,目标函数是一个可分的凸函数,约束函数是一个线性函数,所以它是一个凸背包问题.2004年上海大学硕士学位论文1.2.3.系统可靠性问题5对于—个N级串联模型,问题在于如何进行最优的冗余分配,使得在给定费用约束下系统的可靠度最大.如图(1.1).数学模型可表示为:(蛐)maxR。=ⅡnAxJ)j=tnst.∑gi(xj)≤b,J。10Sxj≤uj,2jinteger,J=1,-..,n,这里我们记:见:整个系统的可靠度;Rj(%):第J个子系统的可靠度;gj(Xj):耗费在第J级上的费用;6:可用费用的总数;lj:第J个子系统最少的级部件数;“第J个子系统的级部件数;uf:第J个子系统最多的级部件数.如果我们把(SR)的目标函数取对数。这样它就可以转化成一个(NKP)问题图1.1:串并联系统2004年上海大学硕士学位论文6§1_3本文工作概要本文的主要工作是把非线性背包问题转化成我们所熟悉的0-1线性背包问题,然后通过解这个o-l线性背包问题来解对应的非线性背包问题.在【3】中Hochbaum把凸背包问题转化成一个等价的o_1线性背包问题,并提出用“贪婪”算法得到与o-1线性背包问题相应的连续解,然而并没有给出数值结果.本文将在第三章将此方法给予介绍,并利用隐枚举法解相应的0-1线性背包问题,最后给出了数值结果,我们把这种方法称为0-1线性化方法.而对于凹背包问题则不能直接利用Hauchbaum提出的这个0-1线性化方法.我们用—个线性函数来逼近目标函数,而约束条件不变,这样我们就得到了一个目标函数是线性函数的凸背包问题,利用o.1线性化方法我们就可以得到凸背包问题的最优值,很容易证明它是原凹背包问题的一个上界,而此时得到的最优解代入原问题就得到一个下界.由于函数具有单调性,我们可以的并集的形式.接下来就可以在这些整箱子中解类似的问题,直到找到原问题的最优解.这种方法我们称之为凹背包问题的o-1线性化分支定界法,在第四章中我们给出了主要算法及数值结果.由于要解0_l线性背包同题,我们还介绍了求解m1线性背包问题的几种经典算法.借助于“区域割”技巧去掉定义域中的一些点,并把余下的区域表示成多个整箱子第二章现有主要算法介绍文献中求解(NKP)问题的算法大多是分支定界算法(【12㈣).当(NKP)为凸背包问题,即以z,)为凹函数,缈(z,)为凸函数时,由于相应的连续松弛问题是一个凸规划问题,可以用成熟的非线性规划方法来求解;而当目标函数,j(z,)为凸函数,约束函数gj(*j)为凸函数时,对应的连续松弛问题是一个全局最优化问题,直接求解将会很困难.另一类方法则是借助了函数的可分性而形成的动态规如算法([11J[7J)和对偶算法(【41),再或者就是分支定界法与动态规划技巧的结合(【51【81).Cooper指出任何求解多维非线性整数规划的技巧都可以用寒求解单一约束的问题(NKP)([2】【101).Lawler在([361)中简单的描述了一个近似算法求解(NKP),Hochbaum([37])也提出了一个解决凸背包问题的算法,但是没有给出数值实验结果.本章介绍了四个算法:借助松弛技巧的Pegging算法。动态规划算法,动态规鲻与分支定界相结合的混合算法,拉格朗日对偶和区域割法.§2.1Pegging算法本算法所考虑的同题(NKP)要求且标函数是可微的单调的凹函数,约束函数是可微的单调凸函数.此算法主要是一个分支定界算法,其中在每个结点处都利用KKT条件求解(NKP)去掉变量整数约束的松弛问题.尤其当决策变量可以表示为单约束函数的拉格朗日乘子的函数形式时,本节给出的求解连续松弛问题的算法非常有效.2.1.1.解连续变量问题令(cP)表示(NKP)的连续松弛问题:(eP)max∑厶(q)st∑野(≈)s6,j=1‘≤。JS“,,J=1,...,n对于把整数约束去掉的这类松弛问题,一般都是利用KKT条件求解.最初研究的此类问题是带有单线性约束的二次背包问题,后来就推广到一般的具有可分的凹的72004年上海大学硕士学位论文8目标函数和单线性约束的问题.类似的研究也用到了具有可分的凹的目标函数和单约束∑冬。q=b以及连续有界变量约束的问题.(CP)的KKT条件为下面的一些公式:∑毋(勺)sb(2.1.1)i=i0≤zJS呵O=I....,n),(2.1.2)aD/a,。j一^a毋/Oxi一20+1吩=oo=l,...,n)(2.1.3)A(6一∑毋(≈))=0,(21.4)J=1吩(fJ—q)=oO=1,...,n),(21.5)1蜥(q一吩)=00=1,...,n),(2.1.6)叶≥00=1,..,n),(2.1.7)q≥ou=1,.,.,n),(2.1.8)A>0.(2.1.9)其中A,叱,屿分别为∑≥1毋(q)曼b,如曼q,qs嘶的拉格朗日乘子-令弓(A)表示方程aD/axj—Aa毋/aq=0的关于A≥0的一个根·考虑下面的表达式,其中∞,q,tq都是乘子^的函数:q^I|^~,、、0一qⅥ;<弓^=v弓∽<似拯吲kb”q蚴ca,={:厶(。)/8zJ一^a9j(b)7。。’;;耄;:;;:qca,={:。厶。q,,。q+。。毋。Ⅵ,,。。,;i,f弓蓄j。(A。,)≥<quj可以证明当A>0时,z,(A).叱(A)1q(A)满足除(2.3.1)和(2.34)之外的(cP)的所有的KKT条件.寻找最优的乘子^使得q(A),u(^),屿(A)满足剩余的这两个KKT条件则是本小节的主要任务.求解非线性方程aD/oxJ—A锄/知,=0,如果_j(^)2004年上海大学硕士学位论文9可以表示成A的显式形式,则把其带入上面的三个式子,得到(CP)的最优解.否则,就要多次寻找非线性方程的根,增加了算法的困难程度.令”表示最优的拉格朗日乘子,如果r=0,则很容易得到(CP)的最优解,否则,单一的非线性约束就没有了松弛即∑%1毋(q)=b且忽略掉变量的上下界,相应的松弛问题比(CP)更容易求解.由此形成了变量固定(pegging)算法,见(f13】).算法每迭代一次都会将一些不满足上下界约束的变量固定为其下(上)界,这样就减少了下次迭代时要解决问题的规模.当所有没被固定的变量都满足其上下界时,算法在有限步内终止.2.1.2.解整数变量问题本节介绍的是一种分支定界算法.算法开始利用上面介绍的方法求解连续松弛问题(CP).在分支定界法的每次迭代序列中,会产生并要懈两个子问题.如果某个子闻厨的解中有分数变量,则选中此问题进行分支,同时我们可以称这个被选中的子问题为“父问题”.假设在“父问题”的馋中第k个分量z:是分数.把zk≤tzlJ加到“父问题”的约束中就构成了。左子问题”,同样的,把Xk≥fz:1加到“父问题*的约束中就构成了。右子问题”.每进行一次迭代,在保留下来的连续子问题的最小的日标函数值作为(NKP)最优值的一个上界。而任何一个带有整数解的予问题的目标函数值都可以作为(NKP)的—个下界.能达到最大下界值的整数解作为当前最好解.此处用标准的去除原则从“树”上消除一些分支.如果(NKP)的目标函数值的下界等于上界,或者“树”上的所有节点都被去掉时,算法终止.§2.2动态规划算法动态规划就是把有n个变量的决策问题转化成n个单独变量问题的技巧.这样,n个变量的决策问题就被构造成一个顺序求解各个单独变量的n级序列决策问题.动态规划是以“最优性原理”为基础的,它对决策问题能给出一个精确的解.动态规划的“最优性原理”是由Bellman于1957年提出的:“一个最优策略具有这样的特性,即无论初始状态和初始决策怎样。剩余的决策对初始决策所产生的状态来说必须构成一个最优策略.”涉及动态规划问题的关键元素是级,状态,奂策,变换和收益.一个物理的操作的或概念化的系统,可以看作是按一系列顺序的级而向前发展的.在每一级,系统可以用一相对来说较小的参数组来描述或表征,这些参数称为状态变量或状态向量(简称状态)在每一级,不管系统处于什么状态,都要做出一次或多次决策,这2004年上海大学硕士学位论文lo些决策可以依赖于级或者状态,或者二者均依赖.当做了一次决策后,会得到一个收益,同时系统经历了一次变换或转移,到达下一级.按级发展的过程的总目标是使状态和决策变量的某个函数最大或者最小化.我们将研究的问题(NKP)看作一个多级决策过程,其状态变量和状态变换给出为:^^一1=^^一9k(。^).61(A1)。悖.≤黑讯岫。},l(。I),k(h)2k!。。蛐max恻√^(。k)+¨(扎一gk(xk))m=2…,n)一般来说,肌(z々)为非线性函数,所以必须用数值方法求h—gk(x女)=0的§2.3DP&BB混合算法本节给出了一个新的方法求解可分的整数规划问蹶.这个方法是动态规划(Dy-Programming)和分支定界(BranchandBound)的结合.定义h(6)为:^。(6)=max∑疗(q)(23.1)J=lns.t.∑9jCzj)sb,J=lxj∈毋,J=l,…,n,0sqsuj,xjinteger}考虑第≈阶段的情况:Ⅳ“(6)=max∑,J(q)(232)J。1ks.t.∑毋(q)≤6,J。1q∈s』,J=l,…,≈.利用上面的状态变换和“最优性原理”。我们能迅速的导出递推公式:其中靠为k—gk(xk)=0的根,根.除了这一点所引起的不太大的复杂化之外,可以利用上面给出的递推公式计算hk(Ak)和xk(Ak)的表格,然后得到原问题的最优值和最优解.namic其中岛={巧f2004年上海大学硕士学位论文注意到h(6)就是(NKP)的最优值,我们的目标就是计算数列{札(b)},(≈:1,…,n).这些公式和迭代的最优化称为动态规划方法.令《表示(23.2)的可行解的一个子集.一个可行解z∈.《称为被另一个可行解z7∈《占优(dominated),如果满足下面的条件:kk∑gjC弓)s∑毋(叶)J2lj=l和kk∑厶(《)≥∑矗(町),j=lj=l且在这两个不等式中至少要有一个是严格不等式.如果。∈《不霰《中的其它任何元素占优,则我们称z关于《是有效的(efficient).令雒表示(2.3.2)的所有有效解的集合.问题(2.3.1)的所有有效解的集合碍可以由下面的公式迭代丽得;西∈Xf∈X?=Sl且x££xf∈础=x£一lx&,≈=1,…,n其中x2之((茹1,..,茁k一1,z女)l(。l,…,z≈一1)∈x毒一l,士k∈鼠)bXf=如∈x2I∑毋(町)≤6)),J2l鬈={£∈xfIzisefficien£"溉respectto《).如果牙∈霹且∑≥l毋(弓)=万,则虿是(2.31)的一个最优解,其中b由万代替.这个结论可以由占优的定义直接得出,所以寻找(2.3.1)右端项为6时的所有有效解就等价于寻找右端项为bIsb时的所有最优解.找到j《的程序可以简单的描述如下:动态规划方法第一步;设k=1,科=Sl第二步:从硼中消去不可行点构造成.础2004年上海大学硕士学位论文第三步:从xf中消去所有被占优的点构造成磺.第四步;如果k=n,终止.否则令k=k+1,x2=X≈一1x岛,转第二步.第二步中的可行性判断是—个简单的事情,即检查需要的资源数量是否超过可用的资源数量.第三步中的占优判断有点复杂,但是通过([7J)中的链式表,就可以把此步有效的解决.当算法终止的时候,我们就得到了(2.3.1)右端项为b’茎b时的有效解集蟛和相应的最优值:nn,n(∥)=nlax{∑fj(xj)Iz∈群,∑卯(勺)≤bI).j=l』=l注意到最优收益函数矗(∥)是一个在0兰b’≤b上非减的上半连续分段函数.由于这个动态规划方法寻找的是每个右端项为∥≤b时的所有的最优解.现在我们把注意力集中在如何求解右端项为b时的最优解.我们借助于分支定界法来完成这个任务.考虑Vz=(轧…,xk)∈雄,令卢=∑名l9』(z』).我们把卢记作部分解z所消耗掉的资源.对于给定的z∈雄,在第k阶段的剩余问题(residualproblem)为:hk+l(6一卢)2j:帆max,。矗(即)(2删s.t.∑毋(q)≤b一反j=k+lzj∈岛,七十1≤J≤n.这样,假定已经消耗掉资源口,则剩余问题的最大收益就是巩+z(6一卢).对所有的0sksn一1,令UBk+1是函数万的一个上界,即瓦+l(b一芦)≤ⅣBk+l(6一口),V0≤卢≤bUB≈+1可以是(2.33)任一松弛问题的值.而(2.31)的任何一个可行解都可以得到^。(6)的一个初始下界.已经知道的最好的解称为当前解(incumbent),其相应的最优全解不可能比当前解更好,此时称。由界去除.在第k阶段耀中余下的元素记为雄,即.磺=扛∈x£I∑;:1矗(q)+UBk+I(b一∑%l毋(q))>LB}.利用启发式算法可以找到更好的可行解,使得下界改进.如果。’=(。:。.,z:.)是由启发式算法找到的可以与z=(%.,“)∈.磙构成一个完全解,且满足£笔l矗(q)+∑饕k+l疗(z;)>工B,值就可以作为当前的一个下界即工B.上面的提到的上界和下界可以用来去掉一些部分解.如果对r∈.磺,有∑;:lIj(zj)+UBk+l(6一∑;:l毋(q))≤LB,则由。组成的完2004年上海大学硕士学位论文13则(z,一)就可以作为更好的当前解.在第k阶段我们知道^。(6)落在LB和全局上界UB=max—.Jk:I厶(q)+UBk+l(b一∑;:l毋(q))1。∈.醒)之间.如果间隙(UB—LB)非常小,算法就可以终止.为了把分支定界法加入动态规划程序里面,必须重新定义雄为有效解集的一个子集和础=.碓一l×鼠,^=2,…,n.令风+l(6一口)表示(2.3.3)的最优值,f表示解的近似程度.这个混合算法可以描述如下:DP和B2-,B算法第一步:设k=1,x}=sl,LB=日1(6),UB=UBI(6),选择E∈【o,1】,L≥1.如果LB=UB,终止;否则转下一步.第二步:从碑中去掉所有不可行点构造xf.第三步:从《中去掉所有被占优的元素构造雄.第五步:构造雄={z∈雄I∑名l疗(q)+UBk+1(6一∑凳1毋(q))>LB}.min{UB,UB,}z∈雄},LB=§2.4拉格朗日对偶和区域割方法由于函数,和g具有可分性,相应的拉格朗日松弛问题就简化为解n个一维的第四步:如果I雄l兰L设雄=雄,转第九步.第六步:令UB7=max{∑;;l厶(q)+U凤+1(6一∑%l毋(q))l。∈雄),且UB=第七步:令LB’=m“(∑譬l矗(%)+凰+1(6一∑譬1鲫(≈))Imax{LB,LB%如果有必要就改进当前最好值.第八步:如果(UB—LB)/UB≤f,终止.当前解充分接近最优解.第九步:如果e=n,终止,否则揣包含一个最优懈或者当前解是最优解。或者设k=k+1,础=榷一】×S。转第二步.此算法综合了动态规划法和分支定界法,比较经典,但不是很有效.最大化问题.关键问题就是构造一个比较有效的算法寻找最优的拉格朗日乘子.为了降低松弛问题和原问题之间的对偶间隙,我们从区域中去掉某些个箱子,函数的单调性保证被去掉的这些箱子不会包含最优解,余下的区域仍然可以表示成箱子的并集,这使得接下来的松弛问题也是非常容易求解.当对偶间隙为零或者剩下的区域中没有可行点时,算法终止.运用stlrrogttte技巧和次梯度法,可以用此方法来求解多约束的非线性整数规划问题.2004年上海大学硕士学位论文142.4.1.拉格朗日对偶本节将要介绍含有单约束的整数规划问题的拉格朗日对偶问题的特性,给出扰动函数和拉格朗日对偶之间的关系.考虑单约束整数规划:(P)搿{m)lg(z)9),其中,和目都是R“上的连续函数,x是任意的包含有限个整数向量的集合.问题(P)的拉格朗日函数定义如下:L(z,^)=,(z)一A(g(T)一6),A≥0.则(P)的拉格朗日松弛问题为:(工^)d(^)2m。∈a.YxL(。,^)·令S={x∈X|g(z)≤6),,’=maxx∈s,(。),弱对偶定理总是成立(WeakDuality):d(A)≥,(z),V£∈S,^≥0.所以对所有的^≥0,有d(^)≥,+.问题(P)的拉格朗日对偶问题为;(D)咖4(^)假设S≠0,x\s≠0,则(P)的扰动函数为;u(Ⅳ)。搿{m)J州≤Ⅳ),”∈Ru的定义域为Y=【1,十。。),其中1=min。∈x9(z).很容易看出,函数“J在y上单调不减.由于X中仅存在有限的点,则Y中也存在有限个点ai∈h,+。。)O=1,…,k)使得u有显式表达式:^,01≤Y<a2,2,啦≤Y<a3叫(Ⅳ)=^一l,ak一1≤Y<akA,‰≤Y<oo,2004年上海大学硕士学位论文15其中1=al<a2<…<ak,且^<,2<··<A.令圣={(q,厶)Ij=1,...,研.垂中的点可以定义为u的角点(CorD.erpoints)定义u的上包络函数为最小化一个由u所引导的凹函数:皿(g)=min{h(y)l^isconcaveonyth(y)≥u(雪),V口∈y}.由于u是y上的单调非减函数,所以函数口也是Y上的一个单调非减函数很明显,皿是具有如下形式的一个逐段线性函数t,』.+∈10一aj。)町1≤Y<a,h,J:+∈2(Ⅳ一aj2)nJ2≤Y<ajs皿(掣)=厶Ⅳ一1+{Ⅳ一1(Ⅳ一aiN—1)ajⅣ一l≤Y<ajⅣ,厶ⅣajⅣ兰Y<oo,其中,1=jl<J2<·<如且靠=垒gJk吐+z-gj,。,≈=1,…,Ⅳ一1.由m的函数线性性,我们有:田(Ⅳ)2^rmainR^Y+7(J)S,t.^q+1≥,J,J=1.....k.对任意固定的Ⅳ∈Y,可以引入约束Aai+1≥厶的对偶变量脚≥0,J=l,…,k.问题(I)的对偶问题为:km(Ⅳ)=max∑心,J(j,)J21^∑脚q="1J2lk∑如=1,蜥≥0,J=1,…,kd=z定理2.4.1令(A’,1+)和矿分别是倒和口珂的最优解,且Y=b,则例A‘是对偶问题r驯的最优解且Ⅲ(6)2m^>inod(A)2d(A+)倒对于任意的z,f‘:>0,如果哥∈X满足(g(面),,(暮))=(ni,^),则i是拉格朗日松弛问题(工^.)的一个最优解.2004年上海大学硕士学位论文16证明:见([4】).定理2.4.2Ⅲ设A‘是fDJ的一个最优解,则(L”)至少存在一个可行最优解.而且如果d(A‘)>,+,则(L”)至少存在一个不可行解.f印如果对某个r≥0,同时能得到的一个可行解和一个不可行解,则A+是对偶问题俐的一个最优解.证明:见(㈤.2.4.2.对偶搜索程序由上面的理论,[4】中构造了一个程序来求解(D),且此方法是有限收敛的.其几何意义可以表示为:这个程序在每个循环中都访问到扰动函数u(Ⅳ)的角点,最终得到拉格朗日乘子的最优值,即在皿(Ⅳ)的图象中与直线Y=b相交的那个线段的斜率.此程序的起始点是在壬中找到最低的角点(al,^)和最高角点‰,^),每进行一次迭代就要解一次拉格朗日松弛(以),其中A是一条直线的斜率。这条直线连接两个点:一个是当前最好的可行解,另一个则是离可行点最近的那个不可行解所代表的点,并且随着迭代步数的增加,直线连接的这两个点之间的距离越来越小,即对偶间隙越来越小.2.4.3.拉格朗日对偶和区域割方法假设”是对偶问题(D)的最优解.众所周知,松弛问题(L”)的所有最优解可能都不是原问题(P)的最优解,即对偶间隙一般都会存在的.为了降低对偶间隙和利用对偶搜索找到(NKP)的最优解,利用f(x)和9(2)的单调性,可以得到一个区域割方法(这个将在第四章具体的介绍).将对偶搜索程序和区域割方法结合在一起,可以得到一个收敛的拉格朗日和区域割算法.算法首先把对偶搜索程序运用到(NKP)以得到一个最优对偶乘子以及一个可行解和—个不可行解,记住可行解。在原来的区域中去掉包含这两个可行解和不可行解的整数箱子,并把余下的区域写成多个整数箱子的并集.在第k步迭代中,方法类似,只是把当前最好的可行解最为当前最优解,相应的当前最优目标函数值作为厂的一个下界,而此时的对偶最优值就是,‘的一个上界.为了防止割去箱子以后的子箱子数目增加太多,可以利用弱对偶定理去除一些箱子:这些箱子上的对偶值不超过当前最优解.在每次迭代过程中,要么当前最优解是原问题的最优解,要么(或同时)某些最优值仍在余下的区域中.当上界不超过下界或者余下的区域是空集时,算法终止.具体的算法见(【41)第三章凸背包问题的0-1线性化方法本章考虑凸背包问题(ConvexKnapsackProblem):n(cvgP)maxE厶(q)J=lns.t.∑gj(xj)冬b,J。l如≤xj≤%,zjinteger,j=l,.t“其中五是非减的凹函数,毋是非减的凸函数,q是决策变量,0和吩分别为勺的下界和上界,不失一般性f,和u,均为整数,这里J=1,…,n由于凸背包问题的目标函数是凹函数。约束函致是凸函数,我们可以把函数厶和g,作一个逐段线性逼近变换,将(CVKP)转化成—个等价的o-l线性背包问题,然后通过解这个o-1线性背包问题就可以得到(cVKP)的最优值和最优解。这种方法我们称之为o.1线性化方法.这个方法是Mathur(133】)解二次背包问题方法的一个推广,在㈣)中有此方法酌详细分绍。但是设有数值实验结果.由于这里要解0-i背包问胚,本章介绍了一些求解0.1线性背包问题的算法,最后给出了凸背包问题的0-1线性化方法的数值结果.§3.10-1线性化本节介绍把(CVKP)转化成一个等价的o.1线性背包问题的方法.令zjk=西(≈),其中0≤≈≤uj.定义一个逐段线性函数hj(zj),其断点为{zjk,fAk)},≈={J,fJ十1...,q,函数b(勺)的图像见图(3.1).定义集合刁={≈k,k=0,0+l,..,uj}={gj(1j),9j(1j+1),…毋(q)},j=1,.,n.则凸背包问题(CVKP)可以写成下面的等价形式:tl(EP)maxEhAz,)j=ls.t.∑刁≤b,j=t≈∈乙,J=l,…,n.172004年上海大学硕士学位论文18叱”俨即gi(k)gj(k+1)zj图31:函数hA2j)引理3.1.1凸函数的差分是非减的.即若g(x)是D上的凸函数,zo<Xl<x2且g(x2)丛型,L!f墅2—X27lol—Z0证明:设A=;;暑等,1一^:署焉,则0<^<1且h。十(1。)一纛射篡一z·因为9(z)是D上的凸函数,所以删=9[慨+(1刊珈】蛐(㈦+(1-蝴啪2篡9(。:)+篡删变形得纛№)一㈣】≤鬟№)一州即止止!幽s型.q(x1)j’l—Z0X2.Fl这说明了凸函数的差分是非减的.命题得证引理3.1.2凹函数的差分是非增的.证明:同上.定理3.1.1函数hj(zj)是一个非减的逐段线性的凹函数,其中gj(1j)≤zj≤卯(“,)2004年上海大学硕士学位论文19证明由于^,(z,)是一个逐段线性函数,只需说明其每段的斜率是单调不’震∞即可.由于,,是凹函数,由引理(3.1.2)知差分是非增的,即对固定的J∈{1,2,,n},,J(女+1)一f/k)s疗(≈)一办(≈一1):同样的,gi是凸函数,由引理(3.1.1)知其差分是非减的,即对固定的J∈{l,2,.,n),卯(≈+1)一gj(k)≥,qj(k)一gj(k—1).这样吗的斜率sj≈=箝苷j!};高随k的增加而非I臀结论得证.注意到集合蜀的元素可以用下面的式子来表示:9j(Ij)=m(fJ).毋(fJ+1)=.qi(1j)+【∞(fJ+1)一.gi(1i)所(“,)=.qj(12)十【9j(1j+1)一目Azj)!+‘十【乳(uJ)一gi(uj一1)I-用归纳法,这些式子可以用一个通项表示集合乃中的元素:I∑翟{,十lb(i)一仍(z一1)1wij+n(2,)毋(zJ)={Wij∈{0,1),i=fJ+1…,~IifWlj=0,thenVk>i,wkj=0其中q∈坞.1j+1….,~),J=1….1"It.Nf4创j乃(q)也可以表示这样的形式:|∑翟11+1[矗(z)一疗(i一1)1tOij+,J(0),』(q)一{ICi,∈(0,1},i=Ij十l,…,u』IjfWij=0,thenVk>¨I?¨=o其中q∈蚂,fJ十l,..tIJ},=1一.r1.令Pu=厅(,)一,j(7一1),心,=∞(,)一y一一1),这样(EP)也就是(CVKP)可以写成下面的等价形式:¨ur,}∑∑n一。。十∑,』(1,)(3.1.11J=li=/j十lJ2lnU,tl∑∑“ijwisb一∑gab),(3l2)J=ti=lj十1J21tl,'ij∈fO,1},(3.1.3)VL{wu>0jt“{。-=l,≈<i}(31.4)2004年上海大学硕士学位论文由于奶(2,)是凹函数,贝6由(31.1)一(3.13)组成的(LP)的松弛问题的最优解必然满足式子(31.4).也就是说,式(3.14)从(LP)中去掉之后,问题(LP)依然与问题(CVKP)等价,而此时由(311)一(3.1.3)组成的(LP)的松弛问题是一个典型的o.1线性背包问题,故问题(CVKP)可以通过解一个等价的0-1线性背包问题获得最优解假设w+是松弛问题的最优解,问题(CVKP)的最优解设为z+,则我们有下面的关系z;=∑兰.。:ujj十』,(7=1,….n)问题(CVKP)的最优值等于松弛问题的最优值.接下来的任务就是求解0-1线性背包问题.§3.20-1线性背包问题及其主要算法0-1线性背包问题是一种最简单的整数规划问题,其一般形式为(o—tKP)m“∑乃≈J=1st∑叩J≤b,q∈(o,1}.J=1,…,n其中X,是决策变量.不失一般性,功.ai.b都是大于等于零的数.任何求解线性整数规划问题的算法都可以用来求解0-1线性背包问题(0-1KP),最一般的可以用来解背包问题的方法主要有以下四种:(1)隐枚举法(hnplicitEnu—meration)(见f22][231124j}21m(2)动态规划法(Dynami(PlogIamming)(见{14111511161117】f181[1_91f20i).(3)网络逼近法(NetwolkApptoaches)(见【28][291130]),(4)增广的拉格朗日法(GenrealizedLagrangiatt)(见【251[2611271).而且当约束函数右端项b的值很小的时候,动态规划算法的效果非常有效,但当b很大时,存储量变得很大,用来解(O-1KP)的动态规划算法则显得很失败,而隐枚举法受b大小的改变影响并不大.网络逼近法把背包问题转化成一个最短路问题:由于产生的网络规模太大,这个算法也不是很有效,这里将不给予介绍.我们这里也不介绍方法(4),因为只有我们考虑近似解的时候,增广的拉格朗日方法才能得以运用.由于动态规划对函数的系数有整数要求,这里分两种动态规划来讨论.3.2.i.动态规划一此种算法要求(o一1KP)的约束中变量的系数以及右端项全是整数,即ai(j=1n)和b都是整数2004年上海大学硕士学位论文21令^(Ⅳ)表示背包的容量为Ⅳ从前≈种物品中选择使得(o、lKP)取得的最大值,其中Y=0,1,.,6:^=12…m注意到^(6)就是(O-1KP)的最优值,我们的目标就是计算数列{A(Ⅳ)).k=l,.定义:∑pja,E。j.T%is!I,Xj∈(o.1},J=1,…,k从上面的式子中分离变量‰,女=1,..,n.得到fIllax麒9J=。名茄}m。‘+{5‘,,、l∑型pjxi∑譬:q即≤Ⅳ一。kXk,【。,∈{o,1).J=1….,≈~i其中缸“们一“卜囊嚣≥_一。f一∑jk-:lp声-|nL一∑譬pjx>A一·(Ⅳ一“n)2max{sf∑;二:c。.。≤Ⅳ~n*,1.o∈(o.1},j=i,.,≈一1这样得到了求解{fk(Y)}的迭代公式式子(3,25)说明假设在前k种物品中选择,若在第≈项得到最优值,则余下的空间Ⅳ一毗必须在前k一1中物品中得到最优配置,这就是动态规划的最优性基本原则.注意到初始条件为:川小{,0。::篡2004年上海大学硕士学位论文利用前面的迭代公式,可以在有限步内找到最优值,,。(6).为了寻找最优解,这里要用到一个示性函数:hk(Ⅳ):{0Ilif^(Ⅳ)3^一1(g),if^(Ⅳ)>A一1(Ⅳ)算法3.2.1第一步:k=1,如果0≤Y<al,则,l(Ⅳ)=0,h1(Y)=o;否则如果al曼Y曼b.则,l(封)=P1.hi(可)=0转第二步.第二步:令k=k+1,对所有的Y<ak有A(Ⅳ)=^一l(Ⅳ),hk(y)=0,此时令Y=ak.转第三步.第三步:计算"=肌+A—l(Y—ak)如果t,>^~l(Ⅳ),则令^(Ⅳ)=u,hk(y)=li否则^(口)=^一l(Ⅳ),hk(y)=0转第四步.第四步:如果Y<b令Ⅳ=Y+1.转第三步如果Y=b,转第五步.第五步:如果k<m转第二步;如果k=n,转第六步.第六步:如果‰(Ⅳ)=1.则。k=l,设Y=Y—ak.如果hk(y)=0,Xk=0,转第七步.第七步:如果k>1,令k=k一1,转第六步;如果k=1,终止.算法最后一次执行第五步时就得到了问题的最优值^。(b),第六步和第七步是计算最优解.此程序会在O(nb)步内找到最优解3.2.2.动态规划=此种算法要求(0-1KP)的目标函数中变量的系数全是整数,即Pj(J=1,…,n)都是整数令F,(一)表示在前y个物品中选择使得目标值为,时必须装入背包中物品的最小的容积.对于这个算法,与前面的动态规划一方法类似,也是需要一个迭代公式列表,最终找到最优值.这个公式需要的边界条件即初始条件为:B(o)=0,J=1…_1.迭代公式:E(,)=rain{弓一1(i—Pj)+aj.毋一l(i)},其中.,=1….mi=1,2….结合边界条件,由迭代公式可以得到一个表格,把这个表格中的值按目标函数值的升序排列如下:El(1).毋(1),…,F,。(1):2004年上海大学硕士学位论文Fl(2),最(2),..,晶(2):23Fl(P+),玛(P+),…R(P4)一旦满足R(t)=b的最大值一P‘出现,此算法戟终止,此时P。就是最大的i,也就是目标函数的最优值.由于每个函数值都在0(1)步内完成,这里共需计算0(nP,)次函数的值,所以次算法的计算时间就是O(nP*),3.2.3.隐枚举法当(0-1KP)的目标函数以及约束函数的系数都不是整数时,可以乘一个很大的数使系数变成整数,但是这样由动态规划构造的表格会需要很大的存储量,从而动态规划就不适合用来解此问题了,一种有效而又快速的求解此类问题的方法则是隐枚举法.最早的解(0-1KP)的隐枚举法是由Kolesm-提出的~种宽度优先(breadth.first)的分支定界算法,由于这种算法需要很大的计算机内存和时间太长,Greenberg和Hegerich提出了一种深度优先(depth-first)的分支定界算法,避免了上述弊端.最近Holowitz和Sahni等人在深度优先算法的基础上得到了一个更好的算法.目前很多人又对此方法进行了深入的研究和改进.这里介绍由Hoiowitz和Sahni提出的算法.在这算法中,要用到问题的上界(UpperBounds).接下来就奔绍(0-1KP)的几种上界.假设在问题(0-1KP)中,所有的物品已按下列顺序排成一列:pl/at≥p2/a2≥一n。/n。且令s是满足约束∑;:lq≤b的决策变量下标的最大整数.Datltzig已经证明了下面的定理.定理3.2.1把似ZKP)中的O-1变量约束换成0≤zJ≤lU=1,,n)后的松弛问题的最优解为:rJ=0,,=1.,s:._=0,J=s十2.n:%一l=(b一∑“j)/峨+12004年上海大学硕士学位论文24推论3.2.1u口L=∑j:lPj+L(b一∑j:【nj)m+l/叽+lJ是fo一』Ⅳ刊问题的一个上界值.Martello和TothNx.J-Dantzig的结论给予改进,得到(0-1KP)问题的一个更好的上界.定理3.2.2B1=∑Pj+L(b一∑q)阱2/as+2J,SB2=∑Pj+慨+l一(n¨一(b∑aj))p。/a。JJ21则UB2=max{BL,B2)是(O-1KP)的一个上界.证明:由上面的排序假设和最大整数S知(0-1KP)的最优解可以由两种方法得到:不装入第s+1个物品和装入第s+1个物品.第一种情况很明显不会超过B1的值;第二种情况则必须从前s个物品中去掉至少一个,B2是最好的可能值,假设要去掉的物品重量正好有最小值吼H一(6一∑::las)则最差的值为m/a,,所以B1,B2中最大的一个必然是(0-1KP)的上界.结论得证.定理3.2.3UB2≤UBt证明:我们只霈iiIi明UBl≥B1和UBL≥B2即可.由于风+Ja。+i≥m+2/as+2,所以前者是很明显的.为了得到后者,需要证明S^(b一∑咖阱l/吣l≥Ps+1一(吣I一(6一∑町))ps/‰J=lJ=1世!.就是(D一∑a2(p”1/a州变形得由s的特性我们知b一∑;:1c。一nnl<0,由排序的结果知p,+l/a¨1一ps/‰蔓0.从而命题得证定理3.2.4令矿为满足∑j:1“』sb一“Hl的最大整数,Bj=阱L十∑Pj+L(b—as+lr∑芦叶m+肛+则UB3=max{B1.B3)是fD一』耳纠问题的一个上界且UBa≤uB22004年上海大学硕士学位论文25Mutler和Merbach通过另一种不同的方法改进了(O-IKP)问题的上界UB2定理3.2.5令酊是定理何2』/中松弛问题的对偶变量的最优解,即孵=Pj—ajps+l/a”l,.,=1,.,s,圬=一乃+吩绺÷I/Ⅱs+l,J=s十2,一,n.则UB4=∑+【(b一∑aj)p¨/n州Ⅷlin{(b∑q)Ml/吣·,mniY;IJ≠s+1))JJ21f-.J31是问题的一个上界注意到UB,l不会大于UBl,但是它可以大于等于,等于或小于U岛和UBa,这样可以从UB3和UB4取最小的那个作为(O-IKP)问题的上界,而UB4的计算量要比UB2和UBa的大。Horowitz和Sahni提出了下面的程序,能够很快的得到(O-1KP)问题的最优解.算法中将会用到下面的符号:,,…Ⅲ。=∑整。功q.其中z=(xl,….Xn)是当前得到的一个可行解;^Ⅲ=∑譬ln蚧其中Ⅳ=(玑….,Ⅳ。)是当前得到的一个最好解.算法3.2.2第一步(赋初值):把n件物品按pj/aj的递减顺序排列.令Pn+l=0,fzn+l=00,^cst=,^“。{wr=07=Ⅳ=0第二步(启发式测试):如果rI,>b.令s=7—1:否则令s是满足∑;;。aj≤b的最大整数,计算:=∑::,lq+(6一∑::。‘o)儿十】/f,什l如果几“≥。+,,。。。ible,转第五步;否则转第三步.第三步(构造一个新得当前解):如果“。≤b且i≤n,设b=b一眦,,,。ibl。=,,…。ok+n,z。=1jt=2一1.否则,如果“,>b且t≤m则设孔=0,2={+1重复此步骤,如果i<n.转第二步;否则i=儿重复第三步,转第四步.第四步(保留当前最好解):如果^。,f<,,。ibl。则令^。n=,,。。ibl。,口=。,令j=72,且如果j·。=1设b=b+n¨.,胁,ibl。=,,。㈣№一Pr。X,。=0,转下一步.最优值为km相应的Ⅳ为最优解;否则令6=b十ftk…Ys。ibl。=,,…ibl。一m,zk=0,第五步(返回):寻找使Tk=1且满足&<,最大的々.若没有这样的々存在,i=e+1,返回第二步.这个算法的主要步骤就是开始于通过第三步的迭代构造初始当前解,相当于令{。:0时由定理:j2l得到的整数解.很明显这是一个深度优先的分支定界算法.2004年上海大学硕士学位论文向前移动是指把满足∑笠-n。.qsb的最大的物品放入当前勰中,向后移动则是通过第五步把装入的具有最大下标的物品从背包中去除.当一个向前移动完成时,第二步将会判断进一步前移能否改进当前最优解;在执行第三步的时候,最后一个物品已经考虑过了,第四步判断是否需要改进当前最优解,如果是,当前最优解得到升级.算法会在无需进一步返回时终止.§3.3数值结果这节我们要用3.1节的0-I线性化方法来求解四类问题,给出数值结果,并与Pegging算法和拉格朗目对偶和区域割方法做了比较.3.3.1.问题这里考虑四类凸背包问题:1)最小费用问题(CostMiniinizationPIoblem)C^,PjL∑cj(~一:。)J。lSf∑1。g(1一(1—7-))‘旷q’<6,J=l27≤:o)≤“,,o7integer,J=1,..,n2)二次规划问题(Quadr£tticProblem)(QP)max∑n¨∑ajz。sb.J=If,S.。JS“J3)系统可靠性问题(s、-st@nlReliabilityProblenSRP)m“∑Log(1一(卜。矿。F1¨∑nJ."Cj曼b,J=1fJS.。J≤i‘J,。Jinteger,J21,···,“2004年上海大学硕士学位论文4)分层抽样最优化配置问题(snatifiedSmnplingProblem)(ssP)m“∑一9/.oj=1tlst∑ajxj】。is6,b≤。】Suj,xjinteger,J耸1,…,礼.3.3.2.数值结果及结论本章提出的o.1线性化求解凸背包问题的算法由Fortran90编程,在奔腾4上运行的,计算结果在下面的表格(31-3PC10)中.在所有的计算例子中,f,=1,“,=5,j=1…,n,并设f=(f¨..,f。),“=(虬.UTt)为保证问题存在可行解,约束函数的右端项设为b=g(z)+r(9(u)一9(眺,n)其中r∈(0,1)其它参数选取如下(J=l,(CMP):e5∈[1,50],rj∈【0.8.0.981;(QP)cj∈[i00,300]、a9∈【1150】,为保证单调性,bj=”勺/(2u,),,’∈(0,1);(SRP):70∈{0,8,o9sl,8』∈【l,50i;(SSP):勺∈【25,50】.aj∈【l,50】.这是一些对于0-1线性化方法来说比较容易求解的问题的参数取法,然而当函数的系数在很小的范围内随机产生时,由于隐枚举法优先考虑系数的比值而不注重系数本身的大小,使得此方法则变得异常不稳定,相应的函数系数取法如下,数值结果见表(38)(QP):白∈f100,noJ.q∈f125。1351.为保证单调性,巧=“j/(2t。),7。∈(0,1)在计算过程中,需要用到下面的符号:·n=变量的数目即问题的规模;·‰=随机产生问题的个数;·』,m,A,mAc,.q=分别表示最大,最小和平均值.4)表明四类问题的维数从1000到7000都可以迅速的计算出来,充分表f31.3表明了此算法的有效性.表(3.2)和表(3.5—3.7)的数据表明,随着r即右端项b的增加,问题的可行点增加,从而增加了问题的难度,计算时间也随之延长.比较表(3,G.3.9,310)知,O-1线性化方法解决问题的规模远远大于Pegging方法和拉格朗日对偶和区域割方法,这就给我们下一章求解凹背包问题提供了一个有效的方法.2004年上海大学硕士学位论文垂!:!!【壁坐里2鲤堑堡堕墨f!=!:!)CPU时I司“唧Mill^IaxA”g壹!:!!f里里2塑塑堡堕墨业=!:!》CPU时间礼礼9MinMaxAvg然而,由于解0-I线性背包问题用的是隐枚举法,它本身的“贪婪”性给一类问题造成了困难,从表(3.2)和表(3,8)可以看到到隐枚举法的不稳定性.其中Ns表示20个问题不能在3个CPU小时内完成,LDC则是拉格朗日对偶和区域割方法的缩写.垂!:!!f!垦旦!堕墼堕堕墨业二!:生CPU时间7‘“”Min^IMAvg2004年上海大学硕士学位论文29壅!:塑墼照堡墨业三!:盟CPU时间“礼pMinMaxAvg垂!:鱼!!塑墼堡鳖墨(!:三!:12CPU时间“””MinMaxAvg垂!:!!fg里)塑塑焦鳖墨(!:三!:!)CPU时间““”MinMaxAvg垂!:!!f旦里)塑塑焦堑墨f!:三!:12CPU时间”唧MillMaxAvg2004年上海大学硕士学位论文30丧!:!!f鱼塑笪墼笪堕墨业三!:j)CPU时间jnTt|’MinMaxAvg2塑墼焦堕墨(r=o.7)CPU时间““9MinMaxAvg表3.10!兰旦曼查羹墅i鱼里2塑鍪焦堡墨寸=o.7)CPU时间71”9MillMaxAvg表3.9.£!g坚竖查鎏墅I鱼1第四章凹背包问题的0ml线性化分支定界算法考虑凹背包问题(ConcaveKnapsackProblems)“(CCKP)in3x,(z)=∑屯(勺)J2lnstg(z)=∑9_』(q)≤b,J=lz∈X=(bS。Jsuj,xjinteger,J=1,...,n),凹背包问题在经济规模的最优化模型中经常出现.由于目标函数是一个凸函本章首先介绍了函数的线性逼近,然后又简要介绍了区域割技巧和整数规划中§4.1线性逼近令n,,j∈z”,f』≤OJ≤j屯≤“P其中“=(ol、,n。)口=(口1...,岛。)考虑CCKP)的子问题:(5尸)II)r'IX“小=∑乃(。),=l㈧Ⅳ(。):∑珊(.F.)sb,J=l&J≤oJS卢,.x5integer,J=l,.,”3l其中乃和毋都是非减的凸函数,q是决策变量,0和u,分别为q的下界和上界,不失一般性1,和啦均为整数,这里J=l…,n.数,其相应的松弛问题是一个全局最优化问题,不好求解.由于凹背包问题与凸背包问题的区别就在于目标函数的凸性,而我们知道在第三章中o.1线性化方法求解凸背包问题非常有效,这里我们提出一个0-1线性化分支定界算法,即首先用一个线性函数逼近目标函数,构造一个目标函数是线性函数的凸背包问题,接下来利用第三章中的O-1线性化方法得到凸背包问题的最优值与最优解,且此时得到的最优值是原问题(cc,I(P)的一个上界,把得到的这个最优解带入原问题(CCKP)的目标函数中,就可以得到一个下界,结合分支定界方法和区域割技巧可以容易得到原问题的最优值与最优解.的分支定界算法,并给出了凹背包问题的0-1线性化分支定界算法,最后给出了数值结果2004年上海大学硕士学位论文则在区间h,』‘]上,J扛,)的上逼近凹函数为过两点(%,^(%)),(岛,^(口J))的一条直线:Lj(xj)=,J(q)+sj(xj—nJ),其中旷{∥鬟线性逼近函数见图(4.1)所以/(x)=∑釜。疗(q)在箱子陋,捌的上逼近凹函数可以35}塑o¨:¨O2(1406081310。120140150180200图q1一“,)的线性逼近函数写为:T,““L(r)=∑与(q)=∑(方(nJ)一s,cq)+∑sjXjJ=1J=lJ=1令s。=∑≈-(乃(q)一sjQj),别我们就可以得到子问题(sP)的线性上逼近问题“Pm地∞=}严,量咖0=乃<一饥吖<一T,印。∑岸≤毋。∑州渤。m魄2004年上海大学硕士学位论文33其中s,是L(x)中z,的系数,so是L(z)的常数项.由于^是非减的函数,所以sj≥o(j=1,…,n).再加上工,(z,)是线陉函数即凹函数,从而知(LSP)是一个带有线性目标函数的凸背包问题,接下来的任务就是把(LSP)转化成一个等价的0-1线性背包问题来求解.事实上,如果.r+是(LSP)的一个最优解,,+是(CCKP)的最优值,则我们有,(矿)≤f’兰L{x+),即由线性逼近得到的问题的最优值是原问题的一个上界,而此时得到的最优解带入原问题就得到原问题的一个下界.这样可以利用分支定界方法逐步缩小上下界的距离,宜到找到原问题的最优值.为了尽快寻找到问题的最优解,这里用到了单调性和区域割方法.§4.2区域割方法令n,口∈z“,其中z,t表示”中整数点的集合,【n,例表示由a,p组成的箱子(hyI)el·rectangle),即h例=缸lOe。≤q≤岛,J=l,…,n)定义(a,卢)为陋,剜中整数点的集合:(a,p)=II(0:9.日)=(OLl,01)בx(om口n).J:1集合(a,口)称为一个整箱子.为方便起见,如果n菇卢,则定义h口】=(。,口)=0.令k(2h,f,,)、t一(¨j...¨.)则(CCKP)中区域x的整数点就可以表示为(2,t‘)由,。gj的单调性,我们有下面的结论:性质4.2.1如果T∈(2t。)是(CCKPJ的一个可行点,则对V焉∈(1,z)都有,(i)≤,【z),所以(2,i)可以从(1,t。)中去掉而不会丢掉fCGK引的任何最优解.下面的引理则说明(2,u)\(f.X)可以分解为多个不相交的整数箱子的并集,从而可以在得到的每个小整数箱子上都可以解(LSP),可以改善整个问题的上界与下界引理4.2.I令A=(n口)且B=(1.占),其中n,口,1,6∈z”且n≤1曼d≤卢.则-4\B={u知。(Ⅱj,-。I(n。6。)×(如+l,岛)×Ⅱ::,+l(叫,觑)))u{u等,(n留(%以)×(n,,∞一1)×n5j+l(。。,t)))证明见(㈤例4.2.1“0,3)×((1.∞}\{(1.2j×(1.∞)(0.:埘U“l2)×《0.0”2004年上海大学硕士学位论文§4.3整数规划中的分支定界方法考虑一般的整数规划问题:IP)ZIp=ma.x{f(x):32∈s}整数规划中的分支定界就是利用松弛等方法将问题的可行域S划分为一些子集(sd(j=l…,≈)的形式,然后在这些子集上求解相应的规划问题,最终根据上下界得到原问题最优解的一种方法.定义4.3.1如果U名l岛=S,则称(岛,J=1…,k)是S的一个分割(division);如果Snsj=O(i,j=1,..,k,i≠J).则称这个分割为S的一个剖分(partitio州.性质4.3.1令(IP’)4P=m≈x{f(x):。∈岛),其中{岛)÷:I是S的一个分割,则zip=maxj:l¨,^。;P.此性质说明如果整数规划问题在可行域S上很难求解,且在更小的集合上比较容易求解,则可以把可行域进行分割,而且这个步骤可以重复进行,这样一个分割可行域的过程称为一个枚举树,对于给定的一个父结点如Sl,其子结点Sll,S12,S13就代表了它的一个分割.定义4.3.2假设s被分离成子集{Sm.瓯),如果确定sJ没必要继续分离,则称S可以从枚举树中剪除,即分支定界中的剪枝.性质4.3.2在枚举树中,如果有下面三种情况中的一种发生,鱼都可以被剪枝:1,不可行性:S=0:2,最优值性:得到了(,P)的最优值;3.值占优:在此结点得到的最优值小于原问题的当前最优解.下面给出一个最基本的求解整数规划(IP)的分支定界算法.其中工表示整数规划问题(IpJ)的集合,i是原问题(,P)的下界,而i,则是原问题(,尸)的一个上界算法4.3.1第一步(赋初值):L:“,P)}S)=S.jo=。。,!=一。。第二步(终止标准):如果L=(i】,则㈨如果!>一。c此时的下界i就是原问题的最优值;rW如果i=一。c.则S=0第三步(问题的选择与松弛):从£中选择一个问题(』纠),考虑其松弛问题(兄纠),2004年上海大学硕士学位论文35如果松弛问题存在最优解.F名.相应的最优值为。女。并把此问题从L中减掉.g四步(剪枝):rⅡJ如果:二≤i,转g二步;,"如果砝《Sj,转第五步;俐如果z南∈0且z★>i.令!=晶从L中去除所有zjsi的问题,如果。☆=zi转第二步,否则转第五步.第五步(分支):令(su}翟l是与的一个分割,把一zij=。h(J=1,…,k)的子问题放入集合L中,转第Z-步.§4.40-1线性化矜支定界算法本节把O-1线性化和分支定界法结合起来,借助于区域割技巧,构造了一个求解非线性凹背包问题的算法.算法中要用到下面的符号:·.。㈣。表示当前最好的可行解;·^。表示当前最好解相应的目标函数值;·n表示有可能存在最优解的整箱子的集合;·x‘表示在第≈次迭代中存在的整箱子的集合,算法4.4.1初始步r峨初值J’如果.B=f对于(CCKP)是不可行的,则原问题没有可行解,终止.否则,令。‰£=f,^州=,(。fle“),X1=(1,Ⅱ),Y1=X1,Z‘=0k=1.第一步:陇性逼近/?考虑每个(d,口)∈p,如果g(a)>b,则令Y‘:=Y‘\(o,口);如果g(口)≤b.则矿=。{且L(x3)=弹扩)=,(p):否地通过用隐枚举法解(o-t即)以得到阻sP)的最优解令3。1是化sp)的最优解.如果,(矿)>^。m设‰“=,(矿),lbj~t2Z+第二步r去除J?令j)=0】对于每个(n,伪∈X。=YouZ‘,如果L(x3)>^“,令f2:=Qu(nn如果r)=01终土,。“。f是rc1CⅣ州的一个最优解.第三步件tJ分与定界√j令,㈧,,)表示在(吼d)上解(LSP)而得到的L(矿)的上界.选择(5.卢)∈n作为获得最大值,,(“,口】的整箱子:^27’(i、口)2(嬲{7㈤疗)令砂+1表示从n中去除(d,声)后的整箱子.令矿表示当&=a,口=口时伍s刊的最优解.Y。+1=(a.西)\(a,i8)2004年上海大学硕士学位论文36利用引理“2.纠把Y‘71剖分成整箱子的并集的形式.设Xk+l:yk+lUZk+1.k:=k+1,转第一步.例4.4.1求解非线性凹背包问题:nick2x{+z】+?;+3x2st譬;+34xl+2x;+1822≤109,0≤。J≤3,。Jinteger,.j一1,2Step0:令f=(o,o),¨=(3,3)由于目(f)=0<b=109,则令。‰c’=f,^。“=,(。b。“)=0,X1=Y1=(1,Ⅱ)=(o,o)×(3,3),Z1=D,≈=1.Stepl:9(uj_183>b=109,则构造(LSP):(LSP)iil&x7。1+6x2stz{+34x1+2x;十18x2≤109,0≤xj≤3,xjinteger,J=1,2.(0—1KP)mgx7wl+7[t:2+7w3+6t174+6w5+6w6st35.’i+37“12+39wa+20w4+24iv5+28叫6曼109,wi∈{01},J=1…..6(LSP)的最优解为矿=(1,3),最优值为L(矿)=25,得到原问题的一个上界.把矿Step2L(。。)>^“,转下一步.Step3:构造x2=(f,u)\(f、_5)=(o.o)×(33)\(O,1)×(o,3)=(2,3)×(o,3),解:把(LSP)转化成一个等价的(0-IKP)问题:利用隐枚举法得(0-1KPj的最优解为w5=(1,0,0,1,1,1),最优值为。=25,故得带入原问题的目标函数,得一个下界,(扩)=21.因为^Ⅲ<y(zs),则记^。“=f(29)=21,55一=一=(1,3).转下一步.转第一步2004年上海大学硕士学位论文37Stepl:g(20)<b,9(3,3)>b,则构造(LSP)(LSP)max1111l十6x2一12st、。i+34xl十2z;+18x2≤37,巩∈(2,3),X2∈(0,3).把(LSP)转化成一个等价的(0-1KP)问题:f0一lⅣP1max11201+6w2+6wa+6w4+10st39wl+20w2+24w3+28w4≤37,w,∈{o,1),j=l,…,4利用隐枚举法得(0-1KP)的最优解为l扩=(0,1,0,o),最优值为==16,故得(LSP)的最优解为矿=(2,1),最优值为L(:一)=16.得到原问题的一个上界.把x8带入原问题的目标函数,得一个下界,(矿)=14Step2:因为血“>L(z。),则n=0.算法终止,原问题的最优解为zk“=(1,3),最优值为^w=21§4.5数值结果为了验证算法(441)的可行性和有效性,我们给出了两类凹背包问题的试验数值结果及结论.4.5.1.问题测试问题具有如下的形式:max几,)=∑叩,+“一1j¨,qsfⅣ(z)-∑”,+”;≤b、J=1x∈X=(1js.rJst。,,:rjinteger根据函数系数的选择,这里考虑了两类问题:(P1):y(x)是凸二次函数,其中勺,dj>0,ej=o(.j=ln)(P2):,(z)是三次多项式函数,其中cJ,dj,勺>o(.7=1n)2004年上海大学硕士学位论文38在所有的测试例子中,』J=1.q=5其它参数在以下区间中取值(J=1,…,n):(p1):cj∈【1,30】、呜∈[1,10],啦∈【1.70】,%∈10:1】;(p2):勺∈【l,40】吗∈[1,io],eJ∈【l,20’’啦∈{1,300],∞∈(1,lo].为了保证问题存在可行解,约束右端项的取值为6=g(f)+r(g(¨)一9(2)),其中r∈(o,1)4.5.2.数值结果及结论此算法由Fortran90编程,在奔腾4PC上运行的.数值结果在表格(41.4.2)中,其中要用到下列符号:·n=变量的数目即问题的规模;·rb=随机产生问题的个数;·Min,Max.Ai,g=分别表示最大,最小和平均值.本章提出的0-I线性化分支定界方法可以求解规模从20到140的非线性背包问题,而且从表中可以看出此方法求解此类规模的问题还是比较快的.但是随着问题的规模的增加,在求解过程中产生的整箱子也随之增多,这就增加了内存的需求量.墨!:!!f!12塑塑堕堕墨壁三!:12迭代次数箱子个数CPU时间(s)n~MiIlMaxAvgMinMaxAvgMinMaxAvg2004年上海大学硕士学位论文39壹!:里12塑墼焦蕉墨(!三!:!!迭代次数箱子个数CPU时间(s)“7。”MinMaxAvgMinMaxAvgMinMaxAvg第五章结论本文给出了o_1线性化方法求解非线性背包问题.利用函数的凸性以及单调性直接把凸背包问题转化为一个等价的m1线性背包问题,利用隐枚举法或动态规划方法求解这个o.1线性背包问题,就可以等到原问题的最优解和最优值.在『61中给出了解央凸背包问题的o.1线性化方法,但是并没有给出数值结果.本文不仅给出了o,1线性化解凸背包问题的数值结果,而且还与Pegging方法以及拉格朗日对偶和区域割方法做了数值比较,充分说明了此方法的优越性.凹背包问题目标函数是一个凸函数,不能直接将其转化成等价的0-1线性背包问题,且将变量整数约束去掉后的松弛问题是一个全局最优化问题,松弛问题则不好求解,基于这些困难和凸背包问题的0-I线性化方法的优越性,本文给出了一个o。L线性化分支定界方法,具体做法是先用一个逐段线性函数逼近目标函数,得到一个凸背包问题,利用0.1线性化方法求解得到原问题的一个上界,同时可以得到一个下界,利用分支定界方法和区域割技巧,可以迅速找到凹背包问题的最优解,最后用数值例子说明了此算法的有效性.本文将来可做的工作之一是提出更好的方法来解决0-1线性化之后那些“难”的问题,另外一个工作是寻找更好的方法求解非线性凹背包问题,这方面的其它研究结果可以参看文㈨参考文献【l】KMBrettbauergildBShettyThenonlinearresotlrceallocationprobleHlOptr.R∞一43670-6831995(2】MDjerdjour.KMathur,andHMSalkin.AsunogateIelaxationba.sedonaIgorithmforageneralcbxs,squadrathmukJ—dimensiomflknapsackproblemOust.ResLett.,7:253—258.1988}31DHochbaumAnonlinealknapsack1)roblem却“.ResLett.17:103一llO,1995[4jDLi,XLSun,o.udK*k'KinnonACOlwergelltlaglangiananddomai{1cutme地odt'ornonlinearknapsackproblemsTechnicalreport,DepartmentofSystemsEngineering&EngineeringManagement,TheClfineseUnivetsityofHongKong,Shatin,NT,HongKong,2002submittedibrpnblicatlon[51REMarstenandTLMorinAhybridapproachtodiscretemathematicalprogrammingMathPwgmra,14:21—40,1978【6】KMathur,HMSalkin,andBBMohanty.AllOceOilageneralnon.1inearknapsackproblemsOper。Res.Lett.5:79~81,1986.吲TLMorinandREMarstenAnalgorithmfornollllnearknapsackproblemsMtpntSci22:1147—11581976{8]TLMorinandREMarstenBranchluldbotmdsc_rategiesfordynamicprogrammingOperRes,24:611—627.197619】XLSmlandDLiOptima]it3comlitionaf)dbrancllandboundalgorithm如rCOnstraineatredlltldaheyoptimizationinseIiessystelasOptimEu93:53—65,2009WCooperSm、e3。fmethodsofpurenontioealintegerprogrammingMgmtSci.27:353—361,1981wCooperTimuseofdynamicprogialluniogforthesohltionofaclassofnonlinearprogramnfingNavalResLogistQuart,27:89—95,1980KGuptaandAR乱indranBranchandbotmdexperimentsincoilvexnonlinearinteEerprogrammingMgmtSci.,3i.1533.1546,1985MBretthaueralldBShett)f.Apeggingalgol’itlnnfortilenonlinearresourceallocati。nproblemCornFuters&OperationsResearch.29:505—5272002BellmanSomeapplicationsofthetlleo*Yofdynami‘plogtannning—are'dew,Oper.Res,2(2j:275—288.i954BelhnanNotesOlltiletheot、ofdytlalnicIuOglammiugIV—maximizationoverdiscretesets.Vat:al拧“Loqt^pfⅢrt3:67.7019jG10]M11】M12】O13]K14】R15]R2004年上海大学硕士学位论文16】RBeIhnaaComment011Dantzi91SpaperOildisc、IeteValiableextremumproblemsOper.Res.5(5):723—724195717]RBellmanancLSDte3,}usAppliedd3’liallliCprogralnlnillgPrincetor。University_DmⅫ,196218jGDantzigDiscrete·varialbeextrenlunipioblenlsOpe,兄e5,5(2):266—277,1957191GDantzigLinearprogrmmningandextensionsPrincetonUniuersityPTess,196320】HGreenbergAnMgorithmforthecomputationofknapsackfunctions.JournalofMathe-maticalAnalysisandApplications.,26:159—162,1969211PKolesarAbranchandboundalgorithmfortheknapsackproblemMymt&k13(9):723-735.1967221VCabotAnelnlnlerationalgoritlnnforknapsackproblems,OperRes.18(2):306-311,197023iBFaalandSohttionoithevalue—indepeilclentknapsackproblembypartitioning0p"Res,2l(1):332—336.197324】HGreenhergandRHegelichAI)ranchsear(halgoiitlnnfoltheknapsackproblemMgmtSci16(5):327-332197025_tlEverettGeneralizedLagrangemultiplielinethodforsolvingproblemsofoptimun'lalfoca—tiollofresoulce8OperRes,Il(3):399·471.1963961BFoxandFLandiSearchingtoIthemultiplierinOlleconstraintoptimizationproblems.Oper.Res,18(2):253·262,197027】PHammerandSRudeanuBooleanmethodsinoperationsresearchandrelatedareasNewYork:Sp,inger—Vetlag.196828lGShapiroDynamicprogrammhlgalgorithmsfoitileintegerprogrammingprobleml:TheintegerprogranuaiugploblemviewedasaknapsacktypeptoblemOperRes.,16(1):103—121,196829】GShapiroGeneializedLagiangemultipliersinintegel1)rogranuningOpeT.Res,19(1):68-771971301GShapii(1andHWagnelAfiniterelleWEdalgoIithmfortileknapsackandturnpikemodels()耻,Re.s、1j(2"19-3一11,1967[311HZieglmSolvingc.eltainsingh('oils[1ail/e(](OllVexopt[1nizH.t,fortpl。obIemsinproductionplanningOperResLettl:246—95'21982[32]tlLussandSKGIIpraAllocationofeffo,tIeSotlrcesamongcompetingactivitiesOper.Res,23:360.366,1975f33]KMathur,HAI,SalkinandSMoritoAbranchaadsearchalgoritlnnforaclassofnonlinearkuapsackproblemsOpesResLett,2:155—160.19832004年上海大学硕士学位论文341S43GTzafestasSciOptimizationofsystemreliability:Asurveyofproblemsandtechniquesll:455·486.1980/nt上Syst35IWEGCochranSamplingtechniquesNewYork:Wiley.1963361L.LaMerFastapproximationalgorithmsforknapsackproblems.Math.∞mRes.,4:339一955。1979,371DSHochbaumThenonlinearknapsackproblemSchoolofBusinessAdministrationandIEORDepartment,UnivmsityofCaliiblIlia.Berkeley,1993381GRBitranandDTirupatlTradeoffcurves,Targetingandbalancinginmanufacturingqtteueingnetworks0bHsRe5.37:547—564.1989Hurwitzand391MHHansell、、NWG^In(10wSamplesurveymethodsandtheory,VotnmesIandIINeⅢ}brk:JohnWiley,1953
2023年8月1日发(作者:)
2004年上海大学硕士学位论文摘要非线性背包问题是一类特殊的非线性整数规划问题.由于在管理,经济以及工业生产的最优化模型中的广泛应用,它在非线性整数规划中担当着十分重要的角色.一个非线性背包问题可描述如下:maxm)=∑厶(q)j=1nsc.口(。)=∑9j(q)sb,j=l。∈X=扛10Sxj≤uj,xjinteger}其中疗,毋为定义在吣,q】上的连续实函数,b和邯分别是变量唧的下界和上界.不失一般性,设ff,uj为整数,这里J—l….,n.本文研究的主要问题是两类非线性背包问题一凸背包问题和凹背包问题.根据这两类背包问题的单调性和凸性,本文给出了0-1线性化方法.凸背包问题可以直接转化成一个等价的0-1线性背包问题,然后通过隐枚举法或动态规划法解这个o.1线性背包问题就可以得到原凸背包问题的最优解.本文把这种o.1线性化方法同Pegging方法以及拉格朗匿对偶和区域割方法做丁数值比较,数值结果充分体现了o_1线性化算法的有效性和优越性.丽对于凹背包问题,首先用一个线性函数逼近目标函数,约束条件不变,这样就得到了一个目标函数是线性函数的凸背包问题,接下来就可以把得到的这个凸背包问题转化成一个等价的o-l线性背包问题,同样可用隐枚举法求解这个0-1线性背包问题.为了保证收敛性,我们利用函数的单调性和区域割技巧丢掉一些整数箱子,然后把保留下来的区域分割成一些整数箱子的并集.本文共由五章组成.第一章是前言部分,对非线性背包同题作了简单的介绍,并给出了几个非线性背包问题的模型;第二章介绍了求解非线性背包问题的现有算法;第三章绘出了凸背包问题的o_1线性化方法和数值结果,以及解0-1线性背包问题的几个常用算法,并与Pegging方法。拉格朗日对偶和区域割方法做了数值结果比较;第四章着重介绍了凹背包问题的0_1线性化分支定界算法;第五章是本文工作的总结以及对未来的研究2004年上海大学硕士学位论文展望.n关键询:非线性背包问题,线性逼近,0-1线性化,动态规划法,隐枚举法,Lagrangian对偶,分支定界算法.2004年上海大学硕士学位论文IIIAbstractNonlinearknapsackproblemis8specialclassofnonlinearintegerprogram-mingproblems.Becauseofitswideapplicationsinoptimizationmodelsincludingmanagement,economicsandindustry,thenonlinearknapsackproblemplaysanimportantroleinnonlinearintegerprogramming.Ageneralnonlinearknapsackcanbedescribedasfollows:nrnaxm)=∑乃(q)』=lst.9(。)=∑鲫(≈)56,j=1£∈X=(zf0Sz,≤%,≈integer},andg{arecontinuousreal-valuedfunctionsoll\},、‰{、。band弘jarethelossofgenerality,bandqaleassumedtobeintegers,Thegoalofthisthesisjstostudytwospecialclassesofnoulhiearknapsackknapsackproblemsandconcaveknapsackproblems.Usingtheandtheconvex/tyofthesetwokindsofknapsackproblems,wepro-a0-1linearizationmethod.Aconvexknapsackproblemcanbetransformedanequivalent0-ilinearknapsackproblemThesolutionoftheprimaryknapsackproblemcanbeobtainedbysolvingtheresulting0-ilinearproblembytheimplicitenumerationmethodorthedynamicprogram—method.Wecomparetheproposed0-1linearizationmethodwithPeggingandLagrangianandDomainCutmethod.Thecomputationalresultsthee最ciencyandtheadvantageoftheproposedalgorithm.Thesecondofthisthesisinvestigatestheconcaveknapsackproblems.First,theobjec-functionisreplacedbyalinearestimationfunctiontogetaconvexknapsackwithalinearobjectivefunction.ThentheresultingconvexknapsackissolvedbYtheimplicitenumerationmethodafterbeingtransformedanequivalent0-1linearknapsackproblemToensuretheconvergence,mono—pr曲lemwhere|ilowerboundandtheupperboundoftheargument%respectivelyforj=l,…,n.Withoutproblems:convexmonotonic/typoseintoconvexknapsackmingmethodshowparttireproblemprobleminto2004年上海大学硕士学位论文tonicityanddomaincuttechniqueareusedtoremovecertainintegerboxesandthereviseddomainarepartitionedintoaunionofintegerboxes.Thisthesisisorganizedasfollows.InChapter1,wegivesomebriefintro-ductionofnonlinearknapsackproblemsandillustratesomeexamplesofitsappli—cationsInChapter2.mintroducesomemethodsintheliteraturesforsolvingthenonlinearknapsackproblems.InChapter3,wepresentthe0-1llnearizationmethodfortheconvexknapsackproblemsandreportsystematiccomputationalresults.Wealsocomparethe0-1linearizationmethodwiththePeggingmethodandtheLagrangianandDomainCutmethod.Chapter4focusesonsolvingtheconcaveknapsackproblems.A0-1linearizationmethodandbranch-and-boundmethodisproposedfortheconcaveknapsackproblems.Finally,wesuumlarizethethesisinChapter5andsuggestsomefutureresearchdirections.Keywords:Nonlinearknapsackproblem,linearestimation,0-Ilinearization—dynamicprogrammingmethod,implicitenumeration,Lagrangiandualmethod,brandl一and.boundmethod.rvY上海大学678043本论文经答辩委员会全体委员审查,确认符合上海大学硕士学位论文质量要求。委员(工作单位、职称)答主辩任:,链移广名飚琴』p争毗;擎炙委员●■上大,)泛、n.磁■燃一儿几,n导师●●锶塍舭荚弓兕垫攻答辩日期:≯邸牛.S原创性声明本人声明:所呈交的论文是本人在导师指导下进行的研究工作。除了文中特别加以标注和致谢的地方外,论文中不包含其他人己发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名:釜丑塞日期塑业.点≥7本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定,即:学校有权保留论文及送交论文复印件,允许论文被套阅和借阅;学校可以公布论文的全部或部分内容。(保密的论文在解密后应遵守此规定)签名:盏丑基导师签名:盈:!缝日{}目=芝纽乡第一章前言§1.1问题的提出和定义一个徒步旅行者带了一个背包,他要用背包装入尽可能多的物品而不能超过这个背包的容量.如果有几种不同的物品可以装进背包,且每种物品都有一定的价值和体积.下面的问题就产生了:如何从这几种物品中选择才能使得放入背包的物品的价值最大.这就是著名的背包问题(KnapsackProblem).令b表示背包的最大容量,整数1,2,…,n表示n种可以选择的物品,聊,q分别表示第J种物品的价值和体积.背包问题的数学公式可以表示为:n暇P)m“∑pjxjJ=ls.t.∑ajxj≤b,j=txj≥0,qinteger,J=l。…,nt其中xj代表第J种物品被选择的数目.当xj∈{o,1}时,同题(KP)就是我们所熟悉的0-1线性背包问题.线性背包问题之所以得到了深入的研究,是因为很多实际问题都可以表示为线性背包问题.而在很多情况下,在经济管理与工业生产中,许多问豚的数学模型却是非线性的,由此产生的最优化问题就是非线性背包问题.非线性背包问题应用广泛,其中包括生产计划,资金预算,网络系统可靠性等.尽管非线性背包问题有着重要的应用,由于问题的困难性。这类问题在文献中并没有受到足够的重视,缺乏有效的算法或算法的实现经验.非线性背包问题的一般形式可表示为:(NKP)maxm)=∑,j(q)j=lst.g(z)=∑.qAxj)≤b,fJ≤qSuj,xjinteger,J=1,...,n.本文将用到一些概念,下面加以简单的说明2004年上海大学硕士学位论文2定义1.1.1某个数学规划限制全部或部分决策变量取整数值,称为整数规划;如果限制全部决策变量都取整数值,就称其为纯整数规划;如果仅限制部分决策变量取整数值,则称其为混合整数规划;如果所有决策变量取值仅限于0或者』,则称为0.i规划,这种决策变量称为止』变量.定义1.1.2若规划中目标函数及约束函数都是线性函数,称它为线性规划;否则,若其中至少有一个是非线性函数,则称它为非线性规划.特别地,若目标函数为二次函数,且约束函数是线性函数,这种非线性规划为二次规划.定义1.1.3如果一个函数可以写成若干十一元函数和的形式,则称其为可分的.即若,知1,x2,…,。。)=,l啊1)+12(z?)+…+^(z。),则称函数,是可分的.定义1.1.4假设函数,是定义在集合D上的函数,如果对VXl,z2∈D且zlS2;2都有,(z1)≤,(。2),则称函数,在D上是非减的.定义1.1.5称Dc酞”是一凸集是指如果对V.TI,x2∈D和A∈爬,0SA≤1,有^01+(1一A)z2∈D定义1.1.6如果DcR,-为一凸集,,:D—R为凸r凹J函数是指如果对V:gl,。2∈D和A∈R,0≤^≤1,有,(A。l+(1一A)。2)≤(≥)A,(z1)+(1一A),(z2)我们这里讨论的目标函数以及约束函数都具有单调性,所以这个问韪可以称为单调规划问题.根据目标函数的凸性,我们可以将此类问题分为两类:定义1.1.7在本文的问题rⅣK列中,如果目标函数是凹函数,则称此规划为凸背包问题;否则,如果目标函数是凸函数,则称此规划为凹背包问题.定义1.1.8【。J是小于等于z的最大的整数,而fz]则是大干等于z的最小的整数.§1.2非线性背包问题的模型非线性背包问题有着广泛的应用,主要包括资金预算(CapitalBudgeting)([33]),生产计划(ProductionPlanning)(f31】),市场生产(Marketing)([321),分层抽样(Strati—fledsampling)([35]),网络中系统可靠性(SystemReliability)([34][13][9]),制造业中容量计划(Capacityplanninginmanufacturingnetworks)(f13】)等,本节介绍三个模型.2(X)4年上海大学硕士学位论文31.2.1.制造业中容量计划问题许多制造业系统都可以看作是一个排队的阿络模型.其中,网络中的一个结点代表一台机器或者一个工作站,制造业容量计划问题就是给定一个总的费用约柬值,使得工作站的服务耗用最小.这个问题可描述成下面的样子;(MCP)rain∑fj(zj)j=lst.∑毋(q)<6,j=l0兰≈≤“J.。jinteger,J=1,..,n,这里我们记;n:网络中工作站的个数;筇第J个工作站的服务率(即决策变量);矗(q):第j个工作站达到容量q所需要的费用(凸函数);gj(xi)=幻岛(≈):第J个工作站工作需要的平均投入费用;6一:第J个工作站完成每个工作需要的平均投入费用;Lj(zj):第j个工作站需要完成工作的均值,具体的函数形式在下面i6:整个工作过程中网络所允许的总投入费用;%:第J个工作站顾客的到来率(对V^∞>o);∞,:第J个工作站等待顾客的时间方差的平方项系数;csj:第j个工作站服务时间方差的平方项系数;BitranandTirupati([38])用下面的函数来近似Lj(xj),并证明了岛(q)是q的凸函数:Lj(xj)=∞/q+((。q+c5J)督/(2q(勺一∞)))^(∞,q,cat,c勺)其中味^p一2竹勺∞cq)(。J一7j)/37j(caj+csi))ifcaj≤1JC勺ff,otherwise1.2.2.分层抽样中的最优样本配置我们来考虑如何估计人口中值p的值F.一个解决此问题的方法就是把人口分成n类,从每类中抽样,人口中值就可以描述为这n类中抽样平均值的加权和.2004年上海大学硕士学位论文4从每类中抽取样本的数量问题就可以形成一个非线性背包问题的模型,其中整数决策变量表示每类中样本的规模.这类问题可以表述为在给定的抽样费用预算下使得估算值§的方差最小.抽样费用函数可以为线性函数也可以为非线性函数(【39】【35】).我们这里考虑约束函数为线性函数的情况.(SAMP)miny(F)ns.t.∑bjxj≤b,j=llj≤qS2b,xjinteger.J=1,...,n,这里我们记:n:分成类的数目;%:每类中样本的大小即决策变量(J=1,…,n);Nj:第J类中抽样单元的数目;Ⅳ:所有类中抽样单元的数目(N=∑譬1%);脚:第J类的实际中值大小;一,:第J类的标准方差;矾:第J类的样本中值;“:人口中值;6:所有可用的抽样费用;bj:在第J类中调查一个单元所需的费用.Cochr∞([35])指出,p的无偏估计量萝可以由所有类的样本中值的加权来计算,也就是可=∑饕lN/F/N.方差估计由下面的公式给出:y(口)=(1/N2)∑孵霹(屿一q)/(^。q).j=l令吗=(Njaj/N)2,D=∑裟i由/坼,问题(SAMP)可以写成:(SAMP’)min∑djlzJ—Dj=ls.t.∑bqsb,j=l0≤叶≤“j,qinteger,J=1,...,n-注意到在(SAMP’)中,目标函数是一个可分的凸函数,约束函数是一个线性函数,所以它是一个凸背包问题.2004年上海大学硕士学位论文1.2.3.系统可靠性问题5对于—个N级串联模型,问题在于如何进行最优的冗余分配,使得在给定费用约束下系统的可靠度最大.如图(1.1).数学模型可表示为:(蛐)maxR。=ⅡnAxJ)j=tnst.∑gi(xj)≤b,J。10Sxj≤uj,2jinteger,J=1,-..,n,这里我们记:见:整个系统的可靠度;Rj(%):第J个子系统的可靠度;gj(Xj):耗费在第J级上的费用;6:可用费用的总数;lj:第J个子系统最少的级部件数;“第J个子系统的级部件数;uf:第J个子系统最多的级部件数.如果我们把(SR)的目标函数取对数。这样它就可以转化成一个(NKP)问题图1.1:串并联系统2004年上海大学硕士学位论文6§1_3本文工作概要本文的主要工作是把非线性背包问题转化成我们所熟悉的0-1线性背包问题,然后通过解这个o-l线性背包问题来解对应的非线性背包问题.在【3】中Hochbaum把凸背包问题转化成一个等价的o_1线性背包问题,并提出用“贪婪”算法得到与o-1线性背包问题相应的连续解,然而并没有给出数值结果.本文将在第三章将此方法给予介绍,并利用隐枚举法解相应的0-1线性背包问题,最后给出了数值结果,我们把这种方法称为0-1线性化方法.而对于凹背包问题则不能直接利用Hauchbaum提出的这个0-1线性化方法.我们用—个线性函数来逼近目标函数,而约束条件不变,这样我们就得到了一个目标函数是线性函数的凸背包问题,利用o.1线性化方法我们就可以得到凸背包问题的最优值,很容易证明它是原凹背包问题的一个上界,而此时得到的最优解代入原问题就得到一个下界.由于函数具有单调性,我们可以的并集的形式.接下来就可以在这些整箱子中解类似的问题,直到找到原问题的最优解.这种方法我们称之为凹背包问题的o-1线性化分支定界法,在第四章中我们给出了主要算法及数值结果.由于要解0_l线性背包同题,我们还介绍了求解m1线性背包问题的几种经典算法.借助于“区域割”技巧去掉定义域中的一些点,并把余下的区域表示成多个整箱子第二章现有主要算法介绍文献中求解(NKP)问题的算法大多是分支定界算法(【12㈣).当(NKP)为凸背包问题,即以z,)为凹函数,缈(z,)为凸函数时,由于相应的连续松弛问题是一个凸规划问题,可以用成熟的非线性规划方法来求解;而当目标函数,j(z,)为凸函数,约束函数gj(*j)为凸函数时,对应的连续松弛问题是一个全局最优化问题,直接求解将会很困难.另一类方法则是借助了函数的可分性而形成的动态规如算法([11J[7J)和对偶算法(【41),再或者就是分支定界法与动态规划技巧的结合(【51【81).Cooper指出任何求解多维非线性整数规划的技巧都可以用寒求解单一约束的问题(NKP)([2】【101).Lawler在([361)中简单的描述了一个近似算法求解(NKP),Hochbaum([37])也提出了一个解决凸背包问题的算法,但是没有给出数值实验结果.本章介绍了四个算法:借助松弛技巧的Pegging算法。动态规划算法,动态规鲻与分支定界相结合的混合算法,拉格朗日对偶和区域割法.§2.1Pegging算法本算法所考虑的同题(NKP)要求且标函数是可微的单调的凹函数,约束函数是可微的单调凸函数.此算法主要是一个分支定界算法,其中在每个结点处都利用KKT条件求解(NKP)去掉变量整数约束的松弛问题.尤其当决策变量可以表示为单约束函数的拉格朗日乘子的函数形式时,本节给出的求解连续松弛问题的算法非常有效.2.1.1.解连续变量问题令(cP)表示(NKP)的连续松弛问题:(eP)max∑厶(q)st∑野(≈)s6,j=1‘≤。JS“,,J=1,...,n对于把整数约束去掉的这类松弛问题,一般都是利用KKT条件求解.最初研究的此类问题是带有单线性约束的二次背包问题,后来就推广到一般的具有可分的凹的72004年上海大学硕士学位论文8目标函数和单线性约束的问题.类似的研究也用到了具有可分的凹的目标函数和单约束∑冬。q=b以及连续有界变量约束的问题.(CP)的KKT条件为下面的一些公式:∑毋(勺)sb(2.1.1)i=i0≤zJS呵O=I....,n),(2.1.2)aD/a,。j一^a毋/Oxi一20+1吩=oo=l,...,n)(2.1.3)A(6一∑毋(≈))=0,(21.4)J=1吩(fJ—q)=oO=1,...,n),(21.5)1蜥(q一吩)=00=1,...,n),(2.1.6)叶≥00=1,..,n),(2.1.7)q≥ou=1,.,.,n),(2.1.8)A>0.(2.1.9)其中A,叱,屿分别为∑≥1毋(q)曼b,如曼q,qs嘶的拉格朗日乘子-令弓(A)表示方程aD/axj—Aa毋/aq=0的关于A≥0的一个根·考虑下面的表达式,其中∞,q,tq都是乘子^的函数:q^I|^~,、、0一qⅥ;<弓^=v弓∽<似拯吲kb”q蚴ca,={:厶(。)/8zJ一^a9j(b)7。。’;;耄;:;;:qca,={:。厶。q,,。q+。。毋。Ⅵ,,。。,;i,f弓蓄j。(A。,)≥<quj可以证明当A>0时,z,(A).叱(A)1q(A)满足除(2.3.1)和(2.34)之外的(cP)的所有的KKT条件.寻找最优的乘子^使得q(A),u(^),屿(A)满足剩余的这两个KKT条件则是本小节的主要任务.求解非线性方程aD/oxJ—A锄/知,=0,如果_j(^)2004年上海大学硕士学位论文9可以表示成A的显式形式,则把其带入上面的三个式子,得到(CP)的最优解.否则,就要多次寻找非线性方程的根,增加了算法的困难程度.令”表示最优的拉格朗日乘子,如果r=0,则很容易得到(CP)的最优解,否则,单一的非线性约束就没有了松弛即∑%1毋(q)=b且忽略掉变量的上下界,相应的松弛问题比(CP)更容易求解.由此形成了变量固定(pegging)算法,见(f13】).算法每迭代一次都会将一些不满足上下界约束的变量固定为其下(上)界,这样就减少了下次迭代时要解决问题的规模.当所有没被固定的变量都满足其上下界时,算法在有限步内终止.2.1.2.解整数变量问题本节介绍的是一种分支定界算法.算法开始利用上面介绍的方法求解连续松弛问题(CP).在分支定界法的每次迭代序列中,会产生并要懈两个子问题.如果某个子闻厨的解中有分数变量,则选中此问题进行分支,同时我们可以称这个被选中的子问题为“父问题”.假设在“父问题”的馋中第k个分量z:是分数.把zk≤tzlJ加到“父问题”的约束中就构成了。左子问题”,同样的,把Xk≥fz:1加到“父问题*的约束中就构成了。右子问题”.每进行一次迭代,在保留下来的连续子问题的最小的日标函数值作为(NKP)最优值的一个上界。而任何一个带有整数解的予问题的目标函数值都可以作为(NKP)的—个下界.能达到最大下界值的整数解作为当前最好解.此处用标准的去除原则从“树”上消除一些分支.如果(NKP)的目标函数值的下界等于上界,或者“树”上的所有节点都被去掉时,算法终止.§2.2动态规划算法动态规划就是把有n个变量的决策问题转化成n个单独变量问题的技巧.这样,n个变量的决策问题就被构造成一个顺序求解各个单独变量的n级序列决策问题.动态规划是以“最优性原理”为基础的,它对决策问题能给出一个精确的解.动态规划的“最优性原理”是由Bellman于1957年提出的:“一个最优策略具有这样的特性,即无论初始状态和初始决策怎样。剩余的决策对初始决策所产生的状态来说必须构成一个最优策略.”涉及动态规划问题的关键元素是级,状态,奂策,变换和收益.一个物理的操作的或概念化的系统,可以看作是按一系列顺序的级而向前发展的.在每一级,系统可以用一相对来说较小的参数组来描述或表征,这些参数称为状态变量或状态向量(简称状态)在每一级,不管系统处于什么状态,都要做出一次或多次决策,这2004年上海大学硕士学位论文lo些决策可以依赖于级或者状态,或者二者均依赖.当做了一次决策后,会得到一个收益,同时系统经历了一次变换或转移,到达下一级.按级发展的过程的总目标是使状态和决策变量的某个函数最大或者最小化.我们将研究的问题(NKP)看作一个多级决策过程,其状态变量和状态变换给出为:^^一1=^^一9k(。^).61(A1)。悖.≤黑讯岫。},l(。I),k(h)2k!。。蛐max恻√^(。k)+¨(扎一gk(xk))m=2…,n)一般来说,肌(z々)为非线性函数,所以必须用数值方法求h—gk(x女)=0的§2.3DP&BB混合算法本节给出了一个新的方法求解可分的整数规划问蹶.这个方法是动态规划(Dy-Programming)和分支定界(BranchandBound)的结合.定义h(6)为:^。(6)=max∑疗(q)(23.1)J=lns.t.∑9jCzj)sb,J=lxj∈毋,J=l,…,n,0sqsuj,xjinteger}考虑第≈阶段的情况:Ⅳ“(6)=max∑,J(q)(232)J。1ks.t.∑毋(q)≤6,J。1q∈s』,J=l,…,≈.利用上面的状态变换和“最优性原理”。我们能迅速的导出递推公式:其中靠为k—gk(xk)=0的根,根.除了这一点所引起的不太大的复杂化之外,可以利用上面给出的递推公式计算hk(Ak)和xk(Ak)的表格,然后得到原问题的最优值和最优解.namic其中岛={巧f2004年上海大学硕士学位论文注意到h(6)就是(NKP)的最优值,我们的目标就是计算数列{札(b)},(≈:1,…,n).这些公式和迭代的最优化称为动态规划方法.令《表示(23.2)的可行解的一个子集.一个可行解z∈.《称为被另一个可行解z7∈《占优(dominated),如果满足下面的条件:kk∑gjC弓)s∑毋(叶)J2lj=l和kk∑厶(《)≥∑矗(町),j=lj=l且在这两个不等式中至少要有一个是严格不等式.如果。∈《不霰《中的其它任何元素占优,则我们称z关于《是有效的(efficient).令雒表示(2.3.2)的所有有效解的集合.问题(2.3.1)的所有有效解的集合碍可以由下面的公式迭代丽得;西∈Xf∈X?=Sl且x££xf∈础=x£一lx&,≈=1,…,n其中x2之((茹1,..,茁k一1,z女)l(。l,…,z≈一1)∈x毒一l,士k∈鼠)bXf=如∈x2I∑毋(町)≤6)),J2l鬈={£∈xfIzisefficien£"溉respectto《).如果牙∈霹且∑≥l毋(弓)=万,则虿是(2.31)的一个最优解,其中b由万代替.这个结论可以由占优的定义直接得出,所以寻找(2.3.1)右端项为6时的所有有效解就等价于寻找右端项为bIsb时的所有最优解.找到j《的程序可以简单的描述如下:动态规划方法第一步;设k=1,科=Sl第二步:从硼中消去不可行点构造成.础2004年上海大学硕士学位论文第三步:从xf中消去所有被占优的点构造成磺.第四步;如果k=n,终止.否则令k=k+1,x2=X≈一1x岛,转第二步.第二步中的可行性判断是—个简单的事情,即检查需要的资源数量是否超过可用的资源数量.第三步中的占优判断有点复杂,但是通过([7J)中的链式表,就可以把此步有效的解决.当算法终止的时候,我们就得到了(2.3.1)右端项为b’茎b时的有效解集蟛和相应的最优值:nn,n(∥)=nlax{∑fj(xj)Iz∈群,∑卯(勺)≤bI).j=l』=l注意到最优收益函数矗(∥)是一个在0兰b’≤b上非减的上半连续分段函数.由于这个动态规划方法寻找的是每个右端项为∥≤b时的所有的最优解.现在我们把注意力集中在如何求解右端项为b时的最优解.我们借助于分支定界法来完成这个任务.考虑Vz=(轧…,xk)∈雄,令卢=∑名l9』(z』).我们把卢记作部分解z所消耗掉的资源.对于给定的z∈雄,在第k阶段的剩余问题(residualproblem)为:hk+l(6一卢)2j:帆max,。矗(即)(2删s.t.∑毋(q)≤b一反j=k+lzj∈岛,七十1≤J≤n.这样,假定已经消耗掉资源口,则剩余问题的最大收益就是巩+z(6一卢).对所有的0sksn一1,令UBk+1是函数万的一个上界,即瓦+l(b一芦)≤ⅣBk+l(6一口),V0≤卢≤bUB≈+1可以是(2.33)任一松弛问题的值.而(2.31)的任何一个可行解都可以得到^。(6)的一个初始下界.已经知道的最好的解称为当前解(incumbent),其相应的最优全解不可能比当前解更好,此时称。由界去除.在第k阶段耀中余下的元素记为雄,即.磺=扛∈x£I∑;:1矗(q)+UBk+I(b一∑%l毋(q))>LB}.利用启发式算法可以找到更好的可行解,使得下界改进.如果。’=(。:。.,z:.)是由启发式算法找到的可以与z=(%.,“)∈.磙构成一个完全解,且满足£笔l矗(q)+∑饕k+l疗(z;)>工B,值就可以作为当前的一个下界即工B.上面的提到的上界和下界可以用来去掉一些部分解.如果对r∈.磺,有∑;:lIj(zj)+UBk+l(6一∑;:l毋(q))≤LB,则由。组成的完2004年上海大学硕士学位论文13则(z,一)就可以作为更好的当前解.在第k阶段我们知道^。(6)落在LB和全局上界UB=max—.Jk:I厶(q)+UBk+l(b一∑;:l毋(q))1。∈.醒)之间.如果间隙(UB—LB)非常小,算法就可以终止.为了把分支定界法加入动态规划程序里面,必须重新定义雄为有效解集的一个子集和础=.碓一l×鼠,^=2,…,n.令风+l(6一口)表示(2.3.3)的最优值,f表示解的近似程度.这个混合算法可以描述如下:DP和B2-,B算法第一步:设k=1,x}=sl,LB=日1(6),UB=UBI(6),选择E∈【o,1】,L≥1.如果LB=UB,终止;否则转下一步.第二步:从碑中去掉所有不可行点构造xf.第三步:从《中去掉所有被占优的元素构造雄.第五步:构造雄={z∈雄I∑名l疗(q)+UBk+1(6一∑凳1毋(q))>LB}.min{UB,UB,}z∈雄},LB=§2.4拉格朗日对偶和区域割方法由于函数,和g具有可分性,相应的拉格朗日松弛问题就简化为解n个一维的第四步:如果I雄l兰L设雄=雄,转第九步.第六步:令UB7=max{∑;;l厶(q)+U凤+1(6一∑%l毋(q))l。∈雄),且UB=第七步:令LB’=m“(∑譬l矗(%)+凰+1(6一∑譬1鲫(≈))Imax{LB,LB%如果有必要就改进当前最好值.第八步:如果(UB—LB)/UB≤f,终止.当前解充分接近最优解.第九步:如果e=n,终止,否则揣包含一个最优懈或者当前解是最优解。或者设k=k+1,础=榷一】×S。转第二步.此算法综合了动态规划法和分支定界法,比较经典,但不是很有效.最大化问题.关键问题就是构造一个比较有效的算法寻找最优的拉格朗日乘子.为了降低松弛问题和原问题之间的对偶间隙,我们从区域中去掉某些个箱子,函数的单调性保证被去掉的这些箱子不会包含最优解,余下的区域仍然可以表示成箱子的并集,这使得接下来的松弛问题也是非常容易求解.当对偶间隙为零或者剩下的区域中没有可行点时,算法终止.运用stlrrogttte技巧和次梯度法,可以用此方法来求解多约束的非线性整数规划问题.2004年上海大学硕士学位论文142.4.1.拉格朗日对偶本节将要介绍含有单约束的整数规划问题的拉格朗日对偶问题的特性,给出扰动函数和拉格朗日对偶之间的关系.考虑单约束整数规划:(P)搿{m)lg(z)9),其中,和目都是R“上的连续函数,x是任意的包含有限个整数向量的集合.问题(P)的拉格朗日函数定义如下:L(z,^)=,(z)一A(g(T)一6),A≥0.则(P)的拉格朗日松弛问题为:(工^)d(^)2m。∈a.YxL(。,^)·令S={x∈X|g(z)≤6),,’=maxx∈s,(。),弱对偶定理总是成立(WeakDuality):d(A)≥,(z),V£∈S,^≥0.所以对所有的^≥0,有d(^)≥,+.问题(P)的拉格朗日对偶问题为;(D)咖4(^)假设S≠0,x\s≠0,则(P)的扰动函数为;u(Ⅳ)。搿{m)J州≤Ⅳ),”∈Ru的定义域为Y=【1,十。。),其中1=min。∈x9(z).很容易看出,函数“J在y上单调不减.由于X中仅存在有限的点,则Y中也存在有限个点ai∈h,+。。)O=1,…,k)使得u有显式表达式:^,01≤Y<a2,2,啦≤Y<a3叫(Ⅳ)=^一l,ak一1≤Y<akA,‰≤Y<oo,2004年上海大学硕士学位论文15其中1=al<a2<…<ak,且^<,2<··<A.令圣={(q,厶)Ij=1,...,研.垂中的点可以定义为u的角点(CorD.erpoints)定义u的上包络函数为最小化一个由u所引导的凹函数:皿(g)=min{h(y)l^isconcaveonyth(y)≥u(雪),V口∈y}.由于u是y上的单调非减函数,所以函数口也是Y上的一个单调非减函数很明显,皿是具有如下形式的一个逐段线性函数t,』.+∈10一aj。)町1≤Y<a,h,J:+∈2(Ⅳ一aj2)nJ2≤Y<ajs皿(掣)=厶Ⅳ一1+{Ⅳ一1(Ⅳ一aiN—1)ajⅣ一l≤Y<ajⅣ,厶ⅣajⅣ兰Y<oo,其中,1=jl<J2<·<如且靠=垒gJk吐+z-gj,。,≈=1,…,Ⅳ一1.由m的函数线性性,我们有:田(Ⅳ)2^rmainR^Y+7(J)S,t.^q+1≥,J,J=1.....k.对任意固定的Ⅳ∈Y,可以引入约束Aai+1≥厶的对偶变量脚≥0,J=l,…,k.问题(I)的对偶问题为:km(Ⅳ)=max∑心,J(j,)J21^∑脚q="1J2lk∑如=1,蜥≥0,J=1,…,kd=z定理2.4.1令(A’,1+)和矿分别是倒和口珂的最优解,且Y=b,则例A‘是对偶问题r驯的最优解且Ⅲ(6)2m^>inod(A)2d(A+)倒对于任意的z,f‘:>0,如果哥∈X满足(g(面),,(暮))=(ni,^),则i是拉格朗日松弛问题(工^.)的一个最优解.2004年上海大学硕士学位论文16证明:见([4】).定理2.4.2Ⅲ设A‘是fDJ的一个最优解,则(L”)至少存在一个可行最优解.而且如果d(A‘)>,+,则(L”)至少存在一个不可行解.f印如果对某个r≥0,同时能得到的一个可行解和一个不可行解,则A+是对偶问题俐的一个最优解.证明:见(㈤.2.4.2.对偶搜索程序由上面的理论,[4】中构造了一个程序来求解(D),且此方法是有限收敛的.其几何意义可以表示为:这个程序在每个循环中都访问到扰动函数u(Ⅳ)的角点,最终得到拉格朗日乘子的最优值,即在皿(Ⅳ)的图象中与直线Y=b相交的那个线段的斜率.此程序的起始点是在壬中找到最低的角点(al,^)和最高角点‰,^),每进行一次迭代就要解一次拉格朗日松弛(以),其中A是一条直线的斜率。这条直线连接两个点:一个是当前最好的可行解,另一个则是离可行点最近的那个不可行解所代表的点,并且随着迭代步数的增加,直线连接的这两个点之间的距离越来越小,即对偶间隙越来越小.2.4.3.拉格朗日对偶和区域割方法假设”是对偶问题(D)的最优解.众所周知,松弛问题(L”)的所有最优解可能都不是原问题(P)的最优解,即对偶间隙一般都会存在的.为了降低对偶间隙和利用对偶搜索找到(NKP)的最优解,利用f(x)和9(2)的单调性,可以得到一个区域割方法(这个将在第四章具体的介绍).将对偶搜索程序和区域割方法结合在一起,可以得到一个收敛的拉格朗日和区域割算法.算法首先把对偶搜索程序运用到(NKP)以得到一个最优对偶乘子以及一个可行解和—个不可行解,记住可行解。在原来的区域中去掉包含这两个可行解和不可行解的整数箱子,并把余下的区域写成多个整数箱子的并集.在第k步迭代中,方法类似,只是把当前最好的可行解最为当前最优解,相应的当前最优目标函数值作为厂的一个下界,而此时的对偶最优值就是,‘的一个上界.为了防止割去箱子以后的子箱子数目增加太多,可以利用弱对偶定理去除一些箱子:这些箱子上的对偶值不超过当前最优解.在每次迭代过程中,要么当前最优解是原问题的最优解,要么(或同时)某些最优值仍在余下的区域中.当上界不超过下界或者余下的区域是空集时,算法终止.具体的算法见(【41)第三章凸背包问题的0-1线性化方法本章考虑凸背包问题(ConvexKnapsackProblem):n(cvgP)maxE厶(q)J=lns.t.∑gj(xj)冬b,J。l如≤xj≤%,zjinteger,j=l,.t“其中五是非减的凹函数,毋是非减的凸函数,q是决策变量,0和吩分别为勺的下界和上界,不失一般性f,和u,均为整数,这里J=1,…,n由于凸背包问题的目标函数是凹函数。约束函致是凸函数,我们可以把函数厶和g,作一个逐段线性逼近变换,将(CVKP)转化成—个等价的o-l线性背包问题,然后通过解这个o-1线性背包问题就可以得到(cVKP)的最优值和最优解。这种方法我们称之为o.1线性化方法.这个方法是Mathur(133】)解二次背包问题方法的一个推广,在㈣)中有此方法酌详细分绍。但是设有数值实验结果.由于这里要解0-i背包问胚,本章介绍了一些求解0.1线性背包问题的算法,最后给出了凸背包问题的0-1线性化方法的数值结果.§3.10-1线性化本节介绍把(CVKP)转化成一个等价的o.1线性背包问题的方法.令zjk=西(≈),其中0≤≈≤uj.定义一个逐段线性函数hj(zj),其断点为{zjk,fAk)},≈={J,fJ十1...,q,函数b(勺)的图像见图(3.1).定义集合刁={≈k,k=0,0+l,..,uj}={gj(1j),9j(1j+1),…毋(q)},j=1,.,n.则凸背包问题(CVKP)可以写成下面的等价形式:tl(EP)maxEhAz,)j=ls.t.∑刁≤b,j=t≈∈乙,J=l,…,n.172004年上海大学硕士学位论文18叱”俨即gi(k)gj(k+1)zj图31:函数hA2j)引理3.1.1凸函数的差分是非减的.即若g(x)是D上的凸函数,zo<Xl<x2且g(x2)丛型,L!f墅2—X27lol—Z0证明:设A=;;暑等,1一^:署焉,则0<^<1且h。十(1。)一纛射篡一z·因为9(z)是D上的凸函数,所以删=9[慨+(1刊珈】蛐(㈦+(1-蝴啪2篡9(。:)+篡删变形得纛№)一㈣】≤鬟№)一州即止止!幽s型.q(x1)j’l—Z0X2.Fl这说明了凸函数的差分是非减的.命题得证引理3.1.2凹函数的差分是非增的.证明:同上.定理3.1.1函数hj(zj)是一个非减的逐段线性的凹函数,其中gj(1j)≤zj≤卯(“,)2004年上海大学硕士学位论文19证明由于^,(z,)是一个逐段线性函数,只需说明其每段的斜率是单调不’震∞即可.由于,,是凹函数,由引理(3.1.2)知差分是非增的,即对固定的J∈{1,2,,n},,J(女+1)一f/k)s疗(≈)一办(≈一1):同样的,gi是凸函数,由引理(3.1.1)知其差分是非减的,即对固定的J∈{l,2,.,n),卯(≈+1)一gj(k)≥,qj(k)一gj(k—1).这样吗的斜率sj≈=箝苷j!};高随k的增加而非I臀结论得证.注意到集合蜀的元素可以用下面的式子来表示:9j(Ij)=m(fJ).毋(fJ+1)=.qi(1j)+【∞(fJ+1)一.gi(1i)所(“,)=.qj(12)十【9j(1j+1)一目Azj)!+‘十【乳(uJ)一gi(uj一1)I-用归纳法,这些式子可以用一个通项表示集合乃中的元素:I∑翟{,十lb(i)一仍(z一1)1wij+n(2,)毋(zJ)={Wij∈{0,1),i=fJ+1…,~IifWlj=0,thenVk>i,wkj=0其中q∈坞.1j+1….,~),J=1….1"It.Nf4创j乃(q)也可以表示这样的形式:|∑翟11+1[矗(z)一疗(i一1)1tOij+,J(0),』(q)一{ICi,∈(0,1},i=Ij十l,…,u』IjfWij=0,thenVk>¨I?¨=o其中q∈蚂,fJ十l,..tIJ},=1一.r1.令Pu=厅(,)一,j(7一1),心,=∞(,)一y一一1),这样(EP)也就是(CVKP)可以写成下面的等价形式:¨ur,}∑∑n一。。十∑,』(1,)(3.1.11J=li=/j十lJ2lnU,tl∑∑“ijwisb一∑gab),(3l2)J=ti=lj十1J21tl,'ij∈fO,1},(3.1.3)VL{wu>0jt“{。-=l,≈<i}(31.4)2004年上海大学硕士学位论文由于奶(2,)是凹函数,贝6由(31.1)一(3.13)组成的(LP)的松弛问题的最优解必然满足式子(31.4).也就是说,式(3.14)从(LP)中去掉之后,问题(LP)依然与问题(CVKP)等价,而此时由(311)一(3.1.3)组成的(LP)的松弛问题是一个典型的o.1线性背包问题,故问题(CVKP)可以通过解一个等价的0-1线性背包问题获得最优解假设w+是松弛问题的最优解,问题(CVKP)的最优解设为z+,则我们有下面的关系z;=∑兰.。:ujj十』,(7=1,….n)问题(CVKP)的最优值等于松弛问题的最优值.接下来的任务就是求解0-1线性背包问题.§3.20-1线性背包问题及其主要算法0-1线性背包问题是一种最简单的整数规划问题,其一般形式为(o—tKP)m“∑乃≈J=1st∑叩J≤b,q∈(o,1}.J=1,…,n其中X,是决策变量.不失一般性,功.ai.b都是大于等于零的数.任何求解线性整数规划问题的算法都可以用来求解0-1线性背包问题(0-1KP),最一般的可以用来解背包问题的方法主要有以下四种:(1)隐枚举法(hnplicitEnu—meration)(见f22][231124j}21m(2)动态规划法(Dynami(PlogIamming)(见{14111511161117】f181[1_91f20i).(3)网络逼近法(NetwolkApptoaches)(见【28][291130]),(4)增广的拉格朗日法(GenrealizedLagrangiatt)(见【251[2611271).而且当约束函数右端项b的值很小的时候,动态规划算法的效果非常有效,但当b很大时,存储量变得很大,用来解(O-1KP)的动态规划算法则显得很失败,而隐枚举法受b大小的改变影响并不大.网络逼近法把背包问题转化成一个最短路问题:由于产生的网络规模太大,这个算法也不是很有效,这里将不给予介绍.我们这里也不介绍方法(4),因为只有我们考虑近似解的时候,增广的拉格朗日方法才能得以运用.由于动态规划对函数的系数有整数要求,这里分两种动态规划来讨论.3.2.i.动态规划一此种算法要求(o一1KP)的约束中变量的系数以及右端项全是整数,即ai(j=1n)和b都是整数2004年上海大学硕士学位论文21令^(Ⅳ)表示背包的容量为Ⅳ从前≈种物品中选择使得(o、lKP)取得的最大值,其中Y=0,1,.,6:^=12…m注意到^(6)就是(O-1KP)的最优值,我们的目标就是计算数列{A(Ⅳ)).k=l,.定义:∑pja,E。j.T%is!I,Xj∈(o.1},J=1,…,k从上面的式子中分离变量‰,女=1,..,n.得到fIllax麒9J=。名茄}m。‘+{5‘,,、l∑型pjxi∑譬:q即≤Ⅳ一。kXk,【。,∈{o,1).J=1….,≈~i其中缸“们一“卜囊嚣≥_一。f一∑jk-:lp声-|nL一∑譬pjx>A一·(Ⅳ一“n)2max{sf∑;二:c。.。≤Ⅳ~n*,1.o∈(o.1},j=i,.,≈一1这样得到了求解{fk(Y)}的迭代公式式子(3,25)说明假设在前k种物品中选择,若在第≈项得到最优值,则余下的空间Ⅳ一毗必须在前k一1中物品中得到最优配置,这就是动态规划的最优性基本原则.注意到初始条件为:川小{,0。::篡2004年上海大学硕士学位论文利用前面的迭代公式,可以在有限步内找到最优值,,。(6).为了寻找最优解,这里要用到一个示性函数:hk(Ⅳ):{0Ilif^(Ⅳ)3^一1(g),if^(Ⅳ)>A一1(Ⅳ)算法3.2.1第一步:k=1,如果0≤Y<al,则,l(Ⅳ)=0,h1(Y)=o;否则如果al曼Y曼b.则,l(封)=P1.hi(可)=0转第二步.第二步:令k=k+1,对所有的Y<ak有A(Ⅳ)=^一l(Ⅳ),hk(y)=0,此时令Y=ak.转第三步.第三步:计算"=肌+A—l(Y—ak)如果t,>^~l(Ⅳ),则令^(Ⅳ)=u,hk(y)=li否则^(口)=^一l(Ⅳ),hk(y)=0转第四步.第四步:如果Y<b令Ⅳ=Y+1.转第三步如果Y=b,转第五步.第五步:如果k<m转第二步;如果k=n,转第六步.第六步:如果‰(Ⅳ)=1.则。k=l,设Y=Y—ak.如果hk(y)=0,Xk=0,转第七步.第七步:如果k>1,令k=k一1,转第六步;如果k=1,终止.算法最后一次执行第五步时就得到了问题的最优值^。(b),第六步和第七步是计算最优解.此程序会在O(nb)步内找到最优解3.2.2.动态规划=此种算法要求(0-1KP)的目标函数中变量的系数全是整数,即Pj(J=1,…,n)都是整数令F,(一)表示在前y个物品中选择使得目标值为,时必须装入背包中物品的最小的容积.对于这个算法,与前面的动态规划一方法类似,也是需要一个迭代公式列表,最终找到最优值.这个公式需要的边界条件即初始条件为:B(o)=0,J=1…_1.迭代公式:E(,)=rain{弓一1(i—Pj)+aj.毋一l(i)},其中.,=1….mi=1,2….结合边界条件,由迭代公式可以得到一个表格,把这个表格中的值按目标函数值的升序排列如下:El(1).毋(1),…,F,。(1):2004年上海大学硕士学位论文Fl(2),最(2),..,晶(2):23Fl(P+),玛(P+),…R(P4)一旦满足R(t)=b的最大值一P‘出现,此算法戟终止,此时P。就是最大的i,也就是目标函数的最优值.由于每个函数值都在0(1)步内完成,这里共需计算0(nP,)次函数的值,所以次算法的计算时间就是O(nP*),3.2.3.隐枚举法当(0-1KP)的目标函数以及约束函数的系数都不是整数时,可以乘一个很大的数使系数变成整数,但是这样由动态规划构造的表格会需要很大的存储量,从而动态规划就不适合用来解此问题了,一种有效而又快速的求解此类问题的方法则是隐枚举法.最早的解(0-1KP)的隐枚举法是由Kolesm-提出的~种宽度优先(breadth.first)的分支定界算法,由于这种算法需要很大的计算机内存和时间太长,Greenberg和Hegerich提出了一种深度优先(depth-first)的分支定界算法,避免了上述弊端.最近Holowitz和Sahni等人在深度优先算法的基础上得到了一个更好的算法.目前很多人又对此方法进行了深入的研究和改进.这里介绍由Hoiowitz和Sahni提出的算法.在这算法中,要用到问题的上界(UpperBounds).接下来就奔绍(0-1KP)的几种上界.假设在问题(0-1KP)中,所有的物品已按下列顺序排成一列:pl/at≥p2/a2≥一n。/n。且令s是满足约束∑;:lq≤b的决策变量下标的最大整数.Datltzig已经证明了下面的定理.定理3.2.1把似ZKP)中的O-1变量约束换成0≤zJ≤lU=1,,n)后的松弛问题的最优解为:rJ=0,,=1.,s:._=0,J=s十2.n:%一l=(b一∑“j)/峨+12004年上海大学硕士学位论文24推论3.2.1u口L=∑j:lPj+L(b一∑j:【nj)m+l/叽+lJ是fo一』Ⅳ刊问题的一个上界值.Martello和TothNx.J-Dantzig的结论给予改进,得到(0-1KP)问题的一个更好的上界.定理3.2.2B1=∑Pj+L(b一∑q)阱2/as+2J,SB2=∑Pj+慨+l一(n¨一(b∑aj))p。/a。JJ21则UB2=max{BL,B2)是(O-1KP)的一个上界.证明:由上面的排序假设和最大整数S知(0-1KP)的最优解可以由两种方法得到:不装入第s+1个物品和装入第s+1个物品.第一种情况很明显不会超过B1的值;第二种情况则必须从前s个物品中去掉至少一个,B2是最好的可能值,假设要去掉的物品重量正好有最小值吼H一(6一∑::las)则最差的值为m/a,,所以B1,B2中最大的一个必然是(0-1KP)的上界.结论得证.定理3.2.3UB2≤UBt证明:我们只霈iiIi明UBl≥B1和UBL≥B2即可.由于风+Ja。+i≥m+2/as+2,所以前者是很明显的.为了得到后者,需要证明S^(b一∑咖阱l/吣l≥Ps+1一(吣I一(6一∑町))ps/‰J=lJ=1世!.就是(D一∑a2(p”1/a州变形得由s的特性我们知b一∑;:1c。一nnl<0,由排序的结果知p,+l/a¨1一ps/‰蔓0.从而命题得证定理3.2.4令矿为满足∑j:1“』sb一“Hl的最大整数,Bj=阱L十∑Pj+L(b—as+lr∑芦叶m+肛+则UB3=max{B1.B3)是fD一』耳纠问题的一个上界且UBa≤uB22004年上海大学硕士学位论文25Mutler和Merbach通过另一种不同的方法改进了(O-IKP)问题的上界UB2定理3.2.5令酊是定理何2』/中松弛问题的对偶变量的最优解,即孵=Pj—ajps+l/a”l,.,=1,.,s,圬=一乃+吩绺÷I/Ⅱs+l,J=s十2,一,n.则UB4=∑+【(b一∑aj)p¨/n州Ⅷlin{(b∑q)Ml/吣·,mniY;IJ≠s+1))JJ21f-.J31是问题的一个上界注意到UB,l不会大于UBl,但是它可以大于等于,等于或小于U岛和UBa,这样可以从UB3和UB4取最小的那个作为(O-IKP)问题的上界,而UB4的计算量要比UB2和UBa的大。Horowitz和Sahni提出了下面的程序,能够很快的得到(O-1KP)问题的最优解.算法中将会用到下面的符号:,,…Ⅲ。=∑整。功q.其中z=(xl,….Xn)是当前得到的一个可行解;^Ⅲ=∑譬ln蚧其中Ⅳ=(玑….,Ⅳ。)是当前得到的一个最好解.算法3.2.2第一步(赋初值):把n件物品按pj/aj的递减顺序排列.令Pn+l=0,fzn+l=00,^cst=,^“。{wr=07=Ⅳ=0第二步(启发式测试):如果rI,>b.令s=7—1:否则令s是满足∑;;。aj≤b的最大整数,计算:=∑::,lq+(6一∑::。‘o)儿十】/f,什l如果几“≥。+,,。。。ible,转第五步;否则转第三步.第三步(构造一个新得当前解):如果“。≤b且i≤n,设b=b一眦,,,。ibl。=,,…。ok+n,z。=1jt=2一1.否则,如果“,>b且t≤m则设孔=0,2={+1重复此步骤,如果i<n.转第二步;否则i=儿重复第三步,转第四步.第四步(保留当前最好解):如果^。,f<,,。ibl。则令^。n=,,。。ibl。,口=。,令j=72,且如果j·。=1设b=b+n¨.,胁,ibl。=,,。㈣№一Pr。X,。=0,转下一步.最优值为km相应的Ⅳ为最优解;否则令6=b十ftk…Ys。ibl。=,,…ibl。一m,zk=0,第五步(返回):寻找使Tk=1且满足&<,最大的々.若没有这样的々存在,i=e+1,返回第二步.这个算法的主要步骤就是开始于通过第三步的迭代构造初始当前解,相当于令{。:0时由定理:j2l得到的整数解.很明显这是一个深度优先的分支定界算法.2004年上海大学硕士学位论文向前移动是指把满足∑笠-n。.qsb的最大的物品放入当前勰中,向后移动则是通过第五步把装入的具有最大下标的物品从背包中去除.当一个向前移动完成时,第二步将会判断进一步前移能否改进当前最优解;在执行第三步的时候,最后一个物品已经考虑过了,第四步判断是否需要改进当前最优解,如果是,当前最优解得到升级.算法会在无需进一步返回时终止.§3.3数值结果这节我们要用3.1节的0-I线性化方法来求解四类问题,给出数值结果,并与Pegging算法和拉格朗目对偶和区域割方法做了比较.3.3.1.问题这里考虑四类凸背包问题:1)最小费用问题(CostMiniinizationPIoblem)C^,PjL∑cj(~一:。)J。lSf∑1。g(1一(1—7-))‘旷q’<6,J=l27≤:o)≤“,,o7integer,J=1,..,n2)二次规划问题(Quadr£tticProblem)(QP)max∑n¨∑ajz。sb.J=If,S.。JS“J3)系统可靠性问题(s、-st@nlReliabilityProblenSRP)m“∑Log(1一(卜。矿。F1¨∑nJ."Cj曼b,J=1fJS.。J≤i‘J,。Jinteger,J21,···,“2004年上海大学硕士学位论文4)分层抽样最优化配置问题(snatifiedSmnplingProblem)(ssP)m“∑一9/.oj=1tlst∑ajxj】。is6,b≤。】Suj,xjinteger,J耸1,…,礼.3.3.2.数值结果及结论本章提出的o.1线性化求解凸背包问题的算法由Fortran90编程,在奔腾4上运行的,计算结果在下面的表格(31-3PC10)中.在所有的计算例子中,f,=1,“,=5,j=1…,n,并设f=(f¨..,f。),“=(虬.UTt)为保证问题存在可行解,约束函数的右端项设为b=g(z)+r(9(u)一9(眺,n)其中r∈(0,1)其它参数选取如下(J=l,(CMP):e5∈[1,50],rj∈【0.8.0.981;(QP)cj∈[i00,300]、a9∈【1150】,为保证单调性,bj=”勺/(2u,),,’∈(0,1);(SRP):70∈{0,8,o9sl,8』∈【l,50i;(SSP):勺∈【25,50】.aj∈【l,50】.这是一些对于0-1线性化方法来说比较容易求解的问题的参数取法,然而当函数的系数在很小的范围内随机产生时,由于隐枚举法优先考虑系数的比值而不注重系数本身的大小,使得此方法则变得异常不稳定,相应的函数系数取法如下,数值结果见表(38)(QP):白∈f100,noJ.q∈f125。1351.为保证单调性,巧=“j/(2t。),7。∈(0,1)在计算过程中,需要用到下面的符号:·n=变量的数目即问题的规模;·‰=随机产生问题的个数;·』,m,A,mAc,.q=分别表示最大,最小和平均值.4)表明四类问题的维数从1000到7000都可以迅速的计算出来,充分表f31.3表明了此算法的有效性.表(3.2)和表(3.5—3.7)的数据表明,随着r即右端项b的增加,问题的可行点增加,从而增加了问题的难度,计算时间也随之延长.比较表(3,G.3.9,310)知,O-1线性化方法解决问题的规模远远大于Pegging方法和拉格朗日对偶和区域割方法,这就给我们下一章求解凹背包问题提供了一个有效的方法.2004年上海大学硕士学位论文垂!:!!【壁坐里2鲤堑堡堕墨f!=!:!)CPU时I司“唧Mill^IaxA”g壹!:!!f里里2塑塑堡堕墨业=!:!》CPU时间礼礼9MinMaxAvg然而,由于解0-I线性背包问题用的是隐枚举法,它本身的“贪婪”性给一类问题造成了困难,从表(3.2)和表(3,8)可以看到到隐枚举法的不稳定性.其中Ns表示20个问题不能在3个CPU小时内完成,LDC则是拉格朗日对偶和区域割方法的缩写.垂!:!!f!垦旦!堕墼堕堕墨业二!:生CPU时间7‘“”Min^IMAvg2004年上海大学硕士学位论文29壅!:塑墼照堡墨业三!:盟CPU时间“礼pMinMaxAvg垂!:鱼!!塑墼堡鳖墨(!:三!:12CPU时间“””MinMaxAvg垂!:!!fg里)塑塑焦鳖墨(!:三!:!)CPU时间““”MinMaxAvg垂!:!!f旦里)塑塑焦堑墨f!:三!:12CPU时间”唧MillMaxAvg2004年上海大学硕士学位论文30丧!:!!f鱼塑笪墼笪堕墨业三!:j)CPU时间jnTt|’MinMaxAvg2塑墼焦堕墨(r=o.7)CPU时间““9MinMaxAvg表3.10!兰旦曼查羹墅i鱼里2塑鍪焦堡墨寸=o.7)CPU时间71”9MillMaxAvg表3.9.£!g坚竖查鎏墅I鱼1第四章凹背包问题的0ml线性化分支定界算法考虑凹背包问题(ConcaveKnapsackProblems)“(CCKP)in3x,(z)=∑屯(勺)J2lnstg(z)=∑9_』(q)≤b,J=lz∈X=(bS。Jsuj,xjinteger,J=1,...,n),凹背包问题在经济规模的最优化模型中经常出现.由于目标函数是一个凸函本章首先介绍了函数的线性逼近,然后又简要介绍了区域割技巧和整数规划中§4.1线性逼近令n,,j∈z”,f』≤OJ≤j屯≤“P其中“=(ol、,n。)口=(口1...,岛。)考虑CCKP)的子问题:(5尸)II)r'IX“小=∑乃(。),=l㈧Ⅳ(。):∑珊(.F.)sb,J=l&J≤oJS卢,.x5integer,J=l,.,”3l其中乃和毋都是非减的凸函数,q是决策变量,0和u,分别为q的下界和上界,不失一般性1,和啦均为整数,这里J=l…,n.数,其相应的松弛问题是一个全局最优化问题,不好求解.由于凹背包问题与凸背包问题的区别就在于目标函数的凸性,而我们知道在第三章中o.1线性化方法求解凸背包问题非常有效,这里我们提出一个0-1线性化分支定界算法,即首先用一个线性函数逼近目标函数,构造一个目标函数是线性函数的凸背包问题,接下来利用第三章中的O-1线性化方法得到凸背包问题的最优值与最优解,且此时得到的最优值是原问题(cc,I(P)的一个上界,把得到的这个最优解带入原问题(CCKP)的目标函数中,就可以得到一个下界,结合分支定界方法和区域割技巧可以容易得到原问题的最优值与最优解.的分支定界算法,并给出了凹背包问题的0-1线性化分支定界算法,最后给出了数值结果2004年上海大学硕士学位论文则在区间h,』‘]上,J扛,)的上逼近凹函数为过两点(%,^(%)),(岛,^(口J))的一条直线:Lj(xj)=,J(q)+sj(xj—nJ),其中旷{∥鬟线性逼近函数见图(4.1)所以/(x)=∑釜。疗(q)在箱子陋,捌的上逼近凹函数可以35}塑o¨:¨O2(1406081310。120140150180200图q1一“,)的线性逼近函数写为:T,““L(r)=∑与(q)=∑(方(nJ)一s,cq)+∑sjXjJ=1J=lJ=1令s。=∑≈-(乃(q)一sjQj),别我们就可以得到子问题(sP)的线性上逼近问题“Pm地∞=}严,量咖0=乃<一饥吖<一T,印。∑岸≤毋。∑州渤。m魄2004年上海大学硕士学位论文33其中s,是L(x)中z,的系数,so是L(z)的常数项.由于^是非减的函数,所以sj≥o(j=1,…,n).再加上工,(z,)是线陉函数即凹函数,从而知(LSP)是一个带有线性目标函数的凸背包问题,接下来的任务就是把(LSP)转化成一个等价的0-1线性背包问题来求解.事实上,如果.r+是(LSP)的一个最优解,,+是(CCKP)的最优值,则我们有,(矿)≤f’兰L{x+),即由线性逼近得到的问题的最优值是原问题的一个上界,而此时得到的最优解带入原问题就得到原问题的一个下界.这样可以利用分支定界方法逐步缩小上下界的距离,宜到找到原问题的最优值.为了尽快寻找到问题的最优解,这里用到了单调性和区域割方法.§4.2区域割方法令n,口∈z“,其中z,t表示”中整数点的集合,【n,例表示由a,p组成的箱子(hyI)el·rectangle),即h例=缸lOe。≤q≤岛,J=l,…,n)定义(a,卢)为陋,剜中整数点的集合:(a,p)=II(0:9.日)=(OLl,01)בx(om口n).J:1集合(a,口)称为一个整箱子.为方便起见,如果n菇卢,则定义h口】=(。,口)=0.令k(2h,f,,)、t一(¨j...¨.)则(CCKP)中区域x的整数点就可以表示为(2,t‘)由,。gj的单调性,我们有下面的结论:性质4.2.1如果T∈(2t。)是(CCKPJ的一个可行点,则对V焉∈(1,z)都有,(i)≤,【z),所以(2,i)可以从(1,t。)中去掉而不会丢掉fCGK引的任何最优解.下面的引理则说明(2,u)\(f.X)可以分解为多个不相交的整数箱子的并集,从而可以在得到的每个小整数箱子上都可以解(LSP),可以改善整个问题的上界与下界引理4.2.I令A=(n口)且B=(1.占),其中n,口,1,6∈z”且n≤1曼d≤卢.则-4\B={u知。(Ⅱj,-。I(n。6。)×(如+l,岛)×Ⅱ::,+l(叫,觑)))u{u等,(n留(%以)×(n,,∞一1)×n5j+l(。。,t)))证明见(㈤例4.2.1“0,3)×((1.∞}\{(1.2j×(1.∞)(0.:埘U“l2)×《0.0”2004年上海大学硕士学位论文§4.3整数规划中的分支定界方法考虑一般的整数规划问题:IP)ZIp=ma.x{f(x):32∈s}整数规划中的分支定界就是利用松弛等方法将问题的可行域S划分为一些子集(sd(j=l…,≈)的形式,然后在这些子集上求解相应的规划问题,最终根据上下界得到原问题最优解的一种方法.定义4.3.1如果U名l岛=S,则称(岛,J=1…,k)是S的一个分割(division);如果Snsj=O(i,j=1,..,k,i≠J).则称这个分割为S的一个剖分(partitio州.性质4.3.1令(IP’)4P=m≈x{f(x):。∈岛),其中{岛)÷:I是S的一个分割,则zip=maxj:l¨,^。;P.此性质说明如果整数规划问题在可行域S上很难求解,且在更小的集合上比较容易求解,则可以把可行域进行分割,而且这个步骤可以重复进行,这样一个分割可行域的过程称为一个枚举树,对于给定的一个父结点如Sl,其子结点Sll,S12,S13就代表了它的一个分割.定义4.3.2假设s被分离成子集{Sm.瓯),如果确定sJ没必要继续分离,则称S可以从枚举树中剪除,即分支定界中的剪枝.性质4.3.2在枚举树中,如果有下面三种情况中的一种发生,鱼都可以被剪枝:1,不可行性:S=0:2,最优值性:得到了(,P)的最优值;3.值占优:在此结点得到的最优值小于原问题的当前最优解.下面给出一个最基本的求解整数规划(IP)的分支定界算法.其中工表示整数规划问题(IpJ)的集合,i是原问题(,P)的下界,而i,则是原问题(,尸)的一个上界算法4.3.1第一步(赋初值):L:“,P)}S)=S.jo=。。,!=一。。第二步(终止标准):如果L=(i】,则㈨如果!>一。c此时的下界i就是原问题的最优值;rW如果i=一。c.则S=0第三步(问题的选择与松弛):从£中选择一个问题(』纠),考虑其松弛问题(兄纠),2004年上海大学硕士学位论文35如果松弛问题存在最优解.F名.相应的最优值为。女。并把此问题从L中减掉.g四步(剪枝):rⅡJ如果:二≤i,转g二步;,"如果砝《Sj,转第五步;俐如果z南∈0且z★>i.令!=晶从L中去除所有zjsi的问题,如果。☆=zi转第二步,否则转第五步.第五步(分支):令(su}翟l是与的一个分割,把一zij=。h(J=1,…,k)的子问题放入集合L中,转第Z-步.§4.40-1线性化矜支定界算法本节把O-1线性化和分支定界法结合起来,借助于区域割技巧,构造了一个求解非线性凹背包问题的算法.算法中要用到下面的符号:·.。㈣。表示当前最好的可行解;·^。表示当前最好解相应的目标函数值;·n表示有可能存在最优解的整箱子的集合;·x‘表示在第≈次迭代中存在的整箱子的集合,算法4.4.1初始步r峨初值J’如果.B=f对于(CCKP)是不可行的,则原问题没有可行解,终止.否则,令。‰£=f,^州=,(。fle“),X1=(1,Ⅱ),Y1=X1,Z‘=0k=1.第一步:陇性逼近/?考虑每个(d,口)∈p,如果g(a)>b,则令Y‘:=Y‘\(o,口);如果g(口)≤b.则矿=。{且L(x3)=弹扩)=,(p):否地通过用隐枚举法解(o-t即)以得到阻sP)的最优解令3。1是化sp)的最优解.如果,(矿)>^。m设‰“=,(矿),lbj~t2Z+第二步r去除J?令j)=0】对于每个(n,伪∈X。=YouZ‘,如果L(x3)>^“,令f2:=Qu(nn如果r)=01终土,。“。f是rc1CⅣ州的一个最优解.第三步件tJ分与定界√j令,㈧,,)表示在(吼d)上解(LSP)而得到的L(矿)的上界.选择(5.卢)∈n作为获得最大值,,(“,口】的整箱子:^27’(i、口)2(嬲{7㈤疗)令砂+1表示从n中去除(d,声)后的整箱子.令矿表示当&=a,口=口时伍s刊的最优解.Y。+1=(a.西)\(a,i8)2004年上海大学硕士学位论文36利用引理“2.纠把Y‘71剖分成整箱子的并集的形式.设Xk+l:yk+lUZk+1.k:=k+1,转第一步.例4.4.1求解非线性凹背包问题:nick2x{+z】+?;+3x2st譬;+34xl+2x;+1822≤109,0≤。J≤3,。Jinteger,.j一1,2Step0:令f=(o,o),¨=(3,3)由于目(f)=0<b=109,则令。‰c’=f,^。“=,(。b。“)=0,X1=Y1=(1,Ⅱ)=(o,o)×(3,3),Z1=D,≈=1.Stepl:9(uj_183>b=109,则构造(LSP):(LSP)iil&x7。1+6x2stz{+34x1+2x;十18x2≤109,0≤xj≤3,xjinteger,J=1,2.(0—1KP)mgx7wl+7[t:2+7w3+6t174+6w5+6w6st35.’i+37“12+39wa+20w4+24iv5+28叫6曼109,wi∈{01},J=1…..6(LSP)的最优解为矿=(1,3),最优值为L(矿)=25,得到原问题的一个上界.把矿Step2L(。。)>^“,转下一步.Step3:构造x2=(f,u)\(f、_5)=(o.o)×(33)\(O,1)×(o,3)=(2,3)×(o,3),解:把(LSP)转化成一个等价的(0-IKP)问题:利用隐枚举法得(0-1KPj的最优解为w5=(1,0,0,1,1,1),最优值为。=25,故得带入原问题的目标函数,得一个下界,(扩)=21.因为^Ⅲ<y(zs),则记^。“=f(29)=21,55一=一=(1,3).转下一步.转第一步2004年上海大学硕士学位论文37Stepl:g(20)<b,9(3,3)>b,则构造(LSP)(LSP)max1111l十6x2一12st、。i+34xl十2z;+18x2≤37,巩∈(2,3),X2∈(0,3).把(LSP)转化成一个等价的(0-1KP)问题:f0一lⅣP1max11201+6w2+6wa+6w4+10st39wl+20w2+24w3+28w4≤37,w,∈{o,1),j=l,…,4利用隐枚举法得(0-1KP)的最优解为l扩=(0,1,0,o),最优值为==16,故得(LSP)的最优解为矿=(2,1),最优值为L(:一)=16.得到原问题的一个上界.把x8带入原问题的目标函数,得一个下界,(矿)=14Step2:因为血“>L(z。),则n=0.算法终止,原问题的最优解为zk“=(1,3),最优值为^w=21§4.5数值结果为了验证算法(441)的可行性和有效性,我们给出了两类凹背包问题的试验数值结果及结论.4.5.1.问题测试问题具有如下的形式:max几,)=∑叩,+“一1j¨,qsfⅣ(z)-∑”,+”;≤b、J=1x∈X=(1js.rJst。,,:rjinteger根据函数系数的选择,这里考虑了两类问题:(P1):y(x)是凸二次函数,其中勺,dj>0,ej=o(.j=ln)(P2):,(z)是三次多项式函数,其中cJ,dj,勺>o(.7=1n)2004年上海大学硕士学位论文38在所有的测试例子中,』J=1.q=5其它参数在以下区间中取值(J=1,…,n):(p1):cj∈【1,30】、呜∈[1,10],啦∈【1.70】,%∈10:1】;(p2):勺∈【l,40】吗∈[1,io],eJ∈【l,20’’啦∈{1,300],∞∈(1,lo].为了保证问题存在可行解,约束右端项的取值为6=g(f)+r(g(¨)一9(2)),其中r∈(o,1)4.5.2.数值结果及结论此算法由Fortran90编程,在奔腾4PC上运行的.数值结果在表格(41.4.2)中,其中要用到下列符号:·n=变量的数目即问题的规模;·rb=随机产生问题的个数;·Min,Max.Ai,g=分别表示最大,最小和平均值.本章提出的0-I线性化分支定界方法可以求解规模从20到140的非线性背包问题,而且从表中可以看出此方法求解此类规模的问题还是比较快的.但是随着问题的规模的增加,在求解过程中产生的整箱子也随之增多,这就增加了内存的需求量.墨!:!!f!12塑塑堕堕墨壁三!:12迭代次数箱子个数CPU时间(s)n~MiIlMaxAvgMinMaxAvgMinMaxAvg2004年上海大学硕士学位论文39壹!:里12塑墼焦蕉墨(!三!:!!迭代次数箱子个数CPU时间(s)“7。”MinMaxAvgMinMaxAvgMinMaxAvg第五章结论本文给出了o_1线性化方法求解非线性背包问题.利用函数的凸性以及单调性直接把凸背包问题转化为一个等价的m1线性背包问题,利用隐枚举法或动态规划方法求解这个o.1线性背包问题,就可以等到原问题的最优解和最优值.在『61中给出了解央凸背包问题的o.1线性化方法,但是并没有给出数值结果.本文不仅给出了o,1线性化解凸背包问题的数值结果,而且还与Pegging方法以及拉格朗日对偶和区域割方法做了数值比较,充分说明了此方法的优越性.凹背包问题目标函数是一个凸函数,不能直接将其转化成等价的0-1线性背包问题,且将变量整数约束去掉后的松弛问题是一个全局最优化问题,松弛问题则不好求解,基于这些困难和凸背包问题的0-I线性化方法的优越性,本文给出了一个o。L线性化分支定界方法,具体做法是先用一个逐段线性函数逼近目标函数,得到一个凸背包问题,利用0.1线性化方法求解得到原问题的一个上界,同时可以得到一个下界,利用分支定界方法和区域割技巧,可以迅速找到凹背包问题的最优解,最后用数值例子说明了此算法的有效性.本文将来可做的工作之一是提出更好的方法来解决0-1线性化之后那些“难”的问题,另外一个工作是寻找更好的方法求解非线性凹背包问题,这方面的其它研究结果可以参看文㈨参考文献【l】KMBrettbauergildBShettyThenonlinearresotlrceallocationprobleHlOptr.R∞一43670-6831995(2】MDjerdjour.KMathur,andHMSalkin.AsunogateIelaxationba.sedonaIgorithmforageneralcbxs,squadrathmukJ—dimensiomflknapsackproblemOust.ResLett.,7:253—258.1988}31DHochbaumAnonlinealknapsack1)roblem却“.ResLett.17:103一llO,1995[4jDLi,XLSun,o.udK*k'KinnonACOlwergelltlaglangiananddomai{1cutme地odt'ornonlinearknapsackproblemsTechnicalreport,DepartmentofSystemsEngineering&EngineeringManagement,TheClfineseUnivetsityofHongKong,Shatin,NT,HongKong,2002submittedibrpnblicatlon[51REMarstenandTLMorinAhybridapproachtodiscretemathematicalprogrammingMathPwgmra,14:21—40,1978【6】KMathur,HMSalkin,andBBMohanty.AllOceOilageneralnon.1inearknapsackproblemsOper。Res.Lett.5:79~81,1986.吲TLMorinandREMarstenAnalgorithmfornollllnearknapsackproblemsMtpntSci22:1147—11581976{8]TLMorinandREMarstenBranchluldbotmdsc_rategiesfordynamicprogrammingOperRes,24:611—627.197619】XLSmlandDLiOptima]it3comlitionaf)dbrancllandboundalgorithm如rCOnstraineatredlltldaheyoptimizationinseIiessystelasOptimEu93:53—65,2009WCooperSm、e3。fmethodsofpurenontioealintegerprogrammingMgmtSci.27:353—361,1981wCooperTimuseofdynamicprogialluniogforthesohltionofaclassofnonlinearprogramnfingNavalResLogistQuart,27:89—95,1980KGuptaandAR乱indranBranchandbotmdexperimentsincoilvexnonlinearinteEerprogrammingMgmtSci.,3i.1533.1546,1985MBretthaueralldBShett)f.Apeggingalgol’itlnnfortilenonlinearresourceallocati。nproblemCornFuters&OperationsResearch.29:505—5272002BellmanSomeapplicationsofthetlleo*Yofdynami‘plogtannning—are'dew,Oper.Res,2(2j:275—288.i954BelhnanNotesOlltiletheot、ofdytlalnicIuOglammiugIV—maximizationoverdiscretesets.Vat:al拧“Loqt^pfⅢrt3:67.7019jG10]M11】M12】O13]K14】R15]R2004年上海大学硕士学位论文16】RBeIhnaaComment011Dantzi91SpaperOildisc、IeteValiableextremumproblemsOper.Res.5(5):723—724195717]RBellmanancLSDte3,}usAppliedd3’liallliCprogralnlnillgPrincetor。University_DmⅫ,196218jGDantzigDiscrete·varialbeextrenlunipioblenlsOpe,兄e5,5(2):266—277,1957191GDantzigLinearprogrmmningandextensionsPrincetonUniuersityPTess,196320】HGreenbergAnMgorithmforthecomputationofknapsackfunctions.JournalofMathe-maticalAnalysisandApplications.,26:159—162,1969211PKolesarAbranchandboundalgorithmfortheknapsackproblemMymt&k13(9):723-735.1967221VCabotAnelnlnlerationalgoritlnnforknapsackproblems,OperRes.18(2):306-311,197023iBFaalandSohttionoithevalue—indepeilclentknapsackproblembypartitioning0p"Res,2l(1):332—336.197324】HGreenhergandRHegelichAI)ranchsear(halgoiitlnnfoltheknapsackproblemMgmtSci16(5):327-332197025_tlEverettGeneralizedLagrangemultiplielinethodforsolvingproblemsofoptimun'lalfoca—tiollofresoulce8OperRes,Il(3):399·471.1963961BFoxandFLandiSearchingtoIthemultiplierinOlleconstraintoptimizationproblems.Oper.Res,18(2):253·262,197027】PHammerandSRudeanuBooleanmethodsinoperationsresearchandrelatedareasNewYork:Sp,inger—Vetlag.196828lGShapiroDynamicprogrammhlgalgorithmsfoitileintegerprogrammingprobleml:TheintegerprogranuaiugploblemviewedasaknapsacktypeptoblemOperRes.,16(1):103—121,196829】GShapiroGeneializedLagiangemultipliersinintegel1)rogranuningOpeT.Res,19(1):68-771971301GShapii(1andHWagnelAfiniterelleWEdalgoIithmfortileknapsackandturnpikemodels()耻,Re.s、1j(2"19-3一11,1967[311HZieglmSolvingc.eltainsingh('oils[1ail/e(](OllVexopt[1nizH.t,fortpl。obIemsinproductionplanningOperResLettl:246—95'21982[32]tlLussandSKGIIpraAllocationofeffo,tIeSotlrcesamongcompetingactivitiesOper.Res,23:360.366,1975f33]KMathur,HAI,SalkinandSMoritoAbranchaadsearchalgoritlnnforaclassofnonlinearkuapsackproblemsOpesResLett,2:155—160.19832004年上海大学硕士学位论文341S43GTzafestasSciOptimizationofsystemreliability:Asurveyofproblemsandtechniquesll:455·486.1980/nt上Syst35IWEGCochranSamplingtechniquesNewYork:Wiley.1963361L.LaMerFastapproximationalgorithmsforknapsackproblems.Math.∞mRes.,4:339一955。1979,371DSHochbaumThenonlinearknapsackproblemSchoolofBusinessAdministrationandIEORDepartment,UnivmsityofCaliiblIlia.Berkeley,1993381GRBitranandDTirupatlTradeoffcurves,Targetingandbalancinginmanufacturingqtteueingnetworks0bHsRe5.37:547—564.1989Hurwitzand391MHHansell、、NWG^In(10wSamplesurveymethodsandtheory,VotnmesIandIINeⅢ}brk:JohnWiley,1953
发布评论