2024年1月22日发(作者：上杭县初中数学试卷一)

五一数学建模竞赛

承 诺 书

我们仔细阅读了五一数学建模竞赛的竞赛规则。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。

我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

参赛题号（从A/B/C中选择一项填写）： B

参赛队号：

参赛组别（研究生、本科、专科、高中）：

所属学校（学校全称）：

参赛队员： 队员1姓名：XXX

队员2姓名：XXX

队员3姓名：XXX

联系方式： Email： 联系电话：

日期： 年 月 日

（除本页外不允许出现学校及个人信息）

五 一 数 学 建 模 竞 赛

题 目： 木料切割最优化问题

关键词：

矩形件下料 切割问题 guillotine

摘 要：

随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具厂木料的切割问题，由一维问题（或者说是1.5维问题）递推到二维问题，通过寻找合适的切割方法（采用guillotine，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一用guillotine方法切割可得一块木板上P1最多能切割59个。问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%，99.23%和99.03%的最佳方案。问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用lingo找寻它的最下限后，用循环得出最大利用率为99.64%，这时候使用的木板数为359块。问题五改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案是在一块木板上切割59块矩形件P1，从而得出最大利润为1174100元，木板的利用率为98.2979%。

问题的提出

优化

问题重述与分析

本题可简化为给你一块已知长宽的矩形木板，和一些知道长宽的矩形产品的生产目标和利润，要求你设计一个最优切割方案，使木板的利用率最高。在本题中，限制因素可以为生产目标、木板的面积、切割一块产品所得的利润。当然，对于这种二维下料问题，还需要考虑零件长、宽两个方向上的限制。

问题一可以看成一个1.5维的切割问题，通过贪心算法我们可以轻易地得出木板切割的近似解，随后利用迭代的思路与方法，逐渐接近它的上限。

问题二除了问题一所涉及的变量P1外增添了新的变量P3，求资源利用率最高的前三种方案。但问题一和问题二都只涉及一块原材料木板。

问题三引入了生产目标作为限制因素，并且要求每块木板上的切割方案相同，目标还是达到最高的利用率。

问题四在问题三的基础上加入P2和P4，因为木板的切割方案相同，实际问题就转化成了一块木板上的切割方案。根据在每块木板上切割同一种的产品，可得到一个需要原材料木板的最低数量，同时可以得出一个生产的优先级，可以根据这个优先级着重安排生产方案，在满足需求的条件下，使木料使用的数量达到最小（这时不一定木板的利用率最大）。后在这个可行解的情形下，找寻最优解。（然后又在不同切割方案下，找寻最佳的木板利用率。）

问题五和问题四类似，在每块木板切割方案一致时，可以转化为一块木板上的最大利润问题。但是问题五放宽了每个产品的需求数量（即生产任务），在给定木板数100的情形下，目标函数变为最大的利润。

条件假设

1、假设在木板上采用guillotine的切割方案

2、采用直线切割

3、合理的切割模式：通常建设一个合理的切割模式的余料不应大于或者等于需要板材的最小尺寸。

4、假设每次切割都精准

符号说明

符号 说明

原料木板的长、宽和数量

第i个产品的长、宽、生产任务和利润

第i个产品在一块木板上切割后的数量

(L,W,B)

(li,wi,di,ci)

xi

xi\' 从第i个条形木板上切割出长度为l1的成材数

自定义的一个期望内的木材的利用率，可以被人为的改动

表示切割方案个数，即有k种切割方案

表示在第i种切割方案下第j种规格板材所切割的数量

K

k

aij

hi

表示第i种方案所用原料木板的数量

模型建立与优化

1、问题一

（1）算法分析

分析第一题，其采用单一材料形式进行分割，我们通过guillotine切割方案进行初步求解，其采用“一刀切”的形式对问题进行求解，得出在一块木板上P1切割的最大数为56，但是（相对误差比较大）利用率比较低。后通过贪心算法再次对问题进行优化求解，得出切割的最大数为60，接近于木板切割（装载）的上限，针对于该问题，贪心策略能得到较好的解，但它不适用于其他问题。

