整数优化(网格法)程序设计及应用

D0I:10.13374/j.issn1001053x.1981.s1.025 北京钢铁学院学报 1984年增刊1 整数优化（网格法） 程序设计及应用 计算机应用室吴镶责 捕 要 目前，在机械优化设计中，离散量或混合量的优化设计程序尚少，而在设计变 量中包含有离散变量时，如齿轮的齿数、模数、钢板厚度等，则应选用整数优化程 序。因此，本文以网格法为基础，根据设计变量变化的性质，分别采用连续量和离 散量进行迭代计算，以获得较理想的最优化解。本文用A LGOL语直编写了整数优 化计算程序，并进行了实例计算。程序简单易懂，使用方便灵活，特别对求解小型 混合量优化设计课题是有参考意义的。 一、整数优化的意义 随着电算技术的广泛应用，在机械设计中采用了数学规划的方法，以选择最佳参数达到 最优方案的目的。研究整数量变化选择最优的问题在实际应用中有着重要意义。因此，本文 就整数规划应用问题编写了网格法计算程序与计算实例。 在机械优化设计过程中，被选定为设计变量的参数=〔X1,X:,,X。)T,其中有 些参数是连续变化的量，如杆件长度、支点位置、温度、压力等，而有些变量是离散变化的 量，如齿轮的齿数、标准模数、钢板厚度等。因此，设计变量即可表示为： 了=(X,X2,…,Xk,Xk+1,…,Xn)TX∈Rn {X,X2,,Xk}∈RCRn {Xk+I,Xk+2,…,X}∈R'CRn 式中R‘一整数空间或广义离散量集 R一实数空间或广义连续量集 对于离散设计变盘优化的方法，一般可选用比较成熟的连续量优化方法，最后将所得到 的连续量优化参数向附近的离散参数点进行圆整靠近，再进行2”次的比较运算，从中选择最 佳散离量参数。这种方法对于设计变量个数少的小型题目是适用的。另一种方法则是整数 规划的方法，即设计变量的变化必须在给定的离散点上变化，迭代过程中的任意点都是有定 义的、可行的。有关这方面的论述请参考专著。而本文在座标轮换法的基础上将给定的离散 点做为优化迭代的可行点，即在座标方向上每走一步都落在离散点上，经过反复迭代计算， 从而得到一组优化的离散量点参数。因此称为网格法。 本文中提到的整数并非只是纯整数，它包括无规律的离散数，同时把连续量看作是有限 多个离散的量。因此，这里所研究的问题即包括离散量也包括连续量，综合为混合量的优化 问题。混合量优化方法的应用是进一步研究机械优化设计的一个突破口，对于解决包合离散 *本文在编写过程中得到了陈立周、吴清一等老师的指导和帮助。 95

