精心整理的运筹学重点12.网络最小费用最大流

网络流：最小费用最大流（最简单的算法）最小费用流在OI 竞赛中应当算是比较偏门的内容，但是NOI2008 中employee 的突然出现确实让许多人包括zkw 自己措手不及。

可怜的zkw 当时想出了最小费用流模型，可是他从来没有实现过，所以不敢写，此题0 分。

zkw 现在对费用流的心得是：虽然理论上难，但是写一个能AC 题的费用流还算简单。

先贴一个我写的employee 程序：只有不到70 行，费用流比最大流还好写～程序代码:C++#include <cstdio>#include <cstring>using namespace std;const int maxint=~0U>>1;int n,m,pi[550]={0},cost=0;bool v[550]={0};struct etype{int t,c,u;etype *next,*pair;etype(){}etype(int t_,int c_,int u_,etype* next_):t(t_),c(c_),u(u_),next(next_){}void* operator new(unsigned,void* p){return p;}} *e[550],*eb[550];int aug(int no,int m){if(no==n)return cost+=pi[1]*m,m;v[no]=true;for(etype *&i=e[no];i;i=i->next)if(i->u && !v[i->t] && pi[i->t]+i->c==pi[no])if(int d=aug(i->t,m<i->u?m:i->u))return i->u-=d,i->pair->u+=d,d;return 0;}bool modlabel(){int d=maxint,c;for(int i=1;i<=n;++i)if(v[i])for(etype *j=eb[i];j;j=j->next)if(j->u && !v[j->t])if((c=j->c-pi[i]+pi[j->t])<d)d=c;if(d==maxint)return false;for(int i=1;i<=n;++i)if(v[i])pi[i]+=d,e[i]=eb[i];return true;}int main(){freopen("costflow.in","r",stdin);freopen("costflow.out","w",stdout);scanf("%d %d",&n,&m);etype *Pe=new etype[m+m];while(m--){int s,t,c,u;scanf("%d%d%d%d",&s,&t,&u,&c);e[s]=new(Pe++)etype(t, c,u,e[s]);e[t]=new(Pe++)etype(s,-c,0,e[t]);e[s]->pair=e[t];e[t]->pair=e[s];}memmove(eb,e,sizeof(e));do do memset(v,0,sizeof(v));while(aug(1,maxint));while(modlabel());printf("%d\n",cost);return 0;}程序代码:CB大牛翻译的PASCALvarn,m,i,l,s,t,c,cost,u:longint;v:array[0..600]of boolean;dis:array[0..600]of longint;e_n,e_t,e_c,e_u,e_p,e_x:array[0..250000]of longint;function min(a,b:longint):longint;beginif a>b then exit(b);exit(a);end;procedure addedge(s,t,c,u,k:longint);begininc(l);e_n[l]:=e_n[s];e_n[s]:=l;//下一条边e_t[l]:=t;//边的另一端e_c[l]:=c;//边的费用e_u[l]:=u;//边的容量e_p[l]:=l+k;//对应的边end;procedure build(s,t,c,u:longint);beginaddedge(s,t,c,u,1);addedge(t,s,-c,0,-1);end;function aug(no,m:longint):longint;vari,d:longint;beginif no=n then begininc(cost,m*dis[1]);exit(m);end;v[no]:=true;i:=e_x[no];while i<>0 do beginif (e_u[i]>0)and(not v[e_t[i]])and(dis[e_t[i]]+e_c[i]=dis[no]) then begind:=aug(e_t[i],min(m,e_u[i]));if d>0 then begindec(e_u[i],d);inc(e_u[e_p[i]],d);e_x[no]:=i;exit(d);end;end;i:=e_n[i];end;e_x[no]:=i;exit(0);end;function modlabel:boolean;vard,i,j:longint;begind:=maxlongint;for i:=1 to n do if v[i] then beginj:=e_n[i];while j<>0 do beginif (e_u[j]>0)and(not v[e_t[j]])and(e_c[j]-dis[i]+dis[e_t[j]]<d) then d:=e_c[j]-dis[i]+dis[e_t[j]];j:=e_n[j];end;end;if d=maxlongint then exit(true);for i:=1 to n do if v[i] then beginv[i]:=false;inc(dis[i],d);end;exit(false);end;beginassign(input,'coflow.in');reset(input);assign(output,'coflow.out');rewrite(output);readln(n,m);l:=n;for m:=m downto 1 do beginreadln(s,t,u,c);build(s,t,c,u);end;repeatfor i:=1 to n do e_x[i]:=e_n[i];while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0);until modlabel;writeln(cost);close(output);end.这里使用的是连续最短路算法。

运筹学必考知识点总结在运筹学中，有一些必考的知识点是非常重要的。

这些知识点涵盖了运筹学的基本概念、方法和模型，对于考生来说，掌握这些知识点是至关重要的。

本文将对运筹学的一些必考知识点进行总结，帮助考生更好地备考。

1. 线性规划线性规划是运筹学中的重要方法之一，它通过建立数学模型来解决各种决策问题。

在线性规划中，目标是最大化或最小化一个线性函数，同时满足一系列线性约束条件。

