第5期 张文学等：基于约束满足的板坯设计模型与求解方法 ·643· 值域Z映射为变量的值域D;问题的约束映射为约 else {sum-=p:x=W-sum:p:-=x; 束集合C,板坯设计的可行解问题可以映射为约束 tot -=xt =i;i--;sum =0; 满足问题.进一步设问题的目标表示为函数F,则 if (tot >0)++;)//end if 可将板坯设计优化问题转化为约束满足优化问题 }//end for P=W,D,C,F),对应的模型如下： }//end if (tot >0) [P]min m (1) 上述算法的时间复杂度为O(n·max{g:/W}), s.t. ∑xg=g,i (2) 解的板坯数m=j（三8：)/且最多只有一 ∑，≤W (3) 块板坯有盈余，故该算法得到的解为最优.[证毕] δ≤x≤W,ifyt=1,i,j (4) 定理2问题P是强NP难的 x=0,if yi=0,Yi,j (5) 证明只需将己知是强NP难的三划分问题多 y时∈{0,1}，Vi,j (6) 项式归结为问题P,即可证明定理成立 上述约束满足模型中，目标函数(1)是最小化 对三划分问题的任一实例：给定正整数c1,c2, 板坯数量；约束(2)表示某订单分配到所有板坯的 …,cn,…,c3m,B,记集合A={1,2,…,3n},使得对 重量等于该订单的重量，约束(3)表示所有订单分 3n 配到某板坯的重量受该板坯的重量限制，约束(2) V:eA,有导<6，<号且立G=nB映射问题P的 和约束(3)共同表示订单与板坯之间为多对多关 一个判定实例：每个订单的重量都不超过板坯的重 系：约束(4)表示订单分配到板坯时受该订单的最 量，令6，=g:=c:,Hi∈A;板坯数为n,板坯重量为 小分配重量限制：约束(5)表示某订单不分配到某 B.判定存在集合A的一个划分S,S2,…,Sn,使得 板坯；约束(6)表示变量y,的取值范围. 对1≤j≤m,∑c:=B的充分必要条件是恰好在n 2问题的复杂性 个重量为B的板坯中可以装入这3n个订单. 充分性：当三划分有解时，存在集合A的一个 在上述模型P中，当Vi∈I,38=0时，板坯的 划分S1,S2,…,S,…,S。,1≤j≤n,其中板坯j的订 大小可以任意切割，即订单在板坯中没有最小分配 单集合S,满足∑c:=B.此时问题P有最优解，板 重量限制.针对这种特殊情况，下面的定理1成立： ieS 当Vi∈I,3:=0的条件不成立，即订单在板坯中 坯数为n. 有最小分配重量限制时，下面的定理2成立 必要性：当问题P有最优解时，由Vi∈A, 定理1当Hi∈I,38,=0时，问题P有多项式 <,<号可得板坯数为且每块板坯中包含三 时间最优算法，其最优解的目标函数值为 个订单.若令板坯j所包含的订单集合为S,1≤j≤ [(三：)/W其中n为向上取整 m,可得名6=反所以有n个不相交的子集S,S, 证明当Hi∈I,36,=0时，首先订单重量g: …,S,…,Sn形成对集合A的一个三划分.故定理2 除以板坯重量W的整数部分W(g:/)恰好可生产 得证.证毕] g:/W块板坯：然后将小数部分与其他订单的小数部 上述定理2表明本文考虑的板坯设计问题具有 分进行组合与分解，安排到相应的板坯.其求算法 强NP难的性质：而定理1则表明将所有订单的重 的伪代码如下： for(i=1,j=0,tot =0;i<=n;i++) 量名岛看成是某个订单的重量，且订单没有最小 pi=gi%W;tot +=pi; 分配重量限制时，可得问题P的一个下界 for(t=1;t<=g:/W;t++） {j++x=W:))//end 「（三&/r if (tot >0) {j++: 3求解方法 for(i=1,t =1,sum =0;i<=n;i++) 3.1算法框架及相关定义 sum +=P:: 由于板坯设计问题具有强NP难的性质，如何 if (sum<=W)(x=p::tot-=p:P:=0;} 设计有效的近似算法成为解决该问题的关键.为第 5 期 张文学等: 基于约束满足的板坯设计模型与求解方法 值域 Z + 映射为变量的值域 D; 问题的约束映射为约 束集合 C，板坯设计的可行解问题可以映射为约束 满足问题． 进一步设问题的目标表示为函数 F，则 可将板坯设计优化问题转化为约束满足优化问题 P =〈V，D，C，F〉，对应的模型如下: ［P］min m ( 1) s． t． ∑ j xij = gi，i ( 2) ∑i xij≤W ( 3) δi≤xij≤W，if yij = 1，i，j ( 4) xij = 0，if yij = 0，i，j ( 5) yij∈{ 0，1} ，i，j ( 6) 上述约束满足模型中，目标函数( 1) 是最小化 板坯数量; 约束( 2) 表示某订单分配到所有板坯的 重量等于该订单的重量，约束( 3) 表示所有订单分 配到某板坯的重量受该板坯的重量限制，约束( 2) 和约束( 3) 共同表示订单与板坯之间为多对多关 系; 约束( 4) 表示订单分配到板坯时受该订单的最 小分配重量限制; 约束( 5) 表示某订单不分配到某 板坯; 约束( 6) 表示变量 yij的取值范围． 2 问题的复杂性 在上述模型 P 中，当i∈I，δi = 0 时，板坯的 大小可以任意切割，即订单在板坯中没有最小分配 重量限制． 针对这种特殊情况，下面的定理 1 成立; 当i∈I，δi = 0 的条件不成立，即订单在板坯中 有最小分配重量限制时，下面的定理 2 成立． 定理 1 当i∈I，δi = 0 时，问题 P 有多项式 时 间 最 优 算 法， ( 其最优解的目标函数值为 ∑ n i = 1 gi ) W ，其中「?为向上取整． 证明 当i∈I，δi = 0 时，首先订单重量 gi 除以板坯重量 W 的整数部分 W( gi /W) 恰好可生产 gi /W 块板坯; 然后将小数部分与其他订单的小数部 分进行组合与分解，安排到相应的板坯． 其求算法 的伪代码如下: for( i = 1，j = 0，tot = 0; i ＜ = n; i + + ) { pi = gi% W; tot + = pi ; for( t = 1; t ＜ = gi /W; t + + ) { j + + ; xij = W; } } / /end if( tot ＞ 0) { j + + ; for( i = 1，t = 1，sum = 0; i ＜ = n; i + + ) { sum + = pi ; if( sum ＜ = W) { xij = pi ; tot － = pi ; pi =0; } else{ sum － = pi ; xij = W － sum; pi － = xij ; tot － = xij ; t = i; i － － ; sum = 0; if( tot ＞ 0) j + + ; } / /end if } / /end for } / /end if( tot ＞ 0) 上述算法的时间复杂度为 O( n·max{ gi /W} ) ， 解的板坯数 m = j = ( ∑ n i = 1 gi ) W ，且最多只有一 块板坯有盈余，故该算法得到的解为最优． ［证毕］ 定理 2 问题 P 是强 NP 难的． 证明 只需将已知是强 NP 难的三划分问题多 项式归结为问题 P，即可证明定理成立． 对三划分问题的任一实例: 给定正整数 c1，c2， …，cn，…，c3n，B，记集合 A = { 1，2，…，3n} ，使得对 i∈A，有 B 4 ＜ ci ＜ B 2 且 ∑ 3n i = 1 ci = nB． 映射问题 P 的 一个判定实例: 每个订单的重量都不超过板坯的重 量，令 δi = gi = ci，i∈A; 板坯数为 n，板坯重量为 B． 判定存在集合 A 的一个划分 S1，S2，…，Sn，使得 对 1≤j≤n，∑i∈Sj ci = B 的充分必要条件是恰好在 n 个重量为 B 的板坯中可以装入这 3n 个订单． 充分性: 当三划分有解时，存在集合 A 的一个 划分 S1，S2，…，Sj ，…，Sn，1≤j≤n，其中板坯 j 的订 单集合 Sj 满足 ∑i∈Sj ci = B． 此时问题 P 有最优解，板 坯数为 n． 必要 性: 当 问 题 P 有 最 优 解 时，由 i ∈ A，  B 4 ＜ ci ＜ B 2 可得板坯数为 n 且每块板坯中包含三 个订单． 若令板坯 j 所包含的订单集合为 Sj ，1≤j≤ n，可得 ∑i∈Sj ci = B． 所以有 n 个不相交的子集 S1，S2， …，Sj ，…，Sn 形成对集合 A 的一个三划分． 故定理 2 得证． ［证毕］ 上述定理 2 表明本文考虑的板坯设计问题具有 强 NP 难的性质; 而定理 1 则表明将所有订单的重 量 ∑ n i = 1 gi 看成是某个订单的重量，且订单没有最小 分 配 重 量 限 制 时，可 得 问 题 P ( 的 一 个 下 界 ∑ n i = 1 gi ) W ． 3 求解方法 3. 1 算法框架及相关定义 由于板坯设计问题具有强 NP 难的性质，如何 设计有效的近似算法成为解决该问题的关键． 为 ·643·