基于背包算法的木板切割方案设计  

Design of board cutting scheme based on Knapsack algorithm

作　　者：周康乔 严沛鑫 庞国庆 ZHOU Kang-qiao;YAN Pei-xin;PANG Guo-qing(Nantong University,Nantong 226000,China)

机构地区：[1]南通大学,江苏南通226000

出　　处：《黑龙江科学》2020年第4期29-31,共3页Heilongjiang Science

摘　　要：工业加工过程中常常会遇到使用切割工具生产规格一定的产品,以使得材料利用率最大化和产品利润最大化的情况,即二维材料的最优排样问题。针对多种产品切割要求下二维木板利用率最大优及利润最大化切割问题,建立了动态规划优化模型,并基于背包算法求解,使用了MATLAB软件进行计算,得出在切割多种产品要求下木板利用率最大以及产品利润最大的切割方案。本模型还可以推广到解决其他各类切割木板、玻璃等矩形形状材料的优化问题。In the process of industrial processing,we often encounter the problems of using cutting tools to produce products with certain specifications,in order to maximizing the utilization rate of materials and maximizing the profits of products,that is,the optimal layout of two-dimensional materials. In this paper,a dynamic programming optimization model is established to solve the problem of two-dimensional board maximum utilization and profit maximum cutting under the cutting requirements of a variety of products. Based on the knapsack algorithm,we use the MATLAB software to solve this model to realize the goal of maximizing board utilization and product profit under the cutting requirements of a variety of products. The model can also be extended to solve the optimization problems of other rectangular materials such as wood,glass and so on.

关 键 词：背包算法 木板切割 方案设计 

分 类 号：O221.3[理学—运筹学与控制论] TS652[理学—数学]