下载文档原格式
-1-目第一章录绪论 …………………………………………...3第二章 下料问题的线性规划模型2.1 线性规划理论 ……………………. ………4 2.2 线性规划问题的一般数学模型………………...52.3 整数规划问题及其一般解法…………….6第三章 模拟退火算法 3.1 3.2 3.3 3.4 3.5 3.6 参考文献 物理学中的模拟退火………………….…8 米特罗波利斯准则………………….……9 优化问题中的模拟退火算法…….………10 冷却进度表……………………………….16 模拟退火算法应用的要求……………….21 实例分析………………………………….22-2-第一章 绪 论唐山铁路道岔厂位于中国北方重工业城市--唐山，它北依燕山，南临渤海， 毗邻京、津两地，与京唐港咫尺相望，海陆交通便利，地理位置优越。
工厂始 建于 1988 年，是铁道部特别许可生产道岔系列品的专业工厂，厂区占地 12 万平 方米，建筑面积 1.2 万平方米，总资产超亿元，现有职工 500 余人，其中各类高、 中级专业技术人员百余人。
工厂工艺装备先进，检测手段齐全，技术力量雄厚具 备年产高锰钢辙叉 8000 根，整组道岔 2000 组的生产能力。
主要生产各种规格型 号的铁路普通辙叉、机加工辙叉、整组道岔，铁路提速辙叉、道岔及其零配件。
工厂坚持"依靠科技进步，严格质量控制，生产优质产品，满足用户需求" 的质 量方针，严格按照 ISO9000 标准建立了完善的质量保证体系，并于 1999 年 12 月通过了 ISO9002 质量体系认证，产品先后荣获"市优"、"省优"称号，遍布全国 14 个铁路局，地方、地下铁路和大厂企，市场覆盖 28 个省、市、自治区。
产品 不仅满足国内市场，还远销东南亚等国家。
工厂是唐山市"重合同，守信用企业 "、"文明单位"、"五十强企业"、"优秀企业"、河北省"百强企业"，被中国企业形 象认定委员会确认为"中国企业形象最佳单位"。
一、问题陈说二、(下料问题)某工厂要做150套钢架, 每套钢架分别需要长度为 2.5米、2.6米和1.9米旳圆钢各一套。
已知原料每根长10米, 问应怎样下料, 可使所用原料最省？三、问题分析该问题是运筹学在实际运用中比较经典旳“线材下料问题”, 从第一部分问题陈说中可以看出, 该问题旳一般提法是, 要做N套产品, 需要用规格不一样旳M种线材, 多种规格旳长度分别为l1, l2, l3, ..., lm, 每一套产品需要不一样规格旳原料分别为m1, m2, m3, ..., mm根, 已知原材料旳长度为一定旳长度, 问应当怎样下料, 从而使原材料旳耗用最省。
四、因此, 在处理此类问题时应分两步考虑：1、确定可行旳切割模式：即按照客户需要在原材料钢材上安排切割旳一种组合；2、确定合理旳切割模式：合理旳切割模式旳预料不应当不小于或等于客户需要旳钢材旳最小尺寸。
五、对于如上第一分部提出旳线材下料问题, 可以用运筹学中线性规划旳措施求解, 通过建立线性规划模型来详细分析。
六、模型建立建立线性规划模型时, 对于约束条件这里为切割要满足客户对钢材数量旳最低规定, 本题将对原则钢材旳切割（2.5米、2.6米、1.9米）, 从而组合成一套钢架, 规定为150套等原因建立约束条件。
不过, 对于目旳函数而言, 会有这样两种状况: 1.求旳钢材原材料总根数至少；2.求旳钢材原材料余料至少。
在本文旳分析中, 我们选择前者, 即: 求解使用旳钢材原材料总根数至少。
为了建立模型以便, 我们把下料后余下旳不不小于最短用料旳钢材称为废弃钢材, 把下料得到旳长为2.5m, 2.6m, 1.9m旳钢材称为规格钢材, 把10米长旳原材料钢材称为原钢。
因此, 所用旳原钢可以分解成三部分：1、成套运用旳规格钢材；2、剩余旳规格钢材；3、废弃钢材。
通过度析计算, 可以得到原钢旳11种下料方式如下：X1X2X3X4X5X6X7X8X9X10X11表1:一条原料钢材旳11种切法1.9m 0 1 1 2 1 3 2 1 2 3 5 Sum 10 9.4 9.5 8.8 9.6 8.2 8.9 9.7 9 8.3 9.5我们设决策变量: 采用第i种下料方式旳有xi根原钢, i=1,2,3,...,11.此外设置辅助变量: 剩余2.5米旳规格钢材为y1根, 剩余旳2.6米规格钢材为y2根, 剩余旳1.9米规格钢材为y3根。
优化线材下料方案编制人：审核人：审批人：年月日目录1、编制依据................................................................................................ 错误!未定义书签。
2、工程概况................................................................................................ 错误!未定义书签。
2.1工程基本概况___________________________________________________________ 错误!未定义书签。
2.2建筑设计概况___________________________________________________________ 错误!未定义书签。
3、基础设计及要求.................................................................................... 错误!未定义书签。
3.1基础设计 _______________________________________________________________________________ 8 3.2基础的确定 _____________________________________________________________ 错误!未定义书签。
3.3基础的验收要求_________________________________________________________ 错误!未定义书签。
3.4防雷接地 _______________________________________________________________ 错误!未定义书签。
线性规划问题的基本概念及求解方法线性规划是一种优化方法，用于找到一个线性方程的最大或最小值，同时满足一组线性约束条件。
线性规划问题广泛应用于经济、工业、运输、物流等各个领域。
本文将讲述线性规划问题的基本概念和求解方法。
一、线性规划的基本概念线性规划问题可表示为：$\max_{x} z = c^Tx$$\text{s.t.} \qquad Ax \leq b$其中，x表示决策变量，z表示目标函数，c和b为常数系数，A为系数矩阵。
目标函数表示要最大化或最小化的数量，约束条件表示限制决策变量取值的条件。
二、线性规划的求解方法线性规划问题的求解方法有两种，即图形法和单纯形法。
1. 图形法图形法是一种用图形的方式来求解线性规划问题的方法。
它可以用于二元线性规划问题求解，但对于多元线性规划问题，它的应用受到了限制。
对于二元线性规划问题，我们可以将目标函数表示为直线，约束条件表示为线段，然后在可行域内寻找能让目标函数最大或最小的点。
2. 单纯形法单纯形法是一种通过交换决策变量的取值来寻找最优解的方法。
它通过构建初始单纯形表格，逐步利用高斯消元法将问题转化为标准型，然后不断交换基变量和非基变量，直到找到最优解。
单纯形法在求解多元线性规划问题时具有广泛的应用，因为它能够较快地寻找最优解。
但是，它也存在一些问题，例如当问题的维度较高时，算法的计算复杂度会相应增加，计算机的处理能力也会受到限制。
三、线性规划的应用线性规划在各个领域中都有着广泛的应用。
以下是一些典型的应用案例：1. 运输问题运输问题是一种线性规划问题，旨在确定一组产品从生产场所运往销售场所的最优方案。
这种问题通常涉及到对物流成本、物流时间等多种因素的优化。
2. 设备维护问题设备维护问题是一种线性规划问题，旨在通过优化设备的维护策略来最大化设备的使用寿命和效益。
这种问题通常涉及到对机器的使用寿命、维修成本、机器停机时间等多种因素的优化。
3. 生产计划问题生产计划问题是一种线性规划问题，旨在通过对原材料和生产线的安排来优化产品的生产过程。
一、问题陈述(下料问题)某工厂要做150套钢架，每套钢架分别需要长度为2.5米、2.6米和1.9米的圆钢各一套。
已知原料每根长10米，问应如何下料，可使所用原料最省？二、问题分析该问题是运筹学在实际运用中比较经典的“线材下料问题”，从第一部分问题陈述中可以看出，该问题的一般提法是，要做N套产品，需要用规格不同的M种线材，各种规格的长度分别为l1，l2，l3，...，l m，每一套产品需要不同规格的原料分别为m1，m 2，m3，...，m m根，已知原材料的长度为一定的长度，问应该如何下料，从而使原材料的耗用最省。
因此，在解决此类问题时应分两步考虑：1、确定可行的切割模式：即按照客户需要在原材料钢材上安排切割的一种组合；2、确定合理的切割模式：合理的切割模式的预料不应该大于或等于客户需要的钢材的最小尺寸。
对于如上第一分部提出的线材下料问题，可以用运筹学中线性规划的方法求解，通过建立线性规划模型来具体分析。
三、模型建立建立线性规划模型时，对于约束条件这里为切割要满足客户对钢材数量的最低要求，本题将对标准钢材的切割（2.5米、2.6米、1.9米），从而组合成一套钢架，要求为150套等因素建立约束条件。
但是，对于目标函数而言，会有这样两种情况：1、求的钢材原材料总根数最少；2、求的钢材原材料余料最少。
在本文的分析中，我们选择前者，即：求解使用的钢材原材料总根数最少。
为了建立模型方便，我们把下料后余下的小于最短用料的钢材称为废弃钢材，把下料得到的长为2.5m，2.6m，1.9m的钢材称为规格钢材，把10米长的原材料钢材称为原钢。
因此，所用的原钢可以分解成三部分：1、成套利用的规格钢材；2、剩余的规格钢材；3、废弃钢材。
通过分析计算，可以得到原钢的11种下料方式如下：表1：一条原料钢材的11种切法X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 X 112.6m 0 0 1 0 2 0 1 3 2 1 0 1.9m 0 1 1 2 1 3 2 1 2 3 5 Sum109.4 9.5 8.8 9.6 8.2 8.9 9.7 9 8.3 9.5我们设决策变量：采取第i 种下料方式的有x i 根原钢，i=1,2,3,...,11.另外设置辅助变量：剩余2.5米的规格钢材为y 1根，剩余的2.6米规格钢材为y 2根，剩余的1.9米规格钢材为y 3根。
因此得到模型一：模型一：剩余的规格钢材当作废弃钢材的情况Min Z=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8+1*x9+1.7*x10+0.5*x11+2.5*y1+2.6*y2+1.9*y3 (1)4*x1+3*x2+2*x3+2*x4+x5+x6+x7-y1=150 s.t. x3+2*x5+x7+3*x8+2*x9+x10-y2=150x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11-y3=150 i >=0, y j >=0,且为整数i=1,2,3...11,j=1,2,3 (2) ∑==111i ixMinZ (3)由（1）、（2）组成的是求废弃钢材最少的整数线性规划模型。
同时，很容易联想到另一个模型，是由（2）、（3）组成的求所用原料钢材最少的整数线性规划模型。
模型二：剩余的规格钢材（可同原钢一样可以再利用），不当作废弃钢材的情况Min Z=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8+1*x9+1.7*x10+0.5*x11 (4)4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150s.t. x3+2*x5+x7+3*x8+2*x9+x10>=150 (5) x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150 x i >=0, i=1,2,3 (11)由（4）、（5）组成的是求废弃钢材最少的整数线性规划模型具有一定的实际意义，特别是当最短的规格钢材长度较长时，剩余的规格钢材就可以再次被利用。
在此，我们应该注意到，由（3）、（5）组成的整数线性规划模型就是模型一。
由于在建立模型一和模型二的时候，考虑了剩余规格钢材的不同处理情况，使这个问题变得清晰了，所得到的模型也比较全面，基本没有漏洞和缺陷，并且比较容易在这些基础上修改或添加一些其它的约束条件（比如：各种规格钢材下料成套时的不同比例等等），所以，我们建立的线材下料问题的模型是可行的。
基于以上的分析，我们选择（3）、（5）组合而成的模型和（4）、（5）组合而成的模型进行具体求解，从而求出组合出150套圆钢所需要的最少原料钢材。
求解模型：∑==111i ix MinZ （3）4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150s.t. x3+2*x5+x7+3*x8+2*x9+x10>=150 （5） x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150x i >=0, i=1,2,3 (11)此模型是设定最小使用原料钢材的条数为目标值进行求解。
Min Z=0*x1+0.6*x2+0.5*x3+1.2*x4+0.4*x5+1.8*x6+1.1*x7+0.3*x8+1*x9+1.7*x10+0.5*x11 (4)4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=150s.t. x3+2*x5+x7+3*x8+2*x9+x10>=150 (5)x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150x i>=0, i=1,2,3 (11)此模型时设定最小废弃钢材为目标值进行求解。
四、方法选择指导思路：线性规划求解思路选择方法：Excel规划求解使用工具：Excel工具五、求解过程1、框架建立2、模式调整3、计算原料钢材使用及剩余钢材4、设置目标函数及变量Ⅰ、以模型（3）、（5）组合而成的求解模型设定的目标值。
说明：目标函数单元格D9即为我们所求的最少使用原料钢材条数。
其具体在excel 中的操作为D9=C12+D12+E12+F12+G12+H12+I12+J12+K12+L12+M12.Ⅱ、以模型（4）、（5）组合而成的求解模型设定的目标值。
说明：目标函数单元格D9即为我们所求最少剩余的废弃钢材。
其具体在excel中的操作为:D9=C7*B12+D7*C12+E7*D12+F7*E12+G7*F12+H7*G12+I7*H12+J7*I12+K7*J12 +L7*K12+M7*L125、设置约束条件说明：约束条件单元格C15、C16、C17分别为规格钢材2.6m、2.5m、1.9m所求的最少使用条数。
其中：C15=C12*4+D12*3+E12*2+F12*2+G12+H12+I12;C16=E12+G12*2+I12+J12*3+K12*2+L12;C17=D12+E12+F12*2+G12+H12*3+I12*2+J12+K12*2+L12*3+M12*5;6、利用规划求解工具Excel :工具- 规划求解- 依次输入目标单元格、可变单元格、约束条件进行求解。
其中，点击规划求解参数选项框右边的选项按钮，在弹出的选项框中选中采用线性模型和假定非负。
求解结果如下图：Ⅰ、以模型（3）、（5）组合而成的求解模型求解结果。
从上表可以直接得出：最小原料钢材使用条数为108条。
但实际的使用情况为107.5条，多切割出来的0.5条（（152-150）*2.5）米）。
Ⅱ、以模型（4）、（5）组合而成的求解模型设定的目标值。
从上表可以直接看得，最小剩余废弃钢材为25米。
但实际的剩余废弃钢材为30米（（152-150）*2.5+25）。
六、答案分析由上图可知，按照模式1切38条原料钢材，按照模式8切原料钢材50条，按照模式11切原料钢材20条，从而可以得到：2.6米规格钢材152（38*4）条，2.5米规格钢材150（50*3）条，1.9米规格钢材150（50*1+20*20）条。
同时，可以从得出来的数据算出剩余的废弃钢材为30米，其中包含多切割出的2条2.5米规格钢材共5米，按照模式8切割的剩余废弃钢材15米（0.3*50）以及按照模式11切割的剩余废弃钢材10米（0.5*20）。
通过分别设置目标值为最小使用原料钢材的使用条数和最小剩余废弃钢材的计算，我们得出相同的结果，即切割2.5米规格钢材152条，2.6米规格钢材150条以及1.9米规格钢材150条，同时剩余废弃钢材为30米，使用原料钢材108条。
但是，对不同目标值设定就一定是会得出相同的结果吗？在这里，我们引出另一种情况来进行对比分析。
如题：某工厂要做100套钢架，每套钢架需要长度分别为2.9米，2.1米和1.5米的圆钢各一根。
已知原料每根长7.4米，问应该如何下料，可以使所用原料最省？在这我们利用之前的分析，分别设定最小使用原料条数和最小剩余材料为目标值进行模型建立，如下：X1 X2 X3 X4 X52.1米0 0 2 2 11.5米 3 1 2 0 3余料0 0.1 0.2 0.3 0.8 设定最小使用原料条数为目标值模型：Min Z=x1+x2+x3+x4+x5x1+2*x2+x4>=1002*x3+2*x4+x5>=1003*x1+x2+2*x3+3*x5>=100xi>=0(i=1,2,...5)设定最小余料为目标值模型：Min Z=0*x1+0.1*x2+0.2*x3+0.3*x4+0.8*x5x1+2*x2+x4>=1002*x3+2*x4+x5>=1003*x1+x2+2*x3+3*x5>=100xi>=0(i=1,2,...5)对这两个模型进行求解，有：最小余料为目标值模型解：最小原料使用条数为目标值模型解：由以上两种模型解答可知：在以最小余料为目标值进行求解的时候，得出的原料使用条数为150条，而以最小原料使用条数为目标值进行求解的时候，得出的原料使用的条数为90条。
综合两道题目的比较，可知，两种类型的模型设定是会得到不同的解答。
因此，在不保证未来多余规格材料是否有用的时候，这就可能会造成原料更大的浪费，所以，对此类问题的求解，应多采用以最小原料使用条数为目标值的模型进行求解。
七、总结通过上面的分析推导，对于线材下料的线性规划模型，目标函数就可以简化为两种明确的情况来考虑，当我们的下料问题是一次行为时，直接求原料钢材总根数最少，而当我们下料问题是多次行为，每次的问题需求各种规格钢材的长度是不变的，并且下料模式中没有余料为零的情况下，才可能考虑使用设置余料最小的模型进行求解。
