数学建模--部门调整方案模型

. CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY 课程设计（论文）课程名称： 运筹学题目： 公司搬迁的数学模型学生姓名：葛贺祥学 号：201464100130班 级: 数学1401所在院部: 数学与统计学院指导教师：罗煦琼 2014 年 1 月 课程设计（论文）任务书 数学与统计 学院 数学与应用数学 专业 1401 班课程名称 运筹学 题 目 公司搬迁的数学模型 任务起止日期： 2016.5.12-2016.5.22 学 生 姓 名 葛贺祥 学 号 201464100130指 导 教 师 罗煦琼 教研室主任 年 月 日 审查课程设计（论文）任务一、课题内容二、课题要求三、课题完成后应提交材料的要求四、主要参考文献（由指导教师选定）同组设计者 ： 无注：1. 此任务书由指导教师填写。如不够填写，可另加页。2. 此任务书最迟必须在课程设计（论文）开始前下达给学生。 学生送交全部材料日期 学生（签名） 指导教师验收（签名） 摘要对于部门调整方案问题，我们可以理解为为了使综合利益最大而采取部门调整措施。本题的综合利益就是经济效益和通讯费用的净收益。对于部门是否迁往Bristol 或 Brighton这两种状态,选择运用运筹学中的0-1线性规划方法,然后根据部门调整后三地的部门是否存在通讯费用这两种状态，确定另一个0-1线性规划方法，故该问题是一个二次指派问题。列出目标函数和约束方程，建立数学模型,最后利用LINGO软件得出最优方案。最优方案：部门ABCDE校区安排Bristol BrightonBrightonBristol Brighton关键词: 0-1线性规划 部门调整 LINGO软件Abstract To the problem of adjusting department .we can understand that it is a measure in order to get the most comprehensive benefits . The comprehensive benefit is net income of economic benefits and the costs of communication in this question. We can select using 0-1 linear programming in operational research method for department whether to move to Bristol or Brighton this two kinds of state, and then according to the department of three departments adjusted whether there is a communication cost these two kinds of state to decide a 0-1 linear programming method, so the problem is a quadratic assignment problem. List the objective function and constraint equation, mathematical model is set up,We can get the optimal solution finally by using LINGO software. The optimal solution: department ABCDECampus to arrange Bristol BrightonBrightonBristol BrightonKeywords: 0-1 linear programming department adjust the LINGO software 一、问题重述伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。公司由五个部门组成，A,B,C,D,和 E,考虑搬迁的地址为Bristol 和 Brighton。每个城市至多安置3个部门。各部门搬迁后每年能节约的费用（千镑）如下表：ABCDEBristol101310208Brighton1028141615各部门间每年的通信量（千单位）如下表：ABCDEA1.01.5B1.41.1C2.0D0.8各部门间的通信单价（镑每年每单位）BristolBrightonLondonBristol51413Brighton1459London13910二、问题分析该问题是一个二次指派问题，通过两次的0-1整数线性规划表示出经济效益和通讯费用，初步分析，不能单独考虑经济效益或通讯费用。综合考虑它们之间的相互约束，列出目标函数和约束方程，利用Lingo软件求解得到最优方案。三、模型假设假设1：题中所给的数据在短期内不会发生较大的变化。假设2：Bristol 和 Brighton都能正常接收搬迁过去的部门。假设3：题中所给数据真实可信。四、定义与符号说明Bij：第i个部门迁往第j个区的好处 i=1,2,3,4,5 j=1,2,3Cik：第i个部门与第k个部门每年的通信量 i，k=1,2,3,4,5Djl：第j个区与第l个区的通讯单价 j，l=1,2,3M：目标函数五、模型建立与求解模型建立1、 变量假设 1 ，如果第i各部门迁往第j个城市 0 ，否则i=1,2,3,4,5， j=1,2,3= 1 ，如果1且=1 0 ，否则i=1,2,3,4,5, j,l=1,2,32、 问题建模1)约束函数 每个部门要么原地不动，要么迁往某个城市， i=1,2,3,4,5由于五个部门中一些部门计划迁往Bristol 或 Brighton市，而每个城市允许接收（包括原地不动）的部门不能超过三个，有 j=1,2,3现在考虑目标函数中二次乘积项，引进变量，并满足=1 1，=1和1，=1 =1上述两个条件等价于如下约束i=1,2,3,4,5 j， l=1,2,3 k i2)目标函数3)0-1线性规划问题： Max -CikDilYijkl S.t. i=1,2,3,4,5 j=1,2,3 Yijkl-Xiji Yijkl-Xkli Xij+Xkl-Yijkli Xij=0或1 i=1,2,3,4,5 j=1,2,3 Yijkl=0或1 i，k=1,2,3,4,5 j,l=1,2,3模型求解利用LINGO软件求解其最大值:运行结果:Local optimal solution found. Objective value: -21.90000 Objective bound: -21.90000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost C( 1, 1) 0.000000 0.000000 C( 1, 2) 0.000000 0.000000 C( 1, 3) 0.000000 0.000000 C( 1, 4) 0.000000 0.000000 C( 1, 5) 0.000000 0.000000 C( 2, 1) 10.00000 0.000000 C( 2, 2) 13.00000 0.000000 C( 2, 3) 10.00000 0.000000 C( 2, 4) 20.00000 0.000000 C( 2, 5) 8.000000 0.000000 C( 3, 1) 10.00000 0.000000 C( 3, 2) 28.00000 0.000000 C( 3, 3) 14.00000 0.000000 C( 3, 4) 16.00000 0.000000 C( 3, 5) 15.00000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 14.80000 X( 1, 3) 0.000000 8.900000 X( 1, 4) 0.000000 4.400000 X( 1, 5) 0.000000 4.500000 X( 2, 1) 1.000000 -17.00000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 7.900000 X( 2, 4) 1.000000 -18.10000 X( 2, 5) 0.000000 0.1000000 X( 3, 1) 0.000000 5.200000 X( 3, 2) 1.000000 0.000000 X( 3, 3) 1.000000 0.000000 X( 3, 4) 0.000000 0.000000 X( 3, 5) 1.000000 0.000000 A( 1, 2) 0.000000 0.000000 A( 1, 3) 1.000000 0.000000 A( 1, 4) 1.500000 0.000000 A( 1, 5) 0.000000 0.000000 A( 2, 3) 1.400000 0.000000 A( 2, 4) 1.100000 0.000000 A( 2, 5) 0.000000 0.000000 A( 3, 4) 0.000000 0.000000 A( 3, 5) 2.000000 0.000000 A( 4, 5) 0.8000000 0.000000 B( 1, 1) 10.00000 0.000000 B( 1, 2) 13.00000 0.000000 B( 1, 3) 9.000000 0.000000 B( 2, 1) 13.00000 0.000000 B( 2, 2) 5.000000 0.000000 B( 2, 3) 14.00000 0.000000 B( 3, 1) 9.000000 0.000000 B( 3, 2) 14.00000 0.000000 B( 3, 3) 5.000000 0.000000 Row Slack or Surplus Dual Price 1 -21.90000 -1.000000 2 0.000000 -28.50000 3 0.000000 -12.10000 4 0.000000 -34.70000 5 0.000000 -32.20000 6 0.000000 -23.90000 7 1.000000 0.000000 8 0.000000 17.70000X12=1, X33=1, X42=1, X23=1, X53=1f=21900即：部门ABCDE调整方案Bristol BrightonBrightonBristol Brighton 六、模型的评价与推广部门调整方案模型主要运用了0-1整数规划,逻辑性强,其所表示的问题简单易懂,没有太复杂的公式.很大程度的省去计算的繁琐,适用于两种状态的问题,但如果目标函数的各个量联系复杂,所需的0-1整数规划将不止一个,反而使问题跟复杂.约束较少的情况下,0-1整数规划可以使问题简单,此时可行性可行性强.可以应用于工件加工的排序问题. 七参考文献1 胡运权运筹学教程（第4版）M北京：清华大学出版社，2012：1-460.2 韩中庚实用运筹学模型、方法与计算M北京：清华大学出版社，2007：1-232.3 姜启源，谢金星，叶 俊编数学模型（第三版）M北京：高等教育出版社，2005：1-202.4 刘琼荪，何中市数学实验（第一版）M北京：高等教育出版社，2004.01：1-247.5 张明辉，王学辉等编著MATLAB6.1最新应用详解M北京：中国水利水电出版社，2001：1-180. 八附录程序：model: sets: city/1,2,3/:; department/1.5/:; link(city,department):c,x; link1(department,department)|&2#gt#&1:a; link2(city,city):b; endsets data: a= 0 1.0 1.5 0 1.4 1.1 0 0 2.0 0.8;b=10 13 913 5 149 14 5 ;c= 0 0 0 0 010 13 10 20 810 28 14 16 15;enddata min=sum(link1(m,n):a(m,n)*sum(link2(p,q):b(p,q)*x(p,m)*x(q,n)-sum(link:c*x); for(department(j):sum(city(i):x(i,j)=1); for(city(i)|i#gt#1:sum(department(j):x(i,j)=3); for(link:bin(x); end结果：Local optimal solution found. Objective value: -21.90000 Objective bound: -21.90000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost C( 1, 1) 0.000000 0.000000 C( 1, 2) 0.000000 0.000000 C( 1, 3) 0.000000 0.000000 C( 1, 4) 0.000000 0.000000 C( 1, 5) 0.000000 0.000000 C( 2, 1) 10.00000 0.000000 C( 2, 2) 13.00000 0.000000 C( 2, 3) 10.00000 0.000000 C( 2, 4) 20.00000 0.000000 C( 2, 5) 8.000000 0.000000 C( 3, 1) 10.00000 0.000000 C( 3, 2) 28.00000 0.000000 C( 3, 3) 14.00000 0.000000 C( 3, 4) 16.00000 0.000000 C( 3, 5) 15.00000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 14.80000 X( 1, 3) 0.000000 8.900000 X( 1, 4) 0.000000 4.400000 X( 1, 5) 0.000000 4.500000 X( 2, 1) 1.000000 -17.00000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 7.900000 X( 2, 4) 1.000000 -18.10000 X( 2, 5) 0.000000 0.1000000 X( 3, 1) 0.000000 5.200000 X( 3, 2) 1.000000 0.000000 X( 3, 3) 1.000000 0.000000 X( 3, 4) 0.000000 0.000000 X( 3, 5) 1.000000 0.000000 A( 1, 2) 0.000000 0.000000 A( 1, 3) 1.000000 0.000000 A( 1, 4) 1.500000 0.000000 A( 1, 5) 0.000000 0.000000 A( 2, 3) 1.400000 0.000000 A( 2, 4) 1.100000 0.000000 A( 2, 5) 0.000000 0.000000 A( 3, 4) 0.000000 0.000000 A( 3, 5) 2.000000 0.000000 A( 4, 5) 0.8000000 0.000000 B( 1,