有理系数整数线性规划的模式化算法

D0I:10.13374/i.issn1001-053x.1991.01.035 第13卷第4(1)期 北京科技大学学报 Vol.13No.4(1) 1991年7月 Journal of University of Science and Technology Beijing July 1991 有理系数整数线性规划的模式化算法 龚金双·李宗元· 摘要：给出了有理系数整数线性规划的新的改进算法，称为模式化算法。其特点是： 首先将此类规划变换（模式化）为一种特殊类型，然后利用其特殊结构建立改进算法。其 综合了分枝定界法与割平面法，减少了分枝次数，简化了割平面的技巧。 关键词：整数线性规划，模式化，自然割平面 The Modelling Algorithm of Solving Integer Linear Programming of the Rational Coefficients Gong Jinshuang Li Zongyuan.. ABSTRACT:A new algorithm of solving integer linear programming is intro- duced in which the coefficients of the objective function are rational.This algorithm is called the modelling algorithm.In this algorithm,first of all, it can transform (ILP)into a special programming,then solve the special programming using a kind of special algorithm.The basic ideas of the algo- rithm is due to concentrating of the brance-bound and the cutting-plane,but it decreases the number of the branch and simplifies the technique of the cutting-plane. KEY WORDS:integer linear programming,modelling algorithm,natural cut- ting-plane 1990-05-04收稿 ·北京石油管现学院 ··数力系(Deprment of Mathematics and Mechanics) 393

第 卷第 ‘ 嘲 北 京 科 技 大 学 学 报 叭 。 。 年 月 五 。 。 有理系数整数线性规划的模式化算法 龚金 双 ， 李 宗元 ‘ 幸 摘 要 给出 了有 理 系数 整数线 性规划 的新的改进算法 ， 称为模式化 算法 。 其特点是 首先 将 此 类规划 变换 模式 化 为一种特殊 类型 ， 然后利 用 其特殊结构建立 改 进 算 法 。 其 综合 了分枝定 界法与割 平面法 ， 减少 了分枝次数 ， 简化了割平面 的技 巧 。 关键词 整数线 性规划 ， 模 式化 ， 自然割 平面 夕 ” 夕 夕夕 二 。 ， ， 扭 ， 。 一 一 ， 一 ， ， 一 一 一 魂收稿 北京石油管理学 院 数 力系 旧 爪 皿 DOI ：10．13374／j ．issn1001－053x．1991．04．035

