下料问题的线性规划模型.pdf

- 1 -
目录
第一章绪论…………………………………………...3

第二章下料问题的线性规划模型
线性规划理论……………………. ………4
线性规划问题的一般数学模型………………...5
整数规划问题及其一般解法…………….6

第三章模拟退火算法
物理学中的模拟退火………………….…8
米特罗波利斯准则………………….……9
优化问题中的模拟退火算法…….………10
冷却进度表……………………………….16
模拟退火算法应用的要求……………….21
实例分析………………………………….22
参考文献







- 2 -
第一章绪论
唐山铁路道岔厂位于中国北方重工业城市--唐山,它北依燕山,南临渤海,
毗邻京、津两地,与京唐港咫尺相望,海陆交通便利,地理位置优越。工厂始
建于 1988 年,是铁道部特别许可生产道岔系列品的专业工厂,厂区占地 12 万平
方米,建筑面积 万平方米,总资产超亿元,现有职工 500 余人,其中各类高、
中级专业技术人员百余人。工厂工艺装备先进,检测手段齐全,技术力量雄厚具
备年产高锰钢辙叉 8000 根,整组道岔 2000 组的生产能力。主要生产各种规格型
号的铁路普通辙叉、机加工辙叉、整组道岔,铁路提速辙叉、道岔及其零配件。
工厂坚持"依靠科技进步,严格质量控制,生产优质产品,满足用户需求" 的质
量方针,严格按照 ISO9000 标准建立了完善的质量保证体系,并于 1999 年 12
月通过了 ISO9002 质量体系认证,产品先后荣获"市优"、"省优"称号,遍布全国
14 个铁路局,地方、地下铁路和大厂企,市场覆盖 28 个省、市、自治区。产品
不仅满足国内市场,还远销东南亚等国家。工厂是唐山市"重合同,守信用企业
"、"文明单位"、"五十强企业"、"优秀企业"、河北省"百强企业",被中国企业形
象认定委员会确认为"中国企业形象最佳单位"。
为了提高企业效益,增加原材料的利用率,唐山铁路道岔厂的下料优化问题
急需解决,过去下料都是由几位有着丰富生产经验的老同志依据经验来确定下料
的方案,而处于信息时代的今天,只有把计算机和运筹学综合起来,才能起到事
半功倍的效果。
根据具体需求,我们学过的运筹学中的线性规划、整数规划融合在计算机软
件设计当中,开发出了基本满足唐山铁路道岔厂需求的下料优化软件。
首先,整个软件的界面简单明了,数据存储继承了原先存在的 FOXPRO 数
据库,在界面的编写中我们选择了 VC++来作为实现语言。这是因为 VC++本身
具有的强大数学库以及其本身的语法简明实用,我们选择其作为界面编译语言。
其次,在前端界面后我们要实现关于各种下料数据的处理。在我们查找了目
前国际上关于实现这类下料问题的各种算法后,最后选择了模拟退火算法来解决
整个下料问题。关于下料问题的算法实现是我们在整个问题解决的第二个步骤。
最后,在解决了前面这些后,我们面临着如何实现模拟退火算法。由于主要
数据为矩阵,在这里我们选择了目前矩阵运算功能最为强大的数学软件
MATLAB 来完成算法,当然 MATLAB 中的许多数学函数和库也是我们选择使用
它的主要原因之一。
运筹学作为一门新兴的学科,在现代管理与生产中有着广泛的应用,它解决
了企业在生产经营中遇到的许多问题,有效的促进了企业管理的现代化和科学
化,为企业带来巨大的经济效益,因此,许多企业都十分重视运筹学的应用。
在实际应用中,企业回面临大量的线性规划问题,而有些问题是必须的求解
结果必须为整数,此类问题就变成整数规划问题。但是,整数规划的求解又存在
诸如运算量大,求解结果精度低等问题,于是,我们引出模拟退火算法,并将模
拟退火算法与局部搜索算法进行比较。
- 3 -
第二章线性规划问题的数学模型
线性规划理论
线性规划(Linear Programming,简称 LP)是运筹学中发展的比较早和比
较快,同时在实际生产中应用比较广泛的一个主要分支。它研究的问题主要有两
类:一类是已有一定数量的人力、物质资源,研究怎样充分和合理的使用这些资
源,才能使完成的任务量最大;另一类是已确定了一项任务,研究怎样合理安排,
才能使完成任务所耗费的资源量最小。实际上,这两类问题是相互联系的,或者
说是一个问题的两种不同提法,总的是要求耗费最小量的资源,完成尽可能多的
任务,获得最好的经济效果。
线性规划问题有各种