最小费用流及其求法
阅读原文时间:2021年04月17日阅读:1

【1】图与网络模型及方法:图与网络的基本概念

【2】图&网络模型应用—最短路径问题

【3】树:基本概念与最小生成树

【4】匹配问题: 匈牙利算法 、最优指派、相等子图

【5】Euler 图和 Hamilton 图

【6】计划评审方法和关键路线法【统筹方法】:广泛地用于系统分析和项 目管理

【7】最小费用流及其求法 :

【8】最大流问题  

【10】钢管订购和运输问题


目录

1 最小费用流                         最小费用流问题的线性规划表示           例 19(最小费用最大流问题)     

2 求最小费用流的一种方法—迭代法       


1 最小费用流

上面我们介绍了一个网络上最短路以及最大流的算法,但是还没有考虑到网络上流 的费用问题,在许多实际问题中,费用的因素很重要。例如,在运输问题中,人们总是 希望在完成运输任务的同时,寻求一个使总的运输费用最小的运输方案。这就是下面要 介绍的最小费用流问题。

最小费用流问题的线性规划表示

在运输网络 N = (s,t,V, A,U) 中,设  是定义在 A 上的非负函数,它表示通过弧 (i, j) 单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已 知量为v( f ) 的总流量。 最小费用流问题可以用如下的线性规划问题描述:

      例 19(最小费用最大流问题)

(续例 18)由于输油管道的长短不一或地质等原因, 使每条管道上运输费用也不相同,因此,除考虑输油管道的最大流外,还需要考虑输油 管道输送最大流的最小费用。图 8 所示是带有运费的网络,其中第 1 个数字是网络的容 量,第 2 个数字是网络的单位运费。

解 按照最小费用流的数学规划写出相应的 LINGO 程序如下:

model:
sets:
nodes/s,1,2,3,4,t/:d;
arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,u,f;
endsets
data:
d=14 0 0 0 0 -14; !最大流为14;
c=2 8 2 5 1 6 3 4 7;
u=8 7 9 5 2 5 9 6 10;
enddata
min=@sum(arcs:c*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,u));
end

求得最大流的最小费用是 205,而原最大流的费用为 210 单位,原方案并不是最优 的。 类似地,可以利用赋权邻接矩阵编程求得最小费用最大流。LINGO 程序如下:

model:
sets:
nodes/s,1,2,3,4,t/:d;
arcs(nodes,nodes):c,u,f;
endsets
data:
d=14 0 0 0 0 -14;
c=0; u=0;
enddata
calc:
c(1,2)=2;c(1,4)=8;
c(2,3)=2;c(2,4)=5;
c(3,4)=1;c(3,6)=6;
c(4,5)=3;c(5,3)=4;c(5,6)=7;
u(1,2)=8;u(1,4)=7;
u(2,3)=9;u(2,4)=5;
u(3,4)=2;u(3,6)=5;
u(4,5)=9;u(5,3)=6;u(5,6)=10;
endcalc
min=@sum(arcs:c*f);
@for(nodes(i):@sum(nodes(j):f(i,j))-@sum(nodes(j):f(j,i))=d(i));
@for(arcs:@bnd(0,f,u));
end 

2 求最小费用流的一种方法—迭代法

这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker 和 Gowan 在 1961 年提出的。其主要步骤如下:

下面我们编写了最小费用最大流函数 mincostmaxflow,其中调用了利用 Floyd 算法 求最短路的函数 floydpath。

求解例 19 具体程序如下(下面的全部程序放在一个文件中):

function mainexample19
clear;clc; 
global M num
c=zeros(6);u=zeros(6);
c(1,2)=2;c(1,4)=8;c(2,3)=2;c(2,4)=5;
c(3,4)=1;c(3,6)=6;c(4,5)=3;c(5,3)=4;c(5,6)=7;
u(1,2)=8;u(1,4)=7;u(2,3)=9;u(2,4)=5;
u(3,4)=2;u(3,6)=5;u(4,5)=9;u(5,3)=6;u(5,6)=10;
num=size(u,1);M=sum(sum(u))*num^2;
[f,val]=mincostmaxflow(u,c)
%求最短路径函数
function path=floydpath(w);
global M num
w=w+((w==0)-eye(num))*M;
p=zeros(num);
for k=1:num
    for i=1:num
        for j=1:num
            if w(i,j)>w(i,k)+w(k,j)
                w(i,j)=w(i,k)+w(k,j);
                p(i,j)=k;
            end
        end
    end
