安徽工程大学安徽工程大学 数学建模数学建模 课程设计论文课程设计论文 姓姓 名名: :匡泽仁匡泽仁 专专 业业: :数学与应用数学数学与应用数学 班班 级级: :数学数学 112112 学学 号号: : 指导老师：邓寿年指导老师：邓寿年 完成日期：完成日期：2013.5.262013.5.26 - 1 - 摘要摘要 在很多工程领域，都有线材切割问题。现假设某装修工程中需 要对铝合金线材进行切割，工程能购买到的同一规格的铝合金线材 有二种长度，一种长度是 8 米，另一种是 12 米。这是个使材料利用率最 大化问题，已知可以购买 8 米和 12 米两种不同长度的铝合金线材， 对所需要的长度进行分析，确定需要 8 米和 12 米两种不同长度的铝 合金线材各是多少。 解决这个问题主要运用线性规划和非线性规划的知识；掌握线 性规划建模的方法和过程，体会线性规划建模的核心思想；掌握线 性规划问题的求解方法；掌握用 MATLAB 或 LINDD 求解线性规划 问题基本方法和步骤，学会分析 MATLAB 或 LINDD 的计算结果； 锻炼应用所学知识解决综合性问题的能力。 因为要求得最少的原材料根数，考虑到“全部用完，没有剩余” 的原则，首先将切割后没有剩余的情况全部列出，利用 lindo 软件 求出最优结果。 计算结果使用长度为 8 米的根数为 0 ，使用长度为 12 米的根数 为 237 ，满足实际要求，并且材料利用率为 100%。 最后针对该模型对方案的结果进行了分析，对模型做出了评价。 关键词关键词：线材切割 最优解 线性规划 - 2 - 目录 一、一、问题重述与分析问题重述与分析 3 3 1-1 提出问题 3 3 1-2 问题分析 4 4 二、模型假设二、模型假设 4 4 三、符号说明三、符号说明 5 5 四、模型建立与求解四、模型建立与求解 5 5 五、结果分析与检验五、结果分析与检验 7 7 六、模型评价六、模型评价 9 9 参考文献参考文献 1010 附录附录 1111 - 3 - 一一 问题重述与分析问题重述与分析 1-11-1 提出问题提出问题 在很多工程领域，都有线材切割问题。这一问题可表述为: 设能购买到的不同长度的原线材有 m 种，长度分别为 L1,.,Lm，这些原 线材只是长度不同，其它都相同。某工程中所要切割出的线材长度分别为 li,i =1,2,.,n(这里 li =90 所要截取长度为3.6米的线材为 120 根，因此有约束条件为： X2+2X7+X8+2X10=120 所要截取长度为2.8米的线材为 136 根，因此有约束条件为： 3X2+X3+2X4+X5+X6+2X11=136 所要截取长度为1.85米的线材为 310 根，因此有约束条件为： 5X1+X4+2X5+2X7+4X9=310 所要截取长度为0.75米的线材为 215 根，因此有约束条件为： 4X3+2X5+4X6+X9+2X10+X11+7X12+16X13=215 所要截取长度为0.55米的线材为 320 根，因此有约束条件为： 5X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12=320 由以上分析可知： 目标函数为： MINZ=X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13 约束条件为： X3+X8+X12=90 X2+2X7+X8+2X10=120 3X2+X3+2X4+X5+X6+2X11=136 5X1+X4+2X5+2X7+4X9=310 4X3+2X5+4X6+X9+2X10+X11+7X12+16X13=215 5X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12=320 X1、X2X13 为非负整数 - 7 - 五、结果分析与检验五、结果分析与检验 运行结果分析： （1）、本次计算用到 53 次迭代。 （2）、材料浪费率为 0，即材料利用率为 100%。 （3）.、最优解变量： VARIABLE VALUE REDUCED COST X1 62. 0. X2 27. 0. X3 55. 0. X4 0. 0. X5 0. 0. X6 0. 0. X7 0. 0. X8 93. 0. X9 0. 0. X10 0. 0. X11 0. 0. X12 0. 0. X13 0. 0. 第二列，即“VALUE”给出最优解中各变量(VARIABLE)的值: X1 = 62.； X2=27.; X3=55.; X8=93.; X4=X5=X6=X7=X9=X10=X11=X12=X13=0 第三列，即“REDUCED COST” 给出最优单纯形表中第 0 行中变量的系数 . 其中基变量的 reduced cost 值应为 0，对于非基变量, 相应的 reduced cost 值表 示当该非基变量增加一个单位时目标函数减少的量。本例中此值均为 0。 （4）、分析结果的下半部分： ROW SLACK OR SURPLUS DUAL PRICES - 8 - 2) 58. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 5. 0. 7) 362. 0. 第二列，即“SLACK OR SURPLUS” 给出松驰变量的值: 第 3、4、5 行松 驰变量均为 0, 说明对于最优解来讲，两个约束（第 3、4、5 行）均取等号。 第三列，即“DUAL PRICES” 给出对偶价格的值: 各行对偶价格均为 0.。 （5）、计算结果： 长度为 8 米的根数为：0 长度为 12 米的根数为：62+27+55+93=237 材料利用率为 100%。 - 9 - 六、模型评价六、模型评价 本课程设计采用整数规划，整数线性规划数学模型的一般形式为: 中部分或全部取整数 或或 或 n j n j ijij n j jj xxx njx mibxa ts xcz , , 2 , 10 , 2 , 1),( . . min)max( 21 1 1 1、模型优点： 1）建立的模型能够完全的解决题中的问题，最终得出最优结果简洁明了。 2）建立的模型能与实际问题紧密联系，从实际问题中发现问题并建立一定的 方案试图更好的解决问题。 3）利用 lindo 软件求出最优结果，数据结果真实可靠。 4）对类似的最优化模型的建立有很好的启示作用，推广性强，实用性强。 2、模型的缺点 1）计算结果只显示了最优方案的结果，不能直观的和其它方案做比较。 2）为了使模型不是过于复杂，对实际应用中可能出现的干扰因素进行了必要 的假设，而实际考虑问题时还需要对其他干扰因素进行分析。 3）没有由此推出新的理论或者或着说没有自己的创新。 - 10 - 参考文献参考文献 1赵静，但琦，严尚安，杨秀文，数学建模与数学实验（第三版） ，北京：高 等教育出版社，2007 。 2姜启源，谢金星，叶俊，数学模型（第三版） ，北京：高等教育出版社， 2003 。 3朱道元，数学建模案例精选，北京：科学出版社，2002 。 4江道琪，何建绅，陈松华.实用线性规划方法及其支持系统 整数规划及 其应用模型。 5王高雄，周之铭，朱思铭，王涛松， （第三版） ，高等教育出版社，2007 。 附录附录 程序： MINX1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11 +0X12+0X13 - 11 - ST X3+X8+X12=90 X2+2X7+X8+2X10=120 3X2+X3+2X4+X5+X6+2X11=136 5X1+X4+2X5+2X7+4X9=310 4X3+2X5+4X6+X9+2X10+X11+7X12+16X13=215 5X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12=320 END GIN X1 GIN X2 GIN X3 GIN X4 GIN X5 GIN X6 GIN X7 GIN X8 GIN X9 GIN X10 GIN X11 GIN X12 GIN X13 结果： SET X2 TO = 27 AT 1, BND= 0.0000E+00 TWIN= 0.0000E+00 43 - 12 - SET X11 TO = 0 AT 2, BND= 0.0000E+00 TWIN= 0.0000E+00 45 SET X4 TO = 41 AT 3, BND= 0.0000E+00 TWIN= 0.0000E+00 50 SET X4 TO = 0 AT 4, BND= 0.0000E+00 TWIN= 0.0000E+00 53 NEW INTEGER SOLUTION OF 0.E+00 AT BRANCH 8 PIVOT 53 BOUND ON OPTIMUM: 0.E+00 DELETE X4 AT LEVEL 4 DELETE X4 AT LEVEL 3 DELETE X11 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 8 PIVOTS= 53 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 0.E+00 VARIABLE VALUE REDUCED COST X1 62. 0. - 13 - X2 27. 0. X3 55. 0. X4 0. 0. X5 0. 0. X6 0. 0. X7 0. 0. X8 93. 0. X9 0. 0. X10 0. 0. X11 0. 0. X12 0. 0. X13 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 58. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 5. 0. 7) 362. 0. NO. ITERATIONS= 53 BRANCHES= 8 DETERM.= 1.000E 0