数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 求如何切割浪费最少
123下一页
返回列表 发新帖
楼主: czboyu

[求助] 求如何切割浪费最少

[复制链接]
czboyu
 楼主| 发表于 2023-5-28 12:23:46 | 显示全部楼层
王守恩 发表于 2023-5-27 18:52
120根，其中
30根=180-78-73
70根=180-78-53-43

能告诉我你算法吗？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
发表于 2023-5-28 12:34:00 | 显示全部楼层
王守恩 发表于 2023-5-27 18:52
120根，其中
30根=180-78-73
70根=180-78-53-43

119根，其中
25根=180-78-78
50根=180-78-53-43
32根=180-73-63-43
06根=180-73-53-53
06根=180-53-53-53
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

czboyu
 楼主| 发表于 2023-5-28 17:57:17 | 显示全部楼层
nyy 发表于 2023-5-27 19:02
果然是钢管切割问题！
先穷举出所有模式。
然后再用lingo！

大大，能给个最优的计算方法吗？，我要写个程序。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

czboyu
 楼主| 发表于 2023-5-28 20:56:35 | 显示全部楼层
王守恩 发表于 2023-5-28 12:34
119根，其中
25根=180-78-78
50根=180-78-53-43

你这个是用算法算的，还是凑数的

点评

王守恩
我会凑数，不会写程序。  发表于 2023-5-29 04:59
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2023-5-29 09:07:15 | 显示全部楼层
王守恩 发表于 2023-5-28 12:34
119根，其中
25根=180-78-78
50根=180-78-53-43

又在胡凑答案！
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2023-5-29 10:03:05 | 显示全部楼层
  1. (*穷举法求解出所有的可能的切割模式*)
  2. Clear["Global`*"];(*清除所有变量*)
  3. list={}
  4. Do[
  5.     cd=i1*3900+i2*3650+i3*3150+i4*2650+i5*2150;
  6.     sy=9000-cd;(*每种模式下钢管的剩余长度*)
  7.     If[sy>=0&&sy<2150,list=Append[list,{i1,i2,i3,i4,i5}]]
  8.     ,{i1,0,9000/3900,1}
  9.     ,{i2,0,9000/3650,1}
  10.     ,{i3,0,9000/3150,1}
  11.     ,{i4,0,9000/2650,1}
  12.     ,{i5,0,9000/2150,1}
  13. ]
  14. Grid[list]
  15. Dimensions[list]
复制代码


先穷举出所有的可能的切割模式：
结果如下：
  1. 0        0        0        0        4
  2. 0        0        0        1        2
  3. 0        0        0        2        1
  4. 0        0        0        3        0
  5. 0        0        1        0        2
  6. 0        0        1        1        1
  7. 0        0        1        2        0
  8. 0        0        2        0        1
  9. 0        0        2        1        0
  10. 0        1        0        0        2
  11. 0        1        0        1        1
  12. 0        1        0        2        0
  13. 0        1        1        0        1
  14. 0        2        0        0        0
  15. 1        0        0        0        2
  16. 1        0        0        1        1
  17. 1        0        1        0        0
  18. 1        1        0        0        0
  19. 2        0        0        0        0

复制代码

点评

