最小费用最大流的Excel解答

posted at 2021.7.28 16:27 by Administrator

下面是最小费用最大流问题的一个实例,笔者使用Excel2010对此进行了剖析。

某公司有三个生产基地,分别为A1A2A3,现需要将三个基地生产的产品运送到C1C2两个经销商手中,中间要经过B1B2两个分销中心。如图所示(弧旁数字代表单位时间最大通过量和单位流量费用)。求把产品从生产基地运送到经销商手中的费用最小的最大运输量。 

该问题是一个最小费用最大流问题。用线性规划方法求解此问题,分两步进行。 

第一步:先求此网络的最大流。 

该网络由于有3个发点(供应点)和2个收点(接收点)。所以增加一个虚拟的发点s,指向三个发点,其容量分别为发点A1A2A3的可供应量;同时增加一个虚拟的收点t2个收点指向它,其容量分别为收点C1C2的需求量。 

fij表示从节点vivj的运输量(流量);设F表示从s流出的流量或者是t流入的流量。该问题的数学模型可以表示为:

     Max F=fsA1+fsA2+fsA3 

该问题的电子表格建模如图所示: 

对该问题的电子表格进行求解如图所示:

可以得出,从三个生产基地运送到两大经销商的最大运量为17 

第二步:求出在可获得的最大流(F=17)下,该网络的最小费用。 

该问题的数学模型可以表示为:

Max F=9fA1B1+2fA2B1+7fA2B2+6fA3B2+2fB1C1+3fB1C2+4fB1B2+5fB2C1+8fB2C2

 该问题的电子表格建模如图所示:

 对该问题的电子表格进行求解如图所示:

 可以得出,从三个生产基地运送到两个经销商的最大运量为17时的最小费用为187

Tags: ,

IT技术 | 生活艺术

添加评论

  Country flag

biuquote
  • 评论
  • 在线预览
Loading