数学建模下料问题

1、整数规划的数学模型Max(Min)(c1 x1+ c2 x2 + cn xn )a11 x1+ a12 x2 + a1n xn (=,) b1a21 x1+ a22 x2 + a2n xn (=,) b2.am1 x1+ am2 x2 + amn xn (=,) bmx1n 0 且取整数纯整数规划: 所有变量都有取整约束混合整数规划: 只有部分变量有取整约束生产中通过切割、剪裁、冲压等生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小手段，将原材料加工成所需大小 钢管和易拉罐下料钢管和易拉罐下料原料下料问题原料下料问题按照工艺要求，确定下料方案，按照工艺要求，确定下料方案，使所用材料最省

2、，或利润最大使所用材料最省，或利润最大问题问题1. 如何下料最节省如何下料最节省 ? 例例1 钢管下料钢管下料 问题问题2. 客户增加需求：客户增加需求：原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式切割模

3、式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)1400

4、3231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14

5、003231013201341203511116030170023需需求求502015最优解：最优解：x2=12, x5=15, 其余为其余为0；最优值：最优值：27。整数约束：整数约束： xi 为整数为整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15, x5=5, x7=5, 其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx152753xxxxi 为整数按模式按

6、模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米” 相比相比 钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定

7、合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量满足需求满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212rrrr19

8、86541643332313rrrr整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）321xxxMin约束约束条件条件整数约束：整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：原料钢管总根数下界： 2619158206105504特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢

9、管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：13+10+8=31 3126321xxx模式排列顺序可任定模式排列顺序可任定 钢管下料问题钢管下料问题2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米LINGO求解整数非线性规划模型求解整数非线性规划模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced

10、 CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.0000

11、00 R43 2.000000 0.000000 模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。板材板材规格规格2：长方形，长方形，32 28cm，2万张。万张。例例2 易拉罐下料易拉罐下料每周工作每周工作40小时，每只易拉罐利润小时，每只易拉罐利润0.10元，原料余料损失元，原料余料

12、损失0.001元元 / cm2（不能装配的罐身、盖、底也是余料）（不能装配的罐身、盖、底也是余料） 模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒模式模式4：3秒秒上盖上盖下底下底罐罐身身罐身高罐身高10cm，上上盖盖、下底直、下底直径均径均5cm。 板材规格板材规格1：正方形，边长正方形，边长24cm，5万张。万张。如何安排每周生产？如何安排每周生产？ 罐身个数罐身个数底、盖底、盖个数个数余料损失余料损失（cm2）冲压时间冲压时间（秒）（秒）模式模式1110222.61.5模式模式224183.32模式模式3016261.81模式模式445169.53模式模式1: 正方形正方形边

13、长边长24cm 问题分析问题分析计算各种模式下的余料损失计算各种模式下的余料损失 上、下底直径上、下底直径d=5cm，罐身高罐身高h=10cm。 模式模式1 余料损失余料损失 242-10 d2/4 - dh=222.6 cm2问题分析问题分析目标目标: :易拉罐利润扣除原料余料损失后的净利润最大易拉罐利润扣除原料余料损失后的净利润最大 约束：约束：每周工作时间不超过每周工作时间不超过40小时；小时； 原料数量：原料数量：规格规格1（模式（模式1 3）5万张，万张， 规格规格2（模式（模式4）2万张；万张； 罐身和底、盖的配套组装罐身和底、盖的配套组装 。注意：不能装配的罐身、上下底也是余料注

14、意：不能装配的罐身、上下底也是余料决策决策变量变量 xi 按照第按照第i 种模式的生产张数种模式的生产张数( (i= =1,2,3,4) )；y1 一周生产的易拉罐个数；一周生产的易拉罐个数；y2 不配套的罐身个数；不配套的罐身个数；y3 不配套的底、盖个数。不配套的底、盖个数。 模型建立模型建立目标目标 约束约束条件条件 )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax时间约束时间约束 144000325 . 14321xxxx原料约束原料约束 ,50000321xxx200004x产量产量余料余料时间时间x1

15、222.61.5x2183.32x3261.81x4169.53模型建立模型建立y1 易拉罐个数；易拉罐个数；y2 不配套的罐身；不配套的罐身；y3 不配套的底、盖。不配套的底、盖。每只易拉罐利润每只易拉罐利润0.10元，元，余料损失余料损失0.001元元 / cm2罐身罐身面积面积 dh=157.1 cm2 底盖底盖面积面积 d2/4=19.6 cm2(40小时小时)约束约束条件条件 配套约束配套约束 2/ )516410(,42min43214211xxxxxxxy1421242yxxxy1432132516410yxxxxy,424211xxxy2/ )516410(43211xxxxy

16、y1 易拉罐个数；易拉罐个数；y2 不配套的罐身；不配套的罐身；y3 不配套的底、盖。不配套的底、盖。罐身罐身底、盖底、盖1102401645产量产量x1x2x3x4虽然虽然xi和和y1，y2，y3应是整数，但是因生产量很大，应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理可以把它们看成实数，从而用线性规划模型处理 。将所有决策变量扩大将所有决策变量扩大10000倍（倍（xi 万张，万张，yi 万件）万件） LINDO发出警告信息：发出警告信息：“数据之间的数量级差别太数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别大，建议进行预处理，缩小数据之间的差别”模式

17、模式2生产生产40125张，张，模式模式3生产生产3750张，张，模式模式4生产生产20000张，张，共产易拉罐共产易拉罐160250个个( (罐身和底、盖无剩余罐身和底、盖无剩余) )，净利润为净利润为4298元元 , 5321xxx24x模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 0.4298337VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 , 4 .143