考生需要掌握线性规划的基本理论，包括线性规划模型的建立、单纯形法和对偶理论等内容。

2. 整数规划整数规划是线性规划的扩展，它要求决策变量取整数值。

整数规划在实际应用中有着广泛的用途，因此对于考生来说，掌握整数规划的基本理论和解题方法是必不可少的。

3. 动态规划动态规划是一种用于求解多阶段决策问题的优化方法。

在动态规划中，问题被分解为多个子问题，并且这些子问题之间存在重叠。

考生需要了解动态规划的基本原理、状态转移方程的建立以及动态规划算法的实现。

4. 网络流问题网络流问题是运筹学中的一个重要领域，它涉及到图论和优化算法等多个方面的知识。

在网络流问题中，主要考察最大流、最小割、最短路等问题的求解方法。

5. 效用理论效用理论是运筹学中的一个重要分支，它研究人们在做出决策时的偏好和选择。

效用函数、期望效用、风险偏好等概念是考试中的热点内容。

6. 排队论排队论是研究排队系统的运作规律和性能指标的数学理论。

在排队论中，考生需要了解排队系统的稳定性条件、平衡方程、性能指标的计算方法等。

7. 多目标决策多目标决策是指在考虑多个目标时的决策问题。

在多目标决策中，往往需要考虑到多个目标之间的矛盾和权衡，因此考生需要掌握多目标规划的基本原理和解题方法。

8. 随机规划随机规划是考虑到不确定因素的决策问题。

在随机规划中，目标函数、约束条件等参数都是随机变量，因此需要考虑到风险和概率的因素。

以上是一些运筹学中的必考知识点，考生在备考过程中需要重点关注这些知识点。

最小费用最大流问题例题讲解
最小费用最大流问题（Minimum Cost Maximum Flow Problem）是一种在特定的多媒体网络中传送给定体积的流量，使总花费最小化的一种算法。

它能满足一些实际生活中的求解，比如电力系统的供求、工厂的物料的分配和两地之间的物品的运输问题，以及更加复杂的产品开发和行业分工中的分布问题等等。

最小费用最大流问题的目标是在满足给定的最大流量要求的前提下，找出具有最小成本的流量方案。

这种问题的解决步骤如下：
1. 在图形中定义网络：用图形表示整个网络，每条边的容量是边上的流量上限。

2. 尝试找出最大流量：在不超过容量限制的前提下，找出输出流量最大的允许方案，也就是最小费用最大流量。

3. 计算最小成本：对所有边的成本进行总结，计算出最小成本。

下面以一个最小费用最大流问题的例题来说明：
假设有一个三角形的网络，它由一个源点S、一个汇点T、一个中间点O以及三条边组成，边的名字分别是SO、OT、OS，它们的容量分别是10、15和5，费用分别是5、3和2。

要求我们在此条件下求解最小费用最大流问题。

解：首先，我们可以求出最大流量：在边SO的容量为10时，我们可以将费用最小的边OT累加，得到最大流量值为10+3=13。

接下来，计算最小费用：根据上述算法，所有边的费用应该都大于等于0，才能累加而得到最大流量。

也就是说，最小费用为
5+3+2=10。

最后，最小费用最大流问题的解为：最大流量13，最小成本10。

最小费用最大流1.最大流问题1.1案例假设现在因为种种原因，我们只能通过地面线路来运输口罩物资，并且每一条线路是有流量限制的。

假设不考虑运输速度，并且源点S （杭州）的口罩物资产量是足够多的，我们需要求解汇点T（武汉）在不计速度的情况下能收到多少物资？对于这个流网络，我们可以轻松的获得汇点T的最大流量。

因为在这个图中，只有两条路径，分别是S → A → B → T和S → C → D → T两条路径来输送流量，前者最大流量是12 ，后者是4，所以最大流量总和是16。

1.2建模图1是连接产品产地Vs和销售地Vt的交通网，每一条弧代表两点间的运输线，弧旁的数字表示这条运输线的最大通过能力。

现在要求制定一个运输方案，使得从Vs运输到Vt的产品数量最多。

图1模型():(,):(,)max .,,,,s ,0,s.t 0,,V V st f c Vf f t f Vμυμυμυυμυυυμμυλμυμυλμλμμμυ∈∈≤∀∈⎧=⎪-=-=⎨⎪≠⎩≥∀∈∑∑其中λ表示总共运输量f μυ表示弧(),μυ中的实际流量(),c μυ表示弧(),μυ中的容量限制S,t 表示物质运输的起点和终点最大流问题的推广现实问题中的网络，不但边有容量，而且点也有容量。

例如运 输网络中表示中转站的点v, 点容量 c(v) 可表示该中转站能容纳的货物的数列。

对点有容量的网络 N ，流函数若满足对一点 v,流入v 的流量之和等于流出v 的流量之和，并且小于等于c(v),2.最小费用最大流问题上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流的费用问题，在许多实际问题中，费用的因素很重要。

例如，在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。

这就是下面要介绍的最小费用流问题。

在运输网络N = (s,t,V, A,U)中，设(),c μυ是定义在A上的非负函数，它表示通过弧(),μυ单位流的费用。