·636· 工程科学学报，第39卷，第4期 含多种钢管产品，可将其拆分为多个同产品的子订单. 当圆坯包含订单时，订单分配在该圆坯的钢管支数必 (6)订单和圆坯之间是多对多关系.一个圆坯可 须不小于订单的最小分配支数，否则，订单在该圆坯的 以包含多个订单，一个订单也可以分配给多个圆坯 分配支数必须为0：约束(7)为决策变量的取值范围 图1给出了单一尺寸圆坯坯料设计问题的一个实 目标函数(1)可做如下变形： 例，假设订单钢管的重量均为1，订单1~4的订单钢 三(c- 管支数分别为9、10、11和9：最小分配重量为3，即订 会)=c-)=mc- 单的最小分配支数为3：圆坯的重量为14.图1给出了 一种订单钢管与圆坯的匹配方案，在该方案中，圆坯的 (心，三w小将约束条件(3)代入上式可知，目标函 使用数量为3，剩余重量为3. 数(1)可以化简为Minimize mC-∑(o,C.).由于 坏 9 三(m,C)和C均为固定值，故目标函数(1)等价 Minimize m,与目标函数(2)相同.因此，当原料库中只 9 有一种尺寸圆坯时，目标函数(1)和(2)具有一致性， 可以用目标(2)代替(1).此时模型可以简化为单目 图1订单圆坯匹配关系 标模型P2]如下： Fig.I Matching relation between orders and billets Minimize m, s.t.(3)~(7) 1.2符号定义 1.4问题下界 为描述无缝钢管坯料设计问题数学模型，对模型 在模型P2]中，将约束条件(4)作如下变形： 中用到的数学符号做如下定义：o为订单序号；n为订 单数量：0为订单序号集合0={1,2，…，n}:b为圆坯 名C, 序号；m为圆坯使用数量；B为已使用圆坯序号集合 Vb∈B曰 B={1,2,,m}:W。为第b支圆坯的重量，由于圆坯 为单一尺寸，假设重量为C,则W。=C,Hb∈B:C。为 三（后≤mc=豆m,c)≤ 订单o的钢管总支数；w。为订单o的钢管的理论重量； 1 C为订单o的钢管最小分配支数：x为订单o分配 mG→m≥乙￡ (o.C). 到圆坯b中的钢管支数，则x的取值范围是整数集合 已知m∈Z,所以，圆坯数量下界为m"= Z:y为0一变量，1表示订单o分配钢管到圆坯b,否 则为0. [亡云.)[o1表示不小于a的最小整数基 1.3数学模型 于此【定理1】给出了圆坯数量m达到下界的条件. 根据上述定义的数学符号，建立混合整数线性规 划模型PI]如下所示： 定理当满是条件宫(C-宫】<c 时，圆坯数量m达到下界 (x） (1) 证明：由以上结论可知，如果 Minimize m. (2) (c- s.t. 三(（)）<C那么，不等式可以简化为： xw=C。,Hoe0: (3) mC- (e.c)c(m-c< (w.C）. A≤C.VbcB:- (4) 由此可以看出，m-1支圆坯无法容纳全部订单. 定理得证 Cya-xb≤C。-C,Ho∈O,b∈B; (5) Cyu-xa≥0，Ho∈0，b∈B; (6) 在【定理1】中， 月(c-()）表示圆坯 x∈Z,y={0,1},Ho∈0，b∈B. (7) 的总剩余量.因此，根据【定理1】可知：当圆坯总剩余 目标函数(1)表示最小化圆坯总剩余量；式(2)表 量小于圆坯重量时，圆坯数量m达到下界 示最小化使用圆坯数量：约束(3)表示订单钢管必须 全部分配到圆坯中：约束(4)表示每支圆坯分配的订 2求解算法 单钢管总重量不能超过圆坯重量：约束(5)和(6)表示 由于问题为NP难题，很难在短时间内求得问题工程科学学报，第 39 卷，第 4 期 含多种钢管产品，可将其拆分为多个同产品的子订单． ( 6) 订单和圆坯之间是多对多关系． 一个圆坯可 以包含多个订单，一个订单也可以分配给多个圆坯． 图 1 给出了单一尺寸圆坯坯料设计问题的一个实 例，假设订单钢管的重量均为 1，订单 1 ～ 4 的订单钢 管支数分别为 9、10、11 和 9; 最小分配重量为 3，即订 单的最小分配支数为3; 圆坯的重量为14． 图1 给出了 一种订单钢管与圆坯的匹配方案，在该方案中，圆坯的 使用数量为 3，剩余重量为 3． 图 1 订单圆坯匹配关系 Fig． 1 Matching relation between orders and billets 1. 2 符号定义 为描述无缝钢管坯料设计问题数学模型，对模型 中用到的数学符号做如下定义: o 为订单序号; n 为订 单数量; O 为订单序号集合 O = { 1，2，…，n} ; b 为圆坯 序号; m 为圆坯使用数量; B 为已使用圆坯序号集合 B = { 1，2，…，m} ; Wb 为第 b 支圆坯的重量，由于圆坯 为单一尺寸，假设重量为 C，则 Wb = C，b∈B; Co 为 订单 o 的钢管总支数; wo 为订单 o 的钢管的理论重量; Cmin o 为订单 o 的钢管最小分配支数; xob为订单 o 分配 到圆坯 b 中的钢管支数，则 xob的取值范围是整数集合 Z; yob为 0--1 变量，1 表示订单 o 分配钢管到圆坯 b，否 则为 0． 1. 3 数学模型 根据上述定义的数学符号，建立混合整数线性规 划模型［P1］如下所示: Minimize ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) ， ( 1) Minimize m． ( 2) s． t． ∑ m b = 1 xob = Co，o∈O; ( 3) ∑ n o = 1 wo xob≤C，b∈B; ( 4) Co yob － xob≤Co － Cmin o ，o∈O，b∈B; ( 5) Co yob － xob≥0，o∈O，b∈B; ( 6) xob∈Z，yob = { 0，1} ，o∈O，b∈B． ( 7) 目标函数( 1) 表示最小化圆坯总剩余量; 式( 2) 表 示最小化使用圆坯数量; 约束( 3) 表示订单钢管必须 全部分配到圆坯中; 约束( 4) 表示每支圆坯分配的订 单钢管总重量不能超过圆坯重量; 约束( 5) 和( 6) 表示 当圆坯包含订单时，订单分配在该圆坯的钢管支数必 须不小于订单的最小分配支数，否则，订单在该圆坯的 分配支数必须为 0; 约束( 7) 为决策变量的取值范围． 目 标 函 数 ( 1 ) 可 做 如 下 变 形: ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) = ∑ m b = 1 C － ∑ m b = 1 ∑ n o = 1 ( wo xob ) = mC － ∑ n o = ( 1 wo ∑ m b = 1 xob ) ． 将约束条件( 3) 代入上式可知，目标函 数( 1) 可以化简为 Minimize mC － ∑ n o = 1 ( woCo ) ． 由于 ∑ n o = 1 ( woCo ) 和 C 均为固定值，故目标函数( 1) 等价于 Minimize m，与目标函数( 2) 相同． 因此，当原料库中只 有一种尺寸圆坯时，目标函数( 1) 和( 2) 具有一致性， 可以用目标( 2) 代替( 1) ． 此时模型可以简化为单目 标模型［P2］如下: Minimize m， s． t． ( 3) ～ ( 7) ． 1. 4 问题下界 在模型［P2］中，将约束条件( 4) 作如下变形: ∑ n o = 1 wo xob≤C， b∈B ∑ m b = 1 ∑ n o = 1 wo xob≤ ∑ m b = 1 C ∑ n o = ( 1 wo ∑ m b = 1 xob ) ≤mC ∑ n o = 1 ( woCo ) ≤ mCm≥ 1 C ∑ n o = 1 ( woCo ) ． 已知 m ∈ Z + ，所 以，圆坯数量下界为 mLB = 1 C ∑ n o = 1 ( woCo ) ，「a?表示不小于 a 的最小整数． 基 于此，【定理 1】给出了圆坯数量 m 达到下界的条件． 【定理1】当 m 满足条件 ∑ m b = ( 1 C － ∑ n o =1 ( wo xob ) ) ＜ C 时，圆坯数量 m 达到下界． 证 明: 由 以 上 结 论 可 知，如 果 ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) ＜ C，那么，不等式可以简化为: mC － ∑ n o = 1 ( woCo ) ＜ C( m － 1) C ＜ ∑ n o = 1 ( woCo ) ． 由此可以看出，m － 1 支圆坯无法容纳全部订单． 定理得证． 在【定理 1】中，∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) 表示圆坯 的总剩余量． 因此，根据【定理 1】可知: 当圆坯总剩余 量小于圆坯重量时，圆坯数量 m 达到下界． 2 求解算法 由于问题为 NP 难题，很难在短时间内求得问题 · 636 ·