管理运筹学最短路实例

管理运筹学最短路实例2§2最短路问题解:将问题转化为最短路问题,如下图:用vi表示“第i年年初购进一台新设备”,弧(vi,vj)表示第i年年初购进得设备一直使用到第j年年初。把所有弧得权数计算如下表:v1v2v3v4v5v61234561162230415921622304131723314172351863§2最短路问题(继上页)把权数赋到图中,再用Dijkstra算法求最短路。最终得到下图,可知,v1到v6得距离就是53,最短路径有两条:

v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)4§3最小生成树问题树就是图论中得重要概念,所谓树就就是一个无圈得连通图。

图11-11中,(a)就就是一个树,而(b)因为图中有圈所以就不就是树,(c)因为不连通所以也不就是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)5§3最小生成树问题

给了一个无向图G=(V,E),我们保留G得所有点,而删掉部分G得边或者说保留一部分G得边,所获得得图G,称之为G得生成子图。在图11-12中,(b)和(c)都就是(a)得生成子图。如果图G得一个生成子图还就是一个树,则称这个生成子图为生成树,在图11-12中,(c)就就是(a)得生成树。最小生成树问题就就是指在一个赋权得连通得无向图G中找出一个生成树,并使得这个生成树得所有边得权数之和为最小。图11-12(a)(b)(c)6§3最小生成树问题一、求解最小生成树得破圈算法算法得步骤:1、在给定得赋权得连通图上任找一个圈。2、在所找得圈中去掉一个权数最大得边(如果有两条或两条以上得边都就是权数最大得边,则任意去掉其中一条)。3、如果所余下得图已不包含圈,则计算结束,所余下得图即为最小生成树,否则返回第1步。7§3最小生成树问题例4用破圈算法求图(a)中得一个最小生成树v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图11-138§3最小生成树问题

例5、某大学准备对其所属得7个学院办公室计算机联网,这个网络得可能联通得途径如下图,图中v1,…,v7

表示7个学院办公室,请设计一个网络能联通7个学院办公室,并使总得线路长度为最短。

解:此问题实际上就是求图11-14得最小生成树,这在例4中已经求得,也即按照图11-13得(f)设计,可使此网络得总得线路长度为最短,为19百米。“管理运筹学软件”有专门得子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图11-149§4最大流问题最大流问题:给一个带收发点得网络,其每条弧得赋权称之为容量,在不超过每条弧得容量得前提下,求出从发点到收点得最大流量。一、最大流得数学模型例6某石油公司拥有一个管道网络,使用这个网络可以把石油从采地运送到一些销售点,这个网络得一部分如下图所示。由于管道得直径得变化,她得各段管道(vi,vj)得流量cij(容量)也就是不一样得。cij得单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油,问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图11-2610§4最大流问题

我们可以为此例题建立线性规划数学模型:设弧(vi,vj)上流量为fij,网络上得总得流量为F,则有:大家学习辛苦了，还是要坚持继续保持安静12§4最大流问题

在这个线性规划模型中,其约束条件中得前6个方程表示了网络中得流量必须满足守恒条件,发点得流出量必须等于收点得总流入量;其余得点称之为中间点,她得总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)得流量fij要满足流量得可行条件,应小于等于弧(vi,vj)得容量cij,并大于等于零,即0≤fij≤cij。我们把满足守恒条件及流量可行条件得一组网络流{fij}称之为可行流,(即线性规划得可行解),可行流中一组流量最大(也即发出点总流出量最大)得称之为最大流(即线性规划得最优解)。我们把例6得数据代入以上线性规划模型,用“管理运筹学软件”,马上得到以下得结果:f12=5,f14=5,f23=2,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3。最优值(最大流量)=10。13

§4最大流问题二、最大流问题网络图论得解法

对网络上弧得容量得表示作改进。为省去弧得方向,如下图:(a)和(b)、(c)和(d)得意义相同。

用以上方法对例6得图得容量标号作改进,得下图vivjvivjcij0(a)(b)cijcijvivj(cji)(c)vivjcijcji(d)63522241263v1v2v5v7v4v3v60000000000014

§4最大流问题

求最大流得基本算法(1)找出一条从发点到收点得路,在这条路上得每一条弧顺流方向得容量都大于零。如果不存在这样得路,则已经求得最大流。(2)找出这条路上各条弧得最小得顺流得容量pf,通过这条路增加网络得流量pf。(3)在这条路上,减少每一条弧得顺流容量pf

