发布时间 : 星期三 文章实验报告数学建模更新完毕开始阅读
《数学建模实验》实验报告
学号： 姓名： 实验七：图论3 1. 某产品从仓库运往市场销售，已知各仓库的可供量、各市场需求量及从i仓库至j市场的路径的运输能力如下表所列(表中数字0代表无路)，试求从仓库可运往市场的最大流量，各市场需求能否满足？ 仓库i 1 2 3 4 可供量 市场j A B C 需求量 30 0 20 20 10 0 10 20 0 10 40 60 40 50 5 20 20 20 100 解答： 将仓库（A,B,C）到市场j(j=1…4)，按交通图用弧连接，并标上容量，再虚设一个发点s和一个收点t，形成以下网络流。问题转化成求S到T的最大流， Lingo程序如下 model: sets: nodes/s,a,b,c,1,2,3,4,t/; arcs(nodes,nodes)/s a,s b,s c,a 1,a 2,a 4,b 3,b 4,c 1,c 2,c 3,c 4,1 t,2 t,3 t,4 t/:c,f; endsets data: c=20 20 100 30 10 40 10 50 20 10 40 5 20 20 60 20; enddata n=@size(nodes);!顶点的个数; max=flow; @for(nodes(i)|i #ne#1 #and# i #ne# n: @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i))); @sum(arcs(i,j)|i #eq# 1:f(i,j))=flow; @sum(arcs(i,j)|i #eq# n:f(i,j))=flow; @for(arcs:@bnd(0,f,c)); end 结果分析： 最大流为110，不满足C的供求量。其中市场 3 只能满足 50 单位，差 10 单位。 2. 某单位招收懂俄、英、日、德、法文的翻译各一名，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？ 解答： 将 5 个人与 5 个语种分别用点表示，把各个人与懂得的外语语种之间用 弧相连。为了求单源和单汇网络的最大流，再加一个虚拟的单源 vs,vs 与 5 个人 之间各有一条弧，再加一个虚拟的单汇 vt，在 5 个外语语种和 vt 之间各有一条 弧。规定每条弧的容量为 1，求出上述网络的最大流数字即为最多能得到招聘的 人数。计算时把源点 vs,甲乙丙丁戊 5 个人，俄英日德法 5 个外语语种和汇点 vt 分别编号为 1,2,...,12. Matlab程序如下 clc,clear a=zeros(12); a(1,[2:6])=1; a(2,[8,9])=1; a(3,[7,8,10])=1; a(4,[8,9])=1; a(5,[8,9])=1; a(6,[10,11])=1; a([7:11],12)=1; a=sparse(a); [b,c]=graphmaxflow(a,1,12) 运行结果: b =4 c = (1,3) 1 (1,4) 1 (1,5) 1 (1,6) 1 (3,7) 1 (5,8) 1 (4,9) 1 (6,10) 1 (7,12) 1 (8,12) 1 (9,12) 1 (10,12) 1 结果分析 求得只有 4 个人得到招聘，乙—俄,丁—英,丙—日,戊—德,甲未能得到应聘. 3. 将下表所列的某运输问题的相关数据转化为最小费用最大流问题，画出网络图并求解。 产地 1 2 3 产量 销地 A B 销量 20 30 4 24 22 5 5 20 6 8 7 解答：构造网络图如图所示：加一个虚拟的源点 S，一个虚拟的汇点T，得到的网络图如图,其中弧旁的第一个数字为单位流的费用,第二数字表示容量. Matlab程序如下： n=7 C=zeros(7) C(1,[2,3])=[8,7] C(2,[4,5,6])=[8,8,8] C(3,[4,5,6])=[7 7 7] C(4,7)=4 C(5,7)=5 C(6,7)=6 运行结果 wf = 15 No = 8 0 0 0 0 0 0 结果分析 得到最大流为15 再建立求最小费用的线性规划模型，求最小费用的Lingo程序如 下： model: sets: nodes/s,a,b,1,2,3,t/:d; arcs(nodes,nodes)/s a,s b,a 1,a 2,a 3,b 1,b 2,b 3,1 t,2 t,3 t/:b,c,f; endsets data: b=0 0 20 24 5 30 22 20 0 0 0; c=8 7 8 8 8 7 7 7 4 5 6; d=15 0 0 0 0 0 -15; !最大流为 15; enddata n=@size(nodes); !顶点的个数; min=@sum(arcs:b*f); @for(nodes(i):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i)); @for(arcs:@bnd(0,f,c)); end 结果分析： 求得最小费用为240。 4. 从网上搜索2000B及2005DVD在线租赁问题相关论文，学习并试着实现程序。