论坛 › 算法交流 › 一维下料算法

aimisiyou 发表于 2019-7-17 12:34:54

一维下料算法

本帖最后由 aimisiyou 于 2019-7-17 12:38 编辑

我根据自己的算法手工可以算出较优解，时间也就几分钟而已。
比如原材料规格2m,毛坯规格及数量要求分别为0.8m10根，0.6m4根，1.5m65根，0.7m6根，0.45m7根，0.2m76根。先按数量从多到少排列((0.276)(1.565)(0.8 10)(0.457)(0.76)(0.64))，然后合并列出每种下料方式剩下的余料长
即((0.276)(1.565)(0.8 10)(0.457)(0.76)(0.64))
=((1.5 0.2) 650.3)(0.211)(0.8 10)(0.457)(0.76)(0.64))
=((1.5 0.2) 650.3)(0.80.2) 101)(0.457)(0.76)(0.64)(0.2 1))
=(((1.5 0.2) 650.3)((0.80.2) 101)((0.7 0.45 ) 6 0.85)(0.64)(0.451)(0.2 1))
=(((1.5 0.2) 650.3)((0.80.2) 101)((0.7 0.45 ) 6 0.85))((0.60.6 0.6) 1 0.2)((0.6 0.450.2)1 0.75));;;然后按预料从小到大排列=( ((0.60.6 0.6) 1 0.2) ((1.5 0.2) 650.3) ((0.6 0.450.2) 1 0.75) ((0.7 0.45 ) 6 0.85) ((0.80.2) 101));;;从第一项开始，余料0.2m>=最小毛坯0.2m,将最后一个0.2m迁移往前，依次往后，尽量使得余料小于最小毛坯长度（核心思想即若是后续零件往前移可以使整体更紧凑，那么就将该零件往前移）。
……
最终得到( ((0.45 0.45 0.45 0.45 0.2) 1 0) ((0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2) 1 0) ((0.8 0.8 0.2 0.2)1 0)((0.6 0.6 0.6 0.2)1 0)((0.8 0.7 0.45) 2 0.05)
    ((1.5 0.45) 1 0.05) ((1.5 0.2 0.2) 32 0.1) ((1.5 0.2) 1 0.3) ((1.5) 31 0.5) ((0.8 0.7) 4 0.5) )
最前面几项余料小于最小毛坯0.2，从（（1.5 0.2）1 0.3）开始余料均大于最小毛料，若将前面 ((1.5 0.2 0.2) 32 0.1)中的0.2迁移过来，余料由0.3变为0.1，但((1.5 0.2 0.2) 32 0.1)中的预料为0.1,即迁移后对整体没有改进，所以不予迁移。以此类推。
故总根数为1+1+1+1+2+1+32+1+31+4=75根

