矩形件二维优化布局问题

摘
文针矩形件二维优化布局问题混合01规划等方法建立材料利
率目标单层优化模型利遗传算法剩余矩阵算法进行求解研究实际
生产生活中矩形零件排样切割问题
针问题第部分题目求方排样行必种类型
零件条件求解利率切割方案通分析种类型零件
摆放排样方式组合成 4 种类型规矩形块降低排样复杂程度
定义材料利率标准确定利率目标目标函数考虑组合矩形
块排列时面积长度数量等限制确定限制条件建立单目标规划模型模型较
简单采枚举法利 lingo 遍历求解具体排列方案编号 2 零件横
排横放 4 行行 29 编号 3 零件横排横放 5 行行 29 编号 4
零件横排横放 3 行行 16 方案终材料利率 9881出具
体排样图结果进行优检验确定优排样方式模型性较高更具
实性
针问题第二部分题目求考虑工艺限制具体讨限制更少切割
方法根资料现实生产加工环节中切割方案分剪切切割正交切割两种方式
针问讨正交切割方案材料利率首先根材料利率定义
确定利率目标目标函数考虑零件板材排放时长度宽度面积等
限制确定限制条件建立单目标规划模型问零件组合方式法简单利
枚举法求解利基低水线空闲区域利搜索算法模型进行
求解利Matlab掉排样限制材料利率提高9903计算结果进行
优检验确定全局优解
针问题二题目求求解宽已知卷材切割出定零件卷材长
度切割方案 通建立坐标系发现意矩形零件位置实际右
角坐标摆放方式决定问题简化首先材料利率确定利
率目标目标函数考虑零件摆放时意零件出界零件坐标关系
邻接零件间长度宽度限制条件零件位置出现重叠等限制确定限制条件建立
单目标规划模型数学计算复杂性理文属NP问题利遗传算法
结合剩余矩阵算法利Matlab编程实现算法模型进行求解卷材长
度40分米利率100必全局优解出具体排样图
文特色采智高效遗传算法矩形件二维优化问题进行求
解解决该类问题起统筹优化目相算法具较优空间复杂
度精确度等优点矩形件排样问题更加科学化智化日工厂合理设计矩形
件切割方案提高生产效率减少生产成提供参考



关键词：单目标规划 01 规划 低水线法 遗传算法 剩余矩阵


问题重述
问题1：现九种矩阵零件1~9编号尺寸（毫米）分（编号排列）：
零件长度l15858515593176150185185
零件宽度w5570751151856937175120
零件数M200200200100100200400100300
现长2500宽1000板材欲充分利（利率）该板材切割出零件应采
什样方案？
时工艺实际情况限制方（横）排样行
排放种类型零件排放行时竖着排横着排（图
示）果种限制应该样切？工艺提高限制少切割方法会更灵
活请结合实际讨种限制更少情况切割方法

问题2：
欲宽15（分米）卷材切割出二十五零件(编号1~25)尺寸（分米）分
（编号排列）：
零件长度：12 4 6 10 2 6 4 4 7 4 6 4 6 4 2 8 8 8 6
2 8 3 2 3 2
零件宽度：6 7 7 2 5 4 2 6 9 5 4 6 3 5 4 4 6 3 3
6 2 5 5 4 4
请出卷材长度方案



二 基假设
1假设切割矩形零件时损耗未排列矩形零件部分外产生废料
2假设材料利率评价材料否充分利标准
3假设卷材长度没限制









三 符号说明

类型 符号 意义
01
变 量
iq 表示组合矩形块排样方式（1 矩形块排样）
ir 表示零件板材放置方式（1 零件横放）
ijs 表示零件卷材位置关系（1 零件 i 零件 j 左侧）
ijt 表示零件卷材位置关系（1 零件 零件 方）
定 义
变 量
ix 零件 i 竖排横放时列中够摆放零件 i 数
m axim 零件 竖排横放时板材够放置组合矩形块数
iy 零件 竖排竖放时列中够摆放零件 数
maxin 零件 竖排竖放时板材够放置组合矩形块数
ic 零件 横排横放时行中够摆放零件 数
maxia 零件 横排横放时板材够放置组合矩形块数
id 零件 横排竖放时行中够摆放零件 数
maxib 零件 横排横放时板材够放置组合矩形块数
 利率加工零件实际面积总原材料面积百分
 ii
rrxy 排列板材第 i 零件右角坐标
 ii
