运筹学课程设计报告书专业班级：信息与计算科学10-1班姓名：指导教师：日期：2012/07/12黑龙江工程学院数学系2012年07月12日一．课程设计的目的和意义运筹学是一门多学科的定量优化技术，为了从理论与实践的结合上，提高学生应用运筹学方法与计算机软件的独立工作能力，本着“突出建模，结合软件，加强应用”的指导思想，以学生自己动手为主，对一些实际题目进行构模，再运用计算机软件进行求解，对解进行检验和评价，写出课程设计报告。

二．课程设计的时间本课程设计时间1周。

三．课程设计的基本任务和要求由于不同的同学选择的方向不同，因此给出如下两种要求，完成其一即可：1．选择建模的同学：利用运筹学基本知识对所选案例建立合适的数学模型，然后利用winQSB、LINDO、LINGO或者其它数学软件进行求解；2．选择编程的同学：根据运筹学基本原理以及所掌握的计算机语言知识，对于运筹学中部分算法编写高级语言的具有可用性的程序软件。

四．课程设计的问题叙述网络中的服务及设施布局长虹街道今年来建立了11个居民小区,各小区的大致位置及相互间的道路距离(单位: 100 m)如图所示，各居民小区数为：①3000，②3500，③3700，④5000，⑤30000，⑥2500，⑦2800，⑧4500，⑨3300，⑩4000，○113500。

试帮助决策：（a）在11个小区内准备共建一套医务所、邮局、储蓄所、综合超市等服务设施，应建于哪一小区，使对居民总体来说感到方便；（b）电信部门拟将宽带网铺设到各小区，应如何铺设最为经济；（c）一个考察小组从①出发，经⑤、⑧、⑩小区（考察顺序不限），最后到小区⑨再离去，试帮助选择一条最短的考察路线。

五． 模型的假设与建立1、对于问题（a ）,用最短距离的矩阵算法建立邻接矩阵用matlab 求解。

定义ij d 为图中相邻点的距离，若i 与j 不相邻，令ij d =inf(表示无穷)，由此⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=Inf 665Inf Inf Inf Inf Inf Inf Inf 6InfInf Inf 5Inf Inf Inf Inf Inf Inf 6InfInf 4Inf 76Inf Inf Inf Inf 5Inf 4Inf 4Inf 86Inf Inf Inf Inf 5Inf 4Inf Inf Inf Inf Inf Inf 8Inf Inf7Inf Inf Inf 4Inf 5Inf Inf Inf Inf68Inf 4Inf 56Inf Inf Inf InfInf 6Inf Inf 5Inf Inf 56Inf InfInf Inf Inf 56Inf Inf 7Inf Inf InfInf Inf Inf Inf Inf 57Inf 4Inf InfInf Inf 8Inf Inf 6Inf 40D 的矩阵表明从i 点到j 点的直接最短距离。

通过程序求解得到最后矩阵为：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=106659131211181617610129519171523171361284876101215165948411861411129584815121018128131971115849512151217681248561011111510610951011561823121418561110711161715111212105784171316128151161140D D 中的元素ij d 表明网络图中从i 到j 的最短距离，即从① ○11最短距离为17. 因为要在11个小区内建一套服务设施，已知各居民小区数为：①3000，②3500，③3700，④5000，⑤30000，⑥2500，⑦2800，⑧4500，⑨3300，⑩4000，○113500，要想使居民方便只需居民的总路程最短，即只需将上述计算得到D 的所有行分别乘各个小区的居民数，则乘积的数字为假定建立服 务设施时小区的居民所走的路程。

小区建服务设施地点时居民所走的路程 ①② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ○11 014000 40700 30000 33000 37500 22400 54000 52800 52000 59500 1200028000 25900 25000 30000 30000 33600 49500 49500 68000 56000 3300024500 37000 55000 18000 12500 50400 63000 39600 92000 63000 1800017500 40700 50000 15000 22500 28000 27000 33000 60000 38500 3300035000 22200 25000 24000 10000 33600 36000 19800 68000 42000 4500042000 18500 45000 12000 20000 42000 49500 23100 76000 45500 2400042000 66600 50000 36000 37500 22400 18000 26400 20000 31500 3600038500 51800 30000 24000 27500 11200 36000 13200 36000 17500 4800052500 44400 50000 18000 17500 22400 18000 26400 48000 21000 3900059500 85100 75000 51000 47500 14000 40500 39600 40000 21000 5100056000 66600 55000 36000 32500 25200 22500 19800 24000 35000 339000 409500 499500 490000 297000 295000 305200 414000 343200 584000430500由表中最后一行可，应服务设施应建在⑥小区。