对比别人EXCEL程序结果74根，发现须补充几条规则：1若迁移后对整体没一影响，但将前面较小的零件移至后面了，这种情况还是要迁移的。如（……（0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2）1 0）……(（0.80.8）2 0.4）），即迁移后（……（（0.8 0.8 0.2 0.2）2 0）……（（0.6 0.2 0.2 0.2）1 0.8））转化为；2、余料（大于最小毛坯长）须两极分化，一个小，一个大，而不能合并取平均，如（（0.80.7）2 0.5）应为（(（0.80.8）1 0.4）((0.7 0.7) 1 0.6)。

aimisiyou 发表于 2019-7-17 12:35:22

本帖最后由 aimisiyou 于 2019-7-17 12:47 编辑

那么有个问题，即若迁移后对整体没影响，但会将较大毛坯和较小毛坯同时后移，此时该不该发生迁移呢？
如（……（（1.50.30.2）1 0）……（（0.6 0.6 0.5）1 0.3）……）？
若前面迁移项中每项均不大于后面迁移项中的最大值，显然迁移。
感觉视后面的情况而定，举个不恰当的例子，如果后面有项差值大于1.5，那么就迁移，否则不迁移。
即（……（（1.50.30.2）1 0）……（（0.6 0.6 0.5）1 0.3）……（（）K   1.6）……）时迁移。

aimisiyou 发表于 2019-7-17 12:44:16

补充几条排位规则：
1、当余料相同且项内最小毛坯相同时，按各项内最大毛坯长度由大到小排列；
2、当余料相同且项内最大、最小毛坯长度相同时，按最小毛坯个数由少到多排列。
故( ((0.45 0.45 0.45 0.45 0.2) 1 0) ((0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2) 1 0) ((0.8 0.8 0.2 0.2)1 0)((0.6 0.6 0.6 0.2)1 0)((0.8 0.7 0.45) 2 0.05)……）正确的排位为( ((0.8 0.8 0.2 0.2)1 0)((0.6 0.6 0.6 0.2)1 0)((0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2) 1 0) ((0.45 0.45 0.45 0.45 0.2) 1 0) ((0.8 0.7 0.45) 2 0.05)……）

aimisiyou 发表于 2019-7-17 12:52:35

((3.623.52 1.72) 110 3.14))   ;;;原料长2m.
=((3.623.52 1.72 1.72) 55 1.72) (3.623.52) 55 4.86) )
=((3.623.52 1.72 1.72 1.72) 27 0) ((3.62 3.52 1.72 1.72) 1 1.72) ((3.623.52 1.72) 27 3.14)(3.623.52) 55 4.86) )
=((3.623.52 1.72 1.72 1.72) 28 0) ((3.623.52 1.72) 26 3.14)(3.623.52) 56 4.86) )
=((3.623.52 1.72 1.72 1.72) 28 0) ((3.623.52 1.72 1.72) 13 1.72)((3.623.52) 13 4.86)(3.623.52) 56 4.86) )=((3.623.52 1.72 1.72 1.72) 28 0) ((3.623.52 1.72 1.72) 13 1.72)((3.623.52) 69 4.86) )
=((3.623.52 1.72 1.72 1.72) 28 0) ((3.623.52 1.72 1.72 1.72) 6 0) ((3.623.52 1.72 1.72) 1 1.72) ((3.623.52 1.72 ) 6 3.14)   ((3.623.52) 69 4.86) )
=((3.623.52 1.72 1.72 1.72) 34 0) ((3.623.52 1.72 1.72) 1 1.72) ((3.623.52 1.72 ) 6 3.14)   ((3.623.52) 69 4.86) )
=((3.623.52 1.72 1.72 1.72) 34 0) ((3.623.52 1.72 1.72 1.72) 1 0) ((3.623.52 1.72 ) 5 3.14)   ((3.623.52) 69 4.86)((3.623.52) 1 4.86) )
=((3.623.52 1.72 1.72 1.72) 35 0) ((3.623.52 1.72 ) 5 3.14)   ((3.623.52) 70 4.86) )
=((3.623.52 1.72 1.72 1.72) 35 0) ((3.623.52 1.72 1.72 ) 2 1.72) ((3.623.52 1.72 ) 1 3.14) ((3.623.52) 2 4.86)   ((3.623.52) 70 4.86) )
=((3.623.52 1.72 1.72 1.72) 35 0) ((3.623.52 1.72 1.72 ) 2 1.72) ((3.623.52 1.72 ) 1 3.14)((3.623.52) 72 4.86) )
=((3.623.52 1.72 1.72 1.72) 36 0) ((3.623.52 1.72 1.72 ) 1 1.72) ((3.623.52) 1 4.86)((3.623.52) 72 4.86) )
=((3.623.52 1.72 1.72 1.72) 36 0) ((3.623.52 1.72 1.72 ) 1 1.72) ((3.623.52) 73 4.86) )
=((3.623.52 1.72 1.72 1.72) 36 0) ((3.623.52 1.72 1.72 ) 1 1.72) ((3.623.52 3.62) 241.24)((3.52 3.62 3.52)24 1.34) ((3.62 3.52) 1 4.86))
=((3.623.52 1.72 1.72 1.72) 36 0)((3.623.52 3.62) 24 1.24) ((3.52 3.62 3.52)24 1.34)((3.623.52 1.72 1.72 ) 1 1.72)((3.62 3.52) 1 4.86))
=((3.623.52 1.72 1.72 1.72) 36 0)((3.623.52 3.62) 251.24) ((3.52 3.62 3.52)24 1.34)((3.52 1.72 1.72 ) 1 5.04))
除最后一项（仅为一根）外，其余每项差值均小于最小毛坯长度，故程序结束。程序运行结果根数为36+25+24+1=86（应该是最优解吧），理论值（3.62+3.52+1.72）*110/12=81.21

aimisiyou 发表于 2019-7-18 00:07:59

本帖最后由 aimisiyou 于 2019-7-18 00:15 编辑