llxy 排列板材第 零件左角坐标
minL 第三问中卷材长度
已 知
常 数
L 定板材长度
W 定板材宽度
il 排放第 i 零件长度
iw 排放第 零件宽度
is 型号零件面积


四 问题分析
41问题整体分析
矩形件排样优化指定长宽板材 排放需矩形件板材
利率高达节省材料目矩形件排样优化问题实际二维
优化布局问题数学计算复杂性理属NP问题1遗传算法
NP问题进行求解
42问题第部分分析
问题求方（横）排样行排放种类型零件排放行时竖着排横着排种限制求解
利率切割方案首先通限制条件分析种类型零件相
摆放排样方式组合成 4 种规矩形块问题成述组合矩形
块定钢板排样问题降低排样难度减少算法中遍历次数
符合题意定义材料利率标准确定利率目标目标函
数考虑组合矩形块排列时面积长度数量等限制确定限制条件建立单目标规划
模型利 lingo 求解结果进行优检验确定否全局优解
43问题第二部分分析
问题二求问题基础掉种种限制具体讨切割方法效果
通资料查阅知道现实生产加工环节中切割方案分剪切切割（刀切）正
交切割（激光切割）两种方式针问计算正交切割方案材料利率
零件排列方式首先根材料利率定义确定利率目标目标
函数考虑零件板材排放时长度宽度面积等限制确定限制条件建立单目标规
划模型问排列方式法直接利lingo遍历求解利
基低水线空闲区域利搜索算法模型进行简化处理利Matlab编
程实现算法步骤结果计算结果进行优检验
44问题三分析
问题三求求解宽定卷材切割出二十五零件卷材长度
切割方案 通分析知问实际二维优化布局问题通建立坐标系
发现意矩形零件位置实际右角坐标摆放方式决定问题简
化首先材料利率确定利率目标目标函数考虑零件
摆放时意零件出界零件坐标关系邻接零件间长度宽度限制条件零
件位置出现重叠等限制确定限制条件建立单目标规划模型文属复杂NP问
题利遗传算法结合剩余矩阵算法利Matlab编程实现算法模型进行求
解计算结果进行优检验确定否全局优解
五 模型建立求解
51 问题第部分模型建立求解
511 题目中限制条件分析
问题求出定限制条件充分利定板材切割出零件方案
首先分析题目中出限制条件第零件排列方式固定方
（横）排样次行零件类型做求行排放种类型
零件排放行时竖着排横着排实纳样限
制条件满足实际生产程中剪切切割（刀切）需求样限制
排样时相类型加工零件构造成组合矩形块组合矩形块长宽相矩
形件种摆放方式排层面形成题中组合矩形块4种情况图1示：
图 1 4 中矩形块示意图
图 1 出相类型矩形块重新组成新规矩形问题
成述组合矩形块定钢板排样问题降低排样难度
减少算法中遍历次数符合题意
512 优化变量相关参数确定
应图 1 中 4 中摆放情况引入参数便模型建立：
（a）竖排横放时
设 ix 零件 i 竖排横放（图 1 a）时列中够摆放零件 i 数
 iix W w （[ ]表示取整）题目求行摆放种类型零件
种零件排满列时板材充分利设  max iiimMx  零件 竖排横
放时板材够放置组合矩形块数参数示意图图 2 示

图 2 竖排横放组合矩形参数示意图
样竖排横放组合矩形块宽变零件 i 长 il 长 iiwx 中 iw
零件 宽根定义规整理出组合矩形块参数表 1 示：
表 1 竖排横放时相应参数计算数
编号 i 1 2 3 4 5 6 7 8 9
限制数 im 11 14 15 12 20 14 14 20 12
列中零件数 ix 18 14 13 8 5 14 27 5 8
组合矩形长 iiwx 990 980 975 920 925 966 999 875 960
组合矩形宽 15 85 85 155 93 176 150 185 185
通表组合矩形块全部参数
（b）竖排竖放时
设 iy 零件 竖排竖放（图 1 b）时列中够摆放零件 数
 iiyWl （[ ]表示取整）题目求行摆放种类型零件
种零件排满列时板材充分利设  max i i in M y 零件 竖排竖
放时板材够放置组合矩形块数参数示意图图 2 示