整数优化 网格法 程序设计及应用 计算机 应 用 室 吴继庚 摘 要 目前 ， 在 机械 优化设 计 中 ， 离散量 或混合 量 的 优化设 计程 序 尚少 ， 而 在设 计 变 量 中包含有 离散变量 时 ， 如 齿轮 的齿数 、 模 数 、 钢板厚度 等 ， 则 应 选用 整数 优化程 序 。 因此 ， 本文 以 网格法为 墓 础 ， 根 据 设计 变量 变化 的性质 ， 分 别采 用连续童和 离 散量 进 行 迭代 计算 ， 以获得 较理 想 的最 优化解 。 本文用 语 官编 写 了整 数 优 化 计算程 序 ， 并进行 了实例计算 。 程 序简单易懂 ， 使 用 方便 灵 活 ， 特别对 求解 小型 混合 量 优化 设 计课 题 是有参考意义 的 。 少 一 、 盛傲优化 的愈义 随着 电算技术 的广 泛应 用 ， 在 机械设 计 中采用 了数学规 划的方法 ， 以选择最佳参数达 到 最优方案的 目的 。 研究 整数 变化选择最 优 的 问题 在 实际应 用 中有着 重 要意 义 。 因 此 ， 本文 就整数规 划应 用 问题 编 写 了网 格法 计算程序 与计算实例 。 在 机械优 化设 计过程 中 ， 被选定 为设 计变里的 参数又 〔 ， ， … … ， 。 〕 ， 其 中有 些参数是连 续变 化的 量 ， 如杆件 长度 、 支点位置 、 温度 、 压 力等， 而有 些 变 是 离散变 化的 量 ， 如 齿轮的齿数 、 标 准模数 、 钢 板厚 度等 。 因此 ， 设计变量即可表示为 又 ， ， … … ， ， ， ， … … ， 。 〕 ， 了 〔 ” ， ， … … ， 〔 ‘ ， 十 ， … … ， 。 〔 ‘ 式中 ‘ — 整数空 间或广义 离散量集 — 实数空 间或广义 连 续量集 对于 离散设 计变量优 化的方法 ， 一般可选 用 比较 成熟的连 续 里优 化方 法 ， 最后 将所得到 的连 续 量优 化参数向附近 的 离散参数点 进 行 圆 整 靠近 ， 再进 行 ” 次 的 比较 运 算 ， 从 中选择最 佳散 离 参数 。 这 种方法 对 于设计变 量个数少 的小型 题 目是适 用 的 。 另一种 方 法 则是 整数 规划的方法 ， 即 设计变 量 的 变 化必 须 在给定的 离散点 上变化 ， 迭 代过程 中的 任意 点都是 有定 义 的 、 可行的 。 有关这方面 的论述 请 参考专著 。 而本 文在座标轮换法 的 基 础 上将给 定的 离散 点做为优化迭 代的可 行点 ， 即 在座标方 向上每走一步都 落在 离散点上 ， 经过反 复迭 代计算 ， 从而得到一组优化的 离散量点 参数 。 因此 称为网格法 。 本文 中提 到 的 整数 并非只 是 纯 整数 ， 它 包括无 规律 的 离散数 ， 同时 把 连续 看作是有限 多个 离散的 量 。 因此 ， 这 里所研究 的 问题 即 包括 离散量也 包括 连续 蛋 ， 综合为混 合 的优化 问题 。 混 合 量 优化方法 的应用是 进 一步研究 机械优 化设 计 的一个突破 口 ， 对于解决 包含离散 朴 本文在编 写过 程 中得 到 了陈立 周 、 吴 清 一 等老 师的指导和 帮助 。 DOI ：10．13374／j ．issn1001—053x．1984．s1．025

