知识卡片

普通读书笔记卡 · 3658.b.7.a

最小费用流固定需求再优化成本

理解等级:中级

最小费用流在容量、流量守恒和非负约束下,增加源点净流出恰为需求d的等式,并最小化各边单位费用与流量乘积之和。

与最大流相比,流量变成指定需求,目标变成总费用。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第29章 线性规划 · 查看原书依据

      Suppose that, in addition to a capacity c(u, v) for each edge (u, v), you are given a real-valued cost a(u, v). As in the maximum-flow problem, assume that c(u, v) = 0 if (u, v) ∉ E and that there are no antiparallel edges. If you send fuv units of flow over edge (u, v), you incur a cost of a(u, v) · fuv. You are also given a flow demand d. You wish to send d units of flow from s to t while

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[25000,30000))。 - 结论依据:原文说明单纯形、整数规划及网络优化模型的变量、约束与目标;对应图和公式已核对。 - 原始内容:Suppose that, in addition to a capacity c ( u , v ) for each edge ( u , v ), you are given a real-valued cost a ( u , v ). As in the maximum-flow problem, assume that c ( u , v ) = 0 if ( u , v ) ∉ E and that there are no antiparallel edges. If you send f uv units of flow over edge ( u , v ), you incur a cost of a ( u , v ) · f uv . You are also given a flow demand d . You wish to send d units of flow from s to t while