基于MATLAB 软件的离散变量优化问题的解法

李 渊，武维承

（山西大同大学机电工程学院，山西大同 037003）

0 引言

离散变量是指在规定的变量界限内，只能从有限个离散值或整数值中取值的一种变量[1]。如齿轮的模数、齿数，型钢的尺寸，加强肋的数目，职工人数、机器台数等。有些性质上属于连续变量的现象也按整数取值，例如评定成绩、年龄等虽属连续变量，但一般按离散变量来处理。

求解离散优化问题的最优解，传统方法的基本思想是先按连续变量方法求得优化解，然后再进一步基于圆整法等寻找整型量或离散量优化解。这种方法的缺点是可能得不到可行最优解，或所得的解不是离散最优解。除了传统方法，还有两种基本方法，隐式枚举法（如分支定界法）和随机或进化方法（如模拟退火算法、遗传算法）。例如，郭璠等[2]针对目前航天器在研制过程中的质量特性配平问题，提出一种利用分支定界法结合序列二次规划法的离散变量优化方法，从而获得配平设计最优解。黄海燕等[3]在船舶工艺可行性分析基础上，针对多工况下船体结构动力特性设计，建立了使用自适应模拟退火算法的优化模型。在齿轮传动或者减速器优化设计方面，王盛等[4]对行星轮系采用遗传算法进行混合离散变量优化。陈连等[5]针对摆动活齿传动，给出了一种用离散变量模拟退火算法进行尺度优化综合的新方法。杜兴[6]针对行星减速器的离散变量多目标优化设计，采用基于改进粒子群算法的离散变量处理策略对优化设计模型进行求解。在钢结构或者桁架设计方面，姚力[7]对影响预应力钢桁架优化设计的2 类变量，包括连续的索力值和离散的截面尺寸进行研究，建立了数学优化模型来确定施加在索上的预拉力。郝润霞等[8]提出了一种基于离散变量的现代混合算法：遗传—加速粒子群混合算法，并且证明了这种新算法在一定程度上适用于检索截面数据库中型钢规格自动选取。在输电塔结构设计方面，金树[9]提出了一套完整的基于蚁群优化算法的输电塔结构离散变量优化设计方法，张卓群[10]基于有限分析方法和蚁群优化算法，提出了一套完整的针对输电塔结构优化设计与验算分析方法。此外，有些学者基于软件进行离散变量问题的优化，如张永存[11]以桁架截面选型优化为应用背景，基于MSC Nastran 的离散变量优化算法的实现。张立杰[12]利用ANSYS 的APDL 语言，采用基于离散变量的两级算法对钢结构进行优化设计。

1 离散变量优化问题实例

经统计，某中型百货商场对售货人员的需求如下：星期一，12 人；星期二，15 人；星期三，12 人；星期四，14 人；星期五，16人；星期六，18 人；星期日，19 人。为了保证销售人员充分休息，销售人员每周工作5 天，连续休息2 天，每人周工资200 元。如何安排销售人员的工作时间，使得售货人员的总费用最少？

2 数学模型

（1）设计变量。设第i 天开始工作的人数为xi，i=17。

（3）约束条件。每人连续工作5 天，休息2 天；每天工作人数不低于需求量，第i 天工作的人数：一周内除了第i+1 和第i+2这两天开始工作人数，其余5 天的总人数有以下约束。

一、x1+0x2+0x3+x4+x5+x6+x7+12

二、x1+x2+0x3+0x4+x5+x6+x7+15

三、x1+x2+x3+0x4+0x5+x6+x7+12

四、x1+x2+x3+x4+0x5+0x6+x7+14

五、x1+x2+x3+x4+x5+0x6+0x7+16

六、0x1+x2+x3+x4+x5+x6+0x7+18

日、0x1+0x2+x3+x4+x5+x6+x7+19

xi0 且为整数，i=17

3 基于intlinprog 函数的求解

intlinprog 是MATLAB 中用于求解混合整数线性规划的一个函数，用法基本和linprog 相差不大。MATLAB 中，该模型的标注写法如下。

公式（1）中，f，x，b，beq，lb，ub，intcon 是向量；A 和Aeq 是矩阵。基于intlinprog 函数，对上述实例求解，程序如下：

4 基于linprog 函数的求解

以连续变量优化方法为基础的方法，有整型化、离散型化（凑整法、圆整法）等。这种方法的基本思想是首先按照连续变量方法求得最优解，然后再进一步寻找整型量或离散量优化解。这种方法简单易行，但是有一定的盲目性，主要原因是圆整（或凑整）后的结果在很大程度上不在可行域以内。

这种方法的缺点是可能得不到可行最优解，或所得的解不是离散最优解。采用圆整法，基于linprog 函数对上述实例求解，程序如下：

求解结果

x=[0.0000，3.0000，4.8720，2.1280，6.6404，1.3596，4.0000]T，fval=4400。

给x 四舍五入取整，有xz=[0，3，5，2，7，1，4]T。将采用圆整法得到的结果带入数学模型进行校核，编程如下：

采用圆整法得到的值，虽然和直接采用intlinprog 函数求解最优值结果不同，但是经验证采用圆整法得到的值也可行，并且两种方法计算的总费用相同，都为4400 元。

5 结论

对于机械优化设计中含有离散变量的线性优化设计问题，数学建模是重点也是难点。在软件编程求解方面，可以采用求解混合整数线性规划的intlinprog 函数进行求解，也可以基于圆整法采用linprog 函数进行求解，两种解法相互验证，可行有效。