钢管下料问题.doc

钢管下料问题摘要： 本文对钢管零售商在满足客户需要的原则下，为了减少余料浪费，并使切割总费用最小，且为了简化生产过程，应如何选取最优切割方案的问题进行了研究。 通过对问题的分析，首先利用C语言编程求解出按照客户需要确定可行的切割模式（具体见附录一）。考虑到规定所使用的切割模式的种类不能超过4种，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5根产品），可以列出一系列约束条件。由于切割模式使用频率可以有两种或两种以上相同，然后按照切割模式使用频率的不同情况建立四种模型。 模型一是：有四种切割模式使用频率均不相同；模型二是：有两种切割模式使用频率相同；模型三是：有三种切割模式使用频率相同；模型四是：有四种切割模式使用频率均相同（模型二与模型三中分别又建立了其不同情况的子模型）。然后利用lingo9.0求解出每种模型的最优方案。考虑余料浪费情况和总费用情况，比较每种模型下得出的最优方案，得出针对客户要求的一种最优方案（具体见正文：六.最优模型的选择）。最后对不同客户的不同要求作出推广模型，针对顾客要求切割不同长度的钢管各多少根，利用该模型可求出最优方案。关键字：钢管下料 c程序处理切割模式 lingo处理优化问题 非线性规划 一：问题重述与提出 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割出售从钢管厂进货得到的原材料的钢管的长度都是1850mm ，现在一顾客需要15根290 mm，28根315 mm，21根350 mm和30根455 mm的钢管为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，以此类推，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5根产品），此外为了减少余料浪费，每种切割模式下的余料浪费不能超过100 mm。市场产品销售价格已知，零售商进货价格已定，零售商的利润主要来自对成本的控制，故要选取合理的切割模式进行下料，使总费用最小，求此合理切割方案。二：问题分析 按照题意列出合理的切割模式方程，可利用C语言编程求出按照客户需求确定可行的切割方式共有多少种。考虑到规定所使用的切割模式的种类不能超过4种，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5根产品），可以列出一系列约束条件。由于切割模式使用频率可以有两种或两种以上相同，所以目标函数也会发生改变。因此建立多种模型，并利用lingo9.0程序求出每种模型的最优解。三：模型假设（1） 假设钢管零售商从钢管厂进的货均为合格品；（2） 假设每次切割时机器工作正常，且每次切割均符合要求；（3） 假设每次按要求切割的钢管均符合顾客要求；（4） 假设不考虑余料的循环利用和其作为废品所带来的价值；（5） 假设不考虑切割时产生的废屑；（6） 假设模式使用频率相同时，其产生的增加费用相同； 四：符号说明 Z :表示切割费用； xi:表示按照第i种切割模式下切割的钢管根数；(i=1,2,3,4) rji:表示第i种切割模式下切割290 mm， 315 mm， 350 mm和455 mm的钢管数量为j;(j=1,2,3,4) n1表示第一种钢管类型所需的数量;l1表示第一种钢管类型的长度； n2表示第二种钢管类型所需的数量;l2表示第二种钢管类型的长度；n3表示第三种钢管类型所需的数量;l3表示第三种钢管类型的长度； n4表示第四种钢管类型所需的数量；l4表示第四种钢管类型的长度；五：模型建立考虑到规定所使用的切割模式的种类不能超过4种，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5根产品），可以列出一系列约束条件（1）切割次数有：r11+r21+r31+r415;（第一种模式下切割次数不超过5）r12+r22+r32+r425;（第二种模式下切割次数不超过5）r13+r23+r33+r435;（第三种模式下切割次数不超过5）r14+r24+r34+r445;（第四种模式下切割次数不超过5） （2）每种切割模式下一根钢管的使用情况有： 1750290r11+315r21+350r31+455r411850;1750290r12+315r22+350r32+455r421850;1750290r13+315r23+350r33+455r431850;1750290r14+315r24+350r34+455r441850; (3)针对客户要求有：x1r11+x2r12+x3r13+x4r1415;x1r21+x2r22+x3r23+x4r2428;x1r31+x2r32+x3r33+x4r3421;x1r41+x2r42+x3r43+x4r4430; （4）每种模式的使用频率：有(x1+x2+x3+x4) (29015+31528+35021+44530)185018.3故有：x1+x2+x3+x419若一根钢管只生产290mm的钢管可切割6根，但每种切割模式下切割次数不能多于4次，故一根钢管应该切割290mm钢管5根，那么切割15根290mm的钢管需要3根原材料；同理可知，若只生产315mm的钢管，为满足28根315mm钢管，需要6根原材料；若只生产350mm的钢管，为满足21根350mm钢管，需要5根原材料；若只生产455mm的钢管，为满足301根455mm钢管，需要8根原材料。所以共需3+5+6+8=22根钢管。综上有：19x2x3x4），使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，以此类推，得目标函数（最小总费用）如下：目标函数为：minz=1.1x1+1.2x2+1.3x3+1.4x42 .模型结果与结果分析利用lingo9.0计算模型一（源程序和运行结果见附录二）结果如下表：模式钢管数290315350455余料1141202202400501003120121040103155minZ 21.5由表可知：按照切割模式使用频率依次选取模式8，模式2，模式9，模式6（见附录一）。所以最优方案为选取19根钢管，其中14根分别切割290mm,315mm,350mm,455mm钢管为1根，2根，0根，2根；4根钢管切割为0根，0根，5根，0根；1根钢管切割为2根，0根，1根，2根；5.2模型二当有两种切割模式的频率使用相同时可分为以下三个子模型。模型2-1： 当切割模式使用频率为x1=x2x3x4时 有： minz=1.1x1+1.1x2+1.2x3+1.3x4 （频率x1=x2,故该两种模式增加费用相同，均按一根原料钢管价值的1/10增加费用）利用lingo9.0计算模型二（源程序和运行结果见附录三模型2-1）结果如下表：模式钢管数290315350455余料171202202712022034005010041201210minZ 21.5 合并相同切割模式有模式钢管数290315350455余料11412022024005010031201210minZ 21.5由表可知：按照切割模式使用频率依次选取模式8，模式2，模式9（见附录一）。所以最优方案为选取19根钢管，其中14根分别切割290mm,315mm,350mm,455mm钢管为1根，2根，0根，2根； 4根钢管切割为0根，0根，5根，0根；1根钢管切割为2根，0根，1根，2根。此模型与模型一情况一样！模型2-2 当切割模式使用频率为x1x2=x3x4时 有： minz=1.1x1+1.2x2+1.2x3+1.3x4 （频率x2=x3,故该两种模式增加费用相同均按一根原料钢管价值的2/10增加费用，）利用lingo9.0计算模型二（源程序和运行结果见附录三模型2-2）结果如下表：模式钢管数290315350455余料11412022022005010032103155410050100minZ 21.5 合并相同切割模式有模式钢管数290315350455余料11412022023005010032103155minZ 21.5由表可知：按照切割模式使用频率依次选取模式8，模式2，模式6，（见附录一）。所以最优方案为选取19根钢管，其中14根分别切割290mm,315mm,350mm,455mm钢管为1根，2根，0根，2根；3根钢管切割为0根，0根，5根，0根；2根钢管切割为1根，0根，3根，1根。模型2-3： 当切割模式使用频率为x1x2x3=x4时 有： minz=1.1x1+1.2x2+1.3x3+1.3x4 （频率x3=x4,故该两种模式增加费用相同，均按一根原料钢管价值的3/10增加费用）利用lingo9.0计算模型二（源程序和运行结果见附录三模型2-3）结果如下表：模式钢管数290315350455余料1141202202300501003101313041103155minZ 21.6 由表可知：按照切割模式使用频率依次选取模式8，模式2，模式3，模式6（见附录一）。所以最优方案为选取19根钢管，其中14根分别切割290mm,315mm,350mm,455mm钢管为1根，2根，0根，2根；3根钢管切割为0根，0根，5根，0根；1根钢管切割为0根，1根，3根，1根；1根钢管切割为1根，0根，3根，1根。5.3模型三 当有三种切割模式的频率使用相同时分为以下两个子模型。模型3-1： 当切割模式使用频率为x1=x2=x3x4时有： minz=1.1x1+1.1x2+1.1x3+1.2x4 （频率x1=x2=x3,故该三种模式增加费用相同，均按一根原料钢管价值的1/10增加费用）利用lingo9.0计算模型三（源程序和运行结果见附录四模型3-1）结果如下表：模式钢管数290315350455余料162102452602216536120220420050100minZ 22.2 由表可知：按照切割模式使用频率依次选取模式10，模式4，模式8，模式2（见附录一）。所以最优方案为选取20根钢管，其中6根分别切割290mm,315mm,350mm,455mm钢管为2根，1根，0根，2根；6根钢管切割为0根，2根，2根，1根；6根钢管切割为1根，2根，0根，2根；1根钢管切割为0根，0根，5根，0根。模型3-2： 当切割模式使用频率为x1x2=x3=x4时有： minz=1.1x1+1.2x2+1.2x3+1.2x4 （频率x2=x3=x4,故该三种模式增加费用相同，均按一根原料钢管价值的2/10增加费用）利用lingo9.0计算模型三（源程序和运行结果见附录四模型3-2）结果如下表：模式钢管数290315350455余料1131202202201313032103155420050100minZ 21.5 由表可知：按照切割模式使用频率依次选取模式8，模式3，模式6，模式2（见附录一）。所以最优方案为选取19根钢管，其中13根分别切割290mm,315mm,350mm,455mm钢管为1根，2根，0根，2根；2根钢管切割为0根，1根，3根，1根；2根钢管切割为1根，0根，3根，1根；2根钢管切割为0根，0根，5根，0根。5.4模型四 当有四种切割模式的频率使用相同时即切割模式使用频率为x1=x2=x3=x4时有： minz=1.1x1+1.1x2+1.1x3+1.1x4 （此时4种使用频率的切割模式均按照一根原料钢管价值的1/10增加费用）利用lingo9.0计算模型四（源程序和运行结果见附录五）结果如下表：模式钢管数290315350455余料152012102501313035120220450311100minZ 22.2 由表可知：按照切割模式使用频率依次选取模式9，模式3，模式8，模式5（见附录一）。所以最优方案为选取20根钢管，其中5根分别切割290mm,315mm,350mm,455mm钢管为2根，0根，1根，2根；5根钢管切割为0根，1根，3根，1根；5根钢管切割为1根，2根，0根，2根；1根钢管切割为0根，3根，1根，1根。六最优模型的选择从minZ及消耗钢管总数角度及生产过程最简化（即生产使用的切割模式种类最少）考虑，优先考虑以下2种最优模型：（模型1与模型2-1情况相同）模型钢管总数MinZ切割模式种类模型一（模型2-1）1921.53模型2-21921.53零售商可从以上两种最优模型中任选其一进行生产切割。七模型推广对于任一顾客的要求：切割n1根l1长度钢管，切割n2根l2长度钢管，切割n3根l3长度钢管，切割n4根l4长度钢管切割nx根lx长度钢管(nx,lx均符合实际情况)，利用以上模型能够很好的求解出最优方案。八模型优缺点1.模型优点：（1）建模思路清晰，模型的建立方案比较简单，易于读懂；（2）模型结构分明；（3）模型在处理切割问题时，考虑到多种切割模式使用频率相同情况，并给出相应模型求解。（4）对模型进行了推广2.模型缺点：（1）没有对模型进行进一步的优化和更深层次的推广；（2）各模型的源程序近乎相同，过程显得有些繁琐。参考文献：1丁勇，钢管下料问题优化，理科爱好者，2010,1（4）：13-14,2010年2 谢金星等，优化模型与LINDO/LINGO优化软件,北京：清华大学出版社，2005年3张胜详，lingo基本教程，/view/114af46527d3240c8447ef3a.html，2010-05-184西北工业大学理学院应用数学系，数学建模精品课程，/jp2008/05/index.htm，2010-05-19 附录一（按照客户需要确定可以的切割模式）C语言源程序#include #include void main()int a,b,c,d,i=0,j,k; /*a,b,c,d表示某模式下切割290，315，350，455mm的数量，j k在变量输出时使用*/int aa164=0; /*定义一个二维数组*/for(a=0;a=5;a+) /*四个for语句是通过枚举方式，得到某模式下切割290，315，350，455mm的数量*/ for(b=0;b=5;b+) for(c=0;c=5;c+)for(d=0;d=5;d+)if(a+b+c+d)=1750&(290*a+315*b+350*c+455*d)=1850) /*筛选符合条件的模式*/aai0=a; /*将符合条件的第i种模式下切割290mm钢管数量a赋给ai0*/aai1=b; /*将符合条件的第i种模式下切割315mm钢管数量b赋给ai1*/aai2=c; /*将符合条件的第i种模式下切割350mm钢管数量a赋给ai2*/aai3=d; /*将符合条件的第i种模式下切割455mm钢管数量a赋给ai3*/i+;for(j=0;ji;j+) /*此时的i代表符合要求的模式数量*/ for(k=0;k=n1;x1*r21+x2*r22+x3*r23+x4*r24=n2;x1*r31+x2*r32+x3*r33+x4*r34=n3;x1*r41+x2*r42+x3*r43+x4*r44=n4;1750=l1*r11+l2*r21+l3*r31+l4*r41;1750=l1*r12+l2*r22+l3*r32+l4*r42;1750=l1*r13+l2*r23+l3*r33+l4*r43;1750=l1*r14+l2*r24+l3*r34+l4*r44;l1*r11+l2*r21+l3*r31+l4*r41=1850;l1*r12+l2*r22+l3*r32+l4*r42=1850;l1*r13+l2*r23+l3*r33+l4*r43=1850;l1*r14+l2*r24+l3*r34+l4*r44=1850;r11+r21+r31+r41=5;r12+r22+r32+r42=5;r13+r23+r33+r43=5;r14+r24+r34+r44x2;x2x3;x3x4;gin(x1); gin(x2); gin(x3);gin(x4);gin(r11);gin(r12);gin(r13);gin(r14);gin(r21);gin(r22);gin(r23);gin(r24);gin(r31);gin(r32);gin(r33);gin(r34);gin(r41);gin(r42);gin(r43);gin(r44);End运行结果如下：Local optimal solution found. Objective value: 21.50000 Extended solver steps: 525 Total solver iterations: 14953 Variable Value Reduced Cost N1 15.00000 0.000000 L1 290.0000 0.000000 N2 28.00000 0.000000 L2 315.0000 0.000000 N3 21.00000 0.000000 L3 350.0000 0.000000 N4 30.00000 0.000000 L4 455.0000 0.000000 X1 14.00000 1.100000 X2 4.000000 1.200000 X3 1.000000 1.300000 X4 0.000000 1.400000 R11 1.000000 0.000000 R12 0.000000 0.000000 R13 2.000000 0.000000 R14 2.000000 0.000000 R21 2.000000 0.000000 R22 0.000000 0.000000 R23 0.000000 0.000000 R24 1.000000 0.000000 R31 0.000000 0.000000 R32 5.000000 0.000000 R33 1.000000 0.000000 R34 0.000000 0.000000 R41 2.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 R44 2.000000 0.000000 Row Slack or Surplus Dual Price 1 21.50000 -1.000000 2 1.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 80.00000 0.000000 7 0.000000 0.000000 8 90.00000 0.000000 9 55.00000 0.000000 10 20.00000 0.000000 11 100.0000 0.000000 12 10.00000 0.000000 13 45.00000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 10.00000 0.000000 19 3.000000 0.000000 20 1.000000 0.000000附录三：（模型二源程序和运行结果）模型2-1源程序如下model:!数据部分; data: !根据客户所需的类型，导入各类型钢管的数量和长度，以便于修改; n1,l1= 15 290;!n1表示第一种钢管类型所需的数量，l1表示第一种钢管类型的长度; n2,l2= 28 315;!n2表示第二种钢管类型所需的数量，l2表示第二种钢管类型的长度; n3,l3= 21 350;!n3表示第三种钢管类型所需的数量，l3表示第三种钢管类型的长度; n4,l4= 30 455;!n4表示第四种钢管类型所需的数量，l4表示第四种钢管类型的长度;enddatamin=1.1*x1+1.1*x2+1.2*x3+1.3*x4;!有两种切割模式使用频率相同x1=x2,故其前系数都为1.1;x1*r11+x2*r12+x3*r13+x4*r14=n1;x1*r21+x2*r22+x3*r23+x4*r24=n2;x1*r31+x2*r32+x3*r33+x4*r34=n3;x1*r41+x2*r42+x3*r43+x4*r44=n4;1750=l1*r11+l2*r21+l3*r31+l4*r41;1750=l1*r12+l2*r22+l3*r32+l4*r42;1750=l1*r13+l2*r23+l3*r33+l4*r43;1750=l1*r14+l2*r24+l3*r34+l4*r44;l1*r11+l2*r21+l3*r31+l4*r41=1850;l1*r12+l2*r22+l3*r32+l4*r42=1850;l1*r13+l2*r23+l3*r33+l4*r43=1850;l1*r14+l2*r24+l3*r34+l4*r44=1850;r11+r21+r31+r41=5;r12+r22+r32+r42=5;r13+r23+r33+r43=5;r14+r24+r34+r44x3;x3x4;gin(x1); gin(x2); gin(x3);gin(x4);gin(r11);gin(r12);gin(r13);gin(r14);gin(r21);gin(r22);gin(r23);gin(r24);gin(r31);gin(r32);gin(r33);gin(r34);gin(r41);gin(r42);gin(r43);gin(r44);End运行结果如下Local optimal solution found. Objective value: 21.50000 Extended solver steps: 3014 Total solver iterations: 90258 Variable Value Reduced Cost N1 15.00000 0.000000 L1 290.0000 0.000000 N2 28.00000 0.000000 L2 315.0000 0.000000 N3 21.00000 0.000000 L3 350.0000 0.000000 N4 30.00000 0.000000 L4 455.0000 0.000000 X1 7.000000 2.200000 X2 7.000000 0.000000 X3 4.000000 1.200000 X4 1.000000 1.300000 R11 1.000000 0.000000 R12 1.000000 0.000000 R13 0.000000 0.000000 R14 2.000000 0.000000 R21 2.000000 0.000000 R22 2.000000 0.000000 R23 0.000000 0.000000 R24 0.000000 0.000000 R31 0.000000 0.000000 R32 0.000000 0.000000 R33 5.000000 0.000000 R34 1.000000 0.000000 R41 2.000000 0.000000 R42 2.000000 0.000000 R43 0.000000 0.000000 R44 2.000000 0.000000 Row Slack or Surplus Dual Price 1 21.50000 -1.000000 2 1.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 80.00000 0.000000 7 80.00000 0.000000 8 0.000000 0.000000 9 90.00000 0.000000 10 20.00000 0.000000 11 20.00000 0.000000 12 100.0000 0.000000 13 10.00000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 1.100000 19 3.000000 0.000000 20 3.000000 0.000000模型2-2原程序如下 model:!数据部分; data: !根据客户所需的类型，导入各类型钢管的数量和长度，以便于修改; n1,l1= 15 290;!n1表示第一种钢管类型所需的数量，l1表示第一种钢管类型的长度; n2,l2= 28 315;!n2表示第二种钢管类型所需的数量，l2