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

. CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY课程设计论文课程名称： 运筹学题目： 公司搬迁的数学模型学生：贺祥学 号：0班 级: 数学1401所在院部: 数学与统计学院指导教师：罗煦琼2014 年 1 月课程设计论文任务书 数学与统计学院 数学与应用数学 专业 1401 班课程名称 运筹学题 目 公司搬迁的数学模型 任务起止日期：学 生 姓 名 贺祥 学 号 0指 导 教 师 罗煦琼教研室主任年 月 日 审查课程设计论文任务一、课题容二、课题要求三、课题完成后应提交材料的要求四、主要参考文献由指导教师选定同组设计者 ： 无注：1. 此任务书由指导教师填写。如不够填写，可另加页。2. 此任务书最迟必须在课程设计论文开场前下达给学生。学生送交全部材料日期 学生签名 指导教师验收签名摘要对于部门调整方案问题，我们可以理解为为了使综合利益最大而采取部门调整措施。此题的综合利益就是经济效益和通讯费用的净收益。对于部门是否迁往Bristol 或 Brighton这两种状态,选择运用运筹学中的0-1线性规划方法,然后根据部门调整后三地的部门是否存在通讯费用这两种状态，确定另一个0-1线性规划方法，故该问题是一个二次指派问题。列出目标函数和约束方程，建立数学模型,最后利用LINGO软件得出最优方案。最优方案：部门ABCDE校区安排Bristol BrightonBrightonBristol Brighton关键词: 0-1线性规划 部门调整 LINGO软件AbstractTo the problem of adjusting department .we can understand that it is a measure in order to get the most prehensive benefits . The prehensive benefit is net ineof economic benefits and the costs of munication in this question. We can select using 0-1 linear programmingin 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 munication 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 theLINGO 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线性规划问题： Ma* -CikDilYijkl S.t. i=1,2,3,4,5 j=1,2,3 Yijkl-*iji Yijkl-*kli *ij+*kl-Yijkli *ij=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 E*tended 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 *( 1, 1) 0.000000 0.000000 *( 1, 2) 0.000000 14.80000 *( 1, 3) 0.000000 8.900000 *( 1, 4) 0.000000 4.400000 *( 1, 5) 0.000000 4.500000 *( 2, 1) 1.000000 -17.00000 *( 2, 2) 0.000000 0.000000 *( 2, 3) 0.000000 7.900000 *( 2, 4) 1.000000 -18.10000 *( 2, 5) 0.000000 0.1000000 *( 3, 1) 0.000000 5.200000 *( 3, 2) 1.000000 0.000000 *( 3, 3) 1.000000 0.000000 *( 3, 4) 0.000000 0.000000 *( 3, 5) 1.000000 0.000000A( 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 Price1 -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.70000*12=1, *33=1, *42=1, *23=1, *53=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,*; link1(department,department)|&2#gt#&1:a; link2(city,city):b; endsetsdata: 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;enddatamin=sum(link1(m,n):a(m,n)*sum(link2(p,q):b(p,q)*(p,m)*(q,n)-sum(link:c*); for(department(j):sum(city(i):*(i,j)=1); for(city(i)|i#gt#1:sum(department(j):*(i,j)