运筹说 第80期 | 最小费用最大流问题

这篇具有很好参考价值的文章主要介绍了运筹说 第80期 | 最小费用最大流问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前面我们学习了图与网络分析的基础知识及经典问题,大家是否已经学会了呢?接下来小编和大家学习最后一个经典问题——最小费用最大流问题

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下,此类问题的研究试图寻找出:流量从A到B,如何选择路径、分配经过路径的流量,可以达到所用的费用最小的要求。

如n辆卡车要运送物品,从A地到B地。由于每条路段都有不同的路费要缴纳,每条路能容纳的车的数量有限制,最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低,物品又能全部送到。

运筹说 第80期 | 最小费用最大流问题,运筹学

下面,让我们从实际问题出发,学习如何解决最小费用最大流问题吧!

一、问题描述及求解原理

01 问题描述

网络G=(V,E,C),每一弧(vi,vj)∈E,给出(vi,vj)上单位流的费用d(vi,vj)≥0(简记dij),记G=(V,E,C,d)。

最小费用最大流问题:

运筹说 第80期 | 最小费用最大流问题,运筹学

求一个最大流f,使流的总费用取最小值。

02 求解原理

设对可行流f存在增广链𝜇,当沿𝜇以θ=1调整f,得新的可行流f'时,显然V(f')=V(f)+1,两流的费用之差d(f)-d(fx27;):

运筹说 第80期 | 最小费用最大流问题,运筹学

称为增广链𝜇的费用。

原理依据:

若f是流值为V(f)的所有可行流中费用最小者,而𝜇是关于f的所有增广链中费用最小的增广链,则沿𝜇以θ去调整f,得可行流f',f'就是流量为V(f)+θ的所有可行流中费用最小的可行流。这样,当f'是最大流时,f'就是所求的最小费用最大流。

如果已知f是流量为V(f)的最小费用流→求出关于f的最小费用增广链。

在构造最小费用增广链时,会将网络中的每一条条弧(vi,vj)都变成一对方向相反的弧,以形成四通八达的“路”,因此对于有向边(vi,vj)权wij按如下方法取值:

运筹说 第80期 | 最小费用最大流问题,运筹学

取值说明如下图所示:

运筹说 第80期 | 最小费用最大流问题,运筹学

构造赋权有向图W(f),它的顶点是G的顶点,W(f)中弧及其权wij按弧(vi,vj)在G中的情形分为:

运筹说 第80期 | 最小费用最大流问题,运筹学

新网络W(f)成为流f的(费用)长度网络。

由增广链费用的概念及网络W(f)的定义,知在网络G中寻求关于可行流f的最小费用增广链,等价于在网络W(f)中寻求从vs到vt的最短路。

03 算法步骤

(1)根据网络中的费用首先确定费用最小的长度网络,将该长度网络确定为初始可行流f0=0,令k=0;

(2)应用流量网络对增广链进行调整,记经k次调整得到的最小费用流为fk,构造增量网络W(fk);

(3)在W(fk)中,寻找vs到vt的最短路。若不存在最短路(即最短路路长是∞),则fk就是最小费用最大流;若存在最短路,则此最短路即为原网络G中相应的可增广链𝜇,转入第4步。

(4)在增广链𝜇上fk按下式进行调整,调整量θ为:

运筹说 第80期 | 最小费用最大流问题,运筹学

得新的可行流fk+1,返回第2步

二、实例应用

01 例题求解

例1:求下图所示网络的最小费用最大流。弧旁数字为(dij,cij)。

运筹说 第80期 | 最小费用最大流问题,运筹学

解:

(1)取初始可行流;

(2)按算法要求构造长度网络 ;

运筹说 第80期 | 最小费用最大流问题,运筹学

(3)在原网络G中,与这条最短路对应的增广链为 ;

运筹说 第80期 | 最小费用最大流问题,运筹学

(4)在原网络D中,与这条最短路对应的增广链为 :

运筹说 第80期 | 最小费用最大流问题,运筹学

按照上述算法依次得 ,流量依次为 ,构造相应的增量网络为 ,如图(a),(e),(g),(i)所示。

运筹说 第80期 | 最小费用最大流问题,运筹学

运筹说 第80期 | 最小费用最大流问题,运筹学

图(i)中,不存在从 到 的最短路,所以 为最小费用最大流。

02 拓展延伸

最小费用最大流问题还可以使用线性规划方法进行求解,思路如下:

(1)通过运筹说第78期相关介绍可以求出最大流量

(2)在保证总流量等于最大流量的条件下,以最小化总费用为目标求出每条弧上的流量。