end
if w(1,num) ==M
    path=[];
    else
    path=zeros(num);
    s=1;t=num;m=p(s,t);
    while ~isempty(m)
        if m(1)
            s=[s,m(1)];t=[t,t(1)];t(1)=m(1);
            m(1)=[];m=[p(s(1),t(1)),m,p(s(end),t(end))];
        else
            path(s(1),t(1))=1;s(1)=[];m(1)=[];t(1)=[];
        end
    end
end
%最小费用最大流函数
function [flow,val]=mincostmaxflow(rongliang,cost,flowvalue);
%第一个参数:容量矩阵;第二个参数:费用矩阵;
%前两个参数必须在不通路处置零
%第三个参数:指定容量值(可以不写,表示求最小费用最大流)
%返回值 flow 为可行流矩阵,val 为最小费用值
global M
flow=zeros(size(rongliang));allflow=sum(flow(1,:));
if nargin<3
    flowvalue=M;
end 
while allflow<flowvalue
    w=(flow<rongliang).*cost-((flow>0).*cost)';
    path=floydpath(w);%调用 floydpath 函数
    if isempty(path)
        val=sum(sum(flow.*cost));
        return;
    end
    theta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)==0).*M));
    theta=min([min(path'.*flow+(path'.*flow==0).*M),theta]);
    flow=flow+(rongliang>0).*(path-path').*theta;
    allflow=sum(flow(1,:));
end
val=sum(sum(flow.*cost)); 

【1】图与网络模型及方法:图与网络的基本概念

【2】图&网络模型应用—最短路径问题

【3】树:基本概念与最小生成树

【4】匹配问题: 匈牙利算法 、最优指派、相等子图

【5】Euler 图和 Hamilton 图

【6】计划评审方法和关键路线法【统筹方法】:广泛地用于系统分析和项 目管理

【7】最小费用流及其求法 :

【8】最大流问题  

【10】钢管订购和运输问题


3 图与网络模型习题

1. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去, 但由于船小,他一次只能运三者之一过河。显然,不管是狼和山羊,还是山羊和卷心菜, 都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去?

2. 北京(Pe)、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的 航线距离如表 16。

由上述交通网络的数据确定最小生成树。

3. 某台机器可连续工作 4 年,也可于每年末卖掉,换一台新的。已知于各年初购 置一台新机器的价格及不同役龄机器年末的的处理价如表 17 所示。又新机器第一年运 行及维修费为 0.3 万元,使用 1-3 年后机器每年的运行及维修费用分别为 0.8,1.5,2.0 万元。试确定该机器的最优更新策略,使 4 年内用于更换、购买及运行维修的总费用为最省。

4. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从i 仓库 至 j 市场的路径的运输能力如表 18 所示(表中数字 0 代表无路可通),试求从仓库可运 往市场的最大流量,各市场需求能否满足?

5. 某单位招收懂俄、英、日、德、法文的翻译各一人,有 5 人应聘。已知乙懂俄 文,甲、乙、丙、丁懂英文,甲、丙、丁懂日文,乙、戊懂德文,戊懂法文,问这 5 个人是否都能得到聘书?最多几个得到聘书,招聘后每人从事哪一方面翻译工作?

6. 表 19 给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最 大流问题,画出网络图并求数值解。

 8. 某公司计划推出一种新型产品,需要完成的作业由表 20 所示。

(1)画出产品的计划网络图;

(2)求完成新产品的最短时间,列出各项作业的最早开始时间、最迟开始时间和 计划网络的关键路线;

(3)假定公司计划在 17 周内推出该产品,各项作业的最短时间和缩短 1 周的费 用如上表所示,求产品在 17 周内上市的最小费用;

(4)如果各项作业的完成时间并不能完全确定,而是根据以往的经验估计出来的, 其估计值如表 21 所示。试计算出产品在 21 周内上市的概率和以 95%的概率完成新产 品上市所需的周数。 

9.已知下列网络图有关数据如表 22,设间接费用为 15 元/天,求最低成本日程。