三级网络的最低费用

三级网络的最低费用 f卜fL- 三级网络的最低费用 程仕军黄洁纲,————一-——————, (上海交通大学管理学院) 22 摘要 三垭罔培在实际中比较常见.末文讨话在二垭顶点已茸定的情况下的三衄同培设计问题,培出 了使丹培用辊小化的两种方法. 关键词: —型笏镯网络 1.?f言 分级厢络在实际中具有广泛的应用.三级网络是简单常见的分级网络.三级网络的顶点 共分为三个层次,形威递阶结掏.煤气管遭罔络,供电线路网络常采取三级的形式.或以三级 网络为其主要结构.倒如,在煤气管道厢络中,一般不直接从煤气站向每一个居民点铺设管 道,而是从居民点中挑选若干作为中转站,从煤气站向各中转站铺设管道,再由中转站向各 居民点铺设管道,假定中转站巳被选定,煤气蛄和中转站之闻的管道费用和中转设备费用以 及各居民点(包括中转站)之间的管道费用为已知.并假定在选择中转站时已保证下述各条 件成立;对于任何一个居民点,至少有—十中转站到这个居民点的管道费用为一确 定的有限 数.每个居民点只能从中转站得到煤气.如何铺设管道使费用最低?如果各中转站能容纳的 居民点个数不能超过一给定的数(这十数可由管道和中转设备的负荷限度确定),如何铺设 管道使费用最低?这两个闻题都是三级网络的最优设计问题.本文提出的基于最小支撑树的 图论方法以及基于指派问题的数学方法可以方便的得到耗费最步的设计. 2.问题的图论表达 设G=(V,E)是以e为顶点集,以E为边集的赋权无向图.V={1.2,…,i'i),E:{(i,j): i,j?v).边(i.j)的权记为cJ.固G为无向图,故(i,j)=(i.i).GI=.记V={1,2,…,m)(1 ?re<n).给定一组正整数b一<iEv_).对于G的支撑子图H;(V,E(H)),若i?v,令dH(i) 一 l(j.(i,j)?E(H))f.考虑下述条件:' (i)对任何j?V\V.,有i?V.,使得(i.j)?E(H)f (d)对任何i?V.,dM(i)?. ?收稿8期#1991—1I一24 三级网络的最低费用 用J'表示O的满足(1)的所有支撑子图的集台.表示G的满足(i)(?)的所有支撑子图的 集台,记c(H)一?c '假定:对任何J?V\,r,有i?使得c..为有限数. (QJ)M|n{C(H):H?, (Q2)M|n{c(H):H?). 设有n个居民点,其中第l,2,…,m个被选作中转站.因煤气站到中转站之间的管道和 设备费已定,故不予考虑,此时V对应于居民点,V.对应于中转站.对应于居民点i和J之 间铺设管道的费用.(i)每一居民点其能从中转站得到煤气(中转站从它自身得到).(?) 要求每一中转站只能供应一定数量的居民点.由此极易看到,引言中提出的两个问题就是这 里的(Q】)和(Qz). 下面的命题说明了(Q-)()的最优解的一些特点.因其很简单,故从略. 命题l设H是(Qj)或(Q|)的最优解,刚 (1)对任何j?V\v一,有且仅有一个i?v_使得(i,j)?E(H). (2)E(H)匕(i,j);j?V.,JEV\v-) 易知命题中(1)比条件(i)更强.(2,则说明(00或(Q2)的最优解中只包含一端在v内 另一端在V\,r内的边,这个命题在后面的讨论中比较重要. 3.圉论方法 本节给出求解(QjY(Qt)的图论方法.基本思想是将它们分别转化为最小支撑树问题… 和具有次限制的最小支撑树问题.[zj 首皋对G进行扩充:在G的顶点之外再增加一个顶点n+1.在顶点n+l和v_中各顶 点之间分别各增加一条边.这样得到的图记为百;(,琶),其中V=Vu{n+1),蔗=Eu{(n+ l,i):i?v_). 给定充分大的正数M.下面给G的各边赋权:己+t~00EV.);若i?v_,j?n+l,则己. =Cj+M,若i?j?V\v-,则己l=GJ+2M.对G的子图T,记dT(D=Ifj:(i,j)?E(T)}l,(T) =, 其中E(T)为T的边集. 命磨2设T.为G的最小支撑树.柯作如下H':V(H')=v;E(H.)=E(T)\{(n+l,i): i?V.).则H'为(Q1)的最优癣且c阻')=(T.)--(n--m)M. 证明因V(H')=V,故H'为G的支撑子图.下证H.?,设?V\v_.因T'连通, 有?V(T')=使得(,j.)EE(T').由6的定义知?n+l,故j.?V.若j.?v\v-.则己^ =cI+2M.记0=Iin(Clj.Ii?V-).定义G的子图如下;V()一;E()=(E(T?)u{. j.))\{(",ja)).由图论中熟知?结果?知,也是G的支撑树,且(T')+己k一己^一芒(T,). 困M充分大,己,一0+M<q^+2M=己^,故芒(TJ)<(T.)这与T'是百的最小支撑树矛 盾.故必有"EV-,由的任意性知(i)威立,即H'?. 设HJ?为(Q-)的最优解,由命题l知不含匿且JE(HJ)l=n—m.现由H,构作百的 子图r:V(r)=审,E(r)一E(HI)U{n+1.j):j?v.).易知T.不含匿且连通;故T?为G的支 撑树.因芒(T)=芒(H)=c(H『)+(n—m)M,C(H,)一芒(r)一一m)M.因T'为百的支掉 树,故lE(T')l=(n+1)一ln,于是lE(H')l=n—I{n+l,i):j?V.}l=rl--~1.因T?为最 ? l2? 管理工程 小主撑树,我们可以推知T'只台两种边.一种是一端在V内另一端为n—l的边,另一_降是 一 端在v-内另一端在v\v内的边.前一种边共m条.后一种边共IE(H')l=n—m条?于 是芒(T?):芒(H-)一c(H?)+(n—m)M.由T'的最优性知C(T)?芒(T,).于是C(H)?c (Hf).因H一为(Q.)的最优解,H?t.故H'必为(QJ)的最优解. 同理可证下述命题. 命题3设T是G的满足下述条件的最小支撑树:对任何i?V,dT'(i)?b"构作如 下H-:V(H.)一v,.E(H')一E(T')\((n+I.i):i?V}.则H.为(Qz)的最优解,且C(H.) :芒(T.)一(n--m)M. 上述命题2,3表明:解(QJ)只须求召的最小支撑树,解(Q2)只须求G中满足次限制条件 的最小支撵树因此,可直接应用[I]或[2]的算法求解(Q)或().[I][2]中算法是对一般 图设计的,命题1说明(Q)(Q2)的最优解具有特殊的性质.下面我们将根据这些特性设计较 简单的算法. ?4.数学规划方法 由命题1可知,(QJ)()的最优解共包古n—m条边,这些边一端在v一内,另一端在V\ v-内,而且v\v.内的顶点只与v_中的一个顶点相连结.这样,我们可把(QJ)看作下面的 指派问题:v-表示m个人,V\v.表示n—m项工作,c.,(j?V,j?\v*)表示第i人做工作j 的时间,要求每项工作只能由一个人做(但一人可做多项工作),如何安捧使总的工作时间之 和最小?而(QD只须在上述问题中再加上一条限制条件;第i(?V-)人最多只能做b-项工 作. f1,在i,j之间连边; . 令一l0,否则. 可得(QJ)(Q:)的0I规划模型: (P)胁??q IEV_JE,v. f?%=1(?) &Lr- 【?{0,1)(i?V.,』?) ()胁??cIjxIIteV_JE' f?=1(』?叭) "1??(?.) iJ?n 【不,?{0,】}(?,?\.) 命题4(Q)(j=1,2)有可行解当且仅当)(i=l,2)有可行解. 证明仅证i=l的情形.设l】为(PI)的可行解,构作图H如下V(H)=V,E(H)={(i, j);一1),易知H?.在以后的讨论中将这种由{)'lI)得到的子图H记为ft({)).反之,设 H?对任何j?V\V.,A;{(i,j))?E(H):j?v_.)?m,从每个AJ中取出条边共碍到1'1 ? 13- 三缀网络的最低费用 一 m条边.这些边的集合记为E(矗).定义:一l,若(i.j)?E(n),一0.否则.易知协.,)为 (Pj)的可行解.i=2情形的证明完全类似. 命墨5设{.)是(R)(i=l,2)的可行解.刚{】''?)是(E)的最优解当且仅当H({})为 (Qi)的最优解. 证明仅证l的情形.显然,己G】=c(H({)).设H((})是(Q.)的最优解, 'EV-J?V,V. '' 对(PI)的任一可行解{),作H({-,})?又c'H'{)''一 . -,-由于c'H ({)))?c(H({..J)),故{)为(PI)的最优解.反之,设J)是(PI)的最优解,任取(QJ)的 一 十最优解HI,定义xIo=l,若(i,j)?E(HJ),x,?;0,否则,由命题l易知{X)为(P-)的可行 解,于是c(H({x.iJ))一??G.???c=c(H),故H({})为(Q-)的最优解. ?Ev-?,v.??-,?V,v. 于是.我们只须解(Pj)(P:)就可以了. (PI)的求解很简单:对任何JoEV\v.,令G^一m_m{cj?V.)(如有多十io,任取其一). 令x一l,一0(i?V\{}),易证这样得到的{)是(PD的最优解. 若n=2m,bl—l(i?),则(P2)化为通常的指搌问题0】.故()是指派问题的一个推 广.[{]中讨论的问题是()在一切=k时的特殊情形.[4]中算法比较复杂.下面我们将 (P|)直接转化为指派问题求解,只须直接利用匈牙利算法0即可,我们的方法对[4]中算法 也是一十改进. ni1 令l一bl,u=(1,2'..?,1).记s(i)一2Jbt,对任何k,j?u,j?V\V.),若s(i--1)+ jEV-t-I l?k?sd)(iEV.),令—GJ.考虑下述指派问题: (P:)胁.??-.】z.J??r,r. ) f?=l(J?)l? .1?五,?l(t?u)I鬲 - 【z?{0,1)(I?,?".) 命题6设(}是(Pr)的最优解,令 =(?,j?叭) 则{埘}是(Pz)的最优解,并且()(P:)的目标函数的最优值相等. 证明{)的可行性可逐条验证,此处从略,下证其最优性.设{xJ.)为()的任一可行 解,对任何k?u,必有i?vm,使s(i—1)+l?k?s(i).令J(i)一{j?V\v-:xr1)一{j.k, …,},其中q?,jI?m+1.-?n.并且j<j2<…<i.定义(z,LI}如下:若j=I,k=s(i--1)+ r(1?r?q),则ZIJ—l否则Z-J一0,容易验证{z,lJ)为(P:)的可行解且x,"一2JZlJ. 又?z一???;??.同理可得??-?Z,一 lE'lE,v.1E-l.-(j—1)+lJ?V-?'v-j?V-.-?-JE,v- 量故q一????z,?GIx,.由{)的l?. ,v-??JeY?'j?V\Y.^?'j?v,-1?V-J?V- ?l4? 管理工程 任意性知{x1.f为(P:)的最优解. 因此?要解(.=)只须用匈牙利算法求解()即可. 参考文献 [1]Rondy3AandMu啊USR:(Graph1rywi也Aop/Jcations},A腱f.Evjef.1976I [2]刘振宏?马种蓍?朱永津?蔡茂诚:{具有次限村的最小树同题,. 应用教学,1980.3(I):l一】2 [3李避,钱颂迪:运筹学).北京,清华大学出版社,1982; [4]周饵:最优分援题的算法',教学的实践与认识.i989.({):49--52. MINIMALCOSTOFATHrEE--LEVELNETWORK (im月_啪J~gaa9 (ManagementSchoo1.日ml喜hi3iaoTongUniversity} AbUra~ Three--!eveln甜boI岫naopee~inpI咖Il咄llI11凼阻perinves~tes血edeitBI. ofithr?一 k侧"then鲫V州嘲havebeen. , damen.Two?_抽,tominimizingnetwork%t presented... Keywor^:Afar,morSe,5'punni~Tr竹.A舒证mnt,IlPr0^懈. 责任编辑:蒋绍忠 ? l5?