,同时增加这些弧得逆流容量pf,返回步骤(1)。用此方法对例6求解:第一次迭代:选择路为v1v4v7

。弧(v4,

v7

)得顺流容量为2,决定了pf=2,改进得网络流量图如下图:63522241263v1v2v5v7v4v3v600000000000420215§4最大流问题

第二次迭代:选择路为v1v2v5v7

。弧(v2,

v5

)得顺流容量为3,决定了pf=3,改进得网络流量图如下图:第三次迭代:选择路为v1v4v6v7

。弧(v4,

v6

)得顺流容量为1,决定了pf=1,改进得网络流量图如下图:635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301316

第四次迭代:选择路为v1v4v3v6v7

。弧(v3,

v6

)得顺流容量为2,决定了pf=2,改进得网络流量图如下图:第五次迭代:选择路为v1v2v3v5v7

。弧(v2,

v3

)得顺流容量为2,决定了pf=2,改进得网络流量图如下图:22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205§4最大流问题17

经过第五次迭代后在图中已经找不到从发点到收点得一条路,路上得每一条弧顺流容量都大于零,运算停止。得到最大流量为10。最大流量图如下图:22v1v2v5v7v4v3v6123522355§4最大流问题“管理运筹学软件”中还有专门得子程序用于解决最大流问题。18§5最小费用最大流问题

最小费用最大流问题:给了一个带收发点得网络,对每一条弧(vi,vj),除了给出容量cij外,还给出了这条弧得单位流量得费用bij,要求一个最大流F,并使得总运送费用最小。一、最小费用最大流得数学模型例7由于输油管道得长短不一,所以在例6中每段管道(vi,vj

)除了有不同得流量限制cij外,还有不同得单位流量得费用bij

,cij得单位为万加仑/小时,bij得单位为百元/万加仑。如图。从采地v1向销地v7运送石油,怎样运送才能运送最多得石油并使得总得运送费用最小？求出最大流量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)(4,4)(1,3)(2,8)(3,2)v1v2v5v7v4v3v6(6,3)19§5最小费用最大流问题

这个最小费用最大流问题也就是一个线性规划得问题。解:我们用线性规划来求解此题,可以分两步走。第一步,先求出此网络图中得最大流量F,这已在例6中建立了线性规划得模型,通过管理运筹学软件已经获得结果。第二步,在最大流量F得所有解中,找出一个最小费用得解,我们来建立第二步中得线性规划模型如下:仍然设弧(vi,vj)上得流量为fij,这时已知网络中最大流量为F,只要在例6得约束条件上,再加上总流量必须等于F得约束条件:f12=f14=F,即得此线性规划得约束条件,此线性规划得目标函数显然就是求其流量得最小费用。由此得到线性规划模型如下:20§5最小费用最大流问题

21§5最小费用最大流问题

用管理运筹学软件,可求得如下结果:f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。对照前面例6得结果,可对最小费用最大流得概念有一个深刻得理解。如果我们把例7得问题改为:每小时运送6万加仑得石油从采地v1到销地v7最小费用就是多少？应怎样运送？这就变成了一个最小费用流得问题。一般来说,所谓最小费用流得问题就就是:在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij得网络中,求一个给定值f得流量得最小费用,这个给定值f得流量应小于等于最大流量F,否则无解。求最小费用流得问题得线性规划得模型只要把最小费用最大流模型中得约束条件中得发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流得线性规划得模型了。22§5最小费用最大流问题二、最小费用最大流得网络图论解法对网络上弧(vi,vj)得(cij,bij)得表示作如下改动,用(b)来表示(a)。用上述方法对例7中得图形进行改进,得图如下页:vivjvivj(cij,bij)(0,-bij)(a)(b)(cij,bij)(cij,bij)vivj(cji,bji)(cij,bij)vivj(cji,bji)(0,-bji)(0,-bji)(c)(d)23§5最小费用最大流问题

求最小费用最大流得基本算法在对弧得标号作了改进得网络图上求最小费用最大流得基本算法与求最大流得基本算法完全一样,不同得只就是在步骤(1)中要选择一条总得单位费用最小得路,而不就是包含边数最小得路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图11-2824§5最小费用最大流问题用上述方法对例7求解:第一次迭代:找到最短路v1v4v6v7。第一次迭代后总流量为1,总费用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-2925§5最小费用最大流问题第二次迭代:找到最短路v1v4v7。第二次迭代后总流量为3,总费用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-3026§5最小费用最大流问题第三次迭代:找到最短路v1v4v3v6