基于梯形和平行四边形的圆片剪冲下料算法设计与实现

提出一种在矩形板材上引入梯形条带来进行排样的方法，首先用两条平行的分界线将板材分为两个大小一致的直角梯形段和一个平行四边形段，分别采用递归算法和动态规划算法确定梯形段和平行四边形段中条带的最优组合，从而确定最优排样方式；再结合线性规划算法解决圆片下料问题，使得整个下料方案的材料利用率最大化。最后采用大量随机生成的例题进行实验，实验结果表明该算法能有效提高材料利用率。

An Algorithm for Circle Cutting Stock Problem Based on Trapezoid and Parallelogram

A pattern of circular cutting in rectangle sheet is proposed by introducing trapezoidalstripes. Plate with two parallel dividing lines will be divided into three segments when the nesting,two segments of the same size right angle trapezoid and one parallelogram segment. Respectivelyrecursive algorithm and dynamic programming algorithm are used to determine the optimalcombination of stripes in trapezoidal section and parallelogram section, so as to determine the optimalpattern. Then combine with linear programming algorithm to solve the problem of thetwo-dimensional cutting pattern problem, making material utilization maximum. Finally, experimentresults of a large number of randomly generated problems show the effectiveness of improvingmaterial utilization of the algorithm.