大学论文电气工程与自动化专业数学建模方法与应用课程论文基于最优理论的钢管下料问题

1、XX 大大 学学 本科生课程论文本科生课程论文 论文题目：论文题目： 基于最优理论的钢管下料问题基于最优理论的钢管下料问题 学学 院：院： 珠海学院珠海学院 学学 系：系： 电气自动化研究所电气自动化研究所 专专 业：业： 电气工程及其自动化电气工程及其自动化 课程名称：课程名称： 数学建模方法及应用数学建模方法及应用 学生姓名：学生姓名： 学学 号：号： 指导教师：指导教师： 2010 年年 6 月月 23 日日 基于最优化理论的钢管下料问题基于最优化理论的钢管下料问题 摘要摘要 本题求解的是钢管下料问题，是一个整数线性规划的优化模型。 问题（1）求解如何下料最为节省，对于如何为最节省，给出

2、两个目标，一个是 剩余总余料最省，另一个是切割原料钢管总根数最少。对于总余料的定义为：每根钢 管切割后不能再切割出产品的部分及生产出来而没有卖掉的产品。 两个目标虽然不同， 但是最优解中所用的切割模式和切割钢管根数是一样的，因此两个模型具有等价性。 问题（2）求解的是如何下了是总费用最少。总费用包括两个方面的费用：一是 用于购买原料钢管的费用，这部分费用由购买原料钢管总根数决定；二是切割原料钢 管的增加费用。由于切割每根原料钢管的增加费用与原料钢管的价值成正比关系，可 以目标函数转化为钢管根数的函数。根据事实依据增加一些适当的约束条件，使软件 快速和有效地求解。 关键字关键字：钢管下料 优化模

3、型 整数规划 目目 录录 1问题重述问题重述 .4 2问题分析问题分析 .4 2.1.问题一问题一 .4 2.2.问题二问题二.5 3模型假设模型假设 .5 4符号说明符号说明 .6 5模型建立与求解模型建立与求解 .6 5.1.问题一问题一 .6 5.2.问题二问题二 .9 6模型检验及模型检验及评评价价 .11 参考文献参考文献 .11 附录一附录一 .12 附录二附录二 .15 1.问题重述问题重述 某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出. 从钢管厂进货时 得到的原料钢管长度都是 1850mm. 现有一客户需要 15 根 290mm、28 根 315mm、21 根 35

4、0mm 和 30 根 455mm 的钢管.一根原料钢管最多生产 5 根产品. 此外, 为了减少余料浪 费,每种切割模式下的余料浪费不能超过 100mm. （1）应如何下料最节省？ （2）为了简化生产过程, 规定所使用的切割模式的种类不能超过 4 种, 使用频率 最高的一种切割模式按照每切割一根原料钢管价值的 1/10 增加费用, 使用频率次之的 切割模式按照一根原料钢管价值的 2/10 增加费用, 依此类推。为了使总费用最小, 应 如何下料? 2、问题分析、问题分析 2.1 问题（问题（1） 要确定如何下了最为节省，首先要确定哪些切割模式是可行的。所谓一个切割模 式，是指按照客户的需要在原料钢

5、管上安排切割的一种组合。显然，可行的切割模式 是很多的。 然而，哪些切割模式是可行的呢？例如如果我们将一根 1850mm 的原料钢管切下 5 根 290mm 规格的钢管，余料为 400mm，还可以切割出一根 299mm、315mm 或着 350mm 规格的钢管，但是产品根数为 6 根，不符合题目中的条件，如果余料不再切割，那就 造成了很大的浪费。 按照题目的要求，即每根原料钢管生产的产品不能超过五根，并且每种切割模式 的余料不能超过 100mm，合理可行的切割模式一共有 11 种，如表 2-1 所示， 表 2-1 290mm 钢管 数 315mm 钢管 数 350mm 钢管 数 455mm 钢

6、管 数余料(mm) 模式1 300270 模式2 210245 模式3 201210 模式4 120220 模式5 112190 模式6 103155 模式7 0311100 模式8 022165 模式9 013130 模式10 0050100 模式11 000430 问题化为在满足客户需要的条件下，按照哪几种合理的模式切割多少根原料钢管， 最为节省。而所谓节省，给定两种标准：一是切割后剩余的总余料量最小，而是切割 原料钢管的总根数最少。 2.2 问题（问题（2） 总费用包括两方面的费用，一是用于购买原料钢管的费用，这部分费用由购买原 料钢管总根数决定，由于假定购买的原料钢管都用于切割，所以切

