求如何切割浪费最少

nyy · 发表于 2023-5-29 10:40:42

MODEL:
TITLE 钢管下料问题;
SETS:
!GENSHU(I)表示选取第I种方式时选取的根数;
!总共有19种方式,每种方式的根数;
FANGSHI/1..19/:GENSHU;
!需求根数;
GGCD/1..5/:XUQIU;
!C(I,J)表示按照第I种方式切割时能获得的第J种钢管的数量;
XISHU(FANGSHI,GGCD):C;
ENDSETS
DATA:
!每种钢管至少需要的数量;
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
!每种钢管都要大于等于需求量;
@FOR(GGCD(J):@SUM(FANGSHI(I):C(I,J)*GENSHU(I))>=XUQIU(J));
!每种方式的根数都要求是整数;
@FOR(FANGSHI(I):@GIN(GENSHU(I)));
!求根数和的最小值;
MIN=@SUM(FANGSHI(I):GENSHU(I));
END

复制代码

继续简化后的代码，求解结果不变！

aimisiyou · 发表于 2023-5-29 10:58:21

nyy 发表于 2023-5-29 10:29
我算出来是118根，你算出来是119根，我把切割方案拿出来了。
确实满足要求且还比你算出来的小，所以你的 ...

随机算法算的，近优解，不是最优解。

nyy · 发表于 2023-5-29 11:09:42

aimisiyou 发表于 2023-5-29 10:58
随机算法算的，近优解，不是最优解。

你怎么随机的？？？？？？
我是先穷举出所有的切割模式的可能，然后再最优化解决问题！

nyy · 发表于 2023-5-29 16:06:49

https://github.com/vim-scripts/lingo.vim--Cataldo
https://github.com/huangyxi/lingo.vim

lingo自身的语法高亮太差了，不得不弄vim的语法高亮，下载这个文件，比他自身的强太多了

nyy · 发表于 2023-5-30 11:51:17

nyy 发表于 2023-5-29 10:40
继续简化后的代码，求解结果不变！

求解结果：
居然迭代10次就能得到结果！

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.14
Model Class: PILP
Total variables: 19
Nonlinear variables: 0
Integer variables: 19
Total constraints: 6
Nonlinear constraints: 0
Total nonzeros: 57
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
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 0.0000000000000 0.0000000000000
2 0.0000000000000 0.0000000000000
3 0.0000000000000 0.0000000000000
4 1.0000000000000 0.0000000000000
5 0.0000000000000 0.0000000000000
6 118.00000000000 -1.0000000000000

复制代码

nyy · 发表于 2023-5-30 11:56:56

nyy 发表于 2023-5-30 11:51
求解结果：
居然迭代10次就能得到结果！

lingo还能直接给出非零解。这样给出来的求解结果更简单表达更简洁！

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.06
Model Title: 钢管下料问题
Variable Value Reduced Cost
GENSHU( 9) 3.0000000000000 1.0000000000000
GENSHU( 12) 12.000000000000 1.0000000000000
GENSHU( 13) 26.000000000000 1.0000000000000
GENSHU( 16) 54.000000000000 1.0000000000000
GENSHU( 19) 23.000000000000 1.0000000000000

复制代码

账号		自动登录	找回密码
密码			欢迎注册

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

点评