图 3 竖排横放组合矩形参数示意图
样竖排横放组合矩形块宽变零件 i 宽 iw 长 iilx 中 il
零件 长根定义规整理出组合矩形块参数表 2 示：
表 2 竖排竖放时相应参数计算数
编号i 1 2 3 4 5 6 7 8 9
限制数 in 3 18 18 16 10 40 66 20 60
列中零件数 iy 66 11 11 6 10 5 6 5 5
组合矩形长 iily 990 935 935 930 930 880 900 925 925

（c）横排横放时
设 ic 零件i 横排横放（图 1 c）时行中够摆放零件i 数
 iicWw （[ ]表示取整）题目求行摆放种类型零件
种零件排满列时板材充分利设  max iiiaMc  零件 横排横
放时板材够放置组合矩形块数样横排横放组合矩形块
宽变零件 宽 长 iilc 中 零件 长根定义规整理出组
合矩形块参数表 3 示：
表 3 横排横放时相应参数计算数
编号 1 2 3 4 5 6 7 8 9
限制数 ia 1 6 6 6 3 14 25 7 23
行中零件数 ic 166 29 29 16 26 14 16 13 13
组合矩形长 iilc 2490 2465 2465 2480 2418 2464 2400 2405 2405

（d）横排竖放时
设 id 零件 横排竖放（图 1 d）时行中够摆放零件 数
 iidLw （[ ]表示取整）题目求行摆放种类型零件
种零件排满行时板材充分利设  max i i ib M d 零件 横排横
放时板材够放置组合矩形块数样横排竖放组合矩形块宽变零件 i 长 il 长 iiwd 中 iw 零件 宽根定义规整理出
组合矩形块参数表 4 示：

表 4 横排竖放时相应参数计算数
编号 i 1 2 3 4 5 6 7 8 9
限制数 ib 4 5 6 4 7 5 5 7 15
行中零件数 id 45 35 33 21 13 36 67 14 20
组合矩形长 2475 2450 2475 2415 2405 2484 2479 2450 2400
原问题限制条件简化原零散零件成参数已知组
合矩形降低排样难度减少算法中遍历次数 513 问题第部分目标函数确定
现定块长宽已知板材排样放置种类限制条件求解充分利
该板材切割出零件优方案首先确定矩形件优化排样问题
结合前做工作题目中零散零件限制条件求转化参数已知
组合矩形块针优方案出材料利率  定义：
材料利率 加工零件实际面积总原材料面积百分衡量切割
方案否合理反映材料利情况济性指标
根材料利率定义出块板材排列型号零件时材料利率：
1
1 100
n
i
i
s LW

   中 L 板材长度 W 板材宽度 is 型号零件面积
确定矩形块板材排样方式引入 01 变量 iq 1iq 时表示矩形块
排样 0iq 时表示矩形块横排样确定零件板材放置方式引入
01 变量 ir 1ir 时表示该零件横放 0ir 时表示该零件竖放
认材料利率时达题目中充分利板材求根定义
确定求目标函数：
     
11
1max z 1 1 1
KK
i iiiii iii i iiiii iii
ii
q wlrmx rny q wlrac rbdS 
            
出目标函数相复杂决策变量 iiiiiiqrmnab
514 问题第部分限制条件确定
通分析知定板材长宽面积定组合矩形块限排列
具体约束：
1长度约束
板长方零件长度应等板材长度限制：
      1 1 1 0iiii iii iiii iiiLqrlm rwn qrcl rdw             
2宽度约束
板宽方零件长度应等板材宽度限制：
     
11
1 1 1 0
KK
i iii iii i iii iii
ii
W q rxw ryl q raw rbl

              3面积约束
排放板材零件总面积应定板材面积：
     
11
0111
KK
ii iii iiiiii ii i iiii
ii
qwlrm xrn yqwlra crb dL W


4数目约束
排列种零件数目应受该种零件总数限制：
0 iimaxMM
5组合矩形块身数量约束
种零件定数量组合矩形块数量限制根排样方式
摆放情况具体限制：
maxmaxmaxmax
0000 iiii
iiii
iiii
MMMMxycdmnab

601 变量取值约束
   0101iirq
约束条件分析完毕
515 问题第部分模型建立
综述该问题背景限制条件矩形件优化排样数学模型：
     
11
1max z111
KK
iii i iii i iiii iiii i i
ii
qwl rmxr n yqwl racr b dS 
   
      
     
     
11
11
1110
1110
0111
0
0