（2）模型建立

建立一个1.5维的切割问题模型来求近似解

图例1：贪心算法

图例2：guillotine切割

minLWl1w1xi\'il1xi\'L,i1,...,nWnw1或者s.t.l1xi\'W,i1,...,nLnw1

（3）模型求解

P1的数量

59

2、问题二

（1）算法分析

木板利用率

98.29793%

在第一题的基础上，继续贪心找到了每种产品的上限，通过guillotine切割进行迭代分析求出不同方案的木板利用率，经过对比分析，选取了三种利用率最高的方案。

（2）模型建立

minLWl1w1x1l1w1x1l3w3x3

x1,x3都为非负整数（3）切割P1和P3的全部方案

方案编号

1

2

3

4

5

6

7

8

9

10

11

12

13

14

P1的数量

4

8

12

16

20

24

28

32

36

40

44

48

52

56

P3的数量

45

40

38

33

31

26

25

21

19

14

12

7

6

0

木板利用率

0.9964

0.9597

0.9850

0.9484

0.9737

0.9370

0.9830

0.9670

0.9923

0.9557

0.9810

0.9443

0.9903

0.9330

（4）模型求解

根据上面的方案，进行利用率的排序，易得三种最佳方案

方案编号

1

9

13

P1的数量

4

36

52

P3的数量

45

19

6

木板利用率

0.9964

0.9923

0.9903

3、问题三

（1）算法分析

可结合问题一，得出在一块木板上分别切割P1和P3所能得到的最大数，再结合生产任务能得

到满足需求的最小木板数，该值为35。假设全部木板都用一种切割方式，并结合贪心启发式算法的多目标二维切割和问题，建立了模型。后进行优化改进，让不同的木板有不同的切割方案，使得木板的利用率达最大。

（2）模型建立

minLWl1w1x11d1Bx3d3LWl1w1x1l3w3x3B35B,x1,x3为非负整数

（3）模型求解

木板S1 P1

的数量

的数量

34 45

2 19

11 6

合计数量：

___47_____

774

minz1d1Bx3d3LWl1w1x1l3w3x3KB35B,x1,x3为非负整数

P3

的数量

4

36

52

1623

木板

利用率

0.9964

0.9923

0.9903

木板

总利用率:

___0.99479___

备注

每块木板切割方案相同

木板总利用率=

问题四

（1）算法分析

问题四采用了guillotine二维切割方法，通过贪心等启发式算法获取最优解的近似解。同时由于该问题属于NP问题，无法采用多项式方法求解，故只能采用guillotine方法得到部分解。

（2）切割方案

P1

25.0000

18.0000

25.0000

34.0000

9.0000

14.0000

19.0000

24.0000

29.0000

34.0000

30.0000

28.0000

26.0000

24.0000

P2

11.0000

13.0000

6.0000

0

3.0000

6.0000

3.0000

0

3.0000

0

0

0

0

0

P3

3.0000

6.0000

9.0000

12.0000

29.0000

20.0000

21.0000

22.0000

13.0000

12.0000

2.0000

4.0000

6.0000

8.0000

P4

9.0000

9.0000

9.0000

9.0000

9.0000

9.0000

9.0000

9.0000

9.0000

9.0000

27.0000

27.0000

27.0000

27.0000

利用率

0.9473

0.9524

0.9218

0.9543

0.9787

0.9658

0.9801

0.9943

0.9814

0.9543

0.9610

0.9690

0.9770

0.9850

20.0000

18.0000

16.0000

4.0000

12.0000

8.0000

4.0000

12.0000

12.0000

12.0000

12.0000

12.0000

12.0000

12.0000

12.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

16.0000

（3）模型建立

0

0

0

6.0000

0

0

0

5.0000

9.0000

8.0000

5.0000

7.0000

6.0000

5.0000

5.0000

0

14.0000

0

8.0000

6.0000

