知识卡片

普通读书笔记卡 · 3646.g.7 · 生成模型:未记录

最小费用流须明确要求的流量

理解等级:中级

超级源到供应点的容量可表示供给上限,需求点到超级汇的容量可表示需求上限;要满足全部需求,还需要求送达总流等于需求总和,或为每个需求点设定适当的等式或下界,并在容量不足时报告不可行。

若仅最小化非负费用且只有上限,零流通常就是最优,因此必须明确固定流量、供需平衡或先最大流再最小费用的目标。残量边的负费用及反向增广也需纳入求解。

239用供应点、需求点和中转仓库构造目标:总费用为各条运输和仓库处理边的流量乘单位费用之和;仓库节点满足流守恒并受吞吐容量限制。所有需求必须满足时需明确可行性。

241没有中转节点;按每条供应到需求边的流量乘单位费用求总成本。若需求必须满足,需要相应等式或下界;仅有不超过需求和供给的上界且成本非负时零运输就是最小费用。

242说明运输到转运的规约;求解和结果验证仍须检查需求量、容量与总流目标。

244将每侧限制为单位供需;若只允许部分配对或存在不等人数,要定义不可行和未分配的处理。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 5 处

    • · 查看原书依据

      供应满足 对每个源点si∈S,所有边(si,v)∈E的f(si,v)之和(流出si的流)减去所有边(u,si)∈E的f(u,si)之和(流入si的流)必须小于等于sup(si),也就是说,每个源点供应的商品的上限是sup(si)。 需求满足 对于每个汇点tj∈T,所有边(u,tj)∈E的f(u,tj

    • · 查看原书依据

      转运问题 有m个供应站si,每个供应站能够生产sup(si)个单位的商品。有n个需求站tj,每个需求站需要dem(tj)个单位的商品。而且还有w个仓库wk,每个仓库能够接收和转运最大为maxk个单位的商品,转运的费用为每个单位wpk。每一个供应站si到需求站tj的单位开销d(i,j)是固定的,从供应

    • · 查看原书依据

      运输问题 运输问题比转运问题要简单得多,因为没有中继仓库节点。有m个供应站si,每个供应站能够生产sup(si)个单位的商品。有n个需求站tj,每个需求站需要dem(tj)个单位的商品。 对于连接供应站si到需求站tj的边(u,v)来说,其单位开销d(i,j)是固定的。我们的目标是决定了从供应站si

    • · 查看原书依据

      没有中继仓库节点的转运问题。

    • · 查看原书依据

      任务分配问题转换成转运问题,只是加上了这样的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。

    参考来源

    - 位置:《算法技术手册》第8章《最小开销流》(spine1638;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1601.html;u238-ch08-008)。 - 结论依据:238全文实读。 - 原始内容:供应满足 对每个源点si∈S,所有边(si,v)∈E的f(si,v)之和(流出si的流)减去所有边(u,si)∈E的f(u,si)之和(流入si的流)必须小于等于sup(si),也就是说,每个源点供应的商品的上限是sup(si)。 需求满足 对于每个汇点tj∈T,所有边(u,tj)∈E的f(u,tj - 位置:《算法技术手册》第8章《转运问题》(spine1639;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1602.html;u239-ch08-008)。 - 结论依据:239用供应点、需求点和中转仓库构造目标:总费用为各条运输和仓库处理边的流量乘单位费用之和;仓库节点满足流守恒并受吞吐容量限制。所有需求必须满足时需明确可行性。 - 原始内容:转运问题 有m个供应站si,每个供应站能够生产sup(si)个单位的商品。有n个需求站tj,每个需求站需要dem(tj)个单位的商品。而且还有w个仓库wk,每个仓库能够接收和转运最大为maxk个单位的商品,转运的费用为每个单位wpk。每一个供应站si到需求站tj的单位开销d(i,j)是固定的,从供应 - 位置:《算法技术手册》第8章《运输问题》(spine1640;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1603.html;u241-ch08-008)。 - 结论依据:241没有中转节点;按每条供应到需求边的流量乘单位费用求总成本。若需求必须满足,需要相应等式或下界;仅有不超过需求和供给的上界且成本非负时零运输就是最小费用。 - 原始内容:运输问题 运输问题比转运问题要简单得多,因为没有中继仓库节点。有m个供应站si,每个供应站能够生产sup(si)个单位的商品。有n个需求站tj,每个需求站需要dem(tj)个单位的商品。 对于连接供应站si到需求站tj的边(u,v)来说,其单位开销d(i,j)是固定的。我们的目标是决定了从供应站si - 位置:《算法技术手册》第8章《解决方案》(spine1640;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1603.html;u242-ch08-008)。 - 结论依据:242说明运输到转运的规约;求解和结果验证仍须检查需求量、容量与总流目标。 - 原始内容:没有中继仓库节点的转运问题。 - 位置:《算法技术手册》第8章《解决方案》(spine1641;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1604.html;u244-ch08-008)。 - 结论依据:244将每侧限制为单位供需;若只允许部分配对或存在不等人数,要定义不可行和未分配的处理。 - 原始内容:任务分配问题转换成转运问题,只是加上了这样的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。