i i i iii iii i ii i i
KK
ii i ii i iii i ii i i
ii
KK
iii i iii iiiii iiii ii
ii
iimax
i
Lq rl mr w nqrc lr d w
Wqr x wr y lqra wr bl
qwl rm xr n yqwl ra cr b dLW
MM
x
st


   
   
   




   
maxmaxmaxmax
000
01 01
iiii
iii
iiii
ii
MMMM ycdmnab
rq








 











该 模 型 中 已 知 参 数 max iiiiiiL x y cLWKM dW求解参数
i i i i i i ir q M m n a b
516 问题第部分模型求解
针矩形块摆放板材利率问题决定lingo遍历寻求全局优解
横排样排样算法程相里取横排样算法例横排样 18
种组合矩形块优组合紧密排列利率废料面积示意图图 4
示：
图 4 剩余废料示意图

中阴影部分代表切割废料出组合矩形块紧密排列方剩余
矩形条放组合矩形块时右侧剩余部分放应行类材
料认时材料利率达
具体程：
1ste p ：横排横放横排竖放 18 种组合矩形块放入集合 A 中
2step ： A 中意抽取元素里求种组合矩形块超限制值抽取
出矩形块紧密排放板材直剩余宽度集合 A 中意种组合矩形块宽
度跳出循环否执行 2step
3step ：计算步骤 2 中组合矩形块面积出材料利率果
矩形块排列方案已结束跳出循环否执行
4step ：较 中材料利率保留中值
算法出横排样利率相较排列材料利率两
者中值问终材料利时排列方案全局优解算法结
束
Lingo 运行结果（程序见附录）表 5 示：
表 5 优排列方案
组合矩形块种类 2 3 4
组合矩形块数 4 5 3
组合矩形块宽度 70 75 115
组合矩形快长度 2465 2465 2480
具体排列方案编号 2 零件横放横排样放置 4 行行 29 编号 3
零件横放横排样放置 5 行行 29 编号 4 零件横放横排样放
置 3 行行 16 方案终材料利率 9881
具体排列方案图 5 示：

图 5 问题终排样图 517 问题第部分结果分析
横排样例通分析知道组合矩形块紧密排列方剩余矩
形条放组合矩形块（题方已剩余矩形块）时右侧剩余部分
放应行类材料板材两方时达优认时
材料利率达结果全局优解
52 问题第二部分模型建立求解
521 关实际加工时种切割方案讨
前讨刀切限制条件问题切割方案实际情况行
业生产设备工艺情况差料方法切割工艺样排样问题求
相根切割时否允许拐弯分问题述剪切切割（称刀切
直线切割）正交切割（激光切割）两种方式切割方案中剪切切割求
切割刀均板材端直线切端挖裁
般说正交切割材料利率剪切切割高实际生产中具体选种切割
方式受生产设备板材厚度生产成等众条件约束问中考虑加工工
艺问题掉排样时种种限制进行具体讨
522 问题第二部分目标函数确定
现定块长宽已知板材考虑排样放置种类限制约束条件求解
充分利该板材切割出零件优方案首先确定矩形件优化排样问题
根材料利率定义问求出块板料排列型号零件时材料利
率：
1
1 100
n
i
i
s LW

  中 L 板材长度 W 板材宽度 is 型号零件面
积根定义确定求目标函数：
1
1max z
K
iii
i
lwMLW 
  

中 il 编号 i 零件长 iw 编号 i 零件宽 iM 编号 零件数
量
523 问题第二部分限制条件确定
确定零件板材放置方式引入 01 变量 ir 1ir 时表示该零件横
放 0ir 时表示该零件竖放通分析知定板材长宽面积定组合矩
形块限排列具体约束：
1长度约束
板长方零件长度应等板材长度限制：
 
1
10
K
i iiiii
i
Lr L Mr W M

  
2宽度约束
板宽方零件长度应等板材宽度限制：
 
1
1
K
i i i i i i
i
W r W M r L M

      
3面积约束
排放零件总面积应板材面积： 1
K
iii
i
L W M S

  
4数目约束
排列零件数目应受需零件数目限制：
0 iimaxMM
501 变量取值约束
 0 1ir 
约束条件分析完毕
524 问题第二部分模型建立
述分析知该问题背景约束排列条件矩形件优化排样数学模型
：
1
1max z
K
iii
i
LWMLW 
  
 
 
 
1
1
1
10
10

0
01
(19)
K
iiiiii
i
K
iiiiii
i
K
iii
i
iimax
i
LrLMrWM
Wr WMrLM
st L WML W
MM
r
i



 

  
 
 
 
 




