无向网络流的最小费用问题

《无向网络流的最小费用问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、无向网络流的最小费用问题付彤郭强!西北工业大学理学院应用数学系"西安?-66@7#摘要该文研究了无向网络上"具有流量上限的网络流最小费用问题"建立了它的数学模型"并且给出了相应的算法$关键词运输问题网络最短路径最小费用8%&’(算法文章编号&""!’%((&’!!""#%!%’""%%’"(文献标识码)中图分类号AB<6-CD!"#$%&’’()*+,)*-.,/’(%,0*"(1234.(5*4,26(*7,.89:;,2<=:,>4&2<&EFGHIJ.F0J&KLGG%/F(MHJNF.HJ/OP!QO

2、N&&%&KQO/F0OF!R&IJNSFPJFI0B&%’JFON0/OH%T0/UFIP/J’!V/WH0?-66?7’?/)*.@5*#AN/PGHGFI(/POXPPFPJNFP.H%%FPJO&PJGI&Y%F.&0JNFX0(/IFOJ/&00FJS&IZ!SN/ONNHPJNFXGGFI%/./J&KIHJF&KK%&S!H0(PFJPXG/JP.HJNF.HJ/OP.&(F%!H0([/UFP/JPIF%FUH0JH%[&I/JN.CA(B7,.3)#JIH0PG&IJHJ/&0GI&Y%F.

3、!0FJS&IZ!PN&IJFPJGHJN!P.H%%FPJO&PJ!8%&’(H%[&I/JN.!引言%’-!)!$!!’是源点"流向汇点的一个可行流%研究#在可行流根据实际情况!网络流最小费用问题可分为有向网络最小大小不变的条件下!无向网络流的最小费用问题%费用问题和无向网络最小费用问题!前者属于经典问题"!#!而针建立数学模型如下#!!对后者研究的文献较为少见!但后者的实际背景却更为广泛"./0""&$%)$%因此!研究如何解决无向网络流最小费用问题有着重要的现实!$1-!%1-%意义"本文通过改变无向

4、网络流最小费用问题的描述!借助’%2/.!.#3$!4-$!$+5’!!’’")#’’$%&’(算法思想!给出了一种求解无向网络流最小费用问题的’")$.2").%1&,!.#3%4-$"$!5’’.""-#-&!$1-!%1-’&,’算法!该算法具有路径标记功能!可以自动生成费用修正回路"’’’(6!.为其它节点’该算法也适用于有向网络流最小费用问题!而且其寻找可降费’’6$)$(!&$!%’-!7!$!’($%$%回路的方法比我们普遍使用的方法"!!*#要便利得多"因此!本文的算法有很好的适用性"*建立算

5、法算法的基本思想是先在构造的赋权网络图上执行8%&’()无向网络流最小费用问题的描述算法!其不但可以计算出任意两个节点之间的最小费用路径无向网络流最小费用问题是指#已知一个无向连通网络上值!而且可以记录任意两个节点间的最小费用路径走向!见步有!+)个节点"!!!)!$!#!其中节点"为源点!节点#为汇点%骤&7’和步骤&*’(然后寻找其负值回路!并且在不改变可行流网络上任意两个节点$与%之间的单位运费为&$%’&%$&$!%’!!)!值的条件下!搜索是否可以沿负值回路调整流量)降低费用!重$!!!"!#’!流

6、量上限为($%’(%$&$!%’!!)!$!!!"!#’!)$%&$!%’!!)!$!复上述过程!即可得到模型的最优解!见步骤&9’至步骤&-7’%!,大小!"!#’是源点"流向汇点#的一个可行流%研究#在可行流具体算法如下#不变的条件下!无向网络流的最小费用问题%&-’输入)$%!($%!)$%&$!%’-!7!$!!’&&$%’&%$!($%’(%$($’%时!&$%’6!若与源点"相邻的节点记为$!&!’-!)!$!*’!与汇点#相($%’!!)$%:6($与%不相邻时!&$%’!!($%’6!)$%1

7、6’(邻的节点记为%"&"!-!)!$!+’!("$!!!$!&!’-!)!$!*’!(%"#!,%"&7’当)$%1)%$16时!0$%’&$%!0%$’&%$(&"’-!)!$!+’则上述无向网络流最小费用问题可以等价地描当)$%1($%时!0$%’!!0%$’2&%$(&$!%’-!7!$!!’述成#已知一个无向连通网络中有!个节点-!)!$!!!其中节当6;)$%;($%时!0$%’&$%!0%$’2&%$(点$!&!’-!)!$!*’是某种物资的发运点!发运量为!$!&!’-!)!1$%#’%&$!

8、%’-!7!$!!’!.#:-($!*’!节点%"&"’-!)!$!+’是这种物资的接收点!其接收量为&<’若0$.20.%’#30$%!则0$%#’#!1$%#’1$.(否则&#)0$%’!0$%与1$%,&"’-!)!$!+’!网络上任意两个节点$与%之间的单位运费都不变&$!%’-!7!$!!’(%"为&$%’&%$&$!%’-!)!$!!’!流量上限为($%’(%$&$!%’-!)!$!!’