2、对于问题（2）电信部门拟将宽带网铺设到各小区，铺设最为经济应该在图中找一个最小树，按照最小树铺设最小最小距离为47。

最小树如下：3、对于问题（c），在问题一中求得的D矩阵分别是各个小区之间的最短路。

考察小组从①出发，经⑤、⑧、⑩小区（考察顺序不限），最后到小区⑨再离去，要想达到目的可以从①出发，根据矩阵D找到，到⑤、⑧、⑩得最短路径①④⑤，再从⑤小区出发到⑧、⑩的最短路径⑤⑧同理找到⑨、⑩即⑧⑦⑩○11○11⑨. 六．模型求解（一）、对于问题（a）求解程序：D=[0 4 inf 6 inf inf 8 inf inf inf inf;4 inf 7 5 inf inf inf inf inf inf inf;inf 7 inf inf 6 5 inf inf inf inf inf;6 5 inf inf 5 inf inf 6 inf inf inf;inf inf 6 5 inf 4 inf 8 6 inf inf;inf inf 5 inf 4 inf inf inf 7 inf inf;8 inf inf inf inf inf inf 4 inf 5 inf;inf inf inf 6 8 inf 4 inf 4 inf 5;inf inf inf inf 6 7 inf 4 inf inf 6;inf inf inf inf inf inf 5 inf inf inf 6;inf inf inf inf inf inf inf 5 6 6 inf];n=length(D);for k=1:nfor i=1:nfor j=1:nif 0<D(i,k) & 0<D(k,j)if D(i,j)==0 & i~=jD(i,j)=D(i,k)+D(k,j);ElseD(i,j)=min(D(i,j),D(i,k)+D(k,j));endendendendendm=[3000 3500 3700 5000 3000 2500 2800 4500 3300 4000 3500];for i=1:11;z(:,i)=D(i,:)*m(i)endfor i=1:11;z(12,i)=sum(z(1:11,i))endmin(12,:)（二）、对于问题（b）的求解程序：model:sets:nodes/1..11/:d;roads(nodes,nodes):w,x,p;endsetsdata:w=0 4 999999 6 999999 999999 8 999999 999999 999999 9999994 0 75 999999 999999 999999 999999 999999 999999 999999999999 7 0 999999 6 5 999999 999999 999999 999999 9999996 5 999999 0 5 999999 999999 6 999999 999999 999999999999 999999 6 5 0 4 999999 8 6 999999 999999999999 999999 5 999999 4 0 999999 999999 7 999999 9999998 999999 999999 999999 999999 999999 0 4 999999 5 999999999999 999999 999999 6 8 999999 4 0 4 999999 5999999 999999 999999 999999 6 7 999999 4 0 999999 6999999 999999 999999 999999 999999 999999 5 999999 999999 0 6999999 999999 999999 999999 999999 999999 999999 5 6 6 0; enddatan=@size(nodes);min=@sum(roads(i,j)|i#ne#j:w(i,j)*x(i,j)); !目标函数;@sum(nodes(i)|i#gt#1:x(1,i))>=1; !根至少有一个出口;@for(nodes(i)|i#gt#1:@sum(nodes(j)|j#ne#i:x(j,i))=1; !除根外的点只允许有一个入口;@for(nodes(j)|j#gt#1#and#j#ne#i:d(j)>=d(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i););@bnd(1,d(i),999999);d(i)<=n-1-(n-2)*x(1,i); !限制构成圈;);@for(roads:@bin(x)); !零一化;end计算结果为：Global optimal solution found.Objective value: 47.00000Objective bound: 47.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 61Variable Value Reduced Cost X( 1, 1) 0.000000 0.000000 X( 1, 2) 1.000000 4.000000 X( 1, 3) 0.000000 999999.0 X( 1, 4) 0.000000 6.000000 X( 1, 5) 0.000000 999999.0 X( 1, 6) 0.000000 999999.0 X( 1, 7) 0.000000 8.000000 X( 1, 8) 0.000000 999999.0 X( 1, 9) 0.000000 999999.0 X( 1, 10) 0.000000 999999.0 X( 1, 11) 0.000000 999999.0 X( 2, 1) 0.000000 4.000000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 7.000000 X( 2, 4) 1.000000 5.000000 X( 2, 5) 0.000000 999999.0 X( 2, 6) 0.000000 999999.0 X( 2, 7) 0.000000 999999.0 X( 2, 8) 0.000000 999999.0 X( 2, 9) 0.000000 999999.0 X( 2, 10) 0.000000 999999.0 X( 2, 11) 0.000000 999999.0 X( 3, 1) 0.000000 999999.0 X( 3, 2) 0.000000 7.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 999999.0 X( 3, 5) 0.000000 6.000000 X( 3, 6) 0.000000 5.000000 X( 3, 7) 0.000000 999999.0 X( 3, 8) 0.000000 999999.0 X( 3, 9) 0.000000 999999.0 X( 3, 10) 0.000000 999999.0 X( 3, 11) 0.000000 999999.0X( 4, 2) 0.000000 5.000000 X( 4, 3) 0.000000 999999.0 X( 4, 4) 0.000000 0.000000 X( 4, 5) 1.000000 5.000000 X( 4, 6) 0.000000 999999.0 X( 4, 7) 0.000000 999999.0 X( 4, 8) 1.000000 6.000000 X( 4, 9) 0.000000 999999.0 X( 4, 10) 0.000000 999999.0 X( 4, 11) 0.000000 999999.0 X( 5, 1) 0.000000 999999.0 X( 5, 2) 0.000000 999999.0 X( 5, 3) 0.000000 6.000000 X( 5, 4) 0.000000 5.000000 X( 5, 5) 0.000000 0.000000 X( 5, 6) 1.000000 4.000000 X( 5, 7) 0.000000 999999.0 X( 5, 8) 0.000000 8.000000 X( 5, 9) 0.000000 6.000000 X( 5, 10) 0.000000 999999.0 X( 5, 11) 0.000000 999999.0 X( 6, 1) 0.000000 999999.0 X( 6, 2) 0.000000 999999.0 X( 6, 3) 1.000000 5.000000 X( 6, 4) 0.000000 999999.0 X( 6, 5) 0.000000 4.000000 X( 6, 6) 0.000000 0.000000 X( 6, 7) 0.000000 999999.0 X( 6, 8) 0.000000 999999.0 X( 6, 9) 0.000000 7.000000 X( 6, 10) 0.000000 999999.0 X( 6, 11) 0.000000 999999.0 X( 7, 1) 0.000000 8.000000 X( 7, 2) 0.000000 999999.0 X( 7, 3) 0.000000 999999.0 X( 7, 4) 0.000000 999999.0 X( 7, 5) 0.000000 999999.0 X( 7, 6) 0.000000 999999.0 X( 7, 7) 0.000000 0.000000 X( 7, 8) 0.000000 4.000000 X( 7, 9) 0.000000 999999.0 X( 7, 10) 1.000000 5.000000 X( 7, 11) 0.000000 999999.0X( 8, 2) 0.000000 999999.0 X( 8, 3) 0.000000 999999.0 X( 8, 4) 0.000000 6.000000 X( 8, 5) 0.000000 8.000000 X( 8, 6) 0.000000 999999.0 X( 8, 7) 1.000000 4.000000 X( 8, 8) 0.000000 0.000000 X( 8, 9) 1.000000 4.000000 X( 8, 10) 0.000000 999999.0 X( 8, 11) 1.000000 5.000000 X( 9, 1) 0.000000 999999.0 X( 9, 2) 0.000000 999999.0 X( 9, 3) 0.000000 999999.0 X( 9, 4) 0.000000 999999.0 X( 9, 5) 0.000000 6.000000 X( 9, 6) 0.000000 7.000000 X( 9, 7) 0.000000 999999.0 X( 9, 8) 0.000000 4.000000 X( 9, 9) 0.000000 0.000000 X( 9, 10) 0.000000 999999.0 X( 9, 11) 0.000000 6.000000 X( 10, 1) 0.000000 999999.0 X( 10, 2) 0.000000 999999.0 X( 10, 3) 0.000000 999999.0 X( 10, 4) 0.000000 999999.0 X( 10, 5) 0.000000 999999.0 X( 10, 6) 0.000000 999999.0 X( 10, 7) 0.000000 5.000000 X( 10, 8) 0.000000 999999.0 X( 10, 9) 0.000000 999999.0 X( 10, 10) 0.000000 0.000000 X( 10, 11) 0.000000 6.000000 X( 11, 1) 0.000000 999999.0 X( 11, 2) 0.000000 999999.0 X( 11, 3) 0.000000 999999.0 X( 11, 4) 0.000000 999999.0 X( 11, 5) 0.000000 999999.0 X( 11, 6) 0.000000 999999.0 X( 11, 7) 0.000000 999999.0 X( 11, 8) 0.000000 5.000000 X( 11, 9) 0.000000 6.000000 X( 11, 10) 0.000000 6.000000 X( 11, 11) 0.000000 0.000000（三）、对于问题（c）于问题（a）求解程序相同。