钢筋切割问题.docx

姓名：李俊江 学号：10011113钢筋切割问题1摘要: 如何购买最少的原材料使满足条件,建立线性规划约束模型,用最佳方法解决问题,并得出结果。2.问题重述：设某种规格的钢筋原材料每根长10m，求解如下优化问题:（1) 现需要该种钢筋长度为4m的28根，长度为1.8m的33根,问至少需要购买原材料几根?如何切割?（2) 如需要该种钢筋长度为4m的28根，长度为1.8m的33根, 长度为3.6m的79根，长度为2.4m的46根,问至少需要购买原材料几根?如何切割?3模型假设与记号：列出各种情况，并制作成表格，分别设变量，切割方式变量为i，对应消耗原材料为xi根。 4分析与建立模型：（问题1):对于钢筋切割问题,我们考虑10m的钢筋原材料切割成4m和1.8m的钢筋有几种分割方法,可以分割成5根1.8m的钢筋,分割成2根4m的钢筋等等,又考虑到要充分利用钢筋故可以切割成2根4m和1根1.8m.故将所有分割情况列成下表1:表1切割方法4m钢筋1.8m钢筋钢筋余量(m)10512130.63210.2 设采用切割方式1,消耗原材料x1根; 采用切割方式2,消耗原材料x2根; 采用切割方式3,消耗原材料x3根.则消耗的总原材料数目为y=x1+x2+x3;即求y的最小值. 根据题目可列出下列式子:min y=x1+x2+x3; (1) 目标函数约 束 条 件 2x3+x2=28; (2)s.t. 5x1+3x2+x3=33; (3) 最后原材料xi为正整数，故问题1)可化为在约束条件下,使目标函数最小的整数规划问题. （问题2):考虑方式同问题1)一样;同样列出表2:表2分割方式1.8m钢筋2.4m钢筋3.6m钢筋4m钢筋钢筋余量(m)110020.2230010.6321010410110.6501110610201702101.6821100.49301011004000.411130011222001.61341000.41450001设采用切割方式i,消耗原材料xi根;总原材料:y=xi;据题意可列出下列式子：min y=xi;2x1+x2+x3+x4+x528;x4+x5+2x6+x7+x8+x979;x3+x5+2x7+x8+4x10+3x11+2x12+x1346;x1+3x2+2x3+x4+x6+2x8+3x9+x11+2x12+4x13+5x1433;最后原材料xi为正整数，故问题1)可化为在约束条件下,使目标函数最小的整数规划问题.5模型求解：（问题1）：利用lingo软件进行整数规划计算；建立lingo模型： min=x1+x2+x3; 2x2+x3=28; 5x1+x2+3x3=33; gin(x1); gin(x2); gin(x3); 求解可得如下最优解： Global optimal solution found. Objective value: 18.00000 Objective bound: 18.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 4 Variable Value Reduced Cost X1 4.000000 1.000000 X2 14.00000 1.000000 X3 0.000000 1.000000 Row Slack or Surplus Dual Price 1 18.00000 -1.000000 2 0.000000 0.000000 3 1.000000 0.000000按照切割方式1切割4根，按照切割方式3切割14根，共18根，即最少切割18根。（问题2）：建立lingo模型：min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14;2x1+x2+x3+x4+x5=28;x4+x5+2x6+x7+x8+x9=79;x3+x5+2x7+x8+4x10+3x11+2x12+x13=46;x1+3x2+2x3+x4+x6+2x8+3x9+x11+2x12+4x13+5x14=33;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(x9);gin(x10);gin(x11);gin(x12);gin(x13);gin(x14);求解可得如下最优解： Global optimal solution found. Objective value: 60.00000 Objective bound: 60.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 6 Variable Value Reduced Cost X1 0.000000 1.000000X2 0.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 28.00000 1.000000 X6 23.00000 1.000000 X7 0.000000 1.000000 X8 5.000000 1.000000 X9 0.000000 1.000000 X10 4.000000 1.000000 X11 0.000000 1.000000 X12 0.000000 1.000000 X13 0.000000 1.000000 X14 0.000000 1.000000Row Slack or Surplus Dual Price 1 60.00000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 3.000000 0.000000 5 0.000000 0.000000按照切割方式5切割28根，按照切割方式6切割23根，按照切割方式8切割5根，按照切割方式10切割4根，共60根，即最少切割60根。6模型检验：把所得结果带入进行验证，问题一中4米的根数为4*0+14*2=28,1.8米的根数为5*4+1*14=3