量优化设计的课题创造了条件。 二、整敏优化程序设计思路 本程序是采用网格法的基本思想，即在几维欧氏空间中依次沿着“直角座标”方向搜 索，其方向矩阵为单位矩阵⑧，在搜索方向确定之后，从某个可行初始点沿着座标方向向前 跨步，其步长是离散量的间距，也就是从一个离散量点跨步到下一个离散量点，比较相邻两 点的函数值，若函数值下降，则继续跨步求下一个离散点的函数值，然后再进行比较·， 当函数值上升或越出可行区时，则停止本次搜索迭代，此点为这一维方向上的极小点，再以 此点作为更换搜索方向的初始迭代点，同理，又求得这个方向上的极小点。重复进行·次迭 代，求得K轮的优化点X“(。若相邻两轮优化点的函数值之差满足给定精度要求时，即， 1F(X#()-F(X#(+1)川≤E 则X(K+)点即为所求的离散量优化点。 对于离散变量X,的取值范围和点值，要以数组的形式输入，对于连续变量X:的取值范 围和点值，要求输入X:的上下边界值和间隔步长值，然后由程序自动将它变为有限多个离 散点值。因此，本程序将送入的离散量X!与连续量X,皆进行离散化处理。为了便于迭代 并记录迭代过程中可行离散点的位置，将已形成的一维数组转变为二维数组。开始计算时， 对输入的初始迭代点或由程序随机产生的初始迭代点首先确定X0)点在二维数组中的编 号，即在维网格空间的位置。然后在给定的座标方向上进行二维变量编号的增减，以达到 极小化的目的。为了加快搜索速度，对于连续量的变化采用了倍增步长法。 按照上述思路绘制程序框图和用A LGOL语言编写源程序，在TQ一16机上进行了数学 题目与实际应用题目的试算，其结果正确、程序易慌、使用方便，对于求解小型整数（实际 可理解为混合量)优化课题是有实用价值的。 三、程序摇图（见下页） 四、整敏规划过程全文 ePe INTEPROG (N,FK,GK,N3,NX,EPS,X,BL,BU,EI,XO,FX, GX,FGH) eVe N,FK,GK,N3,NX,EPSp eINe N,FK,GK,N3,NX; eRe EPS; eAe X,BL,BU,EI,XO,FX,GX; ePe FGH; eBe eINe NP,NP:=N #W2(0,5I10,2/‘,N,FK,GK,N3,NX) #W2(0,F20.10,/“,EPS), eBe eINe I,J,K,ITER,NN,QQ,STEP,EII,ESI,NM; eRe FO,F1,FOO,FOM,Q,M,M35,M36,M37, eAe NI(30)〔1NP), ePe RANDOM; eBe M:=M*5; 96

量 优化设 计的课题 创造了条件 。 二 、 盆橄优化 粗 序设计思路 木程序是 采用 网格法 的基 本思 想 ， 即 在几 维欧 氏空 间中 依次沿 着 “ 直角座标” 方 向搜 索 ， 其方向矩 阵为单位 矩 阵厚 ， 在 搜 索方 向确定之后 ， 从某个可行 初始点沿着座标 方向向前 跨 步 ， 其步长是离散里的 间距 ， 也 就是 从一个 离散量点跨步到下一 个离散量点 ， 比较相 邻 两 点的 函数值 ， 若 函数值下 降 ， 则继续跨步求下一 个离散点 的 函数值 ， 然后再进 行 比较 … … ， 当函数值 上升 或越 出可 行 区 时 ， 则停止 本次搜索迭 代 ， 此点为这 一维方 向上的极小点， 再 以 此点作为更 换搜索方 向的 初始迭 代点 ， 同理 ， 又求得这个方向上的极小点 。 重 复进 行 次迭 代 ， 求得 轮的 优化点 又 ‘ “ 》 。 若相 邻 两轮优 化点的 函数值之 差 满足给 定精度要求时 ， 即 《 一 价 ‘ ’ 三 则戈， 《 “ ‘ ” 点即为所求的 离散 量优 化点 。 对于 离散 变量 的取值范围 和点值 ， 要 以数组 的形 式输入 ， 对于连续变 ， 的取值 范 围和 点值 ， 要求输入 ， 的 上下 边界 值 和 间隔步 长值 ， 然后 由程序 自动将它变为有 限多个离 散点值 。 因此 ， 本程 序将送 入 的 离散量 与连续 量 ， 皆进 行 离 散 化处理 。 为了便 于迭 代 并记 录迭 代过 程 中可 行 离散点的位置 ， 将 已形 成的一维数组转变为二维数组 。 开始计算时 ， 对输 入 的 初始迭 代点或由 程 序随 机产生 的 初始迭 代点 首 先确定 点在二维数组 中的 编 号 ， 即在 维 网 格空 间的位 置 。 然后 在 给 定 的座标方 向上进行二 维变量编号 的增减 ， 以达 到 极小化的 目的 。 为了加快搜索速度 ， 对于连续 量 的变化采 用 了倍 增步 长法 。 按 照 上述 思路 绘制程 序框 图和用 语 言编 写源程序 ， 在 一 机上进行了数学 题 目与实际应 用题 目的试 算 ， 其结果正 确 、 程 序易崔 、 使 用方便 ， 对于求 解小型 整数 实际 可 理解为混 合 量 优 化课题 是有 实用价值 的 。 三 、 粗 序棍日 见下 页 四 、 盆狱规 划过程全 文 巴 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 。 ， ， ， 然 ， ‘ ， ‘ ， ， ， ， ， 然 ， ‘ ， ‘ ， ， 已 ￡ 。 ， ， ， ， ， ， ， ， ， ， 。 ， ， ， ， ， ， ， ， ， 。 〕 ， 一

输入原始数据 开始 第入给定离散量 将光软虽变为出散币 将一维数组变为二领数H 确定初始点在二维中的编号 随机选点并记录标步 11 I中1+1 I≤N FoM-Fsc T 确定步长STEP的正负作 打即优化结果 NN中NN+STEP 计算新点函数值F, 结束 NN NN-STEP X)可行吗？ 下华吗？ ele M>M37 eTe M+=M-M37 eIeM≥M36eTeM:=M-M36影 ele M>M35 eTe M:=M-M35, Q:=M/M35; eEe, M:=2657863, M35:=2个35多 M36:=2M35, M37:=20M365 ITER:=QQ:=03 #W2 (0,10',X,BL,BU,EI,XO); eFe It=N3+1 eSe 1 eUe NeDe EI〔I):=#ENTIER(BU〔I)-BL(I)/(EI〔I)+1.5), NM:=0: eFe I:=1 eSe 1 eUc N eDe 97

输入 原始数据 开始 输 入 给 定离 散量 将 生续 员 之为离故邢 将 一 雏数 组 变为二 约 名女组 确定初始点在二 维 中的 编 号 了 。 叮于丁吗 随机选 点 手记录标 廿 中 卜 ， · ’ 。 幼 毛 确定步 长 的 正 负仇 打 印优 化结 果 计算新点函 数值 结 柬 冈 中 一 ’ ‘ 可 行吗 了 叉 《‘ 一 下华吗 七 。 七 一 ， 。 七 一 ， 。 七 ￡ 一 ， ， ， 二 个 ， 一 ， 浦 ， ‘ ‘ ， ， ， ， ， 。 ￡ 已 〔 〕 纬 〔 〕 一 〔 〕 〔 〕 ， ， ￡ 例 匕

ele EI(I)>NM eTe NM:=EI(I); eBe eAe XX(27000)(1:NP,1:NM), eFe I:=1 eSe 1 eUe N eDe eFe Jt=1 eSe 1 eUe NM eDe XX〔I,J)=0 ESI:=0g eFe It=1 eSe 1 eUe N3 eDe eBa EII:=EI(I); eFe J:=1 eSe 1 eUe EII eDe XX(I,J):=XO(ESI+J); ESI+=ESI+EII; eEer eFe It=N3+1 eSe 1 Ue N eDe eBe EII:=EI(I); eFe J:=1 eSe 1 eUe EIl eDe XX〔I,J):=BL〔)+(BU(I)-BL〔I)#(J-1)/(EII-1), eEey eFe It=1 eSe 1 eUe N eDe eBe EII:=EI(I); eFe J+=1 eSe 1 eUe EII eDe ele￥ABS(X(I)-XX〔I,J)<1o-5 eTe eBe NI(I):=J,eGe L1;Ee; L1* eEey #W2(0,10‘,NI), LQ:FGH (X) eFeK:=1 eSe 1 eUe GK eDe ele GX〔K)<:o-10eTe eBe eFe I:=1 eSe 1 eUe N eDe eBe RANDOM; QQ:=然ENTIER(QEI〔I))+1, NI(1)+=QQ X(I):=XX(I,QQ);Ee; ePAey eGeLQy eEe; EIe QQ+0 eTe #W2(0,‘/,80SQ,F15.7‘,X)3 FO:=FOO:=FX(1); 98

