posted at 2021.7.28 16:27 by Administrator
下面是最小费用最大流问题的一个实例,笔者使用Excel2010对此进行了剖析。
某公司有三个生产基地,分别为A1,A2,A3,现需要将三个基地生产的产品运送到C1,C2两个经销商手中,中间要经过B1,B2两个分销中心。如图所示(弧旁数字代表单位时间最大通过量和单位流量费用)。求把产品从生产基地运送到经销商手中的费用最小的最大运输量。
该问题是一个最小费用最大流问题。用线性规划方法求解此问题,分两步进行。
第一步:先求此网络的最大流。
该网络由于有3个发点(供应点)和2个收点(接收点)。所以增加一个虚拟的发点s,指向三个发点,其容量分别为发点A1、A2、A3的可供应量;同时增加一个虚拟的收点t,2个收点指向它,其容量分别为收点C1、C2的需求量。
设fij表示从节点vi到vj的运输量(流量);设F表示从s流出的流量或者是t流入的流量。该问题的数学模型可以表示为:
Max F=fsA1+fsA2+fsA3
该问题的电子表格建模如图所示:
对该问题的电子表格进行求解如图所示:
可以得出,从三个生产基地运送到两大经销商的最大运量为17。
第二步:求出在可获得的最大流(F=17)下,该网络的最小费用。
该问题的数学模型可以表示为:
Max F=9fA1B1+2fA2B1+7fA2B2+6fA3B2+2fB1C1+3fB1C2+4fB1B2+5fB2C1+8fB2C2
该问题的电子表格建模如图所示:
对该问题的电子表格进行求解如图所示:
可以得出,从三个生产基地运送到两个经销商的最大运量为17时的最小费用为187。
bd273d9a-be2f-4e2b-8ce5-a49d91e182f5|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: 方法, 模
IT技术 | 生活艺术