该模型中已知参数 max iiiL WLWKM 求解参数 iirM相较问该
问限制少模型简单限制越少利 lingo 求解时遍历次数越求
解越困难事实问法利 lingo 遍历求解必须制定新算法解
决该问题
525 问题第二部分模型求解
问求充分利长宽已知板材 9 种零件排样求零件构成集
合中意选取排样整块板材达利率考虑排样程中零件
选取独立性板材中出现未利空白域基低水线
空闲区域利搜索算法加入问中板材限制条件问编程求解算法具体
步骤：
Step1初始低水线设板材面边初始空闲区域链表空矩形零件
面积 iS 定序面积相等长宽 iilw定序形状完全相
类 9 类
Step2：排入矩形件 iR 时先已空闲区域链表中搜索：
（1）果找空闲边形区域排放前排放矩形件该矩形零件
放入空闲边形中 （2）否低水线集合中选取高度低段水线 m inh e igh t 果干段
选取左边段测试该段水线宽度  wide level 否等排放矩形件
宽度 iw ：
果   iwide level w 该矩形件位置排放排放前矩形件更新
高轮廓线 m a xh e ig h t
否   iwide level w iR 位置起搜索排放
矩形件类果存类样矩形件 jR jR 排放前低水线位置减
少该类矩形件 果找放矩形件低水线提升
左右相邻高度较低段水线齐记录产生空闲矩形位置判断否
合算法更新碎片链表更新高轮廓线 maxh e ig h t W  重新找出高度低
低水线 minheight 转(2)
Step3：果矩形件没排放完重复 Step2直轮廓线 minmaxheightheight 结束
通 matlab 实现述算法2（程序见附录）掉排样限制利率
9903
526 正交剪切利率
通问题第部分第二部分结果发现相板材说第
部分条件材料利率 9881第二部分条件材料利率
9903正交切割利率明显高剪切切割通分析发现加工工艺
限制剪切切割方式存足想零件（阴影部分）板材切割图两种
序：

图 6 剪切切割两种切割序示意图
图 b 切割方式时果剩余材料 2 摆放意种零件时废料正
交切割排列方案定考虑切割序说正交切割材料利率
高剪切切割
53 问题二模型建立求解
531 模型建立前准备
问求求解宽已知卷材切割出二十五零件卷材长度
方案设排样卷材宽 W 长 minL卷材面积足排排矩形件
排矩形件 25 种第i 种矩形件长度 il 宽度 iw
知道块矩形件板材位置该矩形件左角右角坐标完
全确定板材左角原点建立坐标系排列板材第 i 零件右角坐标  ii
rrxy 左角坐标  ii
llxy 图 7 示：

图 7 零件卷材坐标示意图
通等式求出：
ii
r l i
ii
r l i
x x l
y x w




（横放）
ii
r l i
ii
r l i
x x w
y x l




（竖放）
确定矩形块板材排样方式引入 01 变量 ir 1ir 时表示零件横
放 0ir 时表示零件竖放样零件位置完全右角坐标摆放
方式（横放竖放）决定块矩形零件排放实际三变量
532 问题二模型目标函数确定
问求求解宽已知卷材切割出二十五零件卷材长度
方案首先确定矩形件优化排样问题根材料利率定义问
求出卷材排列型号零件时材料利率：
1
1 100
n
i
i
s LW

 
中 L 材料长度W 材料宽度 is 型号零件面积根定义
确定求目标函数：
1 min
1max
K
ii
i
z l w WL
   

中 il 编号i 零件长 iw 编号i 零件宽 minL 卷材长
度该目标函数决策优化变量
533 问题二限制条件确定
设零件 ij意相两零件方便表示零件卷材位置关系
引入 01 变量 ij ijst 1ijs  时说明零件i 零件 j 左侧 0ijs  时说明零件 零件
右侧 1ijt  时说明零件 零件 方 0ijt  时说明零件 零件 方根前建立坐标系限制条件：
1零件摆放时意零件出界：
min

i
r
i
r
x L i I
y W i I


摆放时台阶方式左角右角次摆放意零件需
满足出界约束
2零件坐标关系：
 
 
1
1
ii
rliiii
ii
rriiii
xxrwrliI
yyrlrwiI



摆放时意零件言长宽已知该零件左角坐标右角坐标
应满足约束关系
3邻接零件间长度宽度限制条件：
 
 
min1
1
ij
rlij
ij
rlij
yysLijI
xxsWijI