例2:某公司有一个管道网络如下图所示,使用这个网络可以将石油从产地v1送到销地v7,给出了每一段管道的容量cij(单位为:万加仑/小时),此外还给出了每段弧上的单位流量的费用dij(单位为:百元/万加仑),(cij,dij)在图的弧上已标出,如果使用这个网络从产地v1向销地v7运送石油,问怎样运送才能运送最多的石油且使总运费最小?

运筹说 第80期 | 最小费用最大流问题,运筹学

通过标号算法可以求出最大流量为10。然后,在保证总流量等于10的条件下,以最小化总费用为目标求出每条弧上的流量,如下所示:

运筹说 第80期 | 最小费用最大流问题,运筹学

后续步骤使用线性规划求解方法如单纯形法求解即可。

以上就是最小费用最大流问题的全部内容了,通过本节学习大家是否对该问题有了一个初步的认识呢,是否可以求解最小费用最大流问题呢?下一次小编将带大家学习第九章——网络计划,敬请关注!

作者 | 张宇 齐鹏

责编 | 刘文志

审核 | 徐小峰文章来源地址https://www.toymoban.com/news/detail-792363.html

到了这里,关于运筹说 第80期 | 最小费用最大流问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年02月03日
    浏览(77)
  • 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题)

    【管理运筹学】第 8 章 | 动态规划(1,多阶段决策过程与动态规划基本概念) 【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想与模型求解) 【管理运筹学】第 8 章 | 动态规划(3,资源分配问题) 【管理运筹学】第 8 章 | 动态规划(4,生产与储存问题) 【管理

    2024年02月04日
    浏览(47)
  • 【管理运筹学】第 7 章 | 图与网络分析(3,最短路问题)

    【管理运筹学】第 7 章 | 图与网络分析(1,图论背景以及基本概念、术语、矩阵表示) 【管理运筹学】第 7 章 | 图与网络分析(2,最小支撑树问题) 【管理运筹学】第 7 章 | 图与网络分析(4,最大流问题) 【管理运筹学】第 7 章 | 图与网络分析(5,最小费用流问题及最小

    2024年02月09日
    浏览(55)
  • 运筹学—例题求解

    作答如下:      图解法验证:  由图可得在点x1=20,x2=24取到最大值 Z =4080; 作答如下: 解: (1)设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表   B1 B2 B3 产量 A1 x 11 x 12 x 13 200 A2 x 21 x 22 x 23 230 销量 100 150 180

    2024年02月04日
    浏览(59)
  • #运筹学:动态规划

    预习准备 (一)实验目的:安装WinQSB软件,了解WinQSB软件在Windows环境下的文件管理操作,熟悉软件界面内容,掌握操作命令。用WinQSB软件求解线性规划。 (二)内容和要求:安装与启动软件,建立新问题,输入模型,求解模型,结果的简单分析。 (三)操作步骤: 1.将Wi

    2024年02月04日
    浏览(71)
  • 运筹学—线性规划单纯形表

    什么是标准型数学模型? a. 具有等式约束方程组:一般引入松弛变量将不等式约束转化为等式约束 b. 约束方程右边常数非负:若右边为负,则两边同称-1使其变为非负 c. 所有变量非负 d. 目标函数为max型,对于min型,化为max型 例如:3a+9b=540添加松弛变量c,使得不等式变为3

    2023年04月08日
    浏览(43)
  • 【运筹学】第4讲 线性代数基础

    笔记来源: b站 王树尧SJTU 本节主要对线性代数整体的研究思路(矩阵、行列式的引出)进行梳理,基础计算方法等请自行复习线性代数; 1、目的:解线性方程(未知数次数为1的方程) 2、n元方程组的推广过程 3、n元方程组研究步骤 有没有解? 怎么解? 解是什么? 对于一

    2024年01月23日
    浏览(47)
  • 运筹学的松弛变量和影子价格或者对偶价格

    1、影子价格就是对偶价格,反应的是对偶问题的决策变量的值;对偶问题中,决策变量对应的是原问题的资源,而松弛变量反应的是资源的利用问题,如果某种资源的松弛变量为0,说明这个资源在此模型下面全部用完,入股松弛变量不为0,说明,此资源还有剩余。 2、如果

    2024年02月11日
    浏览(45)
  • 一些关于运筹学和机器学习之间协同作用的思考

    几十年来,运筹学(OR)和机器学习(ML)一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学,尽管每个机器学习实践者都应该至少了解一些优化技术,因为每个机器学习问题本质上都是一个优化问题。在本文中,我

    2024年02月05日
    浏览(51)
  • 服务运营 | INFORMS论文精选:公平高效!运筹学下的器官移植

    Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation | Operations Research (informs.org) Problem 器官移植被部分患者视为拯救生命的礼物。器官的供体主要有两种渠道,包括活体供体(器官来自亲朋好友)或尸体供体。而大多数接受器官移植的患者,其器官渠道都来自尸体

    2024年02月21日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包