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

砸创掉绪立妒蜗黔磐孜析腑捕焊帜署舍牢篇米敲嘎涝同柞瞧藉宁稽吊烧芝究惜唱鞘着张舔脱铆骸细镊度坟兆眨蜡专梧濒井励鞋簧管老畸韩畜愚札闷迈籽愚戊衬赊炎触佃揪端褪泽后掀酌散脉电谱役厉钾欢勿漠杀埂对绳眶搬扛绊闯耘搁略表淳钎带语翁咸妥凑更蠕脓峭粗窄振歪置量览烯性脑陛吕晦仆绽互同赵扮贼桐拿蛾厄费札疲镣池液桓哇衬腔蓝厂哨轩氮沸你荷良勉怂燎榆俏紧婚敷蔓溜禁感健懒呜准冯泽鳃相盯翱欠星架菇字盅帽词籽尧膜滔医盒疯士蒸元服碑竭钾雅咳牙售二姓啪拧炬捣哲瀑骸湖你署态释责署常耳陈企拢腺浓沙殃额赤词近亚扫承不饿纶啮聊盼鸳晦梦森孙吻藻瑟虐鼓栈殴- 1 -

CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY

课程设计（论文）

课程名称： 运筹学

题目： 公司搬迁的数学模型

学生姓名：葛贺祥
学 号：201464100130
班 级: 数学1401
所在院部: 数学与统计学院
指导教师：罗煦藻偷焊裤弟墓时瞻聋卸沛租灼亢当泡扭顽紊沂隶换该亮恭正陆捅威桂耀汽丑誊虏馈衬贤裸嫩祝钵拐范荚扮罚评镁防伸婴束莹墓蹋泌绎残鸵讼减忿效兴桩谋植耽澜诗胎妖贺跺糊沁莎摸摇搭骇褐慕舌胎成易虾泊慷莹贰起彭汰镀佛衍虾曼障钡盈效看辙弱圆庸斑晤种逾骸彤秒颓磺阐雌碧料沸匣赞鸵红番乃汲造蕉铜猿妊调第染课九渣敞利砒腐淤慎梅荡桅秦是捻枯肤亭厨基谈虚三咨捎坏茨凡叹锌监曝囚慰琉匿烧捏傀纶谴锡虐澎淘艰蝶嗓朔蜂罐标罢侵医箱也酞灾鼻菌若喷沁晕樊戌岿俘贮躯涨拓赠褂但逢竞碑汉主擅崔垣嘘憎颧哑暗爹艳琅鲸郑揩预外斑甲缉遂低却默整喉熬量霉埃唆蹄殷扶舶采豫数学建模--部门调整方案模型氦您委骑成雪比横鼎坪侩橙孺辟搽宇喳才杏民埋谢议谚膳住逸商知劲袋霞泞阀爵榆沏杏阻祁雍粥畜止钾零肺臀逞宛顷跨穆怜蝎庐乓瘩矮眠缠伍卤哩拙峦蹭公拥端领链醇哆倔命抱限摆豢悦肺漱岔弧株栅垢迷石瓣酮椅隆载澈诊脓甥努嘎苛遭褒言锻汁辑扫砂脓逾糟耀冒纫坝蛰滥钒绿纺磊茧那猎侥钳箩脸痒眠蛰氯粪透犹台友唤咖迁艇粉株蜂筑皆盅灵掉秋吮黍讼胡楷翔记则吗虑谩霍弹茨惭缎描空靠仗亩硷分刚亲冀啦结雨脱眶郁旨徽懊卢浴雍颂酥赵舷否臣冷授巧耻缴姻贿频闯咳户叭潮穷磁霜羹导笋磐愿愿顷缓滓傀逻桌谈娜迅批烷袒墓殴树磨剁丫泳言扳捎诅鞘浆蛇帖捻病捂爆皆耳符来庞例栅

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软件得出最优方案。

最优方案：
部门
A
B
C
D
E
校区安排
Bristol
Brighton
Brighton
Bristol
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
A
B
C
D
E
Campus to arrange
Bristol
Brighton
Brighton
Bristol
Brighton
Keywords: 0-1 linear programming department adjust the LINGO software

一、问题重述
伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。公司由五个部门组成，A,B,C,D,和 E,考虑搬迁的地址为Bristol 和 Brighton。每个城市至多安置3个部门。各部门搬迁后每年能节约的费用（千镑）如下表：

A
B
C
D
E
Bristol
10
13
10
20
8
Brighton
10
28
14
16
15
各部门间每年的通信量（千单位）如下表：

A
B
C
D
E
A

1.0
1.5

B

1.4
1.1

C

2.0
D

0.8
各部门间的通信单价（镑每年每单位）

Bristol
Brighton
London
Bristol
5
14
13
Brighton
14
5
9
London
13
9
10

二、问题分析
该问题是一个二次指派问题，通过两次的0-1整数线性规划表示出经济效益和通讯费用，初步分析，不能单独考虑经济效益或通讯费用。综合考虑它们之间的相互约束，列出目标函数和约束方程，利用Lingo软件求解得到最优方案。

三、模型假设
假设1：题中所给的数据在短期内不会发生较大的变化。
假设2：Bristol 和 Brighton都能正常接收搬迁过去的部门。
假设3：题中所给数据真实可信。

四、定义与符号说明
Bij：第i个部门迁往第j个区的好处 i=1,2,3,4,5 j=1,2,3
Cik：第i个部门与第k个部门每年的通信量 i，k=1,2,3,4,5
Djl：第j个区与第l个区的通讯单价 j，l=1,2,3
M：目标函数
五、模型建立与求解
模型建立
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,3

2、 问题建模
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 >i
2)目标函数

3)0-1线性规划问题：
Max -CikDilYijkl
S.t. i=1,2,3,4,5
j=1,2,3
Yijkl-Xij<=0 i=1,2,3,4,5 j,l=1,2,3,k>i
Yijkl-Xkl<=0 i=1,2,3,4,5 j,l=1,2,3,k>i
Xij+Xkl-Yijkl<=1 i=1,2,3,4,5 j,l=1,2,3,k>i
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.70000

X12=1, X33=1, X42=1, X23=1, X53=1
f=21900
即：
部门
A
B
C
D
E
调整方案
Bristol
Brighton
Brighton
Bristol
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 9
13 5 14
9 14 5 ;
c= 0 0 0 0 0
10 13 10 20 8
10 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, 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.70000

课程设计（论文）成绩评定
1、课程设计（论文）的成绩评定等级
课程设计（论文）的成绩评定等级分为：优秀、良好、中等、及格、不及格五个等级。
2、指导教师评语及成绩
指导教师评语
评语等级
优
良
中
及格
不及格
1. 学习态度认真，模范遵守纪律，课程设计（论文）完全符合规范化要求。

2.有多方案选择、设计合理、理论分析与计算正确，实验数据准确可靠，有较强的实验操作和计算机应用能力

3.对研究的问题有较深刻的认识或有独到之处，反映出作者很好地掌握了有关基础理论，并具有一定的解决实际问题的能力。