近年来，在传统的分枝定界法与割平面法〔1)的基础上，陆续产生了许多改进算法。 本文对如下的有理系数整数线性规划(RIP)提出了一种新的改进算法，称之为模式化算 法： MinCrx (Ax≤b (RIP) (x,取整数 (1) j=1.2……n 其中Cr=(C:,C2…C)C,为有理数 j=1,2…n x=(x1,x2,.)T,b=(61,b26)T A为m×n矩阵 此算法的基本构思是：通过变换将(RIP)化为一种特殊形式的整数线性规划(MIP) MinC,y (MIP) JBy≤b (2) y,为整数 j=1,2…n 其中，C,为C的某一分量，不失一般性，可假定C,>0,B为m×n矩阵，B与A的关系 见定理1多y=(y1,y2…y.)「。 然后，建立求解具有特殊结构的(MIP)的算法。值得注意的是，由于在计算机上求解一 般整数线性规划时，如遇到无理数，均用有理数来近似。所以，本文的方法实际使用范围相 当广泛。 1(RIP)到(MIR)的模式化变换 定理1：任何目标函数系数为有理数的纯整数线性规划都可以化为(2)形式的整数线性 规划。 证明：在(1)形式的(RIP)中，由于C,都是有理数(j=1,2,…n),所以存在整数 w>0,使得Cr=品(C1,C,…C),其中C;(=1,2,…m)均为整数，因而 可设C,均为整数。 (1)如果存在，1≤i≤n,使得C:lC,j=1,2,…n,则作变换： y,=×;j≠i 1 y=C-CIx (3) 即y=Bx (4) 10 0 0 1 0 …0 B=C1C2 C3 C. i行 5) C.C . 0 00 0 394

近年来 ， 在传统的分 枝定界法与割平面法 〔 ” 的基础上 ， 陆续产生 了许多改 进算法 。 本文 对如下的有理系数整数线性规划 提出了 一种新的改进算法 ， 称之为模式 化算 法 ‘ 劣 成 ‘ ， 取整数 其 中 ， ” 一 ， 为有理数 二 。 二 。 二 。 打 ， 。 。 种 二 二 ， ， 义 ， “ 心 。 二 ， ·，一 、 ‘ 为 二 矩阵 此算法 的基本构思是 通过变换将 化为一种特殊形式 的整数线性规划 。 ‘ ， 为整数 ， “ 。 。 “ 月 其 中 ， ‘ 为 的某一分 量 ， 不失 一般性 ， 可假 定 。 ， 为 矩阵 ， 与 的关系 见定理 ， ， … 。 然 后 ， 建立求解具有特殊结构的 的算法 。 值得注意的是 ， 由于在计算机 上求解一 般整数线性规划时 ， 如遇到无理数 ， 均用有理数来近似 。 所以 ， 本文 的方法实际使用 范围相 当广泛 。 到 的模式化变换 定理 任何 目标函数系数为有理数 的纯整数线性规划都可以化 为 形式的整数线性 规划 。 证明 在 形式的 中 ， 由于 ， 都 是 有 理 数 ， ， 一川 ， 。 。 ， 使得 。 一 告 ， ‘ ， “ … ， 其 中 ， ， 一 所 以 存 在 整 数 均 为整数 ， 因 而 可设 ， 均 为整数 。 如 果存在 ， ， 使得 ‘ ， 二 ， ， “ … ， 则作 变换 厂 ， ， 笋 ， ‘ 万一 七 ‘ “ 即 二 二 二 一 ‘ 行 、一 八八… ，’一州﹄卜八 丛认 凡 斌一… 移

易知，B满秩，其逆变换为： x,=y, j≠i *y- A8,· (6) 或 x=B-iy (7) 这里 1 0 0 0 0 1 0 0 B-i= C C2 C3 C. 一i行 (8) C. . C. …1…- C. 0 0 0 1 列 由(3)，(6)可知：x是整向量←→y是整向量，将(7)代入(1)得(MIP): MinCy, (MIP) By≤b y,是整数 j=1,2…n 这里，B=AB-1 (2)如果不存在i,1≤≤n,使得C:iC,j=1,2,…n,则假设|C,l=minC,l}, C中0 令整数9；及r,满足 C,=9C,+r,0≤r,≤|C,j≠i (9) 将(9)代入(1)，可得： Min∑(9，C,+r)x;+C,x: 了Ax≤& (10) (×,为整数 nj=1,2…n 作变换： ￥=， j≠i (I qx;十n 其逆变换为： (xj=x j≠i (12) x,=x!-∑91x{ jxi 由(11)，(12)知：×；是整数←→×；是整数，j=1,2…n,将(12)代入(10)，可得： 395

易知 ， 满秩 ， 其逆变换为 “ 一 夕 ’ ‘ ‘ 一 笋 ‘ 气、 ， 自 一亡几为 或 ‘ 二 一 ‘ 这里 ‘ 卫‘ 公一… 一 一… 一 ·· 一仇… ︸ 口一已… 、 一 一 生 二 行 列 由 ， 可 知 是整向量幸净 是整向 量 ， ‘ ， 簇 了 是整数 将 代入 得 夕 二 ， 。 “ 了气 少、 这里 ， 一 ’ 如果不存在 ， 簇 ‘簇 ， 使得 ‘ ， ， ， … ， 令整数 ， 及 ， 满足 ， 二 ， ‘ ， 簇 ，簇 ‘ 关 将 代入 ， 可得 、 艺 。 ， ‘ 二 ， 、 ‘ ‘ 则 假设 ‘ 卜 ， ， 了今 簇互 “ ， 为整数 。 了 ， “ 。 ” 。 作 变换 盆劣 、、尸 其逆 变换 为 护 一 矛，， 劣 一︸ 劣 ︺、、厂 由 ， 幻 知 ， 是整数“ 净‘ 了 ， 是整数 ， ， 一 ” ， 将 代人 ， 可得

MiaC.+ Ax'≤b (13) (x}为整数， j=1,2n 这里， 1 0 0 海象 0 0 1 0 0 A=AB] B1= 一i行 -q1 -q2 -93 ”14◆ -9。 0 0 0 4中0。 1) i列 此时lr<|C,lj≠i 故每进行一次这样的变换，目标函数中，非零的绝对值最小的系数至少下降1，故经若千次 这样的变换，必能化为情况(1)，定理证华。 2模式化算法 模式化算法，下面以2·表示 step1求解(2)的松弛问题 MinC:y. (14) By≤b 如果(14)无解，则(2)无解，停： 如果(14)有最优解y°=(yi,y,…y)r 若y(j=1,2…n)皆为整数，则y·为(2)的最优解，停； 若y·不为整数，则给定目标函数的初始上界M:=+∞，下界m: Ciy? y”为整数 m:= C:(Cy)+1)y非整数 转step2 step2分枝 (1)若y?是整数，且存在j≠：y?不是整数，则将相应的整数规划分枝，在两个分 枝规划上分别加上约束y1≤〔y)；y,≥〔y)+1； (2)若y:不是整数，且存在j≠，y不是整数，则在两个分枝规划上分别加上约束 y,≤Cy门，y:≥〔y门+1；y≥〔y)+1,y:≥〔y)+1； (3)若y不是整数，y?j≠i均为整数，则在相应整数规划上加上约束y,≥〔y)+1, 仅得一个分枝规划。 step3求解分枝整数规则的松弛问题 如果无解，则进行step4 396

‘ 习 ， 了 劣 产 镇 了为整数 ， ， ， 这里 一 丁 丁 一 一 “ “ 。 “ 。 此时 ， 。 笋 故每进行一次这样的变换 ， 目标 函数 中 ， 非零的绝对值最小 的系数 至少 下降 ， 故经 若干次 这样的变换 ， 必能化为情况 ， 定 理证华 。 模式化算法 模 式化算法 ， 下面以 ’ 表示 求解 的松 弛 问厄 ‘ ‘ 簇 如果 无解 ， 则 无解 ， 停多 如果 有最优解 贯 ， 穿 ， … 忿 若 少 ， “ 皆为整数 ， 则 为 的最优解 ， 停 若 不为格数 ， 则给定 目标 函数 的初始上界 ， 下 界 。 ‘ 〔 乍〕 ，为整数 兮非整 数 转 分技 若 甲是整数 ， 且存在 笋 ‘ 萝不是整数 ， 则 将相应 的整数规翅分枝 ， 在 两 个 分 枝规划 上分别加上约束 二簇 〔 ，〕 ， 〔 ，〕 若 不是整数 ， 且存 在 笋 ， 夕，不是整数 ， 则在两个分 枝规翅上分别加 上 约 束 夕 ，簇 〔少 ， 〕 ， 夕 ‘ 〔夕，〕 夕 ， 〔夕亨〕 ， 夕 ‘ 〔夕兮〕 若 了不是整数 ， 萝 笋 均 为整数 ， 则在相应整数规划上加上约 束 ， 〔 匀 十 ， 仅得一个分 枝 规划 。 求解分技整橄规 划的松 弛 问 皿 如果无解 ， 则进行

如果得到非整数解y·=〔y,…y)T y·是整数 若{C,(Cy)+1)>My不是 则进行step4否则，转step2 如果得到整数解y·=(y?…y·)T 若C,y:>M,则进行step4 若C:≤M,记录此解y",且令M:xCy? 当M>m时，进行step4 当M=m时，进行step5 step4检查是否存在尚未考虑的分枝，若存在，则转step3;否则，进行ste?5, step5终止步 如果M=+∞，则(2)无解 如果M〔y)+1,y,≤〔y)的分枝过程，即不求解(MIP:), (MIPz)便可得到(MIP)的最优解。即存在(MIP'),它是(MIP)增加一些关于y:(i≠)的约 束得出的，且其松弛问题的最优解y=(y1,…y)是(MIP)的最优解。 从而，由假设条件知，存在e>0,使得y=(y1,…y,-e,…y)是(MIP)的松弛 问题的可行解。又注意到y,(j≠)满足(MIP')中关于y,(j≠)的分枝不等式约束，但 (MIP)中没有关于y:的分枝不等式约束，所以，y是(MIP')的松弛问题的可行解。但 C:(y:-e)<C,y,这与y是(MIP')的松弛问题的最优解矛盾，定理证华。 定义：(C,缓慢下降)。若(MIP)与(MIP:)对应的两个松弛问题最优值之差小于 C:时，称为C:缓慢下降。 定理3：用算法2·求解(MIP)时，不存在C:缓慢下降的(MIP,),(MIP,)。 证明：由算法2及(MIP),(MIP。),(MIP:)的意义知，产生(MIPa)与产生(MIP:) 397

如 果得到非整数解 夕 · 二 〔少 兮 ， … 钓 若 心 井 ， 、 蕊裴羹 数 则 进行 否则 ， 转 如果得到整数解 卜二 份 丁 若 、 少 宁 ， 则进行 若 少 于毛 ， 记录此解 ， 且令 二 ‘ ， 当 。 时 ， 进行 当 ， 时 ， 进行 检查是否存在尚未考虑 的分枝 ， 若存在 ， 则转 否 则 ， 进行 终止步 如 果 ， 则 无解 如 果 十 ， 则 为 的 最优值 ， 其对应的整数解为 的 最优 解 。 自然割平面法 与传统 的分 枝定界法相 比 ， 算法 在某些分 枝 规划 中增加 了约 束 ‘ 浮 〔 匀 。 本文 将 它 称 为 自然 割平面 ， 因 为它 类似于作 了一次切割 。 但它 比 的 割平面简单 可 靠 ， 并 且 无需高的技巧性 。 本节定理将表明 ， 由于 引人 自然 割 平面 ， 一般说来 将减少分 枝次数 。 为讨论及叙述的方便 ， 引人下列记号 。 － 表示求解 时 的某个分枝整 数 线 性 规划 也可 以是 、 － 分别 表示 。 增加 夕 ‘ 〔少 宁〕 ， 夕 ‘ 气 〔 宁〕所 得 的分 枝整 数 线性规划 。 否－ 。 的前一级分枝整数线性规划 但 。 为 的情况 除 外 。 定理 如果整数线性规划 有最优解 ，且所有最优解为其松弛问题 的可 行域 的内 点 ， 则用 传统 的分 枝定界法 求解时 ， 必须进行一次 ‘ 〔 份〕 〔 份〕的分枝过程 ， 即 必 须 求解 、 型 的两个分 枝规 划 。 证呱 反证法 。 假设不经过 ‘ 〔 ，〕 ‘ 毛〔 幻 的分枝 过程 ， 即不求解 ， 便可得到 的最优解 。 即存在 ‘ ， 它是 增加一些关于 夕 ， 护 的约 束得 出的 ， 且其松弛问题 的最优解 二 ， ， 夕 。 是 的最优解 。 从而 ， 由假设 条件知 ， 存在 。 ， 使得犷 ， … ‘ 一 。 ， 一 是 ， 的 松 弛 问题的可行解 。 又注意到 ， 笋 ’ 满足 ‘ 中 关 于 ， 并 的 分 枝 不 等 式 约 束 ， 但 ， 中没有 关于 的分枝不 等式约 束 ， 所以 ， ’ 是 ， 的松弛 问 题 的 可 行 解 。 但 ‘ ‘ 一 。 ‘ ‘ ， 这 与 是 ’ 的 松弛问题 的最优 解矛盾 ， 定 理证华 。 定义 ‘ 缓慢下降 。 若 ‘ 与 对应 的两个松 弛问题 最优值 之差 小 于 ‘ 时 ， 称 为 ‘ 缓慢下降 。 定 理 用 算法 求 解 时 ， 不存在 ‘ 缓慢下降 的 。 ， ， 。 证 明 由算法 ， 及 ‘ ， 。 ， ， 的意 义 知 ， 产 生 。 与 产 生

的分枝过程是同时进行的，即使用算法2时，(MIP。)与(MIP,)合并为同一个分枝规划。证 毕。 结 论 用模拟化算法求解，可直接舍掉无解的(MIP,)并将(MIP。)与(MIP,)合并为一。又鉴 于传统的分枝定界法中成对出现C,缓慢下降的(MIP。)与(MIP,),所以，模拟化算法求解 (MIP)时，常常成对减少分枝，从而减少了计算量。 参考文献 1 Land A H,Powell S.A Survey of Available Computer Codes to Solve Integer Linear Programming Problems,Research Report,81-09 LSEPS. London:1981 内凸筋管的成型研究 我国于80年代初引进美国C,E公司火力发电锅炉技术后，高效能的内凸筋管（简称 R.T管)，急需国内试制供应。一台30×10kW火力发电锅炉需用钢管数量2100t,其中R.T 管占14.6%。此外制冷设备等均需这类无缝钢管。电站锅炉上使用R.T管，可以节能、节材 和提高锅炉设备的使用安全，因而国外广泛地研究了此管的成型技术，并获得多项专利。北 京科技大学依据国内现有生产水平，首先在实验室中用冷拔方法生产出了样品，掌握了成型 机理、工具设计、拔制条件等规律后，于1987~1989年与衡阳钢管厂合作进行了4次工业性 试验，拔出了工亚应用的R,T管。· 通过理论和实践研究，得出拔制R,T管的技术关键是： (1)正确选择减壁量和减径量来获得足够高的凸筋高度， (2)减小内模旋转阻力，保证凸筋质量，使之凸筋侧边不刮伤和畸变影 (3)建立理论的内模沟槽曲线方程， (4)选择合理的拔制条件是稳产高产的前提： (5)内模沟槽曲线用折线逼近方法加工，加工费只有原来的1/50，提高了经济效益。 398

的分 枝过程是 同时进行的 ， 即使用算法 ’ 时 ， 种 与 、 合并为同一个分枝规 划 。 证 毕 。 结 论 用模拟化算法求解 ， 可直接舍掉无解的 并将 。 与 合并 为 一 。 又 鉴 于传统 的分 枝定界 法 中成对 出现 ‘ 缓慢下降的 。 与 ， ， 所 以 ， 模拟化算 法 求 解 时 ， 常常成对减少分枝 ， 从而减少了 计算量 。 参 考 文 献 ， 。 ， ， 一 。 内凸筋管的成型研究 我 国于 。年代初引进美国 。 公 司火力发 电锅炉技术后 ， 高效 能 的 内 凸 筋 管 简 称 管 ， 急需国内试制供应 。 一台 弓 火力发 电锅炉需用 钢管数 量 ， 其中 管占 。 。 此 外制冷设备等均需这类无缝钢管 。 电站锅炉上使用 管 ， 可以 节能 、 节材 和提高锅炉设备的使用安全 ， 因而 国外广泛地研究了此管的成型技术 ， 并获得多项专利 。 北 京科技 大学依据 国内现有生 产水 平 ， 首先在实验室 中用冷拔方法生 产 出了样品 ， 掌握了成型 机理 、 工具设计 、 拔 制 条件等规律后 ， 于 年与衡阳钢管厂合作 进行了 次工业性 试验 ， 拔 出 了工业应 用 的 。 管 。 通过理论和 实践研究 ， 得 出拔制 。 管的技术关键是 正确选择减 璧量和减径量来获得足够高的凸筋高度， 减小 内模旋转阻力 ， 保证凸筋质量 ， 使之凸筋侧边不刮伤和畸变， 建立 理论的 内模沟槽曲线方程 选 择 合 理的拔 制条 件是 稳产高产的前提 内模沟槽 曲线 用折线逼 近方法加工 ， 加工 费只 有原来 的 ， 提高了经济效益