第八讲图与网络模型

第八讲图与网络模型问题1最大流问题某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道),(jivv的容许流量ijc（容量）也是不一样的。ijc的单位为万加仑/小时。如果使用这个网络系统从采地1v向销地7v运送石油，问每小时能运送多少加仑石油？方案表述每条弧上的流为多少决策变量设弧),(jivv上的流量为ijf约束条件0521322326600000574746433635252314126746365735254746431436354323252312ijffffffffffffffffffffffffffff63522241263v1v2v7v4v3v6v5目标函数1412ffz数学模型为1412maxffz0521322326600000574746433635252314126746365735254746431436354323252312ijffffffffffffffffffffffffffffExcel求解问题2最小费用最大流问题及其数学模型由于输油管道的长短不一，所以上例中每段管道),(jivv除了有不同的流量限制ijc外，还有不同的单位流量的费用ijb，ijc的单位为万加仑/小时，ijb的单位为百元/万加仑。如图。从采地1v向销地7v运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。本问题的数学模型为jiijijfbz,min0105213223266000001412574746433635252314126746365735254746431436354323252312ijffffffffffffffffffffffffffffff很显然，此问题可以推广为给定流量的最小费用流问题。类似地，可以考虑限制费用的最大流问题。问题3（有向）最短路问题(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v7v3v6(6,3)v5v4问题转换将路长（弧长）看作费用，求一个流值为1的最小费用流（用流值1确定一条路径）问题4（无向）最短路问题v2v3v4v132521v6v517535v2v3v4v132521v6v517535