一维线性切割省料算法

生活生产中的实例

在生产活动中,通常需要通过切割、剪裁等手段将原材料加工成所需要的零件尺寸。钢筋、钢管、木材下料时,都要按照工艺需求,确定下料的最优方案,达到最省材料的目的。

比如,钢管下料案例:

一零售店的客户需要钢管: 4米的50根;6米的20根;8米的15根。

零售店老板现在拥有钢管原材料的尺寸是每根19米,数量足够多。

问: 怎样下料可以达到客户目的而最省材料?

问题归纳

怎样切割才能最省料呢?先找出把19米钢筋切成4米6米8米小段的所有可能的切割方式,比如。

(一)4段4米,0段6米,0段8米, 剩下3米;

(二)0段4米,3段6米,0段8米, 剩下1米;

。。。。

以下这张表列出了全部可能的切割方式

在该下料项目中, 设1,2,3,4,5,6,7这七种方案对应所用的19米的原材料数量分别为X1, X2, X3, X4, X5, X6, X7。则全部所用的原料数量为

Min = X1 + X2 + X3 + X4 + X5 + X6 + X7

客户需求为:4米的50根;6米的20根;8米的15根。即符合以下条件即可:

问题就是在符合约束条件下,要求这条总和的式子(Min)的值最小

找出最省料的方案

至此,实际问题转化为数学中的求最小值问题

经过一系列的数学计算和操作,可以计算出最小值为: Min = 25

X2 = 15, X5 = 5, X7 = 5, 其余的X值均为0。

也就是说最小需要25根钢管就可以满足客户要求,用第2,第5和第7种切割方案去切,这三种方案所用的原材料数量分别为15, 5和5

软件辅助计算

以上的例子中,如果全部用人工去算,不仅耗时废力,还容易计算出错,对生产经营活动不利。如果工程量大,人工是很难算出一个优化结果出来的。于是就有了计算机辅助计算优化软件,以下是一款可以计算最优下料方案的APP,能在线使用,能在手机上用,无须安装,打开即用

复制以下连接在手机中打开: http://apps.cancms.com/linecut
试一试