求最小费用最大流算法的MATLAB 程序代码如下（算例）：
n=5;
C=[0 15 16 0 0
0 0 0 13 14
0 11 0 17 0
0 0 0 0 8
0 0 0 0 0]; %弧容量
b=[0 4 1 0 0
0 0 0 6 1
0 2 0 3 0
0 0 0 0 2
0 0 0 0 0]; %弧上单位流量的费用
wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值
for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流
while(1)
for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图
for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end
for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值
for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路
for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end
if(pd)break;end;end %求最短路的Ford 算法结束
if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有
向赋权图中不会含负权回路, 所以不会出现k=n
dvt=Inf;t=n; %进入调整过程, dvt 表示调整量
while(1) %计算调整量
if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量
elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量
if(dvt>dvtt)dvt=dvtt;end
if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量
t=s(t);end %继续调整前一段弧上的流f
pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值
t=n;while(1) %调整过程
if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整
elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整
if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程
t=s(t);end
if(pd)break;end %如果最大流量达到预定的流量值
wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量
zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end %计算最小费用
f %显示最小费用最大流
wf %显示最小费用最大流量
zwf %显示最小费用, 程序结束
MATLAB: MATLAB是美国MathWorks公司出品的商业数学软件，用于数据分析、无线通信、深度学习、图像处理与计算机视觉、信号处理、量化金融与风险管理、机器人，控制系统等领域。 MATLAB是matrix&laboratory两个词的组合，意为矩阵工厂（矩阵实验室），软件主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式。 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORTRAN，C++，JAVA的支持。 MATLAB有限元分析与应用:
《MATLAB有限元分析与应用》是2004年4月清华大学出版社出版的图书，作者是卡坦，译者是韩来彬。 内容简介： 《MATLAB有限元分析与应用》特别强调对MATLAB的交互应用，书中的每个示例都以交互的方式求解，使读者很容易就能把MATLAB用于有限分析和应用。另外，《MATLAB有限元分析与应用》还提供了大量免费资源。 《MATLAB有限元分析与应用》采用当今在工程和工程教育方面非常流行的数学软件MATLAB来进行有限元的分析和应用。《MATLAB有限元分析与应用》由简单到复杂，循序渐进地介绍了各种有限元及其分析与应用方法。书中提供了大量取自机械工程、土木工程、航空航天工程和材料科学的示例和习题，具有很高的工程应用价值。
北京联合大学 实验报告 项目名称：运筹学专题实验报告 学院：自动化专业：物流工程 班级：1201B 学号：2012100358081 姓名：管水城成绩：
2015 年 5 月 6 日 实验三：使用matlab求解最小费用最大流算问题 一、实验目的： (1)使学生在程序设计方面得到进一步的训练;，学习Matlab语言进行程序设计求解最大流最小费用问题。 二、实验用仪器设备、器材或软件环境 计算机, Matlab R2006a 三、算法步骤、计算框图、计算程序等 1.最小费用最大流问题的概念。 在网络D(V,A)中,对应每条弧(vi,vj)IA,规定其容量限制为cij(cij\0),单位流量通过弧(vi,vj)的费用为dij(dij\0),求从发点到收点的最大流f,使得流量的总费用d(f)为最小,即mind(f)=E(vi,vj)IA 2.求解原理。 若f是流值为W的所有可行流中费用最小者,而P是关于f的所有可扩充链中费用最小的可扩充链,沿P以E调整f得到可行流fc,则fc是流值为(W+E)的可行流中的最小费用流。 根据这个结论,如果已知f是流值为W的最小费用流,则关键是要求出关于f 的最小费用的可扩充链.为此,需要在原网络D的基础上构造一个新的赋权有向图E(f),使其顶点与D的顶点相同,且将D中每条弧(vi,vj)均变成两个方向相反的弧(vi,vj)和(vj,vi)1新图E(f)中各弧的权值与f中弧的权值有密切关系,图E(f)中各弧的权值定义为：
新图E(f)中不考虑原网络D中各个弧的容量cij.为了使E(f)能比较清楚,一般将长度为]的弧从图E(f)中略去.由可扩充链费用的概念及图E(f)中权的定义可知,在网络D中寻求关于可行流f的最小费用可扩充链,等价于在图E(f)中寻求从发点到收点的最短路.因图E(f)中有负权,所以求E(f)中的最短路需用Floyd算法。 1.最小费用流算法的框图描述。 图一 2.计算最小费用最大流MATLAB源代码,文件名为mp_mc.m function[Mm,mc,Mmr]=mp_mc(a,c) A=a; %各路径最大承载流量矩阵 C=c; %各路径花费矩阵 Mm=0; %初始可行流设为零 mc=0; %最小花费变量 mcr=0; mrd=0;
1459:Power Network Time Limit: 2000MS Memory Limit: 32768K Total Submissions: 17697 Accepted: 9349 Description A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l max(u,v) of power delivered by u to v. Let Con=Σu c(u) be the power consumed in the net. The problem is to compute the maximum value of Con. An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6. Input There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n (consumers), and 0 <= m <= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0 <= z <= 1000 is the value of l max(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0 <= z <= 10000 is the value of p max(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0 <= z <= 10000 is the value of
有限元的MATLAB解法 1.打开MATLAB。 2.输入“pdetool”再回车，会跳出PDE Toolbox的窗口（PDE意为偏微分方程，是partial differential equations的缩写），需要的话可点击Options菜单下Grid命令，打开栅格。 3.完成平面几何模型：在PDE Toolbox的窗口中，点击工具栏下的矩形几何模型进行制作模型，可画矩形R，椭圆E，圆C，然后在Set formula栏进行编辑并（如双脊波导R1+R2+R3改为RI-R2-R3,设定a、b、s/a、d/b的值从而方便下步设定坐标） 用算术运算符将图形对象名称连接起来，若还需要，可进行储存，形成M文件。 4.用左键双击矩形进行坐标设置：将大的矩形left和bottom都设为0，width是矩形波导的X轴的长度，height是矩形波导的y轴的长度，以大的矩形左下角点为原点坐标为参考设置其他矩形坐标。 5.进行边界设置：点击“Boundary”中的“Boundary Mode”,再点击
“Boundary”中的“Specify Boundary Conditions”,选择符合的边界条件，Neumann为诺曼条件,Dirichlet为狄利克雷条件，边界颜色显示为红色。 6.进入PDE模式：点击"PDE"菜单下“PDE Mode”命令，进入PDE 模式，单击“PDE Specification”,设置方程类型，“Elliptic”为椭圆型，“Parabolic”为抛物型，“Hyperbolic”为双曲型，“Eigenmodes”为特征值问题。 7.对模型进行剖分：点击“Mesh”中“Initialize Mesh”进行初次剖分，若要剖的更细，再点击“Refine Mesh”进行网格加密。 8.进行计算：点击“Solve”中“Solve PDE”,解偏微分方程并显示图形解，u值即为Hz或者Ez。 9.单击“Plot”菜单下“Parameters”选项，打开“Plot Selection”对话框。选中Color,Height(3-D plot)和Show mesh三项，然后单击“Plot”按钮，显示三维图形解。 10.如果要画等值线图和矢量场图，单击“Plot”菜单下“Parameters”选项,打开“Plot Selection”对话框。选中Contour和Arrows两项，然后单击Plot按钮，可显示解的等值线图和矢量场图。 11.将计算结果条件和边界导入MATLAB中：点击“Export Solution”,再点击“Mesh”中“Export Mesh”。
算法分析与设计题目：最大流算法 院系：软件工程 班级：软件11-2班 ：慕永利 学号： 23 号
目录 1算法提出背景........................................................... - 3 - 2 问题实例及解决......................................................... - 3 - 3算法论述............................................................... - 4 - 3.1、可行流.......................................................... - 4 - 3.2 最大流.......................................................... - 5 - 3.3最大流算法....................................................... - 6 - 3.3.1 增广路径................................................. - 6 - 3.3.2沿增广路径增广............................................. - 7 - 3.3.3样例：..................................................... - 8 - 3.3.4定理：.................................................... - 13 - 3.3.5算法的实现：.............................................. - 13 - 3.3.6 优化...................................................... - 16 - 4算法应用.............................................................. - 18 -
最大流和最小费用流的作业 1.在下图中A 、B 为发点，分别有50和40单位物资往外发送，D 和E 是为收点，分别需要物资30和60单位，C 为中转站，各弧旁数字为（Cij ，Bij ），求满足上述收发量要求的最小费用流。 解：把问题转化为网络图： (20,90) (50,40) ( 10,20 ) (30,20) (10,30) (40,30) (80,10) 决策变量：设A 运到B 为L1, A 运到C 为L2， A 运到D 为L3，B 运到C 为L4， C 到E 为L5 D 到E 为L6， E 到D 为L7。 目标函数： Min Z=L1×20+L2×40+L3×90+L4×30+L5×10+L6×30+L7×20 约束条件： L1<=10,L2<=50,L3<=20,L4<=40,L5<=80,L6<=30,L7<=20 L1+L2+L3=50 L4=40+L1 L2+L4=L5 L3+L7=30 L5+L6=60 Li 为整数（i=1，2，3，4，5，6，7）； A D B E C
结果如下： 解得L1=0 L2=40 L3=10 L4=40 L5=80 L6=0 L7=20 Min Z=4900 2、下图是描述一个水渠系统，其中R1，R2，R3,代表三个水库，A,B,C,D,E,F,代表水渠的交汇点，T 表示水渠终点的一个城市，水渠各段每日允许通过的最大流量（1000m 3）分别见表6-10和6-11.城市水资源管理部门希望制定一个方案，使每天输送到城市的水流量为最大，请将此问题归结为求最大流问题。 表6-10 到 从 A B C R1 73 65 _ R2 40 50 60 R3 _ 80 70 R1 R2 R3 A D B E T C F
基于Matlab语言的按平面三角形单元划分的结构有限元程序设计 专业：建筑与土木工程 班级：建工研12-2 姓名：韩志强 学号： 471220580
基于Matlab语言的按平面三角形单元划分 结构有限元程序设计 一、有限单元发及Matlab语言概述 1. 有限单元法 随着现代工业、生产技术的发展，不断要求设计高质量、高水平的大型、复杂和精密的机械及工程结构。为此目的，人们必须预先通过有效的计算手段，确切的预测即将诞生的机械和工程结构，在未来工作时所发生的应力、应变和位移因此，需要寻求一种简单而又精确的数值分析方法。有限单元法正是适应这种要求而产生和发展起来的一种十分有效的数值计算方法。 有限元法把一个复杂的结构分解成相对简单的“单元”，各单元之间通过结点相互连接。单元内的物理量由单元结点上的物理量按一定的假设内插得到，这样就把一个复杂结构从无限多个自由度简化为有限个单元组成的结构。我们只要分析每个单元的力学特性，然后按照有限元法的规则把这些单元“拼装”成整体，就能够得到整体结构的力学特性。 有限单元法基本步骤如下： (1)结构离散：结构离散就是建立结构的有限元模型，又称为网格划分或单元划分，即将结构离散为由有限个单元组成的有限元模型。在该步骤中，需要根据结构的几何特性、载荷情况等确定单元体内任意一点的位移插值函数。 (2)单元分析：根据弹性力学的几何方程以及物理方程确定单元的刚度矩阵。 (3)整体分析:把各个单元按原来的结构重新连接起来，并在单元刚度矩阵的基础上确定结构的总刚度矩阵，形成如下式所示的整体有限元线性方程： {}[]{}δ F=① K 式中，{}F是载荷矩阵,[]K是整体结构的刚度矩阵,{}δ是节点位移矩阵。 (4)载荷移置:根据静力等效原理，将载荷移置到相应的节点上，形成节点载荷矩阵。 (5)边界条件处理:对式①所示的有限元线性方程进行边界条件处理。 (6)求解线性方程:求解式①所示的有限元线性方程，得到节点的位移。在该步骤中，若有限元模型的节点越多，则线性方程的数量就越多，随之有限元分析的计算量也将越大。 (7)求解单元应力及应变根据求出的节点位移求解单元的应力和应变。
最大流算法 clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10; c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0
下面的最小费用最大流算法采用的是“基于Floyd最短路算法的Ford和Fulkerson迭加算法”，其基本思路为：把各条弧上单位流量的费用看成某种长度，用Floyd求最短路的方法确定一条自V1至Vn的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。本源码由GreenSim团队原创，转载请注明 function [f,MinCost,MaxFlow]=MinimumCostFlow(a,c,V,s,t) %%MinimumCostFlow.m %最小费用最大流算法通用Matlab函数 %% 基于Floyd最短路算法的Ford和Fulkerson迭加算法 % GreenSim团队原创作品，转载请注明 %% 输入参数列表 %a单位流量的费用矩阵 %c链路容量矩阵 %V最大流的预设值，可为无穷大 %s源节点 %t目的节点 %% 输出参数列表 %f链路流量矩阵 %MinCost最小费用 %MaxFlow最大流量 %% 第一步：初始化 N=size(a,1);%节点数目 f=zeros(N,N);%流量矩阵，初始时为零流 MaxFlow=sum(f(s,:));%最大流量，初始时也为零 flag=zeros(N,N);%真实的前向边应该被记住 for i=1:N for j=1:N if i~=j&&c(i,j)~=0 flag(i,j)=1;%前向边标记 flag(j,i)=-1;%反向边标记 end if a(i,j)==inf a(i,j)=BV; w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代无穷大 end end end if L(end) 在科学技术各领域中，有很多问题都可以归结为偏微分方程问题。在物理专业的力学、热学、电学、光学、近代物理课程中都可遇见偏微分方程。 偏微分方程，再加上边界条件、初始条件构成的数学模型，只有在很特殊情况下才可求得解析解。随着计算机技术的发展，采用数值计算方法，可以得到其数值解。 偏微分方程基本形式 而以上的偏微分方程都能利用PDE工具箱求解。 PDE工具箱 PDE工具箱的使用步骤体现了有限元法求解问题的基本思路，包括如下基本步骤： 1) 建立几何模型 2) 定义边界条件 3) 定义PDE类型和PDE系数 4) 三角形网格划分 5) 有限元求解 6) 解的图形表达 以上步骤充分体现在PDE工具箱的菜单栏和工具栏顺序上，如下 具体实现如下。 打开工具箱 输入pdetool可以打开偏微分方程求解工具箱，如下 首先需要选择应用模式，工具箱根据实际问题的不同提供了很多应用模式，用户可以基于适 当的模式进行建模和分析。 在Options菜单的Application菜单项下可以做选择，如下 或者直接在工具栏上选择，如下 列表框中各应用模式的意义为： ① Generic Scalar：一般标量模式（为默认选项）。 ② Generic System：一般系统模式。 ③ Structural Mech.，Plane Stress：结构力学平面应力。 ④ Structural Mech.，Plane Strain：结构力学平面应变。 ⑤ Electrostatics：静电学。 ⑥ Magnetostatics：电磁学。 ⑦ Ac Power Electromagnetics：交流电电磁学。 ⑧ Conductive Media DC：直流导电介质。 ⑨ Heat Tranfer：热传导。 ⑩ Diffusion：扩散。 可以根据自己的具体问题做相应的选择，这里要求解偏微分方程，故使用默认值。此外，对于其他具体的工程应用模式，此工具箱已经发展到了Comsol Multiphysics软件，它提供了更强大的建模、求解功能。 另外，可以在菜单Options下做一些全局的设置，如下 l Grid：显示网格 l Grid Spacing…：控制网格的显示位置 l Snap：建模时捕捉网格节点，建模时可以打开 l Axes Limits…：设置坐标系围 l Axes Equal：同Matlab的命令axes equal命令 建立几何模型 使用菜单Draw的命令或使用工具箱命令可以实现简单几何模型的建立，如下 各项代表的意义分别为 关于最小费用最大流的解题 这是课本235页的一道习题 题目是：求如下图中网络的最小费用最大流。弧旁数字（Cij,Rij）。 根据之前的例题14 解题过程如下： （1）构造一个对偶网络，按狄克斯屈标号法找到最短路，得到相应的增广链，调整; （2）再次构造一个对偶网络，如下图。在书中曾提到在含负权的的网络中不能运用狄克斯屈标号法，只能用距离矩阵摹乘法。 可是距离矩阵摹乘法做起来确实是比较复杂，因此我在研究已经做过的几个题中发现，我们在计算最小费用最大流的时候，可以用如下方法来解该题。 解: 从S点出发，有三条路，分别到1和2，由于标号为-1的路是反向的，排除。因此，我们选标号比较小的S—1这条路……依次类推，得到一条最短路:S—1—2 —4—3—T。再按之前的解题思路解题。 再得到S—2—4—3—T； 不存在从S到T的最短路，故最大流为f(X*)=4+1=5，c（X′）=3×1+4×2+1×2+2×5+1×4+3×3+1×1=37； （3）重复上面的动作； （4）得到最小费用最大流。 我不喜欢复杂的做题的方法，因此，在做这个题的时候，由于之前提到过的狄克斯屈标号法不能用于含负权的网络图中，所以必须用到距离矩阵摹乘法，而距离矩阵摹乘法确实是很麻烦，又得画表，又得计算。所以，我通过书上的图列推出这样来做这个题。虽然并不一定这种做法是不是对的（我目前只在几个题目 中运用，结果是对的），但我相信这样一个方向是对的，以前的运筹学方法也是前辈们研究出来的。 另外，我还在维普中文网上看到了一篇题为《含负权最短路问题的一个改进标号法》的论文，载要：在不出现负回路的情况下，给出了在赋权的网络图中求两点之间的最短路问题的一个改进标号法，该方法对于网络图中出现负权的情况也有效。最后给出了该算法的数值实验结果。 这篇文章中，提到了对狄克斯屈标号法的在负权网络不能运用的缺陷的改进。 这让我体会到了运筹学学习当中的另一个重要方面：我们不能拘泥于课本上一层不变的解题方法，应多了解运筹学发展的最新动态，掌握有关运筹学的最新知识。通过对其的研究，从而找到更好的方法来解决相关的问题。 这是我在这次作业当中，所获得的心得体会。 从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。 2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例 有限元大作业——钢架结构分析 选题人： 日期：2016年6月2日 目录： 第一章：问题重述 (2) 一、题目内容： (3) 二、题目要求： (3) 第二章：有限元法手工求解 (3) 一、平面两单元离散化 (4) 二、单元分析 (4) 三、单元组装 (6) 四、边界条件引入及组装总体方程 (7) 五、求解整体刚度方程，计算节点2的位移和转角 (7) 六、求节点1、3支撑反力 (8) 七、设定数据，求解结果 (8) 八、绘制轴力图、弯矩图、剪力图 (9) 第三章、matlab编程求解： (11) 一、总体流程图绘制： (11) 二、输入数据： (12) 三、计算单元刚度矩阵： (12) 四、建立总体刚度矩阵： (13) 五、计算未约束点位移： (13) 六、计算支反力： (13) 七、输出数据： (13) 八、编程： (13) 第四章有限元求解 (13) 一、预处理 (13) 二、模型建立： (15) 二、分析计算 (17) 三、求解结果 (18) 四、绘制图像 (19) 第五章结果比较 (22) 第六章心得体会 (22) 第七章附录 (23) 一、matlab程序 (24) 第一章：问题重述 一、题目内容： 图示平面钢架结构 图题目内容 二、题目要求： （1）采用平面梁单元进行有限元法手工求解，要求写出完整的求解步骤，包括： a）离散化：单元编号、节点编号； b）单元分析：单元刚度矩阵，单元节点等效载荷向量； c）单元组长：总体刚度矩阵，总体位移向量，总体节点等效载荷； d）边界条件的引入及总体刚度方程的求解； e）B点的位移，A、C处支撑反力，并绘制该结构的弯矩图、剪力图和轴力图。 （2）编制通用平面钢架分析有限元Matlab程序，并计算盖提，与手工结果进行比较； （3）利用Ansys求解，表格列出B点的位移，A、C处支反力，绘制弯矩图、剪力图和轴力图，并与手算和Matlab程序计算结果比较。 （4）攥写报告，利用A4纸打印； （5）心得体会，并简要说明各成员主要负责完成的工作。 第二章：有限元法手工求解 求最小费用最大流算法的MATLAB 程序代码如下（算例）： n=5; C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 if(dvt>dvtt)dvt=dvtt;end if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量 t=s(t);end %继续调整前一段弧上的流f pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值 t=n;while(1) %调整过程 if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整 elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整 if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end %如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end %计算最小费用 f %显示最小费用最大流 wf %显示最小费用最大流量 zwf %显示最小费用, 程序结束 综合性、设计性实验报告格式 桂林电子科技大学 数学与计算科学学院综合性、设计性实验报告 实验室： 实验日期：2014年12月13日 院（系） 数学与计算科学 年级、专业、班 姓名 成绩 课程 名称 运筹学实验 实验项目 名 称 最小费用最大流（综合实验） 指导 教师 南江霞 教师 评语 教师签名： 年 月 日 一 ，实验目的 1. 掌握最大流及最小费用最大流问题的数学建模； 2. 掌握最大流问题的WinQSB 软件求解和Lingo 软件求解； 3. 掌握最小费用最大流问题问题的的WinQSB 软件求解和Lingo 软件求解。 二，实验原理 1、熟悉建立最大流问题的数学模型； 2、熟悉建立最小费用最大流问题的数学模型； 3、熟悉WinQSB 软件的基本操作。 4、熟悉Lingo 软件建模。 三，使用仪器，材料 WinQSB 软件 Lingo 软件 四，实验内容与步骤 求最大流： 五，实验过程原始记录（数据，图表，计算等） 用WinQSB 软件进行求解 S A B C D T （7，2） （10，10） （5，3） （7，7） （5，1） （8，4） （10，9） （5，3） 用Lingo 软件进行求解 建立数学模型 ()()()(),max max ,,min ,..0,0,,ij ij i j A ij ji j V j V i j A j i A ij ij e f f i S s t f f f i T i S T f c i j A ∈∈∈∈∈=??-=-=??≠?≤≤∈∑∑∑ model : sets : nodes/S,A,B,C,D,T/; arcs(nodes,nodes)/ S,A S,B A,B,A,C B,C,B,D C,D,C,T D,T/:C,f; endsets data: C=7 10 5 7 5 8 7 10 5; enddata max=flow; @for(nodes(i)|i#ne#1#and#i#ne#@size(nodes): @sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0); @sum(arcs(i,j)|i#eq#1:f(i,j))=flow; @sum(arcs(i,j)|j#eq#@size(nodes):f(i,j))=flow; @for(arcs:@bnd(0,f,C)); end Global optimal solution found. Objective value: 15.00000 Infeasibilities: 0.000000 Total solver iterations: 4 Variable Value Reduced Cost FLOW 15.00000 0.000000 C( S, A) 7.000000 0.000000 C( S, B) 10.00000 0.000000 C( A, B) 5.000000 0.000000 C( A, C) 7.000000 0.000000 C( B, C) 5.000000 0.000000 C( B, D) 8.000000 0.000000 C( C, D) 7.000000 0.000000 C( C, T) 10.00000 0.000000 C( D, T) 5.000000 0.000000 F( S, A) 7.000000 0.000000 F( S, B) 8.000000 0.000000 F( A, B) 0.000000 0.000000 F( A, C) 7.000000 0.000000 F( B, C) 3.000000 0.000000 F( B, D) 5.000000 0.000000 F( C, D) 0.000000 0.000000 F( C, T) 10.00000 -1.000000 F( D, T) 5.000000 -1.000000 S到T的最大流=15 六，实验结果分析或总结 利用Matlab进行有限单元法计算结果的可视化显示 摘要 本文用一个简单的例子给出了用Matlab进行有限单元法计算结果可视化显示的方法。采用Matlab进行可视化显示，可以在获得较好的可视化显示效果的基础上，节省科研人员的大量时间和精力。 关键字：有限元，后处理，可视化，Matlab 有限单元法是工程数值分析的有力工具，可以应用于固体力学、结构分析、温度场模拟等诸多领域。有限单元法一般可以分为前处理、计算以及后处理三部分，市场上现有的有限元商业软件都提供了这三部分功能模块。但有时，由于各种原因，科研人员必须自行编写有限元分析程序，作者通过自身实践，认为Matlab可以较好的进行有限单元法计算结果的可视化显示。 Matlab由美国MathWorks公司开发，历经二十多年的发展，现已成为国际公认的优秀科技应用软件之一，在机械、航天、医药等多个科研、工程领域有着广泛的应用。Matlab 本身具有丰富的可视化显示手段，但遗憾的是，目前对于Matlab的应用研究主要集中在其强大的科学计算能力方面，而对科学计算结果的可视化显示，尤其对由空间点云构成的形体的可视化显示研究涉及甚少，作者通过查阅相关资料，以及探索和实践，成功地进行了三维形体有限元分析结果的可视化显示。 1.准备数据 针对Matlab对空间点云构成形体的数据格式要求，必须重新编排有限元分析中前处理部分以及计算部分所获得的数据。下面以空间单位立方体为例，介绍Matlab对数据文件格式的要求。 若有空间单位正方体，将其划分为四面体网格，图1为该正方体的节点编号及其网格拓朴结构，表1为节点的坐标值以及节点处的有限元计算结果（此处为温度）。 表1：单位正方体顶点坐标及其温度 图1：空间立方体顶点编号及其网格拓朴结构 网络最大流算法算法拓展 一、网络最大流的算法分类： 一、Ford-Fulkerson增广路方法 1、Ford-Fulkerson标号算法（最简单的实现） 分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。 2、最大容量增广路算法 每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。 3、Edmonds-Karp，最短路增广算法的BFS实现 每次找一条最短的增广路，BFS是一个可以很方便的实现思想。 4、距离标号算法 最短路增广的O(n)寻找实现，使用距离函数d：d[t]=0;d<=d[j]+1若存在(i,j)∈E；只有路径上满足d=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。 5、Dinic，分层思想 对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。 二、预留与推进算法 1、一般性算法 随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。 2、重标记与前移算法 维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。 3、最高标号预留与推进算法 记录d值，然后优先处理d值较高的，直至没有盈余。 二、网络最大流的算法实现 一、Edmonds-Karp（EK）算法 就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的Dinic 算法都属于此。SAP 类算法可统一描述如下： Shortest Augmenting Path { x <-- 0 while 在残量网络Gx 中存在增广路s ~> t do { 找一条最短的增广路径P delta <-- min{rij:(i,j) 属于P} 从一个可行流f 开始, 求最大流的Ford--Fulkerson 标号算法的基本步骤： ⑴ 标号过程 ① 给发点 v s 以标号(+, +∞) , d s = +∞. ② 选择一个已标号的点 x, 对于x 的所有未给标号的邻接点y, 按下列规则处理： 当 yx∈E, 且f yx ＞0 时, 令d y = min { f yx , d x }, 并给y 以标号 ( x ? , d y ). 当 xy∈E, 且f xy＜C xy 时, 令d y = min {C xy ? f xy , d x }, 并给y 以标号 ( x +, d y ). ③ 重复②直到收点v t 被标号或不再有点可标号时为止. 若v t 得到标号, 说明存在一条 可增广链, 转⑵调整过程; 若v t 未得到标号, 标号过程已无法进行时, 说明f 已经是最大流. ⑵ 调整过程 ④ 决定调整量d =d vt , 令u = v t . ⑤ 若 u 点标号为( v +, d u ), 则以f vu + d 代替 f vu ; 若u 点标号为( v ?, d u ), 则以f vu ? d 代替 f vu. ⑥ 若 v = v s, 则去掉所有标号转⑴重新标号; 否则令u = v, 转⑤. 算法终止后, 令已有标号的点集为S, 则割集(S, S c )为最小割, 从而W f = C (S, S c ). 例1 求图 6-19 所示网络的最大流. 利用 Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下： n=8;C=[0 5 4 3 0 0 0 0 0 0 0 0 5 3 0 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0]; %弧容量 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号 while(1) No(1)=n+1;d(1)=Inf; %给发点vs 标号 while(1)pd=1; %标号过程 for(i=1:n)if(No(i)) %选择一个已标号的点vi for(j=1:n)if(No(j)==0&f(i,j)Matlab-PDE工具箱有限元法求解偏微分方程
关于最小费用最大流的解题
从一道题目的解法试谈网络流的构造与算法
有限元钢架结构分析手算matlabansys模拟
求最小费用最大流算法的MATLAB程序代码
运筹学实验之最小费用最大流(综合实验)
利用Matlab进行有限元分析结果的可视化显示
最大流算法拓展
最大流算法MATLAB
相关主题
文本预览