整数规划问题应用毕业论文

《整数规划问题应用毕业论文》由会员分享，可在线阅读，更多相关《整数规划问题应用毕业论文（29页珍藏版）》请在装配图网上搜索。

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 model引言 整数规划(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 资源量、产品单件可变费用及售价、资源单耗

16、量及组织三种产品生产的固定费用资源单耗量产品资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012解：设是第种产品的产量，再设则问题的整数规划模型是（2） 动态生产安排问题设某公司对某种产品要制定一项个阶段的生产（或购买）计划。已知它的初始库存量为零，每阶段生产（或购买）该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在阶段末的终结库存量为零。问该公司如何制定每个阶段的生产（或购买）计划，从而使总成本最小。设为第阶段对产品的需求量，为第阶段该产品的生产量（或采购量），为第阶段结束时的产品库存量，则有以表示第阶段

17、生产产品时的成本费用，它包括生产准备成本和产品成本（其中是单位产品成本）两项费用。即：其中表示每阶段最多能生产该产品的上限数。用表示第阶段结束时库存量为时所需的存储费用，故第阶段的成本费用为。因而，上述问题的数学模型为：例3某柴油机厂接到今年1至4季度柴油机生产订单分别为：3000台，4500台，3500台，5000台。该厂每季度正常生产量为3000台，若加班可多生产1500台。正常生产成本为每台5000元，加班生产还要追加成本每台1500元。库存成本为每台每季度200元，问该柴油机厂该如何组织生产才能使生产成本最低？解： 设为第个季度正常生产的柴油机台数，为第个季度加班生产的柴油机台数，为第

18、个季度初的库存量。第一季度初期及年底的库存量均为零，若记为第个季度的需求量；分别为正常生产、加班生产、库存（每季度）每台柴油机的成本。则该问题的数学模型为：代入具体数据，3.1.3 下料问题制造某种产品，需要中轴件，其长度分别为。各类轴件都用长为的同一种圆钢下料。设长度为的轴件需要量为，问最少要用多少根圆钢？用非负的整数向量表示第种下料方式，其中表示下料长度为的轴件的数量，记所有下料方式的下标集合为，则对，下料方式满足：设采用第种下料方式的圆钢数目为，则问题数学模型为例4 制造某种机床，需要A，B，C三种轴件，其规格与数量如表3-2所示。各类轴件都用5.5m长的同一种圆钢下料。若计划生产100

19、台机床，最少要用多少根圆钢？表3-2 轴件规格及数量轴类规格：长度（m）每台机床所需轴件数A3.11B2.12C1.24依据问题，若直接以要用的圆钢书作为决策变量，则建模变得很困难。所以避免直接由题意建模，先进行分析，实际问题抽象成线性规划的数学模型经常要进行转化。首先考虑一根长5.5m的圆钢截成A，B，C三种轴的毛坯有哪些具体下料方式。为次，只需找出全部省料截法，如下所示余料的各种截法，其中1.2m是各类轴件中最短者。一根圆钢所截各类轴件数轴件需数量12345A(3.1)11000100B(2.1)10210200C(1.2)02124400余料0,300.110.7现在问题归结为：常用上述

20、5种截法用多少根圆钢，才能配成100套轴件，且使总下料根数最少？设按第种截法下料根。这样就可以建立该问题的LP模型为3.2 在指派问题中的应用 在实际中经常会遇到这样的问题，有项不同的任务，需要 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题(Assignment Problem)。3.2.1 平衡指派问题在指派问题中，如果，拟每人做一件工作，且每件工作一个人做。这样的指派问题称为平衡指派问题。这类问

21、题的提法如下：现有项工作分配个工人去完成，已知工人完成工作需要花费时间。要求每项工作只能由一个工人去完成，每个工人只能完成一项工作。应如何分工，使总工时最少？为了建立平衡指派问题的数学模型，引入个0-1变量： 这样，问题的数学模型可写成 （）s.t. 其中，表示每件事必有且只有一个人去做，表示每个人必做且只做一件事。满足约束条件、的可行解也可写成表格或矩阵形式，称为解矩阵。例5. 某游泳队拟选用A、B、C、D四名运动员组成一个4100混合游泳接力队，参加运动会，他们的100m自由泳，蛙泳，蝶泳，仰泳的成绩如表3-3，如何安排游泳才能最大可能得取得好成绩？ 表3-3 四名运动员100m自由泳，蛙

22、泳，蝶泳，仰泳的成绩表姿势队员自由泳蛙泳蝶泳仰泳A56746163B63696571C57776367D55766262解: 引入01变量，并令 可以表示为一个0-1整数规划问题：3.2.2 不平衡指派问题如果，即人数和任务数不等的情况，该类问题称为不平衡指派问题。下面给出不平衡指派问题的两种情形及数学模型：情形1：当人员数少于任务数时，出现部分人员将承担多项任务；情形2：当人员数多于任务数（时，出现部分人员将无任务承担；针对情形1、2的指派问题，令：1. 当时 （3.2.2-1）s.t.注：表示每个人员最少承担一项任务；表示每项任务都有一个人员承担，并只有一个人员承担；特别地，当人员有任务承

23、担量约束时，对上式中的条件（）加强。若每个人员承担的任务数有限制，设每个人员的任务承担量分别为，则约束条件加强为：s.t.此时，问题的模型为对于该类问题的求解，若每每个人员的任务承担量为无穷大，则项余下的任务肯定分别由完成这些任务时间最少的人来完成，才能使目标函数最优，通过添加个虚拟人员，且这些虚拟人员完成各项任务的时间设为完成此项任务的实质人员中的最小时间，进而转化为标准的指派问题：s.t.2. 当时：s.t.注：表示每项任务均有且只有一个人员承担；表示可能有部分人员无任务承担；3.2.3 非确定型指派问题在实际应用中，平衡指派问题带有很大的局限性。对于从事工作的人来说，由于工作的难以程度及

24、个人完成工作的效率不同，所以不同的人在规定时间内完成工作的件数也不相同。例如在学校排课时，由于学习每门课的班数较多，所以每门课的任课教师可能多于一个，且每学科的任课教师的任课门数也不一定就是一门（包括重复上同一门课）。这类指派问题可以描述为：有项工作，可以安排个人去完成，第个人至少可以承担项，最多可承担项工作；而第项工作可以由个人来完成。第个人完成第项工作的效率为，给出指派方案，使完成项工作的总效率最高。以上指派问题，可以用下面的数学模型来描述：其中表示第个人完成第项工作的件数（第项工作需要个人完成，可以把第项工作看成分为件工作）。模型中，1式要求完成工作的成本、时间等为极小值（若是效率、产值

25、、效益等时应取极大值）；2式表示第项工作同时需要个人来完成；3式表示第个人至少可以同时完成件，最多可以同时完成件工作；4式表示完成项工作需要的总人数介于个人可以同时完成的最少工作量和最大工作量之间。由于每个人完成的工作量都是不确定的，所以我们称上面的模型为不确定型指派问题为了求解上述问题，我们将问题进行转换，借助平衡指派问题，所有的数据和已知情况如表3-4所示：表3-4 人员及其可完成工作数据表工作人员至少从事工作件数最多从事工作件数需要人数M N2 N2则原问题的指派矩阵为：为了能用平衡指派问题的方法求解，我们可以将问题进行转换：因为项工作中，每项工作都必须由个人完成，所以我们将其看成为有件

26、工作，一共就有件工作；而个人每人至少做件，最多做件工作，即至少要做，最多要做件工作，所以我们假设最多有个人。因为，我们再假设有件虚拟工作，则所给问题就可以转化为有件工作，每件工作必须且只须由一个人来做，有个人，每人必须且只须做一件工作的平衡指派问题。为了保证第个人至少完成件工作，所以当把第个人要完成的件工作看成有个人时，前个人从事虚拟工作的效率，当问题求最小值时取N（N为非常大的整数），当问题求最大值是取0。此时，新的指派矩阵为：对于变化后的指派问题矩阵，利用解传统指派问题的匈牙利法可求问题德法尔最优解。3.3 在组合优化方面的应用在有限个可行解的集合中找出最优解的一类优化问题称为组合优化问题

27、。它是运筹学的一个重要分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通讯网络等诸多领域。3.3.1 一维背包问题设有一背包，其可携带物品重量的限度为。设有种不同的物品可供他选择装入背包中，已知第种物品的重量为，单位价值为（）。问此人应如何选择携带物品的方案，使总价值最大？设为第种物品的装入件数，则问题的数学模型是例6. 一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表3-5所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。表3-5 每种物品的重量合重要性系数 序号1234567物品食品氧气

28、冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410解：引入01变量其数学模型为：上述问题就是一个标准的整数规划问题.3.3.2 选址问题选址问题的基本提法如下：某机构拟在个被服务点所在城市中建立 个服务中心，每个城市最多建立一个服务中心。若在第个城市建立服务中心，其服务能力为，单位时间的固定成本为，第 j 个被服务点的需求量为。从第个服务中心到第个被服务点的单位运输成本为。应如何选择服务中心位置和安排运输计划，才能得到经济上花费最少的方案。 设在单位时间内，从配货中心运往连锁店的物资数量为， 为单位时间内的总费用。引入变量则上述问题可归结为如下的数学模型：

29、这是一个混合 规划问题例7某企业在地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在地中再选择几个地方建厂。已知在地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，产量及建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如表3-6所示。 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?表3-6 销地的销量以及产地到销地的单位运价销地产地产量（千吨）84330523104342097530104240销量（千吨）302020解： 设为从运往的运输量(单位千箱)此时,该问题可以表示为一个整数规划问题：

30、（其中前4项为固定投资额，后面的项为运输费用）约束条件为：3.4 在集合划分问题中的应用集合划分问题是M.R Garey和D.S Johnson在1979年提出的6个基本NP完全问题之一。最简单的集合划分问题是将个正整数组成的集合A划分成两个子集，使两个子集的元素之和尽可能的接近。更广泛的情况是将这个正数划分到个互不相交的子集中，使各个子集元素之和尽可能相等。集合划分问题的另一种提法为：把个正数组成的集合划分成个互不相交的子集中，使得这些子集各个元素之和中最大者尽可能小。可以证明，两者定义是等价的。引人0-1变量：它的数学模型可以表示为：其中，是集合A中的第个元素。集合划分问题应用很广泛，如处

31、理调度问题，存储分配问题等。3.4.1 中心覆盖问题 设某地区划分为若干个区域，需要建立若干个应急服务中心（如消防站、急救中心等），每个中心的建立都需要一笔建站费用，设候选中心的位置已知，每个中心可以服务的区域预先知道，问如何选取中心使该应急服务能覆盖整个地区且使建站费用最小。记为该地区中的区域，是可选的中心，设为中心可以服务的区域集合，是中心的建站费用，定义0-1关联矩阵，其中，如果，否则。设则问题可以表示为：例8. 该城市共有6个区域，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶时间见表

32、3-7，请帮助该市制定一个布点最少的计划。解 引入变量作决策变量，令表示在地区设消防站；表示在地区不设消防站。表3-7 消防车在各区间行驶时间表 单位 min地区1地区2地区3地区4地区5地区6地区1地区2地区3地区4地区5地区6010162827201002432171016240122721283212015252717271501420102125140本问题的目标是本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，有表#可知，在地区1及地区2内设消防站都能达到要求，即因此本问题的数学模型为：3.4.2 旅行商问题(TSP)设有一个旅行售货员需要去个城市推销他的产

33、品，他必须而且只能访问每个城市一次，并最后返回出发城市。设每个城市直接到达另一个城市的距离已知（如不能直接到达，则可设其距离为），他应该如何选择旅行路线使得总的旅行距离最短？设城市到城市的距离为。设约束条件：他离开城市一次：他离开城市一次：上面的约束条件使得每个城市正好经过一次，但仍可能包括含圈但不联通的路线，我们需要用下面的约束条件来去除这种情况发生：或从而旅行售货员问题可以表示为结论本文在整数规划的理论基础上归纳总结出若干整数规划问题并给出了相应的解答方法，主要涉及一下几个方面：（1）在经济管理问题中的应用。探讨了投资问题、生产安排问题和下料问题；（2）在指派问题中的应用。探讨了平衡指派问

34、题、不平衡指派问题及非确定性指派问题；（3）在组合优化方面的应用。探讨了一维背包问题和选址问题；（4）在集合划分问题中的应用。探讨了中心覆盖问题和旅行商问题。同时列举了这些整数规划在现实中的应用实例，将数学知识应用到实际生活中来解决实际问题。从而使得该问题具有其价值与意义，同时进一步完善和丰富整数规划问题理论。由于知识水平有限，对整数规划问题的动态规划解法及决策论中的应用问题本文并未解决，而且，整数规划在工业和工程设计和科学研究方面还有更广泛的应用，如在计算机设计、系统可靠性、编码、线路设计中的接点串联设计和经济分析等方面都具有新的应用。对这些问题，还需我们继续钻研开发。致谢本论文是在老师的悉

35、心指导与关怀下完成的。从论文的选题、撰写、定稿，导师都给予了精心指导，提出了许多宝贵的修改意见和建议。导师渊博的学识、严谨的治学态度，高尚的人品，不仅在学术上，更重要的是在思想上影响着我，并将不断地激励着我在学业上努力迸取。老师的关心和帮助对我的论文的完成起到了关键性的作用。在此表示深深的谢意。我还要感谢四年来给我们授课的老师。他们不仅教给我知识和方法，更为重要的是他们对教育事业的忠诚、对待科学研究的态度和实事求是的科学精神以及令人仰视的科研成果都给我潜移默化的影响，使我今后的教学、科研受益终身。最后，我要感谢学校的领导给予了我极大的支持，才使我能全身心地投入到学习中来，顺利地完成学业。 参考

36、文献1钱颂迪、甘应爱、陈秉正等.运筹学 M.清华大学出版社.2005年.第三版2卢开澄.单目标、多目标与整数规划M.清华大学出版社.1999年.第一版3王丽.整数规划在实际中的应用 c.应用技术4 冯俊文.中国邮递员问题的整数规划模型 J.系统管理学报.第19卷（第6期）5李炯城、鲍江宏.组合优化中整数规划的数论解法J.计算机工程与设计.2009年6姜启源、谢金星、叶俊.数学模型（第三版） M.高等教育出版社. 2003年7王娜、汪定伟.一种采购中心选址问题的研究 J.沈阳师范大学学报(自然科学版).第29卷（第1期）.2011年8林秋红.整数规划在数学建模中的应用 J.大众科技.2010年第5期9王胜仁、林兵、王聪.整数规划模型在资源分配优化方面的应用 c.中国科技论文在线10王新红，几个组合优化问题的研究及应用 c.山东大学博士论文11刘蕾、鲁华祥，集合划分问题的分布估计求解 J，计算机工程与应用，4009，45（10）12黄龙生、徐光辉，有资格限制的指派问题的求解方法 J，运筹与管理，第14卷第1期，2005年13雷真、缪昇、屈俊童，整数规划在防火预案制定中的应用 J，云南大学学报（自然科学版），2009，31（S1）13doc share.整数规划 OL.http:/www.doc-