7、割的原料钢管总根 数越少，费用越少。二是切割原料钢管的增加费用。由于切割每根原料钢管的增加费 用与原料钢管的价值成正比关系，可以目标函数转化为钢管根数的函数。例如，设每 根钢管的价值为一个单位，则按照使用频率最高的模式切割一根钢管的费用为 1/10 单 位，按照次之使用频率的模式切割一根钢管的费用为 2/10 单位，以此类推，由此可以 给出总费用的目标函数。 按照问题（1）的思路，可以通过枚举法首先确定那些切割模式是可行的。但是， 由于按每种使用频率不同的模式切割单位钢管的增加费用是不同的，所以还要考虑各 种模式使用频率的排列情况，枚举法的工作量就非常大了。因此必须寻找另外的方法。 另外，由于

8、存在着切割原料钢管的增加费用，所以，切割原料钢管最少的方案不 一定使总费用最少。 3、模型假设、模型假设 1.料钢管的费用及切割原料钢管的增加费用之和，不涉及其它的费用如工人工资、 设备损耗费、原料钢管及产品的存储费用，或者认为这些费用已经包含在切割原料钢 管的增加费用之中了。 2.钢管切割的损耗忽略不计。 3.所有被切割的原料钢管都能成功地被切割出期待的产品。 4.所有购买的钢管都能被用于生产。 5.如果生产出来的产品数超过客户的需求，超出的部分的产品认为是被浪费了。 4、符号说明、符号说明 1. 1 Z：切割后剩余的总余料量。 2. i M2：按照第i种模式切割原料钢管的增加费用。 3.

9、i x ：按照第i种模式（i=1，2，3，4， ）切割的原料钢管根数，显然它们 应当是非负整数。 4. i r 1 ：按照第i种切割模式下每根原料钢管生产 290mm 钢管数量。 5. i r2 ：按照第i种切割模式下每根原料钢管生产 315mm 钢管数量。 6. i r3 ：按照第i种切割模式下每根原料钢管生产 350mm 钢管数量。 7. i r4 ：按照第i种切割模式下每根原料钢管生产 455mm 钢管数量。 5、模型建立与求解求解、模型建立与求解求解 5.1 问题（问题（1） 模型建立模型建立 决策变量决策变量 用 i x 表示按照第i种模式（i=1，2，3，4， ）切割的原料钢 管根

10、数，显然它们应当是非负整数。 决策目标决策目标 目标一：以切割后剩余的总余料量最小为目标，则由表 2-1 有 Min 1 Z=70 x1+45x2+10 x3+20 x4+90 x5+55x6+100 x7+65x8+30 x9+100 x10+30 x11 目标二：以切割原料钢管的总根数最少为目标，则有 Min 1 Z= x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11 约束条件约束条件 它们的约束条件相同，按照表2-1，约束条件如下： 3x1+2x2+2x3+x4+x5+x615 x2+2x4+x5+3x7+2x8+x928 x3+2x5+3x6+x7+2x8+3x9+

11、5x1021 2x1+2x2+2x3+2x4+x5+x6+x7+x8+x9+4x1130 模型求解模型求解 1.将目标一和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如 下： Objective value: 430.0000 Extended solver steps: 0 Total solver iterations: 6 Variable Value Reduced Cost X1 0.000000 70.00000 X2 0.000000 45.00000 X3 3.000000 10.00000 X4 11.00000 20.00000 X5 0.000000 90

12、.00000 X6 0.000000 55.00000 X7 0.000000 100.0000 X8 0.000000 65.00000 X9 6.000000 30.00000 X10 0.000000 100.0000 X11 0.000000 30.00000 按照模式3切割3根原料钢管，按照模式4切割11根原料钢管，按照模式9切割6根 原料钢管，总共切割20根，总余料最少，为430mm. 2.将目标二和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如 下： Objective value: 19.00000 Extended solver steps: 0 Total

13、solver iterations: 7 Variable Value Reduced Cost X1 0.000000 1.000000 X2 0.000000 1.000000 X3 1.000000 1.000000 X4 13.00000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 1.000000 X8 0.000000 1.000000 X9 2.000000 1.000000 X10 3.000000 1.000000 X11 0.000000 1.000000 按照模式割1根原料钢管，按模式4切割

