钢管下料问题PPT学习教案

1、钢管下料问题为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式 4米钢管根数6米钢管根数8米钢管根数 余料(米)14003231013201341203511116030170023钢管下料问题1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小第1页/共11页xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需求满足需求 决策变量决策变量 目标目标1（

2、总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015整数约束：整数约束： xi 为整数为整数第2页/共11页目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 最优解：最优解：x2=12, x5=15, 其余为其余

3、为0；最优值：最优值：27xi 为整数为整数钢管下料(问题1) 第3页/共11页以上两个模型均是一般以上两个模型均是一般整数线性规划整数线性规划 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题1 约束条件不变约束条件不变 5023454321xxxxx20326542xxxx152753xxxxi 为整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 第4页/共11页当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）最优解：最优

4、解：x2=15, x5=5, x7=5, 其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx152753xxxxi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，根，余料余料27米米” 相比相比: 钢管下料(问题1) 第5页/共11页钢管下料问题钢管下料问题2 2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增

5、加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量第6页/共11页满足需求满足需求50313212111xrxrxr10323

6、222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整数非线性规划整数非线性规划钢管下料问题钢管下料问题2 2目标函数目标函数（总根数）总根数）321xxxMin约束条件约束条件整数约束：整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数第7页/共11页50313212111xrxrxr10323222121xrxrxr2033323

7、2131xrxrxrxrxr1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr目标函数（目标函数（总根数）总根数）321xxxMinxi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数钢管下料钢管下料( (问题问题2)2)第8页/共11页增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：2619158206105504特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需

8、10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：313126321xxx模式排列顺序可任定需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米钢管下料钢管下料( (问题问题2)2)第9页/共11页Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000

9、R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和