基于MATLAB的非线性01规划的求解

《基于MATLAB的非线性01规划的求解》由会员分享，可在线阅读，更多相关《基于MATLAB的非线性01规划的求解（4页珍藏版）》请在装配图网上搜索。

1、4 4基于MATLAB的非线性0-1规划的求解学 生：易棉生指导教师：宋来忠三峡大学理学院 摘要：本文主要研究非线性0-1整数规划的解法。首先，通过对传统求解方法的研究，提出从0-1整数规划的变量只取值0和1这个特点来求解，为利用好这个特点，构造了一种数据结构组合树，还根据目标函数和约束条件所含的变量是否被包含在解中取值为1的变量集中，将0-1整数规划的解细分为目标特殊解和约束特殊解。然后，把这个特点具体化为4条性质。根据这些性质，设计出合理的算法，并用MATLAB实现该算法。实验表明，该算法是有效的。Abstract: In this paper, the problem about sol

2、ving nonlinear 0-1 integer programming is studied. Firstly the view that we can use the feature that the variables of 0-1 integer programming only have two values 0 and 1 is raised after discussing some traditional algorithms. To express the feature, a new tree structure, called combination tree in

3、the paper is given and also object-satisfied solution and constrain-satisfied solution is defined, based on whether the variables with the value 1 in objective function and constrained condition belong to the variables with the value 1 in solution. Then it can be specified by 4 properties. According

4、 to these properties, a new algorithm is designed and implemented with MATLAB language. From the experiment, it is proved that the algorithm is effective.关键词：0-1规划 非线性 组合树 解的标记 MATLABkey words: 0-1 integer programming; nonlinear; combination tree; the mark of solution; MATLAB前言本文研究的模型可是： (1)其中，都是非线性

5、函数，、是矩阵，非线性矩阵函数。可以看到，本模型实际上代表了一般的0-1整数规划问题。显然，如果一个算法能求解非线性0-1整数规划，也必然能求解一般的0-1整数规划。要完满地解决这个问题，一个算法应具备两个基本条件：1.求解速度较快，即能在较短的时间内计算出答案；2.能够判断出所求解的0-1整数规划的解的情况，即计算出的答案要么是无解要么是全局最优解。但是，目前对这类问题的许多研究都只局限于线性0-1整数规划，利用线性性质来设计一些算法，如隐枚举法和匈牙利法等（详见参考文献5 16）；有些算法虽然可以求解任何0-1整数规划，但是不能肯定所求的解是全局最优解，如遗传算法和模拟退火算法等。求解非线

6、性0-1整数规划的算法，肯定不能再依赖于具体函数的性质了，因为非线性函数的性质是无法预料的。从理论上将，穷举法不依赖于目标函数和约束条件的性质，能够获得全局最优解，但实际上却不可行。这就给我们指明了一个方向，求解非线性0-1整数规划的算法可以基于穷举法，但需要对其做大量的优化。1 解的定义由于每个变量的取值为0或1，因此可把解向量中取值为1的变量取出来组合成一列，记作，这个组合能够标记一个解，称为解的标记（或者标记），简写为，解向量称为解的标记的对应解，特别地当所有变量取值为0时把这个解的标记记作。解的标记中所含有元素的个数称为解的标记的长度。显然解的标记可以确定一个解，并且的对应解与解的标记

7、中元素的排列顺序无关。长度为的解的标记所能确定解的个数为个。而解的标记的长度可以为，则所有组合可确定的解个数为。另一方面，解空间中不同解的总数为，因此，解的标记与解是一一对应的。当穷尽搜索所有解的标记时也就穷尽搜索完了整个解空间。实际上，解的标记就是1到的所有组合。通过上述定义我们可以看到0-1整数规划的解空间与组合的空间是对应的，可以通过下面的树形数据结构来形象地列举所有的组合：图1 5元组合树这棵树列举出了1到5的所有组合，也即列举了含有5个变量的0-1整数规划所有解的标记，其特点是：孩子节点都含有父亲节点的元素并且比父亲节点多一个元素，节点有孩子节点则必有右兄弟节点；同层节点所含有的元素

8、个数相同，并且从左到右升序排列，每个节点内部的元素也都升序排列，从而使得每个节点都不同；第层将所有长为的解的标记全部列举出来，故第层的节点数为个。由于这种树形结构列举出了所有的组合，不妨称这样的树为组合树。一般地，称个变量对应的组合树称为元组合树。为便于把0-1整数规划的特点与组合树的特点结合起来，先作如下定义：在0-1整数规划中，如果一个解中取值为1的变量包含目标函数所含的变量，则称这个解为目标特殊解；如果一个解中取值为1的变量包含某一约束条件所含的变量，则称这个解为该约束条件的约束特殊解，该约束条件位对应解的特殊约束条件。既不是目标特殊解，又不是约束特殊解的解称为一般解。2 基本性质结合组

9、合树，很容易发现0-1整数规划有下列性质：由组合树的特点，很容易发现0-1整数规划有下列性质：性质1 在组合树中，如果节点的对应解是目标特殊解，则以该节点为根的子树中的每一个节点的对应解都是目标特殊解；性质2 在组合树中，如果节点的对应解是目标特殊解，则以该节点为根的子树中的每一个节点的对应解的目标函数值都相等。性质3 在组合树中，如果节点的对应解是约束条件的约束特殊解，则以该节点为根的子树中的每一个节点的对应解都是该约束条件约束的约束特殊解；性质4 在组合树中，如果节点的对应解是约束条件的约束特殊解，若解不满足该约束条件，则以该节点为根的子树都不满足该约束条件；反之亦然。因为这些性质是以1为

