王守恩 发表于 2023-5-27 18:52
120根，其中
30根=180-78-73
70根=180-78-53-43
能告诉我你算法吗？
王守恩 发表于 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
nyy 发表于 2023-5-27 19:02
果然是钢管切割问题！
先穷举出所有模式。
然后再用lingo！
大大，能给个最优的计算方法吗？，我要写个程序。
王守恩 发表于 2023-5-28 12:34
119根，其中
25根=180-78-78
50根=180-78-53-43
你这个是用算法算的，还是凑数的
王守恩 发表于 2023-5-28 12:34
119根，其中
25根=180-78-78
50根=180-78-53-43
又在胡凑答案！
(*穷举法求解出所有的可能的切割模式*)
Clear["Global`*"];(*清除所有变量*)
list={}
Do[
cd=i1*3900+i2*3650+i3*3150+i4*2650+i5*2150;
sy=9000-cd;(*每种模式下钢管的剩余长度*)
If]
,{i1,0,9000/3900,1}
,{i2,0,9000/3650,1}
,{i3,0,9000/3150,1}
,{i4,0,9000/2650,1}
,{i5,0,9000/2150,1}
]
Grid
Dimensions
先穷举出所有的可能的切割模式：
结果如下：
0 0 0 0 4
0 0 0 1 2
0 0 0 2 1
0 0 0 3 0
0 0 1 0 2
0 0 1 1 1
0 0 1 2 0
0 0 2 0 1
0 0 2 1 0
0 1 0 0 2
0 1 0 1 1
0 1 0 2 0
0 1 1 0 1
0 2 0 0 0
1 0 0 0 2
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0
2 0 0 0 0
nyy 发表于 2023-5-29 10:03
先穷举出所有的可能的切割模式：
结果如下：
model:
title 钢管下料问题;
SETS:
!xuanqu(i)表示是否(1/0)选取第i种方式;!genshu(i)表示选取第i种方式时选取的根数;
!总共有19种方式,每种方式的根数,和选取的方式;
fangshi/1..19/:genshu,xuanqu;
!钢管长度,是否需求;
ggcd/1..5/:changdu,xuqiu;
!c(i,j)表示按照第i种方式切割时能获得的第j种钢管的数量;
xishu(fangshi,ggcd):c;
ENDSETS
DATA:
!钢管的长度,这个似乎没有什么用;
changdu=3900,3650,3150,2650,2150;
!每种钢管至少需要的数量;
xuqiu=100,38,32,80,80;
c=
0 0 0 0 4
0 0 0 1 2
0 0 0 2 1
0 0 0 3 0
0 0 1 0 2
0 0 1 1 1
0 0 1 2 0
0 0 2 0 1
0 0 2 1 0
0 1 0 0 2
0 1 0 1 1
0 1 0 2 0
0 1 1 0 1
0 2 0 0 0
1 0 0 0 2
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0
2 0 0 0 0
;
ENDDATA
!是否选取某种方式是0/1变量;
@for(fangshi(i):@bin(xuanqu(i)));
!当xuanqu(i)=0时,自然不选取对应的钢管,而对应的genshu(i)也就等于0;
!当xuanqu(i)=1时,对应的genshu(i)当然不可能大于1000000*xuanqu(i);
!xuanqu(i)这个变量是为了把问题线性化的;
@for(fangshi(i):genshu(i)<=1000000*xuanqu(i));
!每种钢管都要大于等于需求量;
@for(ggcd(j):@sum(fangshi(i):c(i,j)*genshu(i))>=xuqiu(j));
!每种方式的根数都要求是整数;
@for(fangshi(i):@gin(genshu(i)));
!选取的方式<=19;
@sum(fangshi(i):xuanqu(i))<=19;
!求根数和的最小值;
min=@sum(fangshi(i):genshu(i));
end
求解结果：
Global optimal solution found.
Objective value: 118.00000000000
Objective bound: 118.00000000000
Infeasibilities: 0.0000000000000
Extended solver steps: 0
Total solver iterations: 10
Elapsed runtime seconds: 0.04
Model Class: PILP
Total variables: 38
Nonlinear variables: 0
Integer variables: 38
Total constraints: 26
Nonlinear constraints: 0
Total nonzeros: 114
Nonlinear nonzeros: 0
Model Title: 钢管下料问题
Variable Value Reduced Cost
GENSHU( 1) 0.0000000000000 1.0000000000000
GENSHU( 2) 0.0000000000000 1.0000000000000
GENSHU( 3) 0.0000000000000 1.0000000000000
GENSHU( 4) 0.0000000000000 1.0000000000000
GENSHU( 5) 0.0000000000000 1.0000000000000
GENSHU( 6) 0.0000000000000 1.0000000000000
GENSHU( 7) 0.0000000000000 1.0000000000000
GENSHU( 8) 0.0000000000000 1.0000000000000
GENSHU( 9) 3.0000000000000 1.0000000000000
GENSHU( 10) 0.0000000000000 1.0000000000000
GENSHU( 11) 0.0000000000000 1.0000000000000
GENSHU( 12) 12.000000000000 1.0000000000000
GENSHU( 13) 26.000000000000 1.0000000000000
GENSHU( 14) 0.0000000000000 1.0000000000000
GENSHU( 15) 0.0000000000000 1.0000000000000
GENSHU( 16) 54.000000000000 1.0000000000000
GENSHU( 17) 0.0000000000000 1.0000000000000
GENSHU( 18) 0.0000000000000 1.0000000000000
GENSHU( 19) 23.000000000000 1.0000000000000
XUANQU( 1) 1.0000000000000 0.0000000000000
XUANQU( 2) 1.0000000000000 0.0000000000000
XUANQU( 3) 1.0000000000000 0.0000000000000
XUANQU( 4) 1.0000000000000 0.0000000000000
XUANQU( 5) 1.0000000000000 0.0000000000000
XUANQU( 6) 1.0000000000000 0.0000000000000
XUANQU( 7) 1.0000000000000 0.0000000000000
XUANQU( 8) 1.0000000000000 0.0000000000000
XUANQU( 9) 1.0000000000000 0.0000000000000
XUANQU( 10) 1.0000000000000 0.0000000000000
XUANQU( 11) 1.0000000000000 0.0000000000000
XUANQU( 12) 1.0000000000000 0.0000000000000
XUANQU( 13) 1.0000000000000 0.0000000000000
XUANQU( 14) 1.0000000000000 0.0000000000000
XUANQU( 15) 1.0000000000000 0.0000000000000
XUANQU( 16) 1.0000000000000 0.0000000000000
XUANQU( 17) 1.0000000000000 0.0000000000000
XUANQU( 18) 1.0000000000000 0.0000000000000
XUANQU( 19) 1.0000000000000 0.0000000000000
CHANGDU( 1) 3900.0000000000 0.0000000000000
CHANGDU( 2) 3650.0000000000 0.0000000000000
CHANGDU( 3) 3150.0000000000 0.0000000000000
CHANGDU( 4) 2650.0000000000 0.0000000000000
CHANGDU( 5) 2150.0000000000 0.0000000000000
XUQIU( 1) 100.00000000000 0.0000000000000
XUQIU( 2) 38.000000000000 0.0000000000000
XUQIU( 3) 32.000000000000 0.0000000000000
XUQIU( 4) 80.000000000000 0.0000000000000
XUQIU( 5) 80.000000000000 0.0000000000000
C( 1, 1) 0.0000000000000 0.0000000000000
C( 1, 2) 0.0000000000000 0.0000000000000
C( 1, 3) 0.0000000000000 0.0000000000000
C( 1, 4) 0.0000000000000 0.0000000000000
C( 1, 5) 4.0000000000000 0.0000000000000
C( 2, 1) 0.0000000000000 0.0000000000000
C( 2, 2) 0.0000000000000 0.0000000000000
C( 2, 3) 0.0000000000000 0.0000000000000
C( 2, 4) 1.0000000000000 0.0000000000000
C( 2, 5) 2.0000000000000 0.0000000000000
C( 3, 1) 0.0000000000000 0.0000000000000
C( 3, 2) 0.0000000000000 0.0000000000000
C( 3, 3) 0.0000000000000 0.0000000000000
C( 3, 4) 2.0000000000000 0.0000000000000
C( 3, 5) 1.0000000000000 0.0000000000000
C( 4, 1) 0.0000000000000 0.0000000000000
C( 4, 2) 0.0000000000000 0.0000000000000
C( 4, 3) 0.0000000000000 0.0000000000000
C( 4, 4) 3.0000000000000 0.0000000000000
C( 4, 5) 0.0000000000000 0.0000000000000
C( 5, 1) 0.0000000000000 0.0000000000000
C( 5, 2) 0.0000000000000 0.0000000000000
C( 5, 3) 1.0000000000000 0.0000000000000
C( 5, 4) 0.0000000000000 0.0000000000000
C( 5, 5) 2.0000000000000 0.0000000000000
C( 6, 1) 0.0000000000000 0.0000000000000
C( 6, 2) 0.0000000000000 0.0000000000000
C( 6, 3) 1.0000000000000 0.0000000000000
C( 6, 4) 1.0000000000000 0.0000000000000
C( 6, 5) 1.0000000000000 0.0000000000000
C( 7, 1) 0.0000000000000 0.0000000000000
C( 7, 2) 0.0000000000000 0.0000000000000
C( 7, 3) 1.0000000000000 0.0000000000000
C( 7, 4) 2.0000000000000 0.0000000000000
C( 7, 5) 0.0000000000000 0.0000000000000
C( 8, 1) 0.0000000000000 0.0000000000000
C( 8, 2) 0.0000000000000 0.0000000000000
C( 8, 3) 2.0000000000000 0.0000000000000
C( 8, 4) 0.0000000000000 0.0000000000000
C( 8, 5) 1.0000000000000 0.0000000000000
C( 9, 1) 0.0000000000000 0.0000000000000
C( 9, 2) 0.0000000000000 0.0000000000000
C( 9, 3) 2.0000000000000 0.0000000000000
C( 9, 4) 1.0000000000000 0.0000000000000
C( 9, 5) 0.0000000000000 0.0000000000000
C( 10, 1) 0.0000000000000 0.0000000000000
C( 10, 2) 1.0000000000000 0.0000000000000
C( 10, 3) 0.0000000000000 0.0000000000000
C( 10, 4) 0.0000000000000 0.0000000000000
C( 10, 5) 2.0000000000000 0.0000000000000
C( 11, 1) 0.0000000000000 0.0000000000000
C( 11, 2) 1.0000000000000 0.0000000000000
C( 11, 3) 0.0000000000000 0.0000000000000
C( 11, 4) 1.0000000000000 0.0000000000000
C( 11, 5) 1.0000000000000 0.0000000000000
C( 12, 1) 0.0000000000000 0.0000000000000
C( 12, 2) 1.0000000000000 0.0000000000000
C( 12, 3) 0.0000000000000 0.0000000000000
C( 12, 4) 2.0000000000000 0.0000000000000
C( 12, 5) 0.0000000000000 0.0000000000000
C( 13, 1) 0.0000000000000 0.0000000000000
C( 13, 2) 1.0000000000000 0.0000000000000
C( 13, 3) 1.0000000000000 0.0000000000000
C( 13, 4) 0.0000000000000 0.0000000000000
C( 13, 5) 1.0000000000000 0.0000000000000
C( 14, 1) 0.0000000000000 0.0000000000000
C( 14, 2) 2.0000000000000 0.0000000000000
C( 14, 3) 0.0000000000000 0.0000000000000
C( 14, 4) 0.0000000000000 0.0000000000000
C( 14, 5) 0.0000000000000 0.0000000000000
C( 15, 1) 1.0000000000000 0.0000000000000
C( 15, 2) 0.0000000000000 0.0000000000000
C( 15, 3) 0.0000000000000 0.0000000000000
C( 15, 4) 0.0000000000000 0.0000000000000
C( 15, 5) 2.0000000000000 0.0000000000000
C( 16, 1) 1.0000000000000 0.0000000000000
C( 16, 2) 0.0000000000000 0.0000000000000
C( 16, 3) 0.0000000000000 0.0000000000000
C( 16, 4) 1.0000000000000 0.0000000000000
C( 16, 5) 1.0000000000000 0.0000000000000
C( 17, 1) 1.0000000000000 0.0000000000000
C( 17, 2) 0.0000000000000 0.0000000000000
C( 17, 3) 1.0000000000000 0.0000000000000
C( 17, 4) 0.0000000000000 0.0000000000000
C( 17, 5) 0.0000000000000 0.0000000000000
C( 18, 1) 1.0000000000000 0.0000000000000
C( 18, 2) 1.0000000000000 0.0000000000000
C( 18, 3) 0.0000000000000 0.0000000000000
C( 18, 4) 0.0000000000000 0.0000000000000
C( 18, 5) 0.0000000000000 0.0000000000000
C( 19, 1) 2.0000000000000 0.0000000000000
C( 19, 2) 0.0000000000000 0.0000000000000
C( 19, 3) 0.0000000000000 0.0000000000000
C( 19, 4) 0.0000000000000 0.0000000000000
C( 19, 5) 0.0000000000000 0.0000000000000
Row Slack or Surplus Dual Price
1 1000000.0000000 0.0000000000000
2 1000000.0000000 0.0000000000000
3 1000000.0000000 0.0000000000000
4 1000000.0000000 0.0000000000000
5 1000000.0000000 0.0000000000000
6 1000000.0000000 0.0000000000000
7 1000000.0000000 0.0000000000000
8 1000000.0000000 0.0000000000000
9 999997.00000000 0.0000000000000
10 1000000.0000000 0.0000000000000
11 1000000.0000000 0.0000000000000
12 999988.00000000 0.0000000000000
13 999974.00000000 0.0000000000000
14 1000000.0000000 0.0000000000000
15 1000000.0000000 0.0000000000000
16 999946.00000000 0.0000000000000
17 1000000.0000000 0.0000000000000
18 1000000.0000000 0.0000000000000
19 999977.00000000 0.0000000000000
20 0.0000000000000 0.0000000000000
21 0.0000000000000 0.0000000000000
22 0.0000000000000 0.0000000000000
23 1.0000000000000 0.0000000000000
24 0.0000000000000 0.0000000000000
25 0.0000000000000 0.0000000000000
26 118.00000000000 -1.0000000000000
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根九米的钢管
aimisiyou 发表于 2023-5-28 07:31
119根。
我算出来是118根，你算出来是119根，我把切割方案拿出来了。
确实满足要求且还比你算出来的小，所以你的肯定错误了！
nyy 发表于 2023-5-29 10:29
我算出来是118根，你算出来是119根，我把切割方案拿出来了。
确实满足要求且还比你算出来的小，所以你的 ...
方便加个V吗我的180686