5.0000

0

4.0000

2.0000

2.0000

0

0

10.0000

12.0000

14.0000

16.0000

18.0000

20.0000

24.0000

3.0000

6.0000

12.0000

15.0000

18.0000

21.0000

27.0000

30.0000

28.0000

0

18.0000

2.0000

4.0000

6.0000

8.0000

10.0000

12.0000

14.0000

16.0000

18.0000

27.0000

27.0000

27.0000

27.0000

27.0000

27.0000

27.0000

37.0000

24.0000

18.0000

21.0000

12.0000

11.0000

5.0000

0

7.0000

14.0000

21.0000

27.0000

28.0000

28.0000

33.0000

24.0000

25.0000

23.0000

24.0000

21.0000

0.9597

0.9677

0.9757

0.9964

0.9917

0.9664

0.9824

0.9867

0.9661

0.9669

0.9859

0.9677

0.9842

0.9850

0.9692

0.9539

0.9028

0.9650

0.9669

0.9640

0.9754

0.9450

0.9659

0.9630

0.9733

0.9703

0.9650

minLWBhiaijljwji1j1k4minBhiiBhiihai1kiijdj,j1,2,3,4

hai1kiijdj,j1,..,4

aij,hi为非负整数（4）模型求解

P1

木板S1

的数量

的数量

359 4

LWaijljwj,i1,..,kaij,hi为非负整数P2

的数量

6

P3

的数量

16

P4

的数量

27

木板

利用率

0.9964

备注

每块木板切割方案相同

合计数量：

___359____

774 2153 1623 1614

木板

总利用率:

__0.9964__

木板总利用率=

问题五

（1）算法分析

根据第四题所得分割方案，建立数学模型进行求解。

（2）模型建立

maxcjaiji1jhai1iijdj4

LWaijljwj,i1,...,kj1aij,hi为非负整数（3）模型求解

木板S1 P1

的数量

的数量

100 59

木板S1

合计数量100

P2

的数量

0

P3

的数量

0

P4

的数量

0

利润（元）

1174.1

总利润:

1174100

木板

利用率

0.982979

木板

总利用率:

_0.982979_

备注

每块木板切割方案相同

木板总利用率

进一步讨论 结果表示，分析与检验 误差分析

上述问题求得的只是近似解，可能还有优化的空间，目前还没有发现此类解决NP问题一劳永逸的算法方案。

结语（模型评价，特点 优缺点 改进方法 推广）

该数学模型只能得到解的下限，不能直接得出解的结果，一方面是因为该模型选择用面积近似求解而没有考虑到所装载物体的形状，另一方面是因为无法很好的将木板的长宽与变量联系在一起（约束条件的缺少），因此只能求出可行解的上限或者下限，不能求出精确解。除此之外，上述贪心策略求解切割方案的移植性较差，只能用于解决一些问题，但对于某些问题能得到更好的结果，例如问题一，采用guillotine只能求出装载p1数为56，而采用贪心策略则能求出装载p1数为59，更大得接近此问题的上限装载量60。对于已存在的切割方案的优化求解，可以采用一些智能算法对问题的解空间进行检索，进一步获取较多的切割方案。这种方法也是寻求最优的全局最优解的另一种方式。

参考文献

[1] 向文欣,荀珂,冉翠翠.基于两段排样方式的剪冲下料优化算法[J].锻压技术,2019,44(06):35-40.

[2]郑明月,刘林,阚方,方昶.结合批量问题的多目标矩形件优化排样[J].计算机工程与应用,2014,50(22):260-264.

[3]潘卫平. 矩形件二维剪切下料排样算法研究[D].广西大学,2015.

[4]张军,金明爱,王锡禄,冯恩民.一刀切下料的数学模型[J].延边大学学报(自然科学版),2001(01):11-14.

[5]林春婷,杨连池,王志煌,张国忠,叶德火.激光切纸机网络共享的设计实现[J].电子质量,2018(11):32-34


更多推荐

问题,切割,木板,方案