一维下料

ynhh · 发表于 2019-7-15 14:40:53

你这没个直观的结果
不好查看啊

aimisiyou · 发表于 2019-7-16 01:06:46

_$ (defun c:tt()
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
  (fix (* n (rnd)))
)
(defun pick (lst i j)
(setq count (length lst) nc 0 picklst nil)
(while (<= nc j)
   (if (<= i nc)
         (setq picklst (cons (nth nc lst) picklst))
   )
   (setq nc (+ nc 1))
)
(reverse picklst)
)
(defun xipai (n)
  (setq i 1 j 0 klst nil)
  (while (<= i n)
   (setq klst (cons i klst))
   (setq i (+ 1 i))
)
(while (<= j 20)
      (setq i_pot (rnd_n n))
      (setq j_pot (rnd_n n))
      (setq nmin (min i_pot j_pot))
      (setq nmax (max i_pot j_pot))
      (setq klst (append (pick klst  (+ 1 nmax) (- n 1)) (pick klst (+ 1 nmin) nmax) (pick klst 0 nmin)))
      (setq j (+ j 1))
)
klst
)
(setq pts '(65 65 65 54 54 54 54 54 43 43 43 43 22 22 11 11 11 11 11 11))
(mapcar '(lambda (x) (nth (- x 1) pts)) (xipai (length pts)))
)
命令:
命令: tt
(43 11 54 22 22 65 54 65 11 43 65 54 11 54 43 43 11 54 11 11)

命令:
命令: tt
(43 65 11 43 65 11 54 54 22 54 11 65 22 54 54 43 11 11 11 43)

命令:
命令: tt
(65 65 11 54 43 43 11 43 11 65 54 11 22 11 22 54 11 54 54 43)

命令:
命令: tt
(43 11 22 11 54 54 54 22 65 65 65 11 43 54 54 11 11 11 43 43)

命令:
命令: 'VLIDE
命令:
命令: tt
(43 54 65 54 43 54 11 65 11 43 11 22 43 22 65 11 54 54 11 11)

aimisiyou · 发表于 2019-7-16 01:49:33

本帖最后由 aimisiyou 于 2019-7-16 02:06 编辑

即假设原材料L长200，毛坯规格及数量要求见表lst='(65 65 65 54 54 54 54 54 43 43 43 43 22 22 11 11 11 11 11 11).首先我们将lst随机重新排列，如(43 11 54 22 22 65 54 65 11 43 65 54 11 54 43 43 11 54 11 11)，接着从第一位开始，按连续的数总和不超出L进行划分，即((43 11 54 22 22) (65 54 65 11) (43 65 54 11) (54 43 43 11) (54 11 11))，对每项从大到小排序,即((54 43 22 22 11) (65 65 54 11) (65 54 43 11) (54 43 43 11) (54 11 11))，再按每项和值从大到小排序，即((65 65 54 11) (65 54 43 11)(54 43 22 22 11)  (54 43 43 11) (54 11 11))，每项距离L的差值为（5,17,48,49,124）当差值大于最小毛坯规格时，从最后倒数将第一个最接近差值的毛坯迁移，同时更新表（迁移项至最后项合并，并重新划分）。即((65 65 54 11) (65 54 43 11)(54 43 22 22 11)  (54 43 43 11) (54 11 11))
=((65 65 54 11) (65 54 43 11 11)(54 43 22 22 11)  (54 43 43 11) (54 11))
=((65 65 54 11) (65 54 43 11 11)(54 43 43 22 22 11)  (54 43  11  54 11))
=((65 65 54 11) (54 43 43 22 22 11) (65 54 43 11 11) (54 54 43  11 11))
=((65 65 54 11) (54 43 43 22 22 11) (65 54 43 11 11 11) (54 54 43  11 ))
至此，对一个个体操作结束（每个项差值小于毛坯最小规格长度）。

aimisiyou · 发表于 2019-7-16 02:34:59

本帖最后由 aimisiyou 于 2019-7-16 02:43 编辑

直接对lst='(65 65 65 54 54 54 54 54 43 43 43 43 22 22 11 11 11 11 11 11)操作
(65 65 65 54 54 54 54 54 43 43 43 43 22 22 11 11 11 11 11 11)
=((65 65 65) (54 54 54) (54 54 43 43) (43 43 22 22 11 11 11 11 11 11))
=((43 43 22 22 11 11 11 11 11 11)(65 65 65) (54 54 43 43) (54 54 54))
可以看出错排的结果可能会比递降排列的结果好，因为最小规格的毛坯都排在第一项内，后续项的差值略大于最小毛坯长度时就会无法改进。另外，错排的结果每项个数较接近，那么为同一下料方式的几率较高，所以总体的下料方式数相对就少，对现实下料工艺是有益的。

aimisiyou · 发表于 2019-7-16 07:56:09

本帖最后由 aimisiyou 于 2019-7-16 08:06 编辑

为了防止最小规格的毛坯全部出现在第一项，可以设定c=0.05，每次生成一个随机变量p,当p<c时，将第一项移至末尾。显然按大到小排列时，若和值相同，按每项中最小值谁最小谁排在前面（若最小值也相同，就按第二最小值谁最小谁排在前面）。

aimisiyou · 发表于 2019-7-16 12:47:01

((5.12 968) (4.73 88) (3.92 440) (3.62 880) (3.52 176) (3.32 528) (3.12  484)(3.02 770)(2.92 264) (2.64 44)(2.52 22) (2.38 88) (1.72 176) (1.585 88))
=((5.12 968) (3.62 880)(3.02 770)(3.32 528)(3.12 484)(3.92 440)(2.92 264)(3.52 176)(1.72 176) (4.73 88) (2.38 88) (1.585 88) (2.64 44)(2.52 22))
=(((5.12 3.62 3.02) 770 0.24)(3.32 528)(3.12 484)(3.92 440)(2.92 264)(5.12 198)(3.52 176)(1.72 176)(3.62 110) (4.73 88) (2.38 88) (1.585 88) (2.64 44)(2.52 22) )
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)(2.92 264)(5.12 198)(3.52 176)(1.72 176)(3.62 110) (4.73 88)(3.32 88) (2.38 88) (1.585 88) (3.12 44)(2.64 44)(2.52 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)(3.52 176)(1.72 176)(3.62 110)(4.73 88)(3.32 88)(2.92 88)(2.38 88)(1.585 88)(3.12 44)(2.64 44)(5.12  22)(2.52 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)((3.52 1.72 3.62) 110 3.14)(4.73 88)(3.32 88)(2.92 88)(2.38 88)(1.585 88)(3.52 66)(1.72 66)(3.12 44)(2.64 44)(5.12  22)(2.52 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)((3.52 1.72 3.62) 110 3.14)((4.73 3.32 2.92) 88 1.03)(2.38 88)(1.585 88)(3.52 66)(1.72 66)(3.12 44)(2.64 44)(5.12  22)(2.52 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)((3.52 1.72 3.62) 110 3.14)((4.73 3.32 2.92) 88 1.03)((2.38 1.585 3.52 1.72) 66 2.795)(1.72 66)(3.12 44)(2.64 44)(5.12  22)(2.52 22)(2.38 22)(1.585 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)((3.52 1.72 3.62) 110 3.14)((4.73 3.32 2.92) 88 1.03)((2.38 1.585 3.52 1.72) 66 2.795)((1.72 3.12 2.64) 44 4.52)(1.72 22)(5.12  22)(2.52 22)(2.38 22)(1.585 22))
=(((5.12 3.62 3.02) 770 0.24)((3.32 3.12 3.92) 440 1.64)((2.92 5.12 3.52) 176 0.44)((3.52 1.72 3.62) 110 3.14)((4.73 3.32 2.92) 88 1.03)((2.38 1.585 3.52 1.72) 66 2.795)((1.72 3.12 2.64) 44 4.52)((1.72 5.12 2.52 2.38) 22 0.26)((1.585 1.585 1.585 1.585 1.585 1.585 1.585) 3 0.905)((1.585) 1 10.415))
=(((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((1.585 1.585 1.585 1.585 1.585 1.585 1.585) 3 0.905)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 440 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52)((1.585) 1 10.415))
=(((3.32 3.12 3.92 1.585) 1 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((1.585 1.585 1.585 1.585 1.585 1.585 1.585) 3 0.905)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 439 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52))
=(((3.32 3.12 3.92 1.585) 4 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((1.585 1.585 1.585 1.585 1.585 1.585) 3 2.49)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 436 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52))
=(((3.32 3.12 3.92 1.585) 4 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 436 1.64)((1.585 1.585 1.585 1.585 1.585 1.585) 3 2.49)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52))
=(((3.32 3.12 3.92 1.585) 7 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 433 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.585 1.585 1.585 1.585 1.585) 3 4.075)((1.72 3.12 2.64) 44 4.52))
=(((3.32 3.12 3.92 1.585) 10 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92) 430 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52)((1.585 1.585 1.585 1.585 ) 3 5.66))
=(((3.32 3.12 3.92 1.585) 22 0.055)((5.12 3.62 3.02) 770 0.24)((1.72 5.12 2.52 2.38) 22 0.26)((2.92 5.12 3.52) 176 0.44)((4.73 3.32 2.92) 88 1.03)((3.32 3.12 3.92)418 1.64)((2.38 1.585 3.52 1.72) 66 2.795)((3.52 1.72 3.62) 110 3.14)((1.72 3.12 2.64) 44 4.52))