14、13原料钢管，按照模式9切割2原料钢管， 按照模式10切割3根原料钢管，可是切割原料钢管总根数最少，为19根 分别以总余料最小和切割原料钢管总根数最少为目标的线性规划得出的结果存在 相差，两者之中必定只有一种是最为节省的方案。通过观察约束条件，可以发现，每 种规格的钢管的生产数量没有设定上界，即每种规格钢管的实际生产数量都有可能超 过客户的需求，那么，超出客户需求的产品也应该认为是余料。因此，目标一的目标 应该改写为： Min 1 Z=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+290(3x1+2x2+2x3+x4+x5+x6 -15)+315(x2+2x4+x5+3

15、x7+2x8+x9-28)+350(x3+2x5+3x6+x7+2x8+3x9+5x10-21) +455(2x1+2x2+2x3+2x4+x5+x6+x7+x8+x9+4x11-30) 将修改后目标一和约束条件构成的整数线性规划模型输入 lingo 求解，得到最优解 如下： Objective value: 980.0000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost X1 0.000000 1850.000 X2 0.000000 1850.000 X3 1.000000 1

16、850.000 X4 13.00000 1850.000 X5 0.000000 1850.000 X6 0.000000 1850.000 X7 0.000000 1850.000 X8 0.000000 1850.000 X9 2.000000 1850.000 X10 3.000000 1850.000 X11 0.000000 1850.000 修改目标一后最优解为按照模式割1根原料钢管，按模式4切割13原料钢管，按照模 式9切割2原料钢管，按照模式10切割3根原料钢管，实际总余料料最小（包括多生产的 产品），为980mm，切割原料钢管总数为19根。 通过对比修改后的目标一和目标二最优

17、解的方案，可以发现它们是一样的。事实上， 这两种方法在本质上是一致的，因为目标二中，切割的原料钢管最少，剩下的是余料， 客户需求量是固定的，实际的总余料也就最少。 5.25.2问题（问题（2 2） 模型建立模型建立 由于切割模式的种类不能超过4种，可以用 i x 表示按照第i种模式 （i=1，2，3，4）切割的原料钢管根数，它们是非负整数。设所使用的第i种切割模 式下每根原料钢管生产290mm，315mm，350mm和455mm钢管数量分别为 i r 1 ， i r2 ， i r3 ， i r4 ，它们为非负整数。 决策目标决策目标 总费用最少，假设x1x2x3, 这对问题没有影响目标为 mi

18、n=1.1x1+1.2x2+1.3x3+1.4x4 约束条件约束条件 为满足客户的条件，应有 r11x1+r12x2+r1x3+r14x15 r21x1+r22x2+r23x3+r24x428 r31x1+r32x2+r33x3+r34x421 r41x1+r42x2+r43x3+r44x430 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不超过 1850mm， 也不能少于 1750mm（余料不大于 100mm） ，于是 1750290r11+315r21+350r31+455r411850 1750290r12+315r22+350r32+455r421850 1750290r13

19、+315r23+350r33+455r431850 1750290r14+315r24+350r34+455r441850 每种切割模式下每根原料钢管生产的产品数不能超过 5 根，于是 r11+r21+r31+r415 r12+r22+r32+r425 r13+r23+r33+r435 r14+r24+r34+r445 并且 x1x2x3 模型求解模型求解 实际上，上边的约束条件确定的范围是很大的，用 LINGO 求解要很长的时间，因 此需要加上一些显然的约束条件，从而缩小可行解的范围。 由于原料钢管不可能少于(29015+31528+35021+45530)/1850=18.5 根， 于是得

20、到了钢管根数的下界。可以增加约束条件 x1+x2+x319 将目标函数和约束条件构成的整数线性规划模型输入 lingo 求解，得到最优解如 下： Objective value: 21.50000 Extended solver steps: 267 Total solver iterations: 16069 Variable Value Reduced Cost X1 14.00000 -0.1000000 X2 4.000000 0.000000 X3 1.000000 0.1000000 X4 0.000000 0.2000000 R11 1.000000 0.000000 R12 0

21、.000000 0.000000 R13 2.000000 0.000000 R14 4.000000 0.000000 R21 2.000000 0.000000 R22 0.000000 0.000000 R23 0.000000 0.000000 R24 0.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.0000

22、00 R44 1.000000 0.000000 即按照模式 1，2，3 分别切割 14，4，1 根原料钢管，使用原料钢管总根数 19 根 第一种切割模式下一根原料钢管切割成 1 根 290mm 规格钢管、2 根 315mm 规格钢管和 2 根 455mm 规格钢管；第二种切割模式下一根原料钢管切割成 5 根 350mm 规格钢管；第 三种切割模式下一根原料钢管切割成 2 根 290mm 钢管、1 根 350mm 规格钢管和 2 根 455mm 规格钢管。这样的方案使总费用最少，为 21.5 根钢管的价值。 6 6、模型检验及评价、模型检验及评价。 问题（1）需要求的是如何下料最省，从两个不同

