用LINGO求解整数规划的例子

附1：用LINGO求解整数规划的例子。某钢管零售商从钢管厂进货，将钢管按照顾客要求的长度进行切割，称为下料。假定进货时得到的原料钢管长度都是19m。1）现有一客户需要50根长4m、20根长6m和15根长8m的钢管。应如何下料最节省？2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本。所以该零售商规定采用的不同切割模式不能超过3种。此外。该客户除需要1）中的3种钢管外，还要10根长5m的钢管。应如何下料最节省？问题分析：对于下料问题首先要确定采用哪些切割模式。所谓切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如，我们可以将19m的钢管切割成3根长4m的钢管，余料为7m；或者将长19m的钢管切割成长4m、6m和8m的钢管各1根，余料为1m。显然，可行的切割模式是很多的。其次，应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如，可以将长19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可进一步将7m的余料切割成4m钢管（余料为3m），或者将7m的余料切割成6m钢管（余料为1m）。经过简单的计算可知，问题1）的合理切割模式一共有7种，如表1所示：于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。问题1）用xi表示按照表1第i种模式（i=1,2,…,7）切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表1最后一列可得minZ1=3x1+x2+3x3+3x4+x5+x6+3x7若以切割原料钢管的总根数最少为目标，则有表1钢管下料问题1）的合理切割模式模式4m钢管根数6m钢管根数8m钢管根数余料/m14003231013201341203511116030170022MinZ2=x1+x2+x3+x4+x5+x6+x7约束条件为客户的需求，按照表1应有4x1+3x2+2x3+x4+x5≥50x2+2x4+x5+3x6≥20x3+x5+2x7≥15最后，切割的原料钢管的根数xi显然应当是非负整数（用Z表示整数集合，Z+表示非负整数集合）：xi∈Z+，i=1,2,…,7于是，问题1）归结为在约束条件下，使目标达到最小。显然这是线性整数规划模型。问题2）如果按照问题1）的办法处理，首先要通过枚举法确定哪些切割模式是合理的，并从中选出不超过3种模式。而由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍一种带有普遍性的方法，可以同时确定切割模式和切割数量。同问题1）一样，只使用合理的切割模式，其余料不应大于3m（因为客户需要的钢管最小尺寸为4m，而本题中参数都是整数）。由于不同切割模式不能超过3种，可以用用xi表示按照第i种模式（i=1,2,3）切割的原料钢管的根数。又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为r1i，r2i，r3i，r4i。仅以使用的原料总根数最少为目标，即minx1+x2+x3满足客户需求的约束条件为r11x1+r12x2+r13x3≥50r21x1+r22x2+r23x3≥10r31x1+r32x2+r33x3≥20r41x1+r42x2+r43x3≥15每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16m（余料不能大于3m），于是16≤4r11+5r21+6r31+8r41≤1916≤4r12+5r22+6r32+8r42≤1916≤4r13+5r23+6r33+8r43≤19最后，加上非负整数约束：xi，rji∈Z+，i=1,2,3,j=1,2,3,4于是，问题2）归结为在在约束条件下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目标达到最小。当然，这是一个整数非线性规划模型。用LINGO求解整数规划LINGO软件用于线性或非线性规划（无论是连续规划还是整数规划），因此包含了LINDO的功能。在LINGO中，所有的函数均以“@”符号开始，如约束中@gin(x1)表示x1为整数，用bin(x1)表示x1为0-1整数。钢管下料问题1）的求解以切割后剩余的总余料量最小为目标，建立LINGO模型：min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5=50;x2+2*x4+x5+3*x6=20;x3+x5+2*x7=15;@gin(x1);@gin(x2);@gin(x3);求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量27m。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和模式5的余料为1m），这会导致切割原料钢管的总根数较多。以切割原料钢管的总根数最少为目标，建立LINGO模型：min=x1+x2+x3+x4+x5+x6+x7;4*x1+3*x2+2*x3+x4+x5=50;x2+2*x4+x5+3*x6=20;x3+x5+2*x7=15;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000即按照模式2切割15根原料钢管，按照模式5切割5根原料钢管，按照模式7切割5根原料钢管，共25根，总余料量35m。与上面得到的结果相比，总余料量增加了8m，但是所用的原料钢管的总根数减少了2根，在余料没有什么用途的情况下，通常选择总根数最少为目标。钢管下料问题2）的求解非线性整数规划模型虽然用LINGO软件可以直接求解，但为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。例如，由于3种切割模式的排列顺序是无关要紧的，所以不妨增加以下约束：x1≥x2≥x3又如，注意到所需原料钢管的总根数有明显的上界和下界。首先，原料钢管的根数不可能少于2619158206105504（根）。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4m钢管，为满足50根4m钢管的需求，需要13根原料钢管；第二种切割模式下只生产5m，6m钢管，一根原料钢管切割成1根5m钢管和2根6m钢管，为满足10根5m和20根6m钢管的需求，需要10根原料钢管；第三种切割模式下只生产8m钢管，一根原料钢管切割成2根8m钢管，为满足15根8m钢管的需求，需要8根原料钢管。于是满足要求的这种生产计划共需要13+10+8=31根原料钢管，这就得到了最优解的一个上界，所以可增加以下约束：26≤x1+x2+x3≤31LINGO模型为：min=x1+x2+x3;r11*x1+r12*x2+r13*x3=50;r21*x1+r22*x2+r23*x3=10;r31*x1+r32*x2+r33*x3=20;r41*x1+r42*x2+r43*x3=15;4*r11+5*r21+6*r31+8*r41=19;4*r12+5*r22+6*r32+8*r42=19;4*r13+5*r23+6*r33+8*r43=19;4*r11+5*r21+6*r31+8*r41=16;4*r12+5*r22+6*r32+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;x1+x2+x3=26;x1+x2+x3=31;x1=x2;x2=x3;@gin(x1);@gin(x2);@gin(x3);@gin(r11);@gin(r12);@gin(r13);@gin(r21);@gin(r22);@gin(r23);@gin(r31);@gin(r32);@gin(r33);@gin(r41);@gin(r42);@gin(r43);得到输出如下：Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000r113.0000000.000000r122.0000000.000000r130.0000000.000000r210.0000000.000000r221.0000000.000000r230.0000000.000000r311.0000000.000000r321.0000000.000000r330.0000000.000000r410.0000000.000000r420.0000000.000000r432.0000000.000000即按照模式1，2，3分别切割10根，10根，8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管；第二种切割模式下一根原料钢管切割成2根4m钢管，1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成2根8m钢管。