〕 〔 〕 ， ￡ 。 。 ， 〕 ， 已 ￡ ￡ ￡ ￡ 〔 ， 〕 ， ￡ ￡ 已 二 ， ￡ ‘ 〔 ， 〕 〔 〕 ， ， ， ￡ ￡ 。 〕 ， ￡ 二 ￡ 已 ￡ ， 〕 〔 〕 一 〔 〕 一 ￡ ， 已 已 ￡ ￡ 。 〕 ， ￡ ￡ ￡ 。 。 蕊 〔 一 〔 ， 〕 。 一 。 〔 〕 ， 。 ， 。 。 ， 。 。 ， 炸 ， ‘ ‘ ， ， ￡ 。 〔 〕 。 一 。 ￡ 乙 ， 解 一 〔 〕 ， 〕 ， 〕 ， 〕 ， 。 。 ， 。 。 ， 。 ， ， 奔 。 然 ， ‘ ， ， ‘ ， ， 〔 〕 ， 一 一

LN+ITER:=ITER+1 FOM:=FO; #W2(0,3/,20X,5 HITER=,I3,20X,5HF(X)=,F20.10,/,ITER,FO), eFe I:=1 eSe 1 eUe N eDe eBe Q=X〔I), W2(0,2HX(,I2,2H)=,F20.10,/‘,I,Q) eEey eFe I:=1 eSe 1 eUe N eDe eBe NN:=NI(I):=NI〔I)+1s X(I)+=XX(I,NN); FGH(X) F1:=FX(1)3 eFe K:=1 eSe 1 eUe GK eDe ele GX(K)<10-10 eTe eBe NN:=NI(I):=NI(I)-1; X(I):=XX(I,NN); F1:=F0+10-105 eGe L2y eEes L2:J:=0, ele F1<FO eTe STEP:=1 eELe STEP:=-1 LX:J:=J+1 FO:=F1; eIeJ+1∧EI(I)≥500 eTe STEP:=STEP+STEP, NN+=NI(I)+=NI(I)+STEP; ele NN<1 eTe NN:=NI(I)+=1, ele NN>EI(I)eTe NN:=NI(I):=EI(I) X(I):=XX(I,NN); FGH(X);F1:=FX(1) eFe K:=1 eSe 1 eUe GK EDe ele GX(K)<10-10 eTe eGe L3 ele F1<FO eTe eGe LXy L3:NN+=NI(I)+=NI(I)-STEP; X(I):=XX(I,NN); eEer eIe ABS((FOM-FO)/FOM)>EPS eTe eGe LN; #W2(0,2/,80SE,2/,5X,5 HITER=,I3,10X,6HF(X)=,F15.7,10X, 6HF(XO)=,F15.7,2/,ITER,FO,FOO) eFe I:=1 eSe 1 eUe N eDe 99

， 蕊 ， ‘ ， ， ， ， ， ， ， 二 ￡ 〕 件 ， ‘ 〔 ， ， 〕 ， ， ‘ ， ， ￡ ， ￡ ￡ ￡ 〔 〕 〔 〕 〔 〕 ， 〕 ， 〔 〕 ， ￡ ￡ 。 。 〕 。 一 。 。 〕 〕 一 〔 〕 ， 〕 一 ， 。 ， 。 。 ， 。 一 ， ， 。 斗 八 〔 〕 》 ， 〔 〕 〔 〕 ， 。 己 〔 〕 ， 。 。 〔 〕 。 。 〔 〕 〕 〕 〔 ， 〕 ， 二 〔 〕 ， 已 已 已 ￡ 。 〔 〕 。 一 已 。 。 ， ￡ 已 ， 〔 〕 〔 〕 一 ， 〔 〕 〔 ， 〕 ， 。 ， 。 。 游 一 。 。 。 ， 挤 ， ‘ ， ， ， ， ， ， ， 一 ， ， ‘ ， ， ， ， ￡ ￡ ， 卜