23、的目标出发，建立不同的模型， 最后求出最优解，从最优解中可知两者切割模式和计划是相同的，由此得出两者虽然 目标不同，本质上是相同的，并且说明了模型的正确性。 问题（2）需要求的是如何下料使总费用最少，模型通过把目标函数转化为切割 原料钢管总根数函数，方便了求解。同时，为了不使因为求解范围过大而使求解时间 过长或无法求解，从一些明显的事实中，增加了一些适当的约束条件，从而是求解的 时间大大缩短，快速地求出结果。 运用 lingo 软件，使得解决模型简单，明了。 参考文献参考文献 1赵静，但琦主编.数学建模与数学实验J：第三版.北京：高等教育出版社， 2008，37-112 2杜宇.优化数学模型及

24、 LINGO 软件求解J.黔西南民族师范高等专科学校学报， 2008（3）：111-114 3韩中庚，姜启源，陈中月.奶制品加工计划的设计模型J.信息工程大学学报, 2002,3(1):40-42 4谢金星，薛毅.优化模型与 LINDO/LINGO 软件M.北京：清华大学出版社， 2005.166-190 5张杰.建立数学模型解决钢管下料问题M.山西建能，2009，35（35）：146-147 附录一附录一 问题（1）模型 目标一 min=70*x1+45*x2+10*x3+20*x4+90*x5+55*x6+100*x7+65*x8+30*x9+100*x10+30*x11+2 90*(3*

25、x1+2*x2+2*x3+x4+x5+x6-15)+315*(x2+2*x4+x5+3*x7+2*x8+x9- 28)+350*(x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10- 21)+455*(2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11-30); 3*x1+2*x2+2*x3+x4+x5+x6=15; x2+2*x4+x5+3*x7+2*x8+x9=28; x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10=21; 2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11=30; gin(x1); g

26、in(x2); gin(x3); gin(x4); gin(x5); gin(x6); gin(x7); gin(x8); gin(x9); gin(x10); gin(x11); 最优解 Global optimal solution found. Objective value: 980.0000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost X1 0.000000 1850.000 X2 0.000000 1850.000 X3 1.000000 1850.000 X4 13

27、.00000 1850.000 X5 0.000000 1850.000 X6 0.000000 1850.000 X7 0.000000 1850.000 X8 0.000000 1850.000 X9 2.000000 1850.000 X10 3.000000 1850.000 X11 0.000000 1850.000 Row Slack or Surplus Dual Price 1 980.0000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 1.000000 0.000000 5 0.000000 0.000000 目标

28、二 min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11; 3*x1+2*x2+2*x3+x4+x5+x6=15; x2+2*x4+x5+3*x7+2*x8+x9=28; x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10=21; 2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11=30; gin(x1); gin(x2); gin(x3); gin(x4); gin(x5); gin(x6); gin(x7); gin(x8); gin(x9); gin(x10); gin(x11); 最优解 Global optimal s

29、olution found. Objective value: 19.00000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost X1 0.000000 1.000000 X2 0.000000 1.000000 X3 1.000000 1.000000 X4 13.00000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 1.000000 X8 0.000000 1.000000 X9 2.000000

30、 1.000000 X10 3.000000 1.000000 X11 0.000000 1.000000 Row Slack or Surplus Dual Price 1 19.00000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 1.000000 0.000000 5 0.000000 0.000000 附录二附录二 问题（2）模型 min=1.1*x1+1.2*x2+1.3*x3+1.4*x4; r11*x1+r12*x2+r13*x3+r14*x4=15; r21*x1+r22*x2+r23*x3+r24*x4=28; r

31、31*x1+r32*x2+r33*x3+r34*x4=21; r41*x1+r42*x2+r43*x3+r44*x4=30; 290*r11+315*r21+350*r31+455*r41=1850; 290*r12+315*r22+350*r32+455*r42=1850; 290*r13+315*r23+350*r33+455*r43=1850; 290*r14+315*r24+350*r34+455*r44=1750; 290*r12+315*r22+350*r32+455*r42=1750; 290*r13+315*r23+350*r33+455*r43=1750; 290*r14+3

32、15*r24+350*r34+455*r44=1750; x1+x2+x3+x4=19; x1x2; x2x3; x3x4; r11+r21+r31+r41=5; r12+r22+r32+r42=5; r13+r23+r33+r43=5; r14+r24+r34+r44=5; gin(x1); gin(x2); gin(x3); gin(x4); gin(r11); gin(r21); gin(r31); gin(r41); gin(r12); gin(r22); gin(r32); gin(r42); gin(r13); gin(r23); gin(r33); gin(r43); gin(r14); gin(r24); gin