判断条件存在错误，即“每项差值均小于最小毛坯长度，故程序结束”不正确。
如（（0.8   0.40.3   0.3） 100   0.2）
= （（0.8   0.40.3   0.3） 100   0.2）
=（（（0.80.30.30.30.3）25   0）（0.80.80.4）37   0）（0.80.40.40.4）10）（（0.4   0.4   0.4   0.40.4） 12   0）（0.30.30.30.30.30.3）160.2）（0.3 0.3 0.3 0.3）1 0.8））

markfang2050 发表于 2019-10-26 21:16:53

这一类问题叫排样。遗传算法解决。

王守恩 发表于 2019-10-27 12:48:47

我会做具体的题目。
080×10=0800——05，040×05，040×00，040×00
060×04=0240——04，140×04，140×01，140×01
150×65=9750——65，050×65，050×58，050×25
070×06=0420——00，070×06，070×00，070×00
045×07=0315——00，045×07，045×00，045×00
020×76=1520——00，020×76，020×66，020×00
合计13045,下料74根,剩余140×1(根)+50×25(根)
1，至少得66根(13045÷200)；
2，至少得70根(65+10÷2)；
3，至少得73根(65+(10+6)÷2)；
4，74根是可行的(65+5+4)。

aimisiyou 发表于 2019-10-30 16:51:31

王守恩 发表于 2019-10-27 12:48
我会做具体的题目。
080×10=0800——05，040×05，040×00，040×00
060×04=0240——04，140×04，140 ...

看不懂你列式的意义。

王守恩 发表于 2019-10-30 18:18:30

aimisiyou 发表于 2019-10-30 16:51
看不懂你列式的意义。

我会做具体的题目。
比如原材料规格2m,毛坯规格及数量要求分别为0.8m10根，0.6m4根，1.5m65根，0.7m6根，0.45m7根，0.2m76根。
比如原材料规格200,毛坯规格及数量要求分别为080×10根，060×4根，150×65根，070×6根，045×7根，020×76根。
                                    (1)            (2)            (3)
080×10=0800——05，+040×05，+040×00，+040×00
060×04=0240——04，+140×04，+140×01，+140×01
150×65=9750——65，+050×65，+050×58，+050×25
070×06=0420——00，- 070×06，- 070×00，- 070×00
045×07=0315——00，- 045×07，- 045×00，- 045×00
020×76=1520——00，- 020×76，- 020×66，- 020×00
合计13045=800+240+9750+420+315+1520
1，至少得66根(13045÷200)；
2，至少得70根(65+10÷2)；
3，至少得73根(65+(10+6)÷2)；
4，74根是可行的(65+5+4)。
具体方法
下料74根=(80×2)×5根+(60×1)×4根+150×65根,
(1):第一次剩余与不足;
(2):第二次剩余与不足;
(3):最后剩余140×1(根)+50×25(根)

markfang2050 发表于 2019-10-30 23:03:15

clc
clear all
close all
%% 读取钢筋数据
data=load('钢筋明细表.txt');%读取数据
r=unique(data(:,1));%获得有哪几种钢筋直径
L=9000;%原始钢管长度
%% 计算每种钢筋尺寸的原材料的切割方式
global L_data d_data
for i1=3:3%length(r)%每种直径的材料依次循环
    fprintf('XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n')
    fprintf(strcat('直径为',num2str(r(i1)),'的切割方式为:\n'))
%% 获取最终的尺寸和数量
I1=find(data(:,1)==r(i1));
L_data=unique(data(I1,2));%获得有哪几种钢筋长度
d_data=zeros(length(L_data),1);%计算不同钢筋长度的数量
m=length(L_data);%钢筋的种类
for i2=1:length(I1)
    for i3=1:length(L_data)
       if data(I1(i2),2)==L_data(i3)
         d_data(i3)=d_data(i3)+1;
       end
    end
end
k=0;
for i2=1:length(L_data)
    k=k+ceil(d_data(i2)/floor(L/L_data(i2)));%计算一个初始的范围
end
%% 用GA求解
%未知数为aij和k1,aij前k1行有数据，后面k-k1行为0
LB=zeros(k*m+1,1);%下限
b=d_data;
A=zeros(m,k*m);
for i3=1:m%不同的钢筋种类
    for i4=1:k
      A(i3,i3+(i4-1)*k)=1;
    end
end

%% 显示结果
end

查看完整版本: 一维下料算法