《整数规划问题应用毕业论文》由会员分享，可在线阅读，更多相关《整数规划问题应用毕业论文（32页珍藏版）》请在金锄头文库上搜索。
1、目 录摘要IAbstractII引言11 整数规划问题11.1 概念11.2 分类11.3 整数规划的一般形式22 整数规划问题的计算方法22.1 分支定界法22.2 割平面法23 整数规划问题的应用33.1在经济管理问题中的应用33.1.1 投资问题33.1.2 生产安排问题43.1.3 下料问题73.2 在指派问题中的应用83.2.1 平衡指派问题93.2.2 不平衡指派问题103.2.3 非确定型指派问题123.3 在组合优化方面的应用143.3.1 一维背包问题143.3.2 选址问题153.4 在集合划分问题中的应用163.4.1 中心覆盖问题173.4.2 旅行商问题(TSP)18
2、结论19致谢20参考文献20整数规划问题的应用摘要：整数规划(Integer Programming，IP)是带整数变量的最优化问题。即最大化或最小化全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。整数规划的历史可以追溯到20世纪50年代，主要是由于经济管理中的大量问题抽象为模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足取整条件。而今，许多经济、管理、通信和工程中的最优化问题都可以用整数规划来建模。本文主要阐述了整数规划的理论基础，给出了整数规划的基本模型以及计算方法，在此基础上对一些整数规划问题及其解答方法进行归纳总结，最后列举了
3、若干整数规划在现实中的应用实例，将数学知识应用到实际生活中来解决实际问题,从而使得该问题形象化、简单化，同时进一步完善和丰富整数规划理论。关键词： 整数规划问题；实际应用；0-1整数规划；数学模型Application of integer programming problemsAbstract: Integer programming is an optimization problem with integer variables, which maximize or minimize the multiple functions of full or partial variables
4、 for integer, subject to a set of equality and inequality constraint optimization problems.The history of integer programming can be traced back to the nineteen fifties, mainly due to a large number of problems in economic management be abstracted as a model, it is found that many are inseparable, t
5、herefore when they are taken as variables into the planning, often meet the requirements of integral conditions.Now, many optimization problems with integer of economic, management, communication and engineering can be use to build model.This paper discusses the theoretical basis of integer programm
6、ing, on which summarize some integer programming problems and their answers. And how link up with other mathematical knowledge to solve practical problems. Finally, this paper sums up several applications of integer programming in the reality. That makes the problem visualize and simplify, and furth
7、er improve and enrich integer programming theory.Keywords: Integer Programming；Practical application；0-1 integer linear programming；Mathematical modelI引言 整数规划(Integer Programming，IP)是规划论中近30年才发展起来一个重要分支。整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背包（或装载）问题、固定费用问题
8、、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围是极其广泛的。它不仅在工业、工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。此外，整数规划还可以描述和处理互斥决策问题。如运作管理中的决策问题：工厂选址、超市选址、人员的工作指派、设备购置和配置、系统可靠性设计、机床加工任务的均衡分派、线路设计中的接点串联设计等；物流管理中，物流中心的定点决策；以及金融和项目投资中的组合投资和项目选择等等。其规划模型中往往可以引入逻辑变量（即变量仅取 0 或 1 两个值）来反映冲突因素和抉择。另外，整数规划还可以实现不相容状态下，分散模型的
9、模式统一，加强系统研究的集成性。因此，整数规划模型不同于前述的线性规划范畴，而属于一种新的类型。整数规划在实践中有比线性规划更为广泛的应用空间，对整数规划问题的探究是十分有必要的。1 整数规划问题1.1 概念要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integer programming，简记IP)。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题(slack problem)。若松弛问题是一个线性规则，则称该整数规划为整数线性规划(integer linear programming，简记ILP) 1.2 分类 整数规划问题按决策变量取值
10、可分为下列几种类型：1纯整数规划(pure integer programming)：指全部决策变量都必须取整数值的整数规划。有时，也称为全整数规划。2混合整数规划(mixed integer programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。30-1型整数规划(zeroone integer programming)：指决策变量只能取值0或1的整数规划。1.3 整数规划的一般形式 2 整数规划问题的计算方法2.1 分支定界法分支定界法是在20世纪60年代初由Land Doing和Dakin等人提出的适合于解纯整数或混合整数规划问题的方法。分支定界法
11、的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束缩小可行域；将原整数规划问题分支分为两个子规划，再解子规划的伴随规划，以此类推，最后得到原整数规划的伴随规划。这就是所谓的“分支”。所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处理其它分支的一个依据。“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。分支定界法的计算步骤第一步：计算原问题目标函数值的初始上界第二步：计算原问题目标函数值的初始下界第三步：增加约束条件将原问题分支第四步：分别求解一对分支第五步
12、：修改上、下界第六步：比较上、下界大小，如有上界下界，停止计算，找到最优解，否则转32.2 割平面法割平面法由高莫瑞(Gomory)于1958年提出。其基本思想是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。增加的新约束称为割平面方程或切割方程(1)设是相应线性规划最优解中为分数值的一个基变量，则由单纯形表的最终表得到 ()(2)将拆分成整数部分N和非负真分数之和，即： ()表示不超过的最大整数。将()式代入(1)式 （）其中，就是割平面方程的最基本形式。
13、割平面法解整数规划问题的基本步骤第一步：用单纯形法解松弛问题，得到最优单纯形表。第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。3 整数规划问题的应用3.1在经济管理问题中的应用3.1.1 投资问题设有个投资项目及年内逐年投入资金矩阵，其中为第年的投资金额，以及投资矩阵，其中为第年项目所需投入资金。利润矩阵，为项目的利润。投资问题即在提供的资金的容许条件下，求利润最高的投资决策。设则该问题的数学模型为：例1. 某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初可以投资，并于次年末回收本
14、利115%， 但第一年如果投资则最低金额为4万元，第二、三、四年不限；项目B：第三年初可以投资，到第五年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目 C：第二年初可以投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?解： 设分别表示第 年年初给项目A，B，C，D的投资额； 设是01变量 设 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4
15、；第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；目标函数及模型：3.1.2 生产安排问题（1） 静态生产安排问题设有个生产行业，都需要某种资源。对于第个生产行业，如果用第种资源生产，可获得的利润为.若第种资源的单位价格为，现有资金。问应购买第中资源多少单位，分配到个生产行业，使总利润最大？此题的数学模型为：例2. 有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见表3-1。要求制订一个生产计划，使总收益最大。表3-1 资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用资源单耗量产品资源量A248500B234300C
