沈文胜 熊方方 金升平 余后强

（武汉理工大学理学院 武汉 430070）

0 引 言

最优化问题广泛应用于工程应用的各部门中.在实际应用中经常需要求解混合规划问题，对于整数线性规划问题，文献［1］给出了其 MATLAB（本文均指 MATLAB7.0）的实现，而对于求解一般的非线性混合整数规划的问题时，在MATLAB中可以调用一个基于分枝定界法编写的现成函数bnb20（）［2］.但是对于有既含有整数又含有离散型的混合非线性规划问题，例如在机械工程的齿轮设计中涉及到的齿轮的模数以及齿数时，模数就是统一的标准数值（如系列（GB1357－87））而齿数则必须是整数的问题，现在的一些数学软件也没有可以解决此类问题的方法，本文给出一个在MATLAB中求解此类问题的实现方法.

考虑一般的混合型非线性规划问题如式（1）所示.

式中：x ＝（x1，x2，…，xn）T为自变量；UB，LB 为向量x的上下界；Aeq，beq分别为线性约束条件中等式约束条件的系数矩阵和常数项；A，b分别为线性约束条件中不等式约束条件的系数矩阵和常数项；Ceq（x）和C（x）分别为非线性约束条件中等式约束条件和不等式约束条件；xi1，xi2，…，xir为离散型变量，取值范围分别为Di1，Di2，…，Dir，xir＋1，…，xik为整数变量；其余变量均为连续变量.

分枝定界算法是一种在问题的解空间树（二叉树）上搜索问题的解的方法.本文利用分枝定界算法对问题的解空间树进行搜索，所采用的分枝定界法的思想是：将原始问题分解，产生一组子问题，分枝（branching）是将一组解分为几组子解，定界（bounding）是建立这些子组解的目标函数的边界，如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝（prune））.

1 MATLAB实现中的技术处理

搜索算法按搜索的方式分有两类：一类是深度优先搜索（depth first search，DFS），其耗费的时间取决于所采用的存储结构.当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O（n2），其中n为图中顶点数.而当以邻接表作图的存储结构时，查找邻接点所需的时间为O（e），其中e为无向图中边的数或有向图中弧的数.由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度O（n＋e）；另一类是广度优先搜索（breadth first searchm，BFS）是树的按层次遍历的推广，遍历图的过程实质上是通过边或弧找邻接点过程，因此广度优先搜索遍历图的时间复杂性和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同［3］.

在MATLAB实现过程中不需要保留树的结构，所以本文利用了两种常见的数据结构来解决变量存储问题：对于深度优先用栈（stack）数据结构来做其存储结构，这是利用栈是按照后进先出的原则存储数据的性质；对于广度优先法则用队列（queue）来表示，这是利用它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作的特性.再结合MATLAB的特点，在实现过程中来节约时间和空间开销.文献［4］中例子的搜索树如图1所示，以此树为例介绍DFS和BFS两种遍历过程中变量的存储情况.首先介绍DFS这种情况见表1.其初始状态为P0，但是P0中的要左分枝即第1步；P1满足约束条件是叶节点需要剪枝，在表1中就是删除P1，剪枝后P0右分枝得到第2步；P2中的解不满足约束条件，再左分枝得到P3表1第3步；P3中的解不满足约束条件，继续左分得到P4表1第4步；P4满足约束条件，P4小于P1，所以P4是叶节点需要剪枝，剪枝后返回对P3右分枝得到P5（表1第5步），其他的以此类推.

图1 例题的搜索树

表1 DFS遍历过程

BFS具体的实际情况见表2.初始状态是相同，但是分之后存储的方式不同，每次分枝后其原来节点就被删除，被两个分枝节点所代替，即P0分枝后得到表2第1步，P1叶节点需要删除，得到第2步；P2分枝得到第3步；P3分枝后得到第4步.其他的以此类推.

表2 BFS遍历过程

由此可见经过这种处理，极大的减少了计算机的存储空间.尤其对于运用在大规模计算中，其优点是显然的.

对于线性问题，文献［4］中认为DFS方法优于BFS方法，并且给出了3点理由.基于类似的原因，对于非线性问题，建议使用DFS方法，第二部分的设计方法就是以DFS为基础编制的，也可以用BFS来编写，原则上只是访问的顺序不同.

2 基于MATLAB的设计方法

用一个3×k的数组xstatus来设定离散或者整数变量的状态，其中xstatus（1；：）是自变量中离散或整数变量的下标；xstatus（2；：）中的每个元素取值为1或2，1表示xstatus（1；：）中对应列的自变量为整数型变量，2表示xstatus（1；：）中对应列的变量为离散变量；xstatus（3；：）是xstatus（1；：）中对应列的离散变量的取值范围的序号，若变量为整数则为零.于是xstatus就可以表示为

构造节点的数据结构如下.

其中：‘Left＿or＿Right’表示左右节点，‘branch＿variable＿index’表示分枝变量的下标，‘xlowe’和‘xupper’分别表示分枝变量的下界和上界，‘solution’表示解向量，‘obj＿value’表示目标函数的值，‘LB’和‘UB’分别表示该节点中变量的下界和上界.分枝的过程就是不断地修改‘LB’和‘UB’的过程.