nyy
切割模式有19种  发表于 2023-5-29 10:03
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2023-5-29 10:06:13 | 显示全部楼层
nyy 发表于 2023-5-29 10:03
先穷举出所有的可能的切割模式：
结果如下：
  1. model:
  2. title 钢管下料问题;

  4. SETS:
  5. !xuanqu(i)表示是否(1/0)选取第i种方式;!genshu(i)表示选取第i种方式时选取的根数;
  6. !总共有19种方式,每种方式的根数,和选取的方式;
  7. fangshi/1..19/:genshu,xuanqu;
  8. !钢管长度,是否需求;
  9. ggcd/1..5/:changdu,xuqiu;
  10. !c(i,j)表示按照第i种方式切割时能获得的第j种钢管的数量;
  11. xishu(fangshi,ggcd):c;
  12. ENDSETS

  14. DATA:
  15. !钢管的长度,这个似乎没有什么用;
  16. changdu=3900,3650,3150,2650,2150;
  17. !每种钢管至少需要的数量;
  18. xuqiu=100,38,32,80,80;
  19. c=
  20. 0 0 0 0 4
  21. 0 0 0 1 2
  22. 0 0 0 2 1
  23. 0 0 0 3 0
  24. 0 0 1 0 2
  25. 0 0 1 1 1
  26. 0 0 1 2 0
  27. 0 0 2 0 1
  28. 0 0 2 1 0
  29. 0 1 0 0 2
  30. 0 1 0 1 1
  31. 0 1 0 2 0
  32. 0 1 1 0 1
  33. 0 2 0 0 0
  34. 1 0 0 0 2
  35. 1 0 0 1 1
  36. 1 0 1 0 0
  37. 1 1 0 0 0
  38. 2 0 0 0 0
  39. ;
  40. ENDDATA

  42. !是否选取某种方式是0/1变量;
  43. @for(fangshi(i):@bin(xuanqu(i)));
  44. !当xuanqu(i)=0时,自然不选取对应的钢管,而对应的genshu(i)也就等于0;
  45. !当xuanqu(i)=1时,对应的genshu(i)当然不可能大于1000000*xuanqu(i);
  46. !xuanqu(i)这个变量是为了把问题线性化的;
  47. @for(fangshi(i):genshu(i)<=1000000*xuanqu(i));
  48. !每种钢管都要大于等于需求量;
  49. @for(ggcd(j):@sum(fangshi(i):c(i,j)*genshu(i))>=xuqiu(j));
  50. !每种方式的根数都要求是整数;
  51. @for(fangshi(i):@gin(genshu(i)));
  52. !选取的方式<=19;
  53. @sum(fangshi(i):xuanqu(i))<=19;

  55. !求根数和的最小值;
  56. min=@sum(fangshi(i):genshu(i));
  57. end
复制代码


