数学建模-钢管切割问题

问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是21米的。现有一客户需要45根5m，25根7m和20根9m,的钢管。应如何下料最省？零售商如果采用的不同的切割模式太多，将会导致生产过程复杂化，从而增加生产和管理成本，所以该零售商规定采用的切割模式不能超过3种。因此，该客户除需要（1）中的三种钢管外，还需要15根6m的钢管。应如何下料最节省。问题（1）的求解问题分析首先，应该确定哪些切割模式是可行的。所谓的一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如：我们将21m的钢管切割成4根5m的钢管，余料为1m；或者将21m的钢管切割成2根5m，1根7m的钢管，余料是4m。显然这样的切割模式很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或者等于客户需要的钢管的最小尺寸。在这种合理的假设下，切割模式一共有7种，如表所示。5m钢管根数7m钢管根数9m钢管根数余料（m）模式14001模式22104模式32012模式41202模式51110模式60300模式70023问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少原料钢管，最为节省。而所谓节省，可以有两种标准：一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最小。下面将对这两个目标分别讨论。模型建立决策变量用xi表示按照第i种模式（i=1,2,…，7）切割的原料钢管的根数，显然他们是非负整数的。决策目标以切割后剩余的总余料量最小为目标，则由表可得MinZ1=x1+4x2+2x3+2x4+3x7（1）以切割原料钢管的总根数最少为目标，则有MinZ2=x1+x2+x3+x4+x5+x6+x7（2）下面分别在这两种目标下求解。约束条件为了满足客户的需要，按照表应有4x1+2x2+2x3+x4+x5≥45（3）X2+2x4+x5+3x6≥25（4）X3+x5+2x7≥20（5）模型求解将（1），（3），（4），（5）构成的整数线性规划模型（加上整数约束）输入LINDO如下：求解可以得到最优解如下：即按照模式5切割45根原料钢管，按照模式6切割9根原料钢管，共54根。总余料为0。显然，在总余料最小的目标下，最优解将是使用余料尽可能小的切割模式（模式5和6的余料为0）。将（2）~（5）构成的整体线性规划模式（加上整数约束）输入LINDO求解，可以得到最优解如下：即按照模式1切割6根原料钢管，按照模式3切割1根原料钢管，按照模式5切割19根原料钢管，按照模式6切割2根原料钢管，可算出总余料量为8m。与上面得到的结果比，总余料量增加了8m，但是所用的原料钢管总根数减少了26根。在余料没有用途的情况下，选择总根数最少为目标。问题（2）的求解问题分析按照（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但是由于需求的钢管规格增加到了4种，所以枚举的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普通性的方法。同（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸5m，切割计划中只能使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于4m。此外，这里仅选择总根数最少为目标进行求解。模型建立决策变量由于不同切割模式不能超过3种，可以用xi表示按照第i种模式（i=1，2，3）切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第i种切割模式下的每根钢管生产5m,6m,7m和9m的钢管数量分别是r1i,r2i,r3i,r4i.决策目标切割原料钢管的总根数最少，目标为Minx1+x2+x3（6）约束条件为了满足客户的需求，应该有r11x1+r12x2+r13x3≥45（7）r21x1+r22x2+r23x3≥15（8）r31x1+r32x2+r33x3≥25（9）r41x1+r42x2+r43x3≥20（10）每根原料钢管的成品量不能超过21m，也不能少于17m，于是17≤5r11+6r21+7r31+9r41≤21（11）17≤5r12+6r22+7r32+9r42≤21（12） 17≤5r13+6r23+7r33+9r43≤21（13）模型求解在（7）~（10）式中出现决策变量的乘积，是个整数非线性规划模型，虽然用LINGO软件可以直接求解，但是运行很长时间也难得到最优解。为了减少时间，可以增加一些显然的条件。例如：由于3种切割模式的排列顺序是无关紧要的，所以不妨增加一下约束x1≥x2≥x3(14)又如：所需原料钢管的总根数有着明显的上界和下界。首先，无论如何原料钢管的总根数不可能少于[(45×5+5×6+25×7+20×9)/21]+=30根。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产5m和6m的钢管，一根原料钢管切成3根5m和1根6m的钢管，为了满足45根5m和15根6m的钢管要求，需要15根原料钢管；第二种切割模式下只生产7m的钢管，一根原料钢管可以切割成3根7m的钢管，为了满足25根7m的钢管的要求，需要9根原料钢管；第三种切割模式下只生产9m的钢管，一根原料钢管可以切割成2根9m的钢管，为了满足20根钢管需求，需要10根原料钢管，这就得到了最优解得上界。所以可以增加以下约束30≤x1+x2+x3≤34将（6）~（15）构成的模型输入LINGO如下：经过运行，得到输出如