知识卡片
最小费用流须明确要求的流量
超级源到供应点的容量可表示供给上限,需求点到超级汇的容量可表示需求上限;要满足全部需求,还需要求送达总流等于需求总和,或为每个需求点设定适当的等式或下界,并在容量不足时报告不可行。
若仅最小化非负费用且只有上限,零流通常就是最优,因此必须明确固定流量、供需平衡或先最大流再最小费用的目标。残量边的负费用及反向增广也需纳入求解。
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
- · 查看原书依据
没有中继仓库节点的转运问题。
- · 查看原书依据
任务分配问题转换成转运问题,只是加上了这样的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。