对于此类问题所采取的策略是：（1）设定当前最好解 MIDP（1）.设定目标函数 MIDP（1）.obj＿value＝inf；（2）利用函数FMINCON（）计算当前节点松弛后的解.使用MATLAB自带函数FMINCON（）进行求解，若EXITFLAG的返回值小于等于零则求解出现错误，该节点需要剪枝.若当前的目标函数值大于 MIDP（1）.obj＿value，则该节点需剪枝；（3）判断是否符合离散和整数（checkIntDisc）.若是整数变量则执行判断该变量是否在某个整数的δ（δ是计算时允许的误差限，根据实际问题选取一较小的值）邻域内，若在该邻域内则说明该值是一可行解，返回到（3）继续判断下一个变量；若不在该邻域内，则对该变量做向上舍入（ceil）和向下舍入（floor），且将舍入后的值记为该变量的下一次分枝的区间的上界和下界，返回该值.结束此次判断.若是离散变量则将该变量的所有取值范围与此时的值进行判断，判断此变量是否在其取值范围中的某个值的δ邻域内，若在该邻域内则说明该值是一可行解，返回到（3）继续判断下一个变量.否则得到该变量的离散取值范围中的上下值作为下一次分枝的上界和下界；（4）对（3）的结果进行判断.若符合整数和离散的要求，则更新 MIDP（1），此时该节点需剪枝；否则执行（5）；（5）对于节点（node）进行左分枝（left）或者右分枝（right）.设定分枝开关，当 MIDP（index）.Left＿or＿right＝1时向左进行分枝，当MIDP（index）.Left＿or＿right＝2时进行右分枝.具体方法如下：设定MIDP（index）.Left＿or＿right＝1时更新自变量的取值区间，将上一节点取值区间的下界记为这一节点的取值区间的上界；否则 MIDP（index）.Left＿or＿right＝2向右进行分枝，将上一节点取值区间的上界记为这一节点的取值区间的下界，返回（2）.

3 应用举例

3.1 一个实例

给定一个求解某齿轮的问题，自变量为x＝［x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14］.式中：x1，x2，x3为模数且取值只能为D1中的数；x4，x5，x6，x7，x8，x9为齿轮的齿数，故取值只能为整数；x10，x11为螺旋角的弧度；x12，x13，x14为啮合齿齿宽.并且x的上下界和D1分别为选取本问题的初始值为

在MATLAB中运用DFS编制的程序来计算，计算过程如下：在MATLAB中输入A＝［］；b＝［］；Aeq＝［］；beq＝［］；xstatus＝［1，2，3，4，5，6，7，8，9；2，2，2，1，1，1，1，1，1；1，1，1，0，0，0，0，0，0］；以及LB，UB，D1，X0后，运行本方法所编软件，经过约4 min的计算，得出解向量和目标函数值分别为：［2.75，2.5，6，28，85，11，74，12，53，0.254 8，0.254 8，31.052 5，31.157 8，74.778 7］和1.157 8×107.

3.2 应用于文献［5］问题

对于优化问题，工程人员常用的方法是把先忽略自变量的离散或整数约束要求，当作连续型的非线性规划问题进行求解，然后将得到的结果圆整［5］，即将自变量选取和它最近的离散值或整数值.这在数学中是没有理论依据的，进行圆整所得到的结果很有可能不满足约束条件.

对于文献［5］中的目标函数及其约束条件，运用本文方法和所开发的程序进行求解，设置参数如下：D1＝［2，2.5，3，4，5］；D2＝［3，4，5，6］；xstatus＝［1，2，3，4；2，2，1，1；1，2，0，0］.可得到如下解向量和目标函数的值：解向量为［2，4，19，17，5.816 9，0.990 3］；目标函数值为351.054 7.

文献［5］的解向量和目标函数的值分别是［2.005 0，4.004 2，14.001 7，16.376 6，5.8，0.99］和346.259，其圆整后结果解向量为［2，4，15，17，6，0.990 3］，目标函数值是350.

经过实际验算，还发现文献［5－7］圆整后的解向量不满足第一和第二个约束条件，是不可行解，说明其圆整的方法对所述问题是行不通的.而本文的方法勿需"圆整"，简单易行，且求出的解为最优解.

4 结束语

对于变量中既含离散约束、又含整数约束的混合非线性规划问题，本文依据分枝定界原理给出了MATLAB中的实现方法，在其实现过程中，在树的遍历上运用了两种存储技巧，减少了运行时间和存储空间，开发了相应的软件，实例表明方法的正确性和软件的可行性.

［1］潘 君.整数规划的分枝定界法及其MATLAB实现［J］.科技信息，2008，（7）：167－168.

［2］薛定宇，陈阳泉.高等应用数学问题的 MATALAB求解［M］.北京：清华大学出版社，2004.

［3］严蔚敏，吴伟民.数据结构［M］.北京：清华大学出版社，1997.

［4］Vanderbei R J.Linear programming：foundations and extensions［M］.Boston：Kluwer Academic Publisher，2001.

［5］崔树平，赵 亮，崔 涵.基于 MATLAB最小体积齿轮减速器的优化设计［J］.机械管理开发，2008，23（6）：54－55.

［6］金全意，孟 航.基于 MATLAB的圆柱齿轮减速器优化设计［J］.辽宁工程技术大学学报：自然科学版，2010，29（z1）：55－59.

［7］张慧鹏.基于MATLAB的二级圆柱齿轮减速器优化设计 ［J］.Machinery Design ＆ Manufacture，2010（4）：101－106.