aimisiyou · 发表于 2019-7-16 13:05:37

本帖最后由 aimisiyou 于 2019-7-16 13:12 编辑

算法如下：
1、按数量的大小将毛坯规格排序
2、按连续规格的之和不超过L合并，数值为相邻规格毛坯的最小值，多余的保留继续转1，最终得到（（（规格大规格中规格小）数量差值）……（（规格大规格中规格小）数量）差值）)形式的表lst.
3、将lst按差值从小到大排列；
4、考虑差值大于最小毛坯的情况，从lst逆向找到最接近差值的数所在的项，迁移出该毛坯（即满足迁移项的位置前移，否则转至下一个较大差值项），获得新的组合，转3。
5、所有项的差值均小于最小毛坯值，程序结束。

ynhh · 发表于 2019-7-16 14:07:44

aimisiyou 发表于 2019-7-16 13:05
算法如下：
1、按数量的大小将毛坯规格排序
2、按连续规格的之和不超过L合并，数值为相邻规格毛坯的最小 ...

你这精神太牛了
不放弃
支持你

aimisiyou · 发表于 2019-7-16 15:02:21

对于这种情况似乎还可以处理
((3.52 2.38  1.72 1.585) 16 2.795)
=((3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 1.72 1.585 ) 8  5.175 )
=((3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 3.52 1.72 1.585) 4 1.655)((1.72 1.585) 4 8.695)）
=((3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 3.52 1.72 1.585) 4 1.655)((1.72 1.72 1.585 1.585) 2 5.39)）
=((3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 3.52 1.72 1.585) 4 1.655)((1.72 1.72 1.72 1.585 1.585) 1 3.67)((1.72 1.585 1.585) 1 7.11)）
=(((3.52 3.52 1.72 1.585 1.585) 2 0.07)(3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 3.52 1.72 1.585) 2 1.655)((1.72 1.72 1.72 1.585 1.585) 1 3.67)((1.72) 1 10.28)）
=(((3.52 3.52 1.72 1.585 1.585) 3 0.07)(3.52 2.38  2.38 1.72 1.585) 8 0.415)((3.52 3.52 1.72 1.585) 1 1.655)((1.72 1.72 1.72 1.585 1.72) 1 3.535)）
=(((3.52 3.52 1.72 1.585 1.585) 4 0.07)(3.52 2.38  2.38 1.72 1.585) 8 0.415)((1.72 1.72 1.72  1.72) 1 10.28))
理论数值（3.52+2.38+1.72+1.585）*16/12=12.2733
而现在的根数为4+8+1=13，所以是最优的。

