（运筹学与控制论专业论文）求解可分离非线性整数规划的新途径.pdf

摘要 非线性整数规划是最优化理论的一个重要分支。当所求解的非线性整数 规划问题的目标函数和约束函数都是可分函数时，称为可分离非线性整数规 划问题。这一类问题在实际生活中有着广泛的应用，因此，近30 年来受到了 相当大的关注。由于最优化工作者的努力和计算机技术的高速发展，可分离 非线性整数规划的理论分析和计算方法取得了可喜的进展。由于它的可分离 性，该问题可以通过动态规划来求解。动态规划是在最优性原理的基础上，将 待解决问题看成是一个多阶段决策过程，每一个阶段都需作出最优决策，从 而使整个过程达到最优。尽管在理论上动态规划是求解可分离整数规划问题 的理想方法，但“维数的灾难”却限制了它在大型问题中的应用。 替代约束方法通过将多个约束的原问题变成单个替代约束的松弛问题， 而该松弛问题又可以通过动态规划有效地求解，从而为减轻“维数的灾难 提 供了一个很好的平台，进而被广泛应用于整数规划中。因此，本文的主要工作 就是在替代约束这一平台上，将动态规划与割方法结合起来，这样既降低了 维数，又可逐步消除对偶间隙，从而提供了一种求解可分离非线性整数规划 问题的途径。 对偶理论是构造求解可分离非线性整数规划问题有效算法的基础工具之 一。替代对偶能够为最优值提供比拉格朗日对偶更佳的界，所以本文的另一 主要工作就是改进传统的替代对偶方法，将替代对偶方法与割方法相结合，利 用割方法达到更新替代对偶乘子、消除对偶间隙的e 1 的，从而提出了又一种 求解可分离非线性整数规划问题的算法。 全文共分四章。第一章介绍了可分离的非线性整数规划的发展背景，给 出它的一般形式。第二章介绍几种求解可分离非线性整数规划问题的解法，包 括分支定界方法、拉格朗日对偶方法和动态规划方法。第三章在替代约束方 法基础上，将动态规划与目标水平割方法相结合，提出了一种收敛的替代约 束目标水平割的动态规划算法。第四章，我们结合扰动函数说明了最优目标 值界的情况。进一步，将传统的替代对偶搜索与目标水平割方法结合，通过目 标水平割方法逐步消除替代对偶间隙，从而找到原问题的最优值。数值计算 结果说明了所给方法是可行的、有效的。 关键词：可分离非线性整数规划；动态规划；替代约束；目标水平割 i i 4b s t r a c t n o n l i n e a ri n t e g e rp r o g r a m m i n gi sa ni m p o r t a n tb r a n c ho fo p t i m i z a t i o n i ft h e o b j e c t i v ef u n c t i o na n dc o n s t r a i n tf u n c t i o n sa r ea l ls e p a r a b l ef u n c t i o n s ，t h ep r o b l e m i sc a l l e ds e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m t h i st y p ep r o b l e m sa r ew i d e l ya p p l i e d i nr e a ll i f e i nt h er e c e n t3 0y e a r s ，s e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n gr e c e i v e s t h eq u i t eb i ga t t e n t i o n t h es e p a r a b i l i t yo ft h eo b j e c t i v ef u n c t i o na n dc o n s t r a i n t f u n c t i o n sm a k e sd y n a m i cp r o g r a m m i n gm e t h o da ni d e a lt e c h n i q u et os o l v es e p a r a b l e n o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e m s d y n a m i cp r o g r a m m i n gi sb a s e do nt h e p r i n c i p l eo fo p t i m a l i t y a l t h o u g hd y n a m i cp r o g r a m m i n gi sc o n c e p t u a l l ya ni d e a l m e t h o df o rs e p a r a b l ei n t e g e rp r o g r a m m i n gp r o b l e m ，b u tt h e “c u r s eo fd i m e n s i o n - a l i 蚵”p r e v e n t sad i r e c ta p p l i c a t i o ni nl a r g e s c a l ep r o b l e m s t h er e s e a r c h e r sh a v e m a d eal o n gt i m er e s e a r c ht om i t i g a t i n gt h e c u r s eo fd i m e n s i o n a l i t y ”i nd y n a m i c p r o g r a m m i n g t h es u r r o g a t ec o n s t r a i n tm e t h o ds u r r o g a t e st h em u l t i p l ec o n s t r a i n t sb yas i n - g l ec o n s t r a i n t t h es i n g l yc o n s t r a i n e ds u r r o g a t er e l a x a t i o np r o b l e mc a nb es o l v e d e f f i c i e n t l yb y ( 1 y n a m i cp r o g r a m m i n g p r o v i d i n gap l a t f i ) r mt om i t i g a t i n gt h e “c u r s e o fd i m e n s i o n a l i t y ”t h u si ti sw i d e l yu s e di ni n t e g e rp r o g r a m m i n g o n eo ft h em a i n j o b so ft h i sa r t i c l ei sc o m b i n i n gd y n a m i cp r o g r a m m i n ga n dc u t t i n gm e t h o do nt h e p l a t f o r mo fs u r r o g a t ec o n s t r a i n tt e c h n o l o g y w ec a nn o to n l yr e d u c et h ed i m e n s i o n o ft h ep r o b l e m ，b u ta l s oe l i m i n a t et i l ed u a lg a p ，t h u sf i n da l le f f e ( ：t i w , m e t h ( ) df o r s o l v i n gs e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e m t h ed u a l i t yt h e o r yi so n eo ft h ef u n d a m e n t a lt o o l sf o rt h ed e v e l o p m e n to fe l - f i c i e n ta l g o r i t h m sf o rg e n e r a ln o n l i n e a rp r o g r a m m i n gp r o b l e m s s u r r o g a t ed u a lc a l l g i v eab e t t e rb o u n df o rt h eo b j e c t i v ef u n c t i o nt h a nl a g r a n g i a nd u a l ，t h u sa n o t h e r m a i nj o bo ft h i sa r t i c l ei sc o m b i n i n gs u r r o g a t ed u a lm e t h o da n dc u t t i n gm e t h o d t h r o u g ht h i s ，w ec a nu p d a t et h es u r r o g a t em u l t i p l i e ra n de l i m i n a t et h ed u a lg a p ， i i i a n o t h e re f f e c t i v ef o rs o l v i n gs c p a r a l ) h 、l l o l l l i l l c j t ri n t e , g ( ；r1 ) r o g r a m r u i n gp r o b l e m t h ep a p e rc o n s i s t so ff o u rc h a p t e r s c h a p t e rii n t r o d u c e st h eb a c k g r o u n do f s e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n ga n dg i v e si t sg e n e r a lf o r m c h a p t e ri i i n t r o d u c e ss e v e r a lm e t h o d st os o l v es e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b - l e m s ，i n c l u d i n gb r a n c ha n db o u n dm e t h o d ，l a g r a n g i a nd u a lm e t h o d sa n dd y n a m i c p r o g r a m m i n gm e t h o d i nc h a p t e ri i i ，an e wc o n v e r g e n ts u r r o g a t ec o n s t r a i n ta n d o b j e c t i v el e v e lc u td y n a m i cp r o g r a m m i n gm e t h o di sp r o p o s e d t h i sm e t h o di st h e c o m b i n a t i o no fd y n a m i cp r o g r a m m i n ga n d c u t t i n gm e t h o db a s e do ns u r r o g a t ec o n s t r a i n tm e t h o d c h a p t e ri vc o m b i n e st h et r a d i t i o n a ls u r r o g a t ed u a lm e t h o da n d t h eo b j e c t i v el e v e lc u tm e t h o d t h en e w a l g o r i t h me l i m i n a t e st h ed u a lg a pt h r o u g h t h eo b j e c t i v el e v e lc u tm e t h o da n df i n a l l yf i n d st h eo p t i m a lv a l u eo ft h eo r i g i n a l p r o b l e m e x t e n s i v ec o m p u t a t i o n a le x p e r i m e n t sa n dn u m e r i c a lr e s u l t sa r ep r e s e n t e d i nt a b u l a rf o r mf o re a c ha l g o r i t h mi nc h a p t e r si i ia n di v k e yw o r d s s e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n g ；d y n a m i cp r o g r a m m i n g ； s u r r o g a t ec o n s t r a i n t ；o b j e c t i v el e v e lc u t i v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的 研究工作。除了文中特别加以标注和致谢的地方外，论文 中不包含其他人己发表和撰写过的研究成果。参与同一工 作的其他同志对本研究所做的任何贡献均已在论文中作了 说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规 定，即：学校有权保留论文及送交论文复印件，允许论文 被查阅和借阅；学校可以公布论文的全部或部分内容。 签名：刍幽鲤导师签名洳建及日期：单r ， 2 上海大学硕士学位论文 第一章绪论 最优化是一门应用性相当广泛的学科，它讨论决策问题的最优选择，构 造寻求最优解的计算方法并研究这些方法的理论性质及方法实现。这类问题 在经济、管理和工程应用中普遍存在，广泛见于经济计划、工程设计、生产管 理、交通运输、国防军事等重要领域。随着生产和科学研究突飞猛进的发展， 特别是电子计算机日益广泛的应用，最优化理论及应用受到高度重视。 整数规划问题是指在一些等式( 或不等式) 的约束下，最小化( 或最大 化) 某个目标函数的优化问题，其中要求某些变量必须取整数。在实际生活 中，有许多量具有不可分割的性质，如人数、机器数、元件数等。另外利用阻l 变量，可以数量化地描述开与关、取与舍、有与无等现象。所以在很多领域 中，如线路设置、工厂选址、人员安排( 分配) 、代码选取等，常常出现整数规 划问题。如果问题中的所有函数都是线性的，就称为线性整数规划问题。否 则，就称之为非线性整数规划问题。而非线性整数规划的实际应用是相当广 泛的，如资源分配问题 1 】 2 】、投资组合问题 3 】【4 】【5 】 6 【7 】、分层抽样问题 1 i s 】 【9 1 、系统可靠性问题【1 0 1 1 1 1 、生产计划问题【1 2 】等。由于问题的非线性性，非 线性整数规划问题的理论和求解方法本质上是不同于线性整数规划的。 按照问题函数的可分性，非线性整数规划问题又可分为可分离非线性整 数规划问题和不可分离非线性整数规划问题两种。可分离非线性整数规划问 题就是指问题中的目标函数和约束函数都是可分函数，否则就称为不可分离 非线性整数规划问题。可分函数是由一个单变量的函数的和所组成的函数，即 f ( x ) = a ( x 1 ) + 厶( z 2 ) + + 厶( z n ) ( 1 0 1 ) 故可分离非线性整数规划问题的一般形式为： ( p ) m i n f ( x ) = 。尼( 巧) s t g i ( x ) = 警1 9 i j ( x j ) 瓯，i = 1 ，m ( 1 0 2 ) z x = x 1 x 2 ) 厶， 1 上海大学硕士学位论文 其中x ，是酞上的有限整数集合，函数厶，仇，是定义在r 上的实值函数，并且 办，吼j 至少有一个函数是非线性的( i = 1 ，m ，j = 1 ，佗) 。 由于问题( 尸) 在实际生活中有着广泛的应用，但是它的计算复杂度与问 题的维数又呈指数型增长，因而求解可分离非线性整数规划问题是一项具有 重要意义且有挑战性的工作。文【1 3 】、【1 4 】和f 1 5 1 证明了非线性整数规划问题 的几种特殊形式都是n p 困难的。 可分离非线性整数规划问题在近3 0 年来受到相当大的关注。由于非线性 整数规划问题的特殊性一变量要求是整数，所以它的求解方法受到一定的限 制，非线性规划中对于连续变量的最优化理论对非线性整数规划已不适用。 例如，非线性整数规划问题的最优解不一定满足k k 丁条件。当然，由于问题 ( p ) 的可行域内有有限个整点，所以我们可以尝试用穷举法。通过比较可行域 内每个整点的函数值，从而找到原问题的最优解。对于小规模问题而言，这种 方法是可行的。但是对于规模较大的问题，穷举法显然不可行，因为穷举法的 计算量是随变量的增加呈指数增加的。求解可分离非线性整数规划问题的现 有方法主要是以动态规划为基础的各种方法和以连续松弛问题为基础的分支 定界法。 对于一般的非线性整数规划问题，文【1 6 】提出了基于连续松弛的分支定 界方法。对于单约束且f j ，s 和矾i ，s 均为凸函数的可分离非线性整数规划问题， 文【1 7 】将p e g g i n g 算法与分支定界算法结合，提出了种新的分支定界算法， 并且给出了多达2 0 0 个整数变量的非线性资源分配问题的数值试验结果。文 1 0 】和【1 8 】分别对非线性背包问题和可靠性系统的冗余优化问题提出了相应 的基于求解连续松弛子问题的分支定界方法。要指出的是，该方法之所以能 够很好的求解整数规划问题，是因为它可以确定全部连续松弛子问题的全局 最优解。因此，应用这一类方法时，通常需要假设，是凹的，吼是凸的。 拉格朗日对偶方法是求解离散优化问题的一种强有力的方法。利用分解 技术求解拉格朗日松弛问题，可以有效地找到最优对偶值。最优对偶值为原 问题的最优目标函数值提供了一个下界。但是大多数情况下，由于对偶间隙 2 上海大学硕士学位论文 的存在，拉格朗日对偶方法不能找到原问题的最优解，甚至不能给出一个原 问题的可行解。文f 1 9 1 一f 2 4 1 分别将拉格朗日对偶方法和凸化方法或者割方法结 合，提出了求解一些具有特殊结构的非线性整数规划问题的拉格朗日方法。 对于问题( p ) ，由于它的可分离性，可以通过动态规划来求解( 见【2 5 1 、f 2 6 1 ) 。 尽管动态规划在理论上是求解可分离整数规划问题的理想方法，但是“维数 的灾难”限制了它在大型问题中的应用。一些基于动态规划和分支定界技术 的精确求解方法被用来求解非线性整数规划问题( 2 7 】) 。m a r s t e n 和m o r i n 提 出一种混合算法( 见【2 6 】， 2 8 】和f 2 9 0 ，利用动态规划方法产生有效可行解，并 且通过分支定界方法去除多余的不完全可行解。 替代约束公式可以将多约束问题转化成单个约束问题，由此提供了减轻 “维数的灾难”的平台，但通常情况下会存在对偶间隙，并不能找到原问题的 最优解。文3 0 1 提出了一个收敛的动态规划区域割算法，该算法将区域割和 替代约束方法相结合，利用区域割方法去除已探明区域，逐渐消除对偶间隙 来找到原问题的最优解。文3 1 1 将替代约束和目标水平割结合，提出一种新 的动态规划目标水平割算法，利用目标水平割方法增大替代约束问题的最优 值，使其逐渐接近原问题最优值。多种其他的方法也相继被提出。 本文主要是在替代约束这一平台上，将动态规划与目标水平割方法结合 起来，给出了一种收敛的替代约束目标水平割的动态规划算法。此外，结合扰 动函数说明了最优目标值界的情况。进一步，通过改进传统的替代对偶方法， 将替代对偶方法与目标水平割相结合，来更新替代对偶乘子，并通过目标水 平割方法逐步消除替代对偶间隙，提出了一种求解可分离非线性整数规划问 题的算法。数值计算结果说明了所给方法是可行的、有效的。 3 上海大学硕士学位论文 第二章可分离非线性整数规划问题的几种解法 本章主要介绍可分离非线性整数规划问题的几种解法，其中包括： ( 1 ) 分支定界方法； ( 2 ) 拉格朗日对偶方法； ( 3 ) 动态规划方法。 2 1 分支定界方法 在2 0 世纪6 0 年代初，l a n dd o i g 和d a k i n 等人提出了分支定界法。由于 该方法灵活且便于用计算机求解，所以目前已成为解整数规划问题的重要方 法之一。 分支定界的基本原理 3 2 对于整数规划问题，当直接求解它比较困难时，可以采用“分而治之 ( d i v i d ea n dc o n q u e r ) 的策略，先将可行域分割成一些小的集合，然后，在比较 小的集合上求解相应目标函数的最优值，并将结果集成在一起生成原问题的 最优解。值得指出的是，在求解较小集合对应的子问题时，还可以利用分而治 之的策略进一步分割。此外，可以采取多种措施对子问题进行分析，例如，可 以估计子问题最优值的某个界，将它与已经知道的原问题的可行目标值进行 比较，如果能断定子问题无法获得更好的可行目标值，那么就不需要对子问 题进行精确求解。这就是分支定界法的基本思想。至于如何分支和如何定界， 则构成了分支定界方法研究和应用的核心环节。 下面，我们给出一些关于定界和分支的基本概念，以及对分支进行处理 的基本原理。 定义2 1 给定最优化问题 ( p )，= m i n f ( x ) iz s ) ， 4 上海大学硕士学位论文 其中s = o f f xig i ( x ) b i ，i - - - - 1 ，m ) 。若存在集合s a pcr n 和函 数 护( z ) 满足 ( j )s s n p ， ( i i )，( z ) 尹r p ( z ) ，v x s ， 则称优化问题 ( r p )岛- - - m i n f r p ( x ) lz s r p ) 为问题( p ) 的松弛问题。 容易看出，若松弛问题( r j p ) 是不可行的，则问题( p ) 也是不可行的。 定义2 2 若集合族 s ii = 1 ，七) 满足u 整1 鼠- - - s ，则称为s 的一 个分割。 命题2 1 设s 是问题( p ) 的可行域，集合族 s ) 笔1 为s 的一个分割。 若令子问题 ( p )，“= m i n f ( a ! ) iz s ) ， 则原问题的最优值，+ = m i nf “。 t = 膳 由于可行域s 可以分割成一些较小的集合s ( i = 1 ，七) ，集合又可 以继续分割成更小的集合，所以依次类推，就可以生成一个分支定界树，其中 s 称为的父结点，称为s 的子结点。如果通过某种方法能够判定的 进一步分割是不必要的，则对应的结点就可以从分支定界树中删除，这种 现象称为剪枝。实行剪枝操作的条件可以描述成如下命题。 命题2 2 在s 对应的结点处，如果下面三个条件之一成立： 以，不可行性：s = 0 ； 俐最忧。眭：已经求出最优值f “； 俐可控性：，埘， 则可以将结点从分支定界树中剪去。 5 上海大学硕士学位论文 分支定界的算法步骤 下面我们正式给出一般的分支定界法的算法步骤。 分支定界法 步骤1 ：初始化 令整数规划问题表c = ( 户) ) ，s o = s ，最优值的上界厂= + o o ，下界 f o = 一0 0 。 步骤2 ：最优性检验 若c = 仍，则当，= + 时，可行域s = ( i ；当， 儡，转步骤5 。 步骤5 ：分割 生成s 的一个分割 s 巧) 每1 。将 ( 尸，j j k ：1 增加到表c 中，并且置，= 廊，j = 1 ，k 。转步骤2 。 算法终止。 以上算法描述了求解整数规划的分支定界法的一般特征。针对具体的问 题，研究人员又提出了各种各样的分支定界法。g u p t a 和r a v i n d r a n 1 6 】针对 凸非线性整数规划问题提出了一种基本的分支定界法。先求解原问题的连续 松弛问题，得到全局最优解。如果这个全局最优解是整数解，那么这个全局最 优解就是问题的最优解。否则，从全局最优解出发，进行分枝。对于每枝， 6 上海大学硕士学位论文 就对应一个子问题，通过解决系列子问题的连续松弛问题，直到找到一个 可行整解为止。这个可行整解的函数值为问题( p ) 提供了一个上界。而每个 子问题的连续最优解的目标函数值为相应子问题提供了一个下界，如果某一 枝无可行解，或连续最优解是整解，或者其下界超过了上界，就可以剪掉这一 枝。对于没有剪掉的枝重复进行分枝、剪枝过程，直到所有的枝都被剪掉为 止。如果某一枝有可行整解，必要的话需要更新上界，以确保上界是找到的 可行整解中目标函数值最小的。程序结束时，当前最好的可行整解就是问题 ( p ) 的最优解。 p a r d a l o s 和r o s e n 3 3 】针对可分离非线性整数规划问题提出了一种m 1 线 性化的方法。值得注意的是，为了保证全局最优性，用以连续松弛问题为基础 的分支定界法求解时，要求办( 勺) 和( 勺) ，i = 1 ，m ，j = 1 ，n 是可微 凸函数。 2 2 拉格朗e t 对偶方法 对偶理论不论是在连续优化还是离散优化中都发挥了重要作用，它是构 造求解可分离非线性整数规划问题有效算法的基础工具之一。毫无疑问，拉 格朗日对偶方法是在整数规划中应用最广泛的对偶方法之一，这很大程度上 是因为拉格朗日对偶方法丰富的对偶理论以及求解的高效性。 考虑可分离非线性整数规划问题的一般形式： ( p ) m i n ( z ) = 。乃( ) s t 俄( z ) = 1 ( ) b i , i = 1 ，m ( 2 2 1 ) z x = x 1 x 2 x n z n ， 问题( 尸) 称为原问题，约束g i ( x ) b i ( i = 1 ，2 ，m ) 称为拉格朗日约束。令 9 ( z ) = ( g l ( z ) ，夕2 ( z ) ，9 m ( z ) ) t ，b = ( b 1 ，b 2 ，k ) t 。问题( p ) 的可行域记为 s = z xlg ( x ) 6 ) 。令，+ = m i n z s 厂( z ) 。通过引入一个非负的拉格朗日乘 子向量，将拉格朗日约束合并到目标函数上，就构成了拉格朗日函数，记为 7 上海人学硕士学位论文 l ( x ，a ) ，即 l ( x ，a ) = ，( z ) + a t ( 9 ( z ) 一6 ) 问题( p ) 的拉格朗日松弛就是对一个给定的a ，求拉格朗日函数的最小值： ( l a ) d ( 入) 2 装蛩l ( z ，入) = ，( z ) + a t 0 ( z ) 一6 ) ， ( 2 2 2 ) 其中( f ( 入) 称为对偶函数。拉格朗日对偶问题就是对于a 最大化对偶函数，即： ( d ) m r a x t d ( a ) ( 2 2 3 ) 令可( q ) 表示问题( q ) 的最优值。 定理2 1 ( 弱对偶定理) 对于所有的入er 7 , ， u ( 工a ) u ( p ) ( 2 2 4 ) 更有 v ( d ) t ，( p ) ( 2 2 5 ) 证明：对任何入r t ，显然有 可( p ) = m i n f ( x ) ig ( z ) sb ，z x ) m i n f ( x ) ia t ( g ( z ) 一b ) 0 ，z x ) m i n f ( x ) + a t ( 夕( z ) 一b ) la t ( 9 ( 上) 一b ) 0 ，x x ) m i n f ( x ) + a t ( 9 ( z ) 一b ) iz x ) = 移( 厶 ) 这证明了一式。既然对于所有的a r ? ，都有v ( l x ) u ( 尸) ，二式也成立。 口 由弱对偶定理知，问题( l a ) 是问题( p ) 的一个松弛，且最优拉格朗日对 偶值v ( d ) 为v ( p ) 提供了一个下界。 8 上海人学硕士学位论文 定理2 2 ( 强对偶定理) 如果对于入+ r ? ，z 。x 是( 工入) 的解，且满 足下面的条件： g i ( x 。) b i ，i = 1 ，2 ，m ， 入：( g ( z + ) 一b 1 ) = 0 ，i = 1 ，2 ，m ， 则z 。是问题( p ) 的解且v ( d ) = ( p ) 。 ( 2 2 6 ) ( 2 2 7 ) 证明：显然，z 4 对于问题( p ) 是可行的，所以f ( x ) ”( p ) 。由弱对偶定 理和假设，我们有 v ( p ) v ( d ) 钉( l a ) = f ( x + ) + ( a 。) 丁( 9 ( z + ) 一b ) = f ( x + ) u ( 尸) 因此，v ( d ) = v ( p ) = f ( x ) 且z 4 是问题( p ) 的解。 和： 其中 口 由于闯题( j p ) 的可分离性，拉格朗日函数可以表示为佗个单变量函数的 则拉格朗日松弛问题( 厶) 可以分解成n 个一维子问题， d ( a ) 2 m i n l ( x ，入) = m z i n j ：1l j ( x j ，入) 一入t 6 ( 2 2 8 ) 2 j ：1 z m j 匕i n j l j ( z 歹，a ) 】一a ? 6 假设，z j 分别为集合鼍o = 1 ，2 ，n ) 的上界和下界，则通过这一分解方 n 法，计算d ( 入) 至多需要o ( ( 一+ 1 ) ) 次对l j 的计算和比较。跟求解问题 扛= 1 ( 厶) 相比，求解上面的一维整数优化问题要容易得多。因此，对于可分离非 线性整数规划问题，拉格朗日对偶问题是十分有效的。 9 d r 入一入z 己 n 他 = 入 zl 吼九 m 谢 十 巧厶 = u 巧0 上海大学硕士学位论文 但是，在整数规划中满足强拉格朗日对偶性的情况是很少的。v ( i ，) 一v ( o ) 称为问题( 尸) 和( d ) 之间的对偶间隙。由于对偶间隙的存在，多数情况下，拉 格朗日对偶方法不能找到原问题的最优解，甚至找到的对偶最优解对原问题 不可行。文f 1 9 1 _ f 2 4 1 分别将拉格朗日对偶方法和凸化方法或者割方法结合，提 出了求解一些具有特殊结构的非线性整数规划问题的拉格朗日方法。这也是 本文利用割方法改进替代对偶方法的主要动机。 2 3 动态规划方法 动态规划方法已经被广泛的应用在可分离整数规划中。由于目标函数厂 和约束函数9 ：s 的可分性，使得动态规划成为求解问题( p ) 的一种理想方法。 为了更有效地应用动态规划方法求解问题( j ) ) ，我们做一下假设： 假设2 1 对于任意的z x ，函数，( 刃) 和g i ( x ) 是整数值的，i = 1 ，m 。 本文中，如非特殊说明，则问题( p ) 满足上述假设。 最优性原理 动态规划是基于所谓的“最优性原理”产生的。2 0 世纪5 0 年代，b e l l m a n 等人在研究具有无后效性的多阶段决策问题的基础上，提出了最优性原理：作 为整个过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状 态和决策如何，对该状态而言，余下的诸决策必构成最优子策略。即最优策略 的任一后部子策略都是最优的。 为了应用动态规划，我们首先引入一个阶段变量k ，0 k 佗，以及在阶 段k 上的状态向量r m ，且满足下面的迭代方程： s 七+ 1 = s 七+ 9 七( z 七) ，k = 1 ，n 一1 ，( 2 3 1 ) 其中s 1 = o ，矿( ) = ( g v , ( z 知) ，七( ) ) t 。 1 0 上海大学硕士学位论文 既然约束函数是整数值的，我们只需要考虑状态空间中的整点。而且，在 阶段k ( 2 k 礼+ 1 ) 状态向量的可行域可以表示为： 其中 s k ：2 甄2 甄s 七巩， 扛k - 1 1m i n 玳凰g u ( 兢) 扛k - 1 1m i n x t 凰g m t ( 乜) m i n 旨m 瓯。噩g u ( ) ，b 1 一：七m i n z 。盈g ux t ) ) m l n t 厶拄k - 1 1m a x x t 凰g m t ( ) ，b m 一：七m i n 。凰g m ( 也) ) 动态规划基本方程 ( 2 3 2 ) ( 2 3 3 ) 在动态规划中，有后向动态规划和前向动态规划两种方法。后向法是由 终点向始点逐段递推；而前向法是由始点向终点逐段递推，因此它们的基本 方程不尽相同。 后向动态规划的基本方程 对于阶段k ( 1s 尼n ) 上一个给定的状态s ，定义成本函数( c o s t t o g of u n c t i o n ) 如下： 显然 反( s ) n = m i n f j ( z j ) ， j = k n s t s + g j ( z j ) b ， j = k 玛，j = k ，n v ( p ) = i l ( 0 ) 根据b e l l m a n 的最优性原理，对于k = n 一1 ，n 一2 ，1 ，后向动态规划方法 的成本函数满足以下递推关系： 蠢( s ) = = z m 。i a n 。 a ( z 七) + 气+ 1 ( s + 夕七( z 七) ) ) 1 1 上海大学硕士学位论文 边界条件： 定义 乙( s ) = z m 。e i n 。 a ( z n ) is + 9 n ( z n ) b 】- z 荆= a r g 般 厶( z n ) is + 9 n ( z n ) 0 ，所以替代对偶问题( d s ) 可以化为下面的等价 问题，使得问题的可行域是紧的： ( d )m a x 幻( 丘) ( 3 1 3 ) s t 弘a ， 其中a = p r ? le 丁p 1 】，e = ( 1 ，1 ) r 。 3 2替代约束目标水平割的动态规划算法 式( 3 1 1 ) 中的替代约束可以表示为 0 # t g ( x ) p t b ， 我们可以将【0 ，p t 6 】分解为u ；m 1m 一1 ，“】，其中，o = 0 ，h m = 丁f ，。然后我们把替 代约束问题( 丘) 看作一系列子问题： ( p 弘，i )m i n ，( z ) s t h l 一1 ，t g ( x ) h t ，i = 1 ，m ( 3 2 1 ) z x 对于问题( 丘) 和( 0 ，f ) ，有 命题3 1 对于所有的l ，有锄( 兄) 钐( b ，1 ) 。 在本节中，我们假定原问题( 尸) 有解且最优值有限，假设x + 是原问题( 尸) 的最优解，“取整数值。 在新的算法中，首先给定一个肛，利用动态规划求解替代约束问题( 兄) 。 如果在( 兄) 的解集中有一个解对( 尸) 可行，则该解对( p ) 也是最优的。否则， 用动态规划求解子问题( o ，1 ) ，1 2 m 。如果( 屹，1 ) 的一些解对原问题( p ) 是可行的，记这些解的目标函数值中最小的一个为，且用x 卿表示这些可 行解中目标函数值与厶。相等的解的集合。把最优值大于或者等于的子 1 6 上海大学硕士学位论文 问题去掉，记剩余的子问题的标号组成的集合为z 。然后选取剩余子问题的最 优值中最小的一个值加上1 ，记为c ，求解下面的子问题： ( p 川( c ) ) m i n f ( x ) s t h t - a 网z ) h t , 16z ( 3 2 2 ) f ( x ) 芝c ， z x 通过逐步增大cg i f t ，问题( 丘，l ( c ) ) 的最优值必定相应的增加，对偶间隙将逐 渐减少。重复这一过程，如果有必要更新和t ，最后将得到原问题( p ) 的最优值。 下面，我们来描述这一新算法。 算法3 1 ( 替代约束目标水平割的动态规划算法) 步骤0 选定p ，用动态规划方法求解( r ) 。如果在( 以) 的解集中有一个 解对( j p ) 可行，则停止且该解对( p ) 也是最优的。否则，把 0 ，p 丁6 】分解为 u 篷lh 一1 ，h i ，其中h o = 0 ，h m = p t b 。记蜀= _ 1 ，2 ，m 。 步骤1 用动态规划求解下列子问题： ( p ) m i n s ( x ) s t h f 一1 u t g ( x ) h f ，2ei o ， ( 3 2 ，3 ) z fx 记解为x 件，f z o 。 步骤2 如果( 兄，f ) 的一些解对( p ) 可行，记为z h ，z 知，z 硒+ 。令岛= m i n 。匀t 。 ，( ) ) ，砩= 牙i 孟 z b ，z 知，一。) ，( 2 ) = 岛) 。如果( 丘，z ) 的 解对( 尸) 都不可行，则令岛= + ，码。= d 。 令蜀= f 而i ( 以，1 ) 岛) ，五= z o z ；。记c 1 = m i n l e z , 秒( 丘，z ) ) + 1 。如 果五= d 或者c 1 岛，则停止且对( p ) 最优。否则，令k = 1 转步骤3 1 7 上海大学硕士学位论文 步骤3 用动态规划求解下列子问题： f ( x ) h i - 1 纵z ) h l , i 死 ( 3 2 4 ) y ( x ) c 七， z x 记v l = 秒( 兄1 ( c 惫) ) ，相应的解记为z “，l 五。 步骤4 如果( ，么，l ( o k ) ) 的一些解对原问题( p ) 是可行的，记为z h ，z 知，z 小 。如果m i n l _ j _ 艨t ，则令瞄1 = m i n l j i k f ( z j + ) ) ，x 茹1 = 圣i 牙 t h ，z 2 搴，t + ) ，( 童) = 磁1 ) 。否则，令磁1 = 碡。，x 茹1 = x 品。u zi 王 z h ，z 缸，* ) ，( 叠) = z 茹1 ) 。 记夏= f 磊lv l 像1 ) ，五+ 1 = 五夏，c k + 1 = m i n f 磊+ 。 叻卜+ - 1 。如果 五+ 1 = 仍或者c i i 。+ 12 像1 ，则停止，像1 是原问题( p ) 的最优值，磙1 中的解 是( p ) 的最优解。否则，令k ：= k + 1 转步骤3 。 算法终止。 若存在c 七，我们有下面的结论： 引理3 1 印，算法中c 知的个数是有限的，即有c 知，知= 1 ，2 ，k ，k z + ： ( 2 ) c l c 2 c k ； ( 3 ) m i n l e ：r l v ( p 一, ，1 ) ) = 口( 丘) 。 证明：( 1 ) 由算法中c 七的定义可知，它是由问题( 丘) 的最优值逐渐靠近 ( ，) 的最优值，一旦超过可( p ) ，算法必定停止，故c k 的有限性是显然的。 ( 2 ) 由c 南的构造方式可知，它是个严格递增的序列。 ( 3 ) 设岛= z xih j l 矿夕( z ) ) ，则 昂) 筵1 是j s ( p ) 的一个分割， 故由命题2 1 可知，移( 丘) = m i n , e z o _ 口( 0 ，z ) ) 。由假设存在，则( 0 ) 的最优 解对原问题不可行且最优值是子问题中最小的，所以在第一次去除子问题不 会被去掉，因此，有m i n t 5 h v ( o ，1 ) ) = u ( 丘) 。 口 】8 蛊 疏 、l ，、i ， k c ，fl l p p ，- 上海大学硕士学位论文 引理3 2 假设岛不是( p ) 的最优值。令6 = m i n v ( p ) 一，( z ) i x ，( z ) 移( p ) ) 。当v ( p ) 一6 ( p ) 。因为c 1 c 2 c k 一1 c k u ( p ) ，有 ( 丘1 ) 秒( 丘 1 ( c 1 ) ) 移( 丘，l ( c 2 ) ) 冬 ( 匕 l ( 反一1 ) ) s v ( p ) 岛像1 f 2 0 p t 岛。所以问题( o ，f ) 和( 以，( c t ) ) ( i = 1 ，2 ，k 一1 ) 不会被移除，因此