摆放时相邻零件间长度宽度限制条件
4零件位置出现重叠：
1 ijjiijjissttijI ij
防止零件位置出现重叠零件间必须满足者左者右关系
5变量数量约束：
 
0
01
iiii
rrll
iijij
WLxyxy
rst


534 问题二模型建立
述分析知该问题背景建立宽已知卷材切割出二十五零件
卷材长度方案模型：
1 min
1max
K
ii
i
zlw WL
 
 
 
 
 
 
min
min


1
1
1
1
1
0
0

1
i
r
i
r
ii
r l i i i i
ii
r r i i i i
ij
r l ij
ij
r l ij
ij ji ij ji
i i i i
r r l l
ij ij ij
x L i I
y W i I
x x r w rl i I
y y r l r w i I
y y s L i j I
x x s W i j I
s s t t i j I i j
W L x y x y
rs
st
t


    
    
    





   
   





 








535 问题二模型求解
问求求解宽已知卷材切割出二十五零件卷材长度
方案零件排样时零件排样序实际先分动态
程剩余矩阵算法块零件排样完成时会产生新预留矩阵供
零件填充整程定排样序进行时遗传算法结合剩余矩
阵算法排样程进行动态优化排样序横竖摆放状态作二维编码
利率适应度函数通选择交叉变异体进行筛选保留适应度函数体
利率基步骤：
Step1：设置遗传算法参数种群 M代数 G交叉率 cP变异率 mP
Step2：采十进制编码排样序中 25 零件编号 iR 应 i 0 2 5 i
产生 1225   序列编码组成染色体 i 数值 0 时判断竖放否
横放
Step3：机产生初始种群获 M 染色体编码
Step4：目标函数板材利率适应度函数取目标函数计算种群
适应度：
1 min
1K
iii
i
flw WL
 
中找出优体保留求解种群适应度需零件板材排
样进行设计剩余矩阵算法算法：
（1）：建立 W 横轴L 轴直角坐标系定义板材左角原点（00）
右角坐标（WL）初始矩形    1 00 RWL 
（2）： 排入矩形    li li ri rix y x y剩余矩形数集合中矩形减掉
矩形件占位置记录剩余矩形剩余矩形进行处理跳转（3）
（3）： 掉面积零已法排剩矩形件剩余矩形具完
全包含关系剩余矩形中面积矩形相交关系矩形全部保留
新剩余矩形集处理完成跳转（4）
（4）：剩余矩形集继续放入矩形排放时选择宽高均等排放矩形件底部
低左剩余矩形矩形件剩余矩形左角重叠排放完成时
跳转（3）直 25 零件排样完成
Step5：次进行选择操作交叉操作变异操作中选择操作轮盘赌选出
批适应度高父代遗传代体 i 选中概率
1

M
i i i
i
P f f

  交
叉操作父代染色体中机设定两交叉点交叉率 cP 实行交叉互换
产生新体变异率 mP 机选取染色体某点值进行单点变异
Step6：重复验算达预定进化代数时结束
通 matlab 编程实现述算法运行结果4：
生成迭代程图形图 8 示：

图 8 算法迭代程图形
图 8 中出着迭代次数增加算法逐渐收敛确定
定迭代次数结果稳定准确信
通述算法终 25 矩形零件排列方案图 9 示：

图 9 25 矩形零件排样图
图中矩形零件摆放方式具体位置出卷材长度 40
分米材料利率 100
六 模型评价改进推广
61模型优点
问题第部分中相类型矩形块重新组成新规矩形
问题成组合矩形块定钢板排样问题降低排样难度
减少算法中遍历次数符合题意具极强实性广泛性 问题第二部分中考虑排样程中零件选取独立性板材
中出现未利空白域基低水线空闲区域利搜索算法加入
问中板材限制条件该问求解算法智高效操作性强
问题二中遗传算法结合剩余矩阵算法排样程进行动态优化排样
序横竖摆放状态作二维编码利率适应度函数通选择交叉变
异体进行筛选保留适应度函数体视利率符合 NPhard 问题
解法具科学性创新性 62模型缺点
文建立模型时忽略部分细节素结果产生定影响次遗传算法
身缺陷构造群体容易进入早熟阶段求解结果局部优解
题目身数规模选遗传算法够体现时间复杂度较低优
点
63模型改进
（1）第问中剪切切割身条件限制刀切割序会导致
结果应结合刀序建立更加智精确模型
（2）台阶法第二问模型进行求解低水线法结果进
行较选取优解
64模型推广
文特色采智高效遗传算法矩形件二维优化问题进行
求解解决该类问题起统筹优化目相算法具较优空间复
杂度精确度等优点矩形件排样问题更加科学化智化日工厂合理设计矩
形件切割方案提高生产效率减少生产成提供参考
七 参考文献
1曹炬矩形件排样优化种似算法北京：现代工业出版社20035
2郑阿奇MATLAB 实教程北京：电子工业出版社20078
3韩中庚数学建模方法应北京：高等教育出版社20096
4姜启源 谢金星 叶俊数学模型（第三版）北京高等教育出版社2006912