aimisiyou · 发表于 2019-7-16 16:01:26

本帖最后由 aimisiyou 于 2019-7-20 12:30 编辑

((3.62  3.52 1.72) 110 3.14))
=((3.62  3.52 1.72 1.72) 55 1.72) (3.62  3.52) 55 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 27 0) ((3.62 3.52 1.72 1.72) 1 1.72) ((3.62  3.52 1.72) 27 3.14)(3.62  3.52) 55 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 28 0) ((3.62  3.52 1.72) 26 3.14)(3.62  3.52) 56 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 28 0) ((3.62  3.52 1.72 1.72) 13 1.72)  ((3.62  3.52) 13 4.86)  (3.62  3.52) 56 4.86) )=((3.62  3.52 1.72 1.72 1.72) 28 0) ((3.62  3.52 1.72 1.72) 13 1.72)  ((3.62  3.52) 69 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 28 0) ((3.62  3.52 1.72 1.72 1.72) 6 0) ((3.62  3.52 1.72 1.72) 1 1.72) ((3.62  3.52 1.72 ) 6 3.14) ((3.62  3.52) 69 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 34 0) ((3.62  3.52 1.72 1.72) 1 1.72) ((3.62  3.52 1.72 ) 6 3.14) ((3.62  3.52) 69 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 34 0) ((3.62  3.52 1.72 1.72 1.72) 1 0) ((3.62  3.52 1.72 ) 5 3.14) ((3.62  3.52) 69 4.86)  ((3.62  3.52) 1 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 35 0) ((3.62  3.52 1.72 ) 5 3.14) ((3.62  3.52) 70 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 35 0) ((3.62  3.52 1.72 1.72 ) 2 1.72) ((3.62  3.52 1.72 ) 1 3.14) ((3.62  3.52) 2 4.86) ((3.62  3.52) 70 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 35 0) ((3.62  3.52 1.72 1.72 ) 2 1.72) ((3.62  3.52 1.72 ) 1 3.14)  ((3.62  3.52) 72 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 36 0) ((3.62  3.52 1.72 1.72 ) 1 1.72) ((3.62  3.52) 1 4.86)  ((3.62  3.52) 72 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 36 0) ((3.62  3.52 1.72 1.72 ) 1 1.72) ((3.62  3.52) 73 4.86) )
=((3.62  3.52 1.72 1.72 1.72) 36 0) ((3.62  3.52 1.72 1.72 ) 1 1.72) ((3.62  3.52 3.62) 24  1.24)((3.52 3.62 3.52)  24 1.34) ((3.62 3.52) 1 4.86))
=((3.62  3.52 1.72 1.72 1.72) 36 0)((3.62  3.52 3.62) 24 1.24) ((3.52 3.62 3.52)  24 1.34)((3.62  3.52 1.72 1.72 ) 1 1.72)  ((3.62 3.52) 1 4.86))
=((3.62  3.52 1.72 1.72 1.72) 36 0)((3.62  3.52 3.62) 25  1.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

跟EXCEL远算结果根数92对比，还是优越很多。

ynhh · 发表于 2019-7-16 18:51:30

aimisiyou 发表于 2019-7-16 16:01
((3.62  3.52 1.72) 110 3.14))
=((3.62  3.52 1.72 1.72) 55 1.72) (3.62  3.52) 55 4.86) )
=((3.62  3 ...

这电子表可设置多种不同长度，不同根数的原材料
你这能做到吗？

aimisiyou · 发表于 2019-7-16 19:49:06

本帖最后由 aimisiyou 于 2019-7-16 20:14 编辑

(((2.64 2.64 1.72 1.72) 8 1.56)((3.32 3.32 3.12) 33 2.44))
=(((3.32 3.32 3.12) 17 2.44)((3.32 3.32 3.12) 16 2.44)((2.64 2.64 1.72 1.72) 8 1.56))
=(((3.32 3.32 3.12) 17 2.44)((3.32 3.32 3.12 1.72) 16 0.72)((2.64 2.64) 8 6.72))
=(((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 17 2.44)((2.64 2.64) 8 6.72))
=(((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)((2.64 2.64) 8 6.72)((3.32 3.32 3.12) 8 2.44))
=(((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)((3.32 3.32 2.64 2.64) 8 0.08)(( 3.12 3.12 3.12) 2 2.64)((3.12 3.12) 1 5.76))
=(((3.32 3.32 2.64 2.64) 8 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)(( 3.12 3.12 3.12) 2 2.64)((3.12 3.12) 1 5.76))
=(((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)(( 3.12 3.12 3.12) 2 2.64)((3.32 3.32 2.64 2.64) 1 0.08)((3.12 3.12) 1 5.76))
=(((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)(( 3.12 3.12 3.12 2.64) 2 0)((3.32 3.32) 1 5.36)((3.12 3.12) 1 5.76))
=(((3.12 3.12 3.12 2.64) 2 0)((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)((3.32 3.32) 1 5.36)((3.12 3.12) 1 5.76))
=(((3.12 3.12 3.12 2.64) 2 0)((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 9 2.44)((3.32 3.32 3.12) 1 2.24) ((3.12) 1 8.88))
=(((3.12 3.12 3.12 2.64) 2 0)((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 16 0.72)((3.32 3.32 3.12) 1 2.24)((3.32 3.32 3.12) 9 2.44)((3.12) 1 8.88))
=(((3.12 3.12 3.12 2.64) 2 0)((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 15 0.72)((3.32 3.32 3.12 1.72) 1 0.52)((3.32 3.32 3.12) 9 2.44)((3.12) 1 8.88)((3.32 3.32 3.12) 1 2.44))
=(((3.12 3.12 3.12 2.64) 2 0)((3.32 3.32 2.64 2.64) 7 0.08)((3.32 3.32 3.12 1.72) 1 0.52)((3.32 3.32 3.12 1.72) 15 0.72)((3.32 3.32 3.12) 10 2.44)((3.12) 1 8.88))
可见开始时总根数为8+33=41，运算处理后的总根数为2+7+1+15+10+1=36根。
关键核心是当差值大于最小毛坯长度且所有最接近该差值的数在左边的项内，而且该项差值与接近的毛坯长度差不小于迁移项内的差值时，不发生迁移，往后一项继续运算，直至最后一项。
如上，((3.32 3.32 3.12) 10 2.44) 的差值为2.44，最接近它的毛坯为1.72，且均在左边，且1.72所在项的最大差值为0.72,2.44-1.72=0.72，故不进行迁移1.72。再往后一项判断是否进行迁移运算，直至最后一项程序结束。这很好理解，如果前面一根的空余多，进行迁移后空余小，那么就互换位置，即把空余多的都往后移，更省料，所以下料的总根数非递增（要么不变，要么减少）。
感觉运算的最终结果应该是根数最少的情况。

aimisiyou · 发表于 2019-7-16 20:09:16

本帖最后由 aimisiyou 于 2019-7-16 22:26 编辑

ynhh 发表于 2019-7-16 18:51
这电子表可设置多种不同长度，不同根数的原材料
你这能做到吗？

原理搞清楚了，多种尺寸的原材料也不是问题，只是运算量大大增加了。对于一种尺寸L的原材料，只需判断连续的几个毛坯长度之和是否在L内？对于多种情况（L1<L2<L3……），对于一个随机排列的lst=(q1 ,q2,q3,q4……)，判断q1+q2更接近L1，还是q1+q2+q3更接近L2，还是……然后整合成（（q1 q2）(q3 q4 q5) ……），最后按迁移法则处理。举个简单例子来说吧，原材料两种规格9m和12m,毛坯长度规格和数量分别为2.2m10根，3.1m9根，5.2米6根。先按一种规格9m计算
即lst='((2.2 2.2 2.2 2.2) 2 0.2)((5.2 3.1) 6 0.7)((3.1 3.1 2.2) 1 0.6)((3.1 2.2) 1 2.7)
=((2.2 2.2 2.2 2.2) 2 0.2)((3.1 3.1 2.2) 1 0.6)((5.2 3.1) 6 0.7)((3.1 2.2) 1 2.7)) 此时利用率为(2.2*10+3.1*9+5.2*6)/(9*（2+1+6+1）)=90.11%

最终结果如图，即需要5根12米的，3根9m的，所得的利用率最高，(2.2*10+3.1*9+5.2*6)/(12*5+9*3)=93.21%.

aimisiyou · 发表于 2019-7-17 10:04:31

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

我根据自己的算法手工可以算出较优解，时间也就几分钟而已。
比如原材料规格2m,毛坯规格及数量要求分别为0.8m10根，0.6m4根，1.5m65根，0.7m6根，0.45m7根，0.2m76根。先按数量从多到少排列((0.2  76)(1.5  65)(0.8 10)(0.45  7)(0.7  6)(0.6  4))，然后合并列出每种下料方式剩下的余料长
即((0.2  76)(1.5  65)(0.8 10)(0.45  7)(0.7  6)(0.6  4))
=((1.5 0.2) 65  0.3)(0.2  11)(0.8 10)(0.45  7)(0.7  6)(0.6  4))
=((1.5 0.2) 65  0.3)(0.8  0.2) 10  1)(0.45  7)(0.7  6)(0.6  4)(0.2 1))
=(((1.5 0.2) 65  0.3)((0.8  0.2) 10  1)((0.7 0.45 ) 6 0.85)(0.6  4)(0.45  1)(0.2 1))
=(((1.5 0.2) 65  0.3)((0.8  0.2) 10  1)((0.7 0.45 ) 6 0.85))((0.6  0.6 0.6) 1 0.2)((0.6 0.45  0.2)1 0.75))  ;;;然后按预料从小到大排列=( ((0.6  0.6 0.6) 1 0.2) ((1.5 0.2) 65  0.3) ((0.6 0.45  0.2) 1 0.75) ((0.7 0.45 ) 6 0.85) ((0.8  0.2) 10  1));;;从第一项开始，余料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根，理论数为（0.8*10+1.5*65+0.7*6+0.45*7+0.2*76）/2.0=65.225。
对比EXCEL结果74根，发现须补充几条规则：1若迁移后对整体没一影响，但将前面较小的零件移至后面了，这种情况还是要迁移的。如（……（0.6 0.2 0.2 0.2 0.2 0.2 0.2 0.2）1 0）……(（0.8  0.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.8  0.7）2 0.5）应为（(（0.8  0.8）1 0.4）((0.7 0.7) 1 0.6)。

aimisiyou · 发表于 2019-7-17 11:37:14

本帖最后由 aimisiyou 于 2019-7-17 11:46 编辑

那么有个问题，即若迁移后对整体没影响，但会将较大毛坯和较小毛坯同时后移，此时该不该发生迁移呢？
如（……（（1.5 0.3 0.2）1 0）……（（0.6 0.6 0.5）1 0.3）……）？
若前面迁移项中每项均不大于后面迁移项中的最大值，显然迁移。
感觉视后面的情况而定，如果后面有项差值大于1.5，那么就迁移，否则不迁移。
即（……（（1.5 0.3 0.2）1 0）……（（0.6 0.6 0.5）1 0.3）……（（）K 1.6）……）时迁移。如（……（（1.5 0.3 0.2）2 0）……（（0.6 0.6 0.5）2 0.3）……（（）K 3.1）……）
即迁移项中最大毛坯总和与后续项中的差值相近（差值略大）时，允许迁移的。
人很轻易理解，但电脑判断起来还真麻烦。

账号		自动登录	找回密码
密码			立即注册

[研讨] 一维下料

点评

点评

点评