求解结果：
  1.   Global optimal solution found.
  2.   Objective value:                       118.00000000000
  3.   Objective bound:                       118.00000000000
  4.   Infeasibilities:                       0.0000000000000
  5.   Extended solver steps:                               0
  6.   Total solver iterations:                            10
  7.   Elapsed runtime seconds:                          0.04

  9.   Model Class:                                      PILP

  11.   Total variables:                     38
  12.   Nonlinear variables:                  0
  13.   Integer variables:                   38

  15.   Total constraints:                   26
  16.   Nonlinear constraints:                0

  18.   Total nonzeros:                     114
  19.   Nonlinear nonzeros:                   0



  23.   Model Title: 钢管下料问题

  25.                   Variable                  Value               Reduced Cost
  26.                 GENSHU( 1)        0.0000000000000            1.0000000000000
  27.                 GENSHU( 2)        0.0000000000000            1.0000000000000
  28.                 GENSHU( 3)        0.0000000000000            1.0000000000000
  29.                 GENSHU( 4)        0.0000000000000            1.0000000000000
  30.                 GENSHU( 5)        0.0000000000000            1.0000000000000
  31.                 GENSHU( 6)        0.0000000000000            1.0000000000000
  32.                 GENSHU( 7)        0.0000000000000            1.0000000000000
  33.                 GENSHU( 8)        0.0000000000000            1.0000000000000
  34.                 GENSHU( 9)        3.0000000000000            1.0000000000000
  35.                GENSHU( 10)        0.0000000000000            1.0000000000000
  36.                GENSHU( 11)        0.0000000000000            1.0000000000000
  37.                GENSHU( 12)        12.000000000000            1.0000000000000
  38.                GENSHU( 13)        26.000000000000            1.0000000000000
  39.                GENSHU( 14)        0.0000000000000            1.0000000000000
  40.                GENSHU( 15)        0.0000000000000            1.0000000000000
  41.                GENSHU( 16)        54.000000000000            1.0000000000000
  42.                GENSHU( 17)        0.0000000000000            1.0000000000000
  43.                GENSHU( 18)        0.0000000000000            1.0000000000000
  44.                GENSHU( 19)        23.000000000000            1.0000000000000
  45.                 XUANQU( 1)        1.0000000000000            0.0000000000000
  46.                 XUANQU( 2)        1.0000000000000            0.0000000000000
  47.                 XUANQU( 3)        1.0000000000000            0.0000000000000
  48.                 XUANQU( 4)        1.0000000000000            0.0000000000000
  49.                 XUANQU( 5)        1.0000000000000            0.0000000000000
  50.                 XUANQU( 6)        1.0000000000000            0.0000000000000
  51.                 XUANQU( 7)        1.0000000000000            0.0000000000000
  52.                 XUANQU( 8)        1.0000000000000            0.0000000000000
  53.                 XUANQU( 9)        1.0000000000000            0.0000000000000
  54.                XUANQU( 10)        1.0000000000000            0.0000000000000
  55.                XUANQU( 11)        1.0000000000000            0.0000000000000
  56.                XUANQU( 12)        1.0000000000000            0.0000000000000
  57.                XUANQU( 13)        1.0000000000000            0.0000000000000
  58.                XUANQU( 14)        1.0000000000000            0.0000000000000
  59.                XUANQU( 15)        1.0000000000000            0.0000000000000
  60.                XUANQU( 16)        1.0000000000000            0.0000000000000
  61.                XUANQU( 17)        1.0000000000000            0.0000000000000
  62.                XUANQU( 18)        1.0000000000000            0.0000000000000
  63.                XUANQU( 19)        1.0000000000000            0.0000000000000
  64.                CHANGDU( 1)        3900.0000000000            0.0000000000000
  65.                CHANGDU( 2)        3650.0000000000            0.0000000000000
  66.                CHANGDU( 3)        3150.0000000000            0.0000000000000
  67.                CHANGDU( 4)        2650.0000000000            0.0000000000000
  68.                CHANGDU( 5)        2150.0000000000            0.0000000000000
  69.                  XUQIU( 1)        100.00000000000            0.0000000000000
  70.                  XUQIU( 2)        38.000000000000            0.0000000000000
  71.                  XUQIU( 3)        32.000000000000            0.0000000000000
  72.                  XUQIU( 4)        80.000000000000            0.0000000000000
  73.                  XUQIU( 5)        80.000000000000            0.0000000000000
  74.                   C( 1, 1)        0.0000000000000            0.0000000000000
  75.                   C( 1, 2)        0.0000000000000            0.0000000000000
  76.                   C( 1, 3)        0.0000000000000            0.0000000000000
  77.                   C( 1, 4)        0.0000000000000            0.0000000000000
  78.                   C( 1, 5)        4.0000000000000            0.0000000000000
  79.                   C( 2, 1)        0.0000000000000            0.0000000000000
  80.                   C( 2, 2)        0.0000000000000            0.0000000000000
  81.                   C( 2, 3)        0.0000000000000            0.0000000000000
  82.                   C( 2, 4)        1.0000000000000            0.0000000000000
  83.                   C( 2, 5)        2.0000000000000            0.0000000000000
  84.                   C( 3, 1)        0.0000000000000            0.0000000000000
  85.                   C( 3, 2)        0.0000000000000            0.0000000000000
  86.                   C( 3, 3)        0.0000000000000            0.0000000000000
  87.                   C( 3, 4)        2.0000000000000            0.0000000000000
  88.                   C( 3, 5)        1.0000000000000            0.0000000000000
  89.                   C( 4, 1)        0.0000000000000            0.0000000000000
  90.                   C( 4, 2)        0.0000000000000            0.0000000000000
  91.                   C( 4, 3)        0.0000000000000            0.0000000000000
  92.                   C( 4, 4)        3.0000000000000            0.0000000000000
  93.                   C( 4, 5)        0.0000000000000            0.0000000000000
  94.                   C( 5, 1)        0.0000000000000            0.0000000000000
  95.                   C( 5, 2)        0.0000000000000            0.0000000000000
  96.                   C( 5, 3)        1.0000000000000            0.0000000000000
  97.                   C( 5, 4)        0.0000000000000            0.0000000000000
  98.                   C( 5, 5)        2.0000000000000            0.0000000000000
  99.                   C( 6, 1)        0.0000000000000            0.0000000000000
  100.                   C( 6, 2)        0.0000000000000            0.0000000000000
  101.                   C( 6, 3)        1.0000000000000            0.0000000000000
  102.                   C( 6, 4)        1.0000000000000            0.0000000000000
  103.                   C( 6, 5)        1.0000000000000            0.0000000000000
  104.                   C( 7, 1)        0.0000000000000            0.0000000000000
  105.                   C( 7, 2)        0.0000000000000            0.0000000000000
  106.                   C( 7, 3)        1.0000000000000            0.0000000000000
  107.                   C( 7, 4)        2.0000000000000            0.0000000000000
  108.                   C( 7, 5)        0.0000000000000            0.0000000000000
  109.                   C( 8, 1)        0.0000000000000            0.0000000000000
  110.                   C( 8, 2)        0.0000000000000            0.0000000000000
  111.                   C( 8, 3)        2.0000000000000            0.0000000000000
  112.                   C( 8, 4)        0.0000000000000            0.0000000000000
  113.                   C( 8, 5)        1.0000000000000            0.0000000000000
  114.                   C( 9, 1)        0.0000000000000            0.0000000000000
  115.                   C( 9, 2)        0.0000000000000            0.0000000000000
  116.                   C( 9, 3)        2.0000000000000            0.0000000000000
  117.                   C( 9, 4)        1.0000000000000            0.0000000000000
  118.                   C( 9, 5)        0.0000000000000            0.0000000000000
  119.                  C( 10, 1)        0.0000000000000            0.0000000000000
  120.                  C( 10, 2)        1.0000000000000            0.0000000000000
  121.                  C( 10, 3)        0.0000000000000            0.0000000000000
  122.                  C( 10, 4)        0.0000000000000            0.0000000000000
  123.                  C( 10, 5)        2.0000000000000            0.0000000000000
  124.                  C( 11, 1)        0.0000000000000            0.0000000000000
  125.                  C( 11, 2)        1.0000000000000            0.0000000000000
  126.                  C( 11, 3)        0.0000000000000            0.0000000000000
  127.                  C( 11, 4)        1.0000000000000            0.0000000000000
  128.                  C( 11, 5)        1.0000000000000            0.0000000000000
  129.                  C( 12, 1)        0.0000000000000            0.0000000000000
  130.                  C( 12, 2)        1.0000000000000            0.0000000000000
  131.                  C( 12, 3)        0.0000000000000            0.0000000000000
  132.                  C( 12, 4)        2.0000000000000            0.0000000000000
  133.                  C( 12, 5)        0.0000000000000            0.0000000000000
  134.                  C( 13, 1)        0.0000000000000            0.0000000000000
  135.                  C( 13, 2)        1.0000000000000            0.0000000000000
  136.                  C( 13, 3)        1.0000000000000            0.0000000000000
  137.                  C( 13, 4)        0.0000000000000            0.0000000000000
  138.                  C( 13, 5)        1.0000000000000            0.0000000000000
  139.                  C( 14, 1)        0.0000000000000            0.0000000000000
  140.                  C( 14, 2)        2.0000000000000            0.0000000000000
  141.                  C( 14, 3)        0.0000000000000            0.0000000000000
  142.                  C( 14, 4)        0.0000000000000            0.0000000000000
  143.                  C( 14, 5)        0.0000000000000            0.0000000000000
  144.                  C( 15, 1)        1.0000000000000            0.0000000000000
  145.                  C( 15, 2)        0.0000000000000            0.0000000000000
  146.                  C( 15, 3)        0.0000000000000            0.0000000000000
  147.                  C( 15, 4)        0.0000000000000            0.0000000000000
  148.                  C( 15, 5)        2.0000000000000            0.0000000000000
  149.                  C( 16, 1)        1.0000000000000            0.0000000000000
  150.                  C( 16, 2)        0.0000000000000            0.0000000000000
  151.                  C( 16, 3)        0.0000000000000            0.0000000000000
  152.                  C( 16, 4)        1.0000000000000            0.0000000000000
  153.                  C( 16, 5)        1.0000000000000            0.0000000000000
  154.                  C( 17, 1)        1.0000000000000            0.0000000000000
  155.                  C( 17, 2)        0.0000000000000            0.0000000000000
  156.                  C( 17, 3)        1.0000000000000            0.0000000000000
  157.                  C( 17, 4)        0.0000000000000            0.0000000000000
  158.                  C( 17, 5)        0.0000000000000            0.0000000000000
  159.                  C( 18, 1)        1.0000000000000            0.0000000000000
  160.                  C( 18, 2)        1.0000000000000            0.0000000000000
  161.                  C( 18, 3)        0.0000000000000            0.0000000000000
  162.                  C( 18, 4)        0.0000000000000            0.0000000000000
  163.                  C( 18, 5)        0.0000000000000            0.0000000000000
  164.                  C( 19, 1)        2.0000000000000            0.0000000000000
  165.                  C( 19, 2)        0.0000000000000            0.0000000000000
  166.                  C( 19, 3)        0.0000000000000            0.0000000000000
  167.                  C( 19, 4)        0.0000000000000            0.0000000000000
  168.                  C( 19, 5)        0.0000000000000            0.0000000000000

  170.                        Row           Slack or Surplus             Dual Price
  171.                          1        1000000.0000000            0.0000000000000
  172.                          2        1000000.0000000            0.0000000000000
  173.                          3        1000000.0000000            0.0000000000000
  174.                          4        1000000.0000000            0.0000000000000
  175.                          5        1000000.0000000            0.0000000000000
  176.                          6        1000000.0000000            0.0000000000000
  177.                          7        1000000.0000000            0.0000000000000
  178.                          8        1000000.0000000            0.0000000000000
  179.                          9        999997.00000000            0.0000000000000
  180.                         10        1000000.0000000            0.0000000000000
  181.                         11        1000000.0000000            0.0000000000000
  182.                         12        999988.00000000            0.0000000000000
  183.                         13        999974.00000000            0.0000000000000
  184.                         14        1000000.0000000            0.0000000000000
  185.                         15        1000000.0000000            0.0000000000000
  186.                         16        999946.00000000            0.0000000000000
  187.                         17        1000000.0000000            0.0000000000000
  188.                         18        1000000.0000000            0.0000000000000
  189.                         19        999977.00000000            0.0000000000000
  190.                         20        0.0000000000000            0.0000000000000
  191.                         21        0.0000000000000            0.0000000000000
  192.                         22        0.0000000000000            0.0000000000000
  193.                         23        1.0000000000000            0.0000000000000
  194.                         24        0.0000000000000            0.0000000000000
  195.                         25        0.0000000000000            0.0000000000000
  196.                         26        118.00000000000           -1.0000000000000

复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2023-5-29 10:21:41 | 显示全部楼层
nyy 发表于 2023-5-29 10:06
求解结果：

结果用图表来解释一下，你需要的只是图中带绿色的部分。
方式        3900        3650        3150        2650        2150        总长        剩余        根数        根数       


9        0        0        2        1        0        8950        50        GENSHU( 9)        3        1

绿色的第九行的结果表示
第九种切割模式，每根9000的钢管，切割成2根3150、1根2650，这种切割模式的钢管3根，

剩下以此类推。

总共需要118根九米的钢管
QQ截图20230529101727.jpg
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2023-5-29 10:29:16 | 显示全部楼层
aimisiyou 发表于 2023-5-28 07:31
119根。

我算出来是118根，你算出来是119根，我把切割方案拿出来了。
确实满足要求且还比你算出来的小，所以你的肯定错误了！
QQ截图20230529102642.jpg
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

czboyu
 楼主| 发表于 2023-5-29 10:38:17 | 显示全部楼层
nyy 发表于 2023-5-29 10:29
我算出来是118根，你算出来是119根，我把切割方案拿出来了。
确实满足要求且还比你算出来的小，所以你的 ...

方便加个V吗我的180686
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-20 06:35 , Processed in 0.060205 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表