附录：
程序：
第问：
model
sets
element118longwidemc
square1LW
endsets
data
long55 70 75 115 185 69 37 175 120 15 85 85 155 93 176 150
185 185
wide990 980 975 920 925 966 999 875 960 990 935 935 930 930
880 900 925 925
c11 14 15 12 20 14 14 20 12 3 18 18 16 10 40 66 20 60

enddata
min2500@sum(element(i)long(i)*m(i))
@for(element(2500@sum(element(i)long(i)*m(i)))>0)
@for(element@gin(m))
@for(element(i)@bnd(0m(i)c(i)))
end


model
sets
element118longwidemc
square1LW
endsets
data
long55 70 75 115 185 69 37 175 120 15 85 85 155 93 176 150
185 185
wide2490 2465 2465 2480 2418 2464 2400 2405 2405 2475 2450
2475 2415 2405 2484 2479 2450 2400
c1 6 6 6 3 14 25 7 23 4 5 6 4 7 5 5 7 15
enddata
min1000@sum(element(i)long(i)*m(i))
@for(element(1000@sum(element(i)long(i)*m(i)))>0)
@for(element@gin(m))
@for(element(i)@bnd(0m(i)c(i)))
End





第三问：
function height draww(abflagwaha)

NN length(a)
P a
R b
ZZlength(wa)

for i 1ZZ
W(i) wa(i)H(i) ha(i)x(i) 0y(i) 0w(i) 0h(i)
0lengthh(i) 0
end

for a 1NN整理排序矩形长宽信息
temp0
w(a)W(P(a))
h(a)H(P(a))
if R(a) 1
tempw(a)
w(a)h(a)
h(a)temp
end
end wh量记录排样方案排样矩形长宽信息
S[0015150] S剩余矩形集

for n1NN程序体部分确定矩形件计算整理剩余矩阵集
sortedx0剩余矩形集进行排序
sortedy0
sortedwide0
sortedhigh0
[sortedy sortedyposition]sort(S(2))
for b 1size(S2)
sortedx(b)S(1sortedyposition(b))
sortedwide(b)S(3sortedyposition(b))
sortedhigh(b)S(4sortedyposition(b))
end
S[sortedxsortedysortedwidesortedhigh]时S根
y排序剩余矩阵集
for d1size(S2) 确定矩形位置
if S(3d)>w(n)&&S(4d)>h(n)
x(n)S(1d)
y(n)S(2d)
numdnum选放置n号矩形件剩余矩形
break
end
end
Snew[[S(1num)y(n)+h(n)S(3num)S(4num)h(n)+S(2num)y
(n)]

[x(n)+w(n)S(2num)S(3num)w(n)+S(1num)x(n)S(4num)]]
Snew记录新产生剩余矩形
for b1size(S2)
if bnum
continue
else
if
(S(1b)b)+S(4b)))||

(S(1b)y(n)<(S(2b)+S(4b)))||

(S(1b)h(n)<(S(2b)+S(4b)))||

(S(1b)(n)&&y(n)+h(n)<(S(2b)+S(4b)))||

((y(n)S(2b)||y(n)+h(n)S(2b)+S(4b))&&(x(n)>S(1b)&&x(
n)S(1b)&&x(n)+w(n)))||

((x(n)S(1b)||x(n)+w(n)S(1b)+S(3b))&&(y(n)>S(2b)&&y(
n)S(2b)&&y(n)+h(n)))||

(S(2b)S(3b)&&(x(n)(1b)&&x(n)+w(n)>S(1b)+S(3b)||x(n)S(1b)||x(n)+w(n)S(
1b)+S(3b)))||

