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

-1-CHANGSHAUNIVERSITYOFSCIENCE&TECHNOLOGY课程设计（论文）课程名称：运筹学题目：公司搬迁的数学模型学生姓名：葛贺祥学号：201464100130班级:数学1401所在院部:数学与统计学院指导教师：罗煦琼2014年1月-2-课程设计（论文）任务书数学与统计学院数学与应用数学专业1401班课程名称运筹学题目公司搬迁的数学模型任务起止日期：2016.5.12-2016.5.22学生姓名葛贺祥学号201464100130指导教师罗煦琼教研室主任年月日审查-3-课程设计（论文）任务一、课题内容二、课题要求三、课题完成后应提交材料的要求-4-四、主要参考文献（由指导教师选定）同组设计者：无注：1.此任务书由指导教师填写。如不够填写，可另加页。2.此任务书最迟必须在课程设计（论文）开始前下达给学生。学生送交全部材料日期学生（签名）指导教师验收（签名）-5-摘要对于部门调整方案问题，我们可以理解为为了使综合利益最大而采取部门调整措施。本题的综合利益就是经济效益和通讯费用的净收益。对于部门是否迁往Bristol或Brighton这两种状态,选择运用运筹学中的0-1线性规划方法,然后根据部门调整后三地的部门是否存在通讯费用这两种状态，确定另一个0-1线性规划方法，故该问题是一个二次指派问题。列出目标函数和约束方程，建立数学模型,最后利用LINGO软件得出最优方案。最优方案：部门ABCDE校区安排BristolBrightonBrightonBristolBrighton关键词:0-1线性规划部门调整LINGO软件AbstractTotheproblemofadjustingdepartment.wecanunderstandthatitisameasureinordertogetthemostcomprehensivebenefits.Thecomprehensivebenefitisnetincomeofeconomicbenefitsandthecostsofcommunicationinthisquestion.Wecanselectusing0-1linearprogramminginoperationalresearchmethodfordepartmentwhethertomovetoBristolorBrightonthistwokindsofstate,andthenaccordingtothedepartmentofthreedepartmentsadjustedwhetherthereisacommunicationcostthesetwokindsofstatetodecidea0-1linearprogrammingmethod,sotheproblemisaquadraticassignmentproblem.Listtheobjectivefunctionandconstraintequation,mathematicalmodelissetup,WecangettheoptimalsolutionfinallybyusingLINGOsoftware.Theoptimalsolution:departmentABCDECampustoarrangeBristolBrightonBrightonBristolBrightonKeywords:0-1linearprogrammingdepartmentadjusttheLINGOsoftware-6-一、问题重述伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。公司由五个部门组成，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,5j=1,2,3-7-Cik：第i个部门与第k个部门每年的通信量i，k=1,2,3,4,5Djl：第j个区与第l个区的通讯单价j，l=1,2,3M：目标函数五、模型建立与求解模型建立1、变量假设xij1，如果第i各部门迁往第j个城市0，否则i=1,2,3,4,5，j=1,2,3yijkl=1，如果xij1且xkl=10，否则i=1,2,3,4,5,j,l=1,2,32、问题建模1)约束函数每个部门要么原地不动，要么迁往某个城市，131jijxi=1,2,3,4,5由于五个部门中一些部门计划迁往Bristol或Brighton市，而每个城市允许接收（包括原地不动）的部门不能超过三个，有351iijxj=1,2,3现在考虑目标函数中二次乘积项xxklij，引进变量yijkl，并满足yijkl=1xij1，xkl=1和xij1，xkl=1yijkl=1上述两个条件等价于如下约束100yxxxyxyijklklijklijklijijkli=1,2,3,4,5j，l=1,2,3ki-8-2)目标函数yDCxBijklilijiklikiijjijyxf51315315131,3)0-1线性规划问题：Max51i31jBijXij-51i31j5ik31lCikDilYijklS.t.311jXiji=1,2,3,4,5513iXijj=1,2,3Yijkl-Xij=0i=1,2,3,4,5j,l=1,2,3,kiYijkl-Xkl=0i=1,2,3,4,5j,l=1,2,3,kiXij+Xkl-Yijkl=1i=1,2,3,4,5j,l=1,2,3,kiXij=0或1i=1,2,3,4,5j=1,2,3Yijkl=0或1i，k=1,2,3,4,5j,l=1,2,3模型求解利用LINGO软件求解其最大值:运行结果:Localoptimalsolutionfound.Objectivevalue:-21.90000Objectivebound:-21.90000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:7VariableValueReducedCostC(1,1)0.0000000.000000C(1,2)0.0000000.000000C(1,3)0.0000000.000000C(1,4)0.0000000.000000C(1,5)0.0000000.000000C(2,1)10.000000.000000C(2,2)13.000000.000000C(2,3)10.000000.000000C(2,4)20.000000.000000C(2,5)8.0000000.000000C(3,1)10.000000.000000C(3,2)28.000000.000000-9-C(3,3)14.000000.000000C(3,4)16.000000.000000C(3,5)15.000000.000000X(1,1)0.0000000.000000X(1,2)0.00000014.80000X(1,3)0.0000008.900000X(1,4)0.0000004.400000X(1,5)0.0000004.500000X(2,1)1.000000-17.00000X(2,2)0.0000000.000000X(2,3)0.0000007.900000X(2,4)1.000000-18.10000X(2,5)0.0000000.1000000X(3,1)0.0000005.200000X(3,2)1.0000000.000000X(3,3)1.0000000.000000X(3,4)0.0000000.000000X(3,5)1.0000000.000000A(1,2)0.0000000.000000A(1,3)1.0000000.000000A(1,4)1.5000000.000000A(1,5)0.0000000.000000A(2,3)1.4000000.000000A(2,4)1.1000000.000000A(2,5)0.0000000.000000A(3,4)0.0000000.000000A(3,5)2.0000000.000000A(4,5)0.80000000.000000B(1,1)10.000000.000000B(1,2)13.000000.000000B(1,3)9.0000000.000000B(2,1)13.000000.000000B(2,2)5.0000000.000000B(2,3)14.000000.000000B(3,1)9.0000000.000000B(3,2)14.000000.000000B(3,3)5.0000000.000000RowSlackorSurplusDualPrice1-21.90000-1.00000020.000000-28.5000030.000000-12.1000040.000000-34.7000050.000000-32.20000-10-60.000000-23.9000071.0000000.00000080.00000017.70000X12=1,X33=1,X42=1,X23=1,X53=1f=21900即：部门ABCDE调整方案BristolBrightonBrightonBristolBrighton六、模型的评价与推广部门调整方案模型主要运用了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-11-data:a=01.01.501.41.1002.00.8;b=10139135149145;c=000001013102081028141615;enddatamin=@sum(link1(m