10、标志出现的，不妨称上述性质为0-1整数规划1的继承性。3 性质的证明下面对上述性质一一证明。对于根节点，性质1，2，3，4显然是成立的。对于非根节点，设组合树中节点，记为A。若A的对应解是目标特殊解，则A的对应解中取值为1的变量包含目标函数所含有的全部变量，由于在以A为根的子树节点都含有A的元素，则其对应解中取值为1的变量都含有 A的对应解中取值为1的变量，从而也包含目标函数所含有的变量。因此以A为根的子树节点的对应解都是目标特殊解，性质1成立。因为目标特殊解中取值为1的变量都包含目标函数所含有的变量，这就是说目标函数中的变量都取值1，故目标特殊解的函数值相等；再由性质1知，A的对应解是目标特

11、殊解，则以A节点为根的子树的每一个节点的对应解都是目标特殊解，从而其目标函数值必都相等，即性质2成立。类似可以证明性质3，4。通过把组合树的特点与0-1整数规划相结合，以上4条性质很好地体现了0-1整数规划中变量只取值0和1的特点，更为重要的是这些性质不受目标函数和约束条件的非线性限制。4 算法对组合树进行遍历，就是穷举法。为利用上述性质，应对组合树进行深度优先遍历。在遍历过程中，如果出现了目标函数值比当前最优值还劣，直接舍去该解，即定界；在出现目标特殊解或者有解不满足特殊约束条件时，停止对解对应节点的子树进行遍历，即剪枝。具体算法如下（初始节点为根节点）：1. 计算节点的对应解的函数值，判断

12、该解是否为目标特殊解。在函数值比当前最优解优时，若该解是目标特殊解，标记此解。在函数值比当前最优解劣时，若该解是目标特殊解转4（剪枝）；若该解不是目标特殊解，转3。2. 依次检验每个约束条件，如下：a. 若该约束条件被标记，检验下一个约束条件；b. 解满足约束条件时，若约束条件是该解的特殊约束条件，对其作标记，检验下一个约束条件；c. 解不满足此条件时，若约束条件是该解的特殊约束条件，转4（剪枝）否则，转3；d. 若解均满足约束条件，即此解为可行解也为当前最优解，替换当前解。若解被标记，转4（剪枝），否则，转3。3. 若该节点有孩子节点，对其最左孩子节点的对应解作上述计算，转1；否则，转4。4

13、. 取消对当前节点的对应解的特殊约束条件的标记。若当前节点有右兄弟，对其右兄弟节点的对应解进行上述计算，转1；若当前节点没有右兄弟，则取消对其父亲节点的对应解的特殊约束条件的标记，并对其父亲节点的右兄弟节点的对应解进行上述计算，转1（回溯）；若其父亲节点没有右兄弟节点，算法结束。由于篇幅有限，算法流程图和程序略。5 算法评价及改进设0-1整数规划含有个变量，在目标函数中含有个变量，第个约束条件含有个变量（，为约束条件的个数）。则在整个解空间中，目标特殊解有个，第个约束条件的约束特殊解有个。这说明，在最好的情况下，即约束特殊解都不满足对应的特殊约束条件，要检验的解个数为：。由此可以看到、越小，我

14、们要检验的解个数就越少，从而算法的执行效率就越高。因此，在用此算法计算前如果能对目标函数和约束条件进行简单变形，减少各自所含的变量数将有助与提高算法效率。另外，对约束条件进行的变换使得约束特殊解不满足特殊约束条件，可以使接近算法接近最好的情况，也就是说，通过这个变换使某个约束条件中的变量都取值1的解不满足该约束条件。参考文献01 D.Hanselman,B.Littlef著、张航、黄攀译. 精通MATLAB6北京. 清华大学出版社，2002.6.02 Mathworks: MATLAB6.5:The Language of Technical Compating . Version 6.5.0

15、.18091913 a Release 13. June 18 2002.03 宋来忠等. 数学建模与实验. 科学出版社. 2005.804 姜启源. 数学模型.北京. 高等教育出版社，1993.805 任民. 01规划的单纯形算法J. 宝鸡文理学院学报(自然科学版) , 1997,(02)06 乔学军、刘蓉. 0-1规划的填充函数算法J . 渭南师范学院学报，2005，(02)07 严凌. 大型0-1目标规划的启发式算法J. 上海理工大学学报 , 1998,(03)08 李超. 解0-1线性规划问题的最小部分系数和法J. 韶关大学学报 , 2000,(02)09 唐林炜. 求解01规划的Pe

16、tri网方法J. 山东矿业学院学报 , 1994,(04)10 高培旺、范国兵. 0-1整数线性规划的一种组合直接搜寻法J. 苏州科技学院学报(自然科学版) , 2004,(01)11 祁荣宾、 冯汝鹏. 求解一类0-1整数规划问题的新方法混沌搜索算法J. 控制与决策 , 2003,(06)12 黄惠青. 求0-1型整数规划的一种新方法J. 数学的实践与认识 , 2002,(06)13 高尚、杨靖宇. 非线性整数规划的蚁群算法. 南京理工大学学报，2005,(29)14 胡元明、程学光. 一类01整数规划问题的解法J. 测绘信息与工程 , 1995,(02)15 陶友传、唐泳洪、段正澄. 01整数规划的枚举算法J. 计算机应用研究 , 1992,(03)16 罗余才. 0-1规划的一种新直接列举法J. 系统工程理论与实践 , 1984,(01)