(S(1b)S(4b)&&(y(n)(2b)&&y(n)+h(n)>S(2b)+S(4b)||y(n)S(2b)||y(n)+h(n)S(
2b)+S(4b)))
Stemp[[S(1b)S(2b)S(3b)y(n)S(2b)]
[S(1b)S(2b)x(n)S(1b)S(4b)]

[S(1b)y(n)+h(n)S(3b)S(4b)h(n)+S(2b)y(n)]

[x(n)+w(n)S(2b)S(3b)w(n)+S(1b)x(n)S(4b)]]
Snew[SnewStemp]
else Snew[SnewS(b)]
end
end end
SSnew
SBS＇SCunique(SB＇rows＇)SSC＇删重复剩余矩形
m1delete[]删面积零存剩余矩形
for k1size(S2)
if S(3k)<0||S(4k)<0
delete(m)kmm+1
end
end
S(delete)[]
m1delete[]删法放未放置矩形件剩余矩形
for r1size(S2)
for s(n+1)NN
if
S(3r)>w(s)&&S(4r)>h(s)||S(3r)>w(s)&&S(4r)h(s)||S(3r)
w(s)&&S(4r)>h(s)||S(3r)w(s)&&S(4r)h(s)
delete(m)rmm+1break
end
end
end
SS(delete)
m1delete[]删完全包含关系剩余矩形
for v1size(S2)
for t1size(S2)
if
((S(1v)>S(1t))&&(S(2v)>S(2t))&&((S(1v)+S(3v))<(S(1t)
+S(3t)))&&((S(2v)+S(4v))<(S(2t)+S(4t))))||
(S(2v)S(2t)&&S(4v)S(4t)&&S(3v)
S(1t)&&S(1v)+S(3v)+S(3v)S(1t)+S(3t)))||
(S(1v)S(1t)&&S(3v)S(3t)&&S(4v)
S(2t)&&S(2v)+S(4v)+S(4v)S(2t)+S(4t)))
delete(m)vmm+1
break
end
end
end
S(delete)[]
m1delete[]

end
for n1NN矩形作图
lengthh(n)y(n)+h(n)length变量记录高度
end
height max(lengthh) if flag 1
for n1NN矩形作图
rectangle(＇Position＇[x(n)y(n)w(n)h(n)])
text(x(n)+w(n)2y(n)+h(n)2num2str(P(n)))
end

axis equal
set(gca＇xlim＇[015])
set(gca＇ylim＇[0max(lengthh)])
title(＇排样图＇)
end



clcclear all
w50初始种群
dai10
N 25
wa
[124610264474646428886283232]
ha [6772542695463544633625544]
机数产生初始父代
for k 1 w
a randperm(N)
b randi([0 1]NN)
b b(1)
J1(k) a
J2(k) b
end
rand(＇state＇sum(clock))

遗传算法实现程
A J1
AA J2

for k1dai 产生0～1 间机数列进行编码
B A
BB AA
c randperm(w)
交配产生子代B
for i 1242
F 1 + floor(N*rand(1))
tempA B(c(i)FN)
tempB B(c(i+1)FN)
L length(tempA)
for mm 1L for nn 1N
if B(c(i)nn) tempB(mm)
B(c(i)nn) tempA(mm)
B(c(i)F+mm1) tempB(mm)
tempA B(c(i)FN)
end
end
end
for mm 1L
for nn 1N
if B(c(i+1)nn) tempA(mm)
B(c(i+1)nn) tempB(mm)
B(c(i+1)F+mm1) tempA(mm)
tempB B(c(i+1)FN)
end
end
end
F 1 + floor(N*rand(1))
BB(c(i)FN) BB(c(i+1)FN)
end

变异产生子代C
byfind(rand(1w)<06)
if isempty(by)
byfloor(w*rand(1))+1
end
CA(by)
L3length(by)
for j1L3
bw1 + floor(N*rand(13))
bwsort(bw)

C(j)C(j[1bw(1)1bw(2)+1bw(3)bw(1)bw(2)bw(3)+1N])

end
by1 + floor(w*rand(1L3))
CC AA(by)
for j1L3
bbw1 + floor(w*rand(1))
CC(j) CC(j) + 1
end

生成新父类
G[ABC]
GG [AABBCC]
TLsize(G1) 返回行数
for paixu 1TL height(paixu)
draww(G(paixu)GG(paixu)0waha)
end
TTL length(height)
for TT TL + 1 TTL
height(TT) 100000
end
[ddIX] sort(height)
sel IX(1w)

A G(sel())
AA GG(sel())
hit(k) dd(1)
end
heightt draww(A(1)AA(1)1waha)




《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档