（应用数学专业论文）网络模型中分式规划问题的研究.pdf

摘要 摘要 普通网络下的最大流问题，最短路问题，运输问题及分配问题作为 最小费用流问题的特例在六七十年代就有了许多有效的算法，而最小费 用流问题是各种网络规划问题的核心和基础，在金融，管理，经济等科 学应用与研究中发挥着重要作用。很多工作者致力于建立新的数学模型 并把它转化成最小费用流问题来解决。 研究网络图上的线性分式规划有着重要的理论背景与实际意义，本 文首先考虑了普通网络模型中有限制的线性分式转运问题的数学模型， 给出了基本可行解的概念并通过引进一个新的检验数论证了基本可行 解是最优解的判别准则，总结了有限步终止的迭代步骤。其次把目标函 数推广为分段线性分式函数给出了普通网络模型中的分段线性分式转 运问题的数学模型，给出了该模型下的基本可行解的概念，论证了基可 行解是最优解的充要条件，总结了有限步终止的迭代步骤。本文最后考 虑了增益网络模型下的线性分式转运问题，通过分析增益网络中节点位 势及流量增广迹上流量调整算法，提出了增益网络中线性分式转运问题 基的迭代算法及有限终止。 关键词网络图，支撑树，增益网络，基可行解，检验数 a b s t r a c t a b s t r a c t s o m es p e c i a lm i n i m a lc o s tf l o wp r o b l e m so nn e t w o r ks u c ha st h em a x i m a lf l o w p r o b l e m ，t h es h o r t e s tp a t hp r o b l e m ，t r a n s p o r f a t i o np r o b l e ma n da s s i g n m e n tp r o b l e mh a v e h a dm a n ye f f i c i e n ta l g o r i t t u n si n1 9 6 0 s t h em i n i m ac o s tf l o wp r o b l e mi st h ec o l ea n d b a s eo fe v e r yo p t i m i z a t i o np r o b l e mo nn e t w o r k s ，a n db e c o m e sm o r ei m m i n e n c ei nt h e s t u d ya n da p p l i c a t i o no fa d m i n i s t r a t i o n ，e c o n o m i c ，b a n ka n d s oo n m a n yr e s e a r c h w o r k e r sg i v en e wm a t h e m a t i c a lm o d u l ea n dc h a n g ei ti n t om i n i m a lc o s tp r o b l e m s t u d y i n go ff r a c t i o n a lp r o g r a m m i n go nn e t w o r kh a sa ni m p o r t a n t t h e o r e t i c a l b a c k g r o u n da n dp r a c t i c a lg r o u n d s i nt h i sp a p e rif i r s t l yc o n s i d e r e dt h em o d u l ea b o u tt h e l i n e a rf r a c t i o n a lt r a n s s h i p m e n tp r o b l e mo nn e t w o r kw i t hb o u n d e dv a r i a b l e s ，g a v ea d e f i n i t i o no ft h eb a s i cf e a s i b l es o l u t i o na n dp r o v e dt h ec r i t e r i o na b o u tab a s i cf e a s i b l e s o l u t i o ni so p t i m i z a t i o ns o l u t i o nb yi n t r o d u c i n gan e wn u m b e ro fi n s p e c t i o n ，s u m m a r i z e d t h ei t e r a t i o ns t e p se n d e di nl i m i t e ds t e p s t h e nic h a n g e dt h eo b j e c t i v ef u n c t i o ni n t ot h e p i e c e w i s el i n e a rf r a c t i o n a lf u n c t i o no nn e t w o r k ，g i v et h eb a s i cf e a s i b l es o l u t i o no ft h e m o d u l e ，p r o v e dt h eo p t i m a l i t yc r i t e r i o n ，a n ds u m m a r i z e dt h ea l g o r i t h m s f i n a l l y , t h e p a p e rc o n s i d e r st h el i n e a rf r a c t i o n a lt r a n s s h i p m e n tp r o b l e mo ng a i nn e t w o r ka n dg a v et h e e f f i c i e n ta l g o r i t h m s k e yw o r d s ：n e t w o r k ，s p a n n i n gt r e e ，g a i nn e t w o r k , b a s i cf e a s i b l e s o l u t i o n ，n u m b e ro fi n s p e c t i o n 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 己属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：彳勿c 浮缸日期：抄9 年r 月6 日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于 论文作者签名，拎v 和 导师笨名：讫 保密口，在年解密后适用于本声明。 不保密口。 ( 请在以上方框内打“”) 同期：一7 年8 月6 日 日期：砌沣5 月6 日 青岛大学硕士学位论文 引言 随着计算机科学的应用和发展，网络规划与计算机科学相互渗透，推动着网络 规划的应用范围不断扩大和深入。研究网络规划问题，如网络的最短路问题，最小 费用支撑树问题，最小( 最大) 费用流问题，及s t e i n e r 树问题的算法设计与分析， 已成为计算机科学的一个重要研究方向。普通网络下的最大流问题，最短路问题， 运输问题及分配问题作为最小费用流问题的特例在六七十年代就有了许多有效的算 法，而最小费用流阿题是各种网络规划问题的核心和基础，在金融，管理，经济等 科学应用与研究中发挥着重要作用。很多工作者致力于建立新的数学模型并把它转 化成最小费用流问题来解决。在这些网络问题中，对于每条弧来说，流入的流量总 是等于流出的流量。例如设弧f ，= l ，。，j ，记从节点y 。流入p ，的流量为x ，a e ，流 入节点v ，的流量为t ，则总假定，= j ：。然而在现实问题中也会碰到另一种情况， j 即这两者并不相等。一般地我们可表为x ：= 口，工，其中口为非负实数，称为弧p ，的 增益系数。如果口， 1 ，则流过p ，后流动对象会增加；反之，口， 0 ，则称q 为发点，匆的 值为该点的供给量；若包 1 流量通过该弧时就增加，若o 0 ，则有 ”，剖姐 m 砷：黔：糍 o k b a c x # - u y x 4 如果蚴晦且勺巩脯乃一蚓 o ，因此如果。s 一有 。( ”，貅( ”。制卜 = 剖籍= 所以石。是( 2 i ) 的最优解。 因此如果存在伉，五) e 2 ，黾 o ：或者纯，五) 岛， 0 ，设 伊= m i n 幻l ( 硎彬一x ；i o k o ) ： j 心= z ：+ 口( f ，) c 0 ) 工：= 司- 0 ( f - ，) e c ( 2 2 ) l 砖= 巧o ( f ，) 薯c 容易证明ej 是一基本可行解，并且有 和) = 剖= 掣斧s ( 2 ) 纯， ) e 3 ，s o ，设 口= m i n 兢一习j o 。脚 ；霉k 抽，；k j 隧；。黔亿s ， 容易证明弛 是一基本可行解，并且有 删= 剥= 蚓铲 = ，。) = ，伍。) 定理2 2 2 如果问题( 2 i ) 是非退化的，并且存在最优解，那么我们可以通 过有限步的计算得到其最优解。 证明 如果问题( 2 1 ) 是非退化的。则有o 口 。，按照定理1 的证 明，似1 ) ，。) ， 因为有有限个基本可行解，所以定理2 2 2 是正确的 第二章运输能力有限制的线性分式转运问题 2 3 计算步骤 s t e p l 设x o 是( 2 1 ) 的基本可行解，对每一边q ，力芒e 计算 铲。j , a l 五( n e 秭)o ，k c “) 圹。毛，铲。石西o j 蓐c 协)o k c ) 铲”，制 如果( f ) e 2 ，- o ；o r ( i ，) 易， o 。 f 批 设o = 石9 眉 咒+ = 是乃k ) 的分段点， 且 0 = 0 0 酣 g 岂 瑙。= 是 岛k ) 的分段点 设 o = 酵 群 镌 镌+ ，= 一是集合9 ，彰j ，= o 1 + l ，七= o 1 ，o ，+ l j 的元 素按递增顺序排列成的，则在每一区间盼，敞】，= o ，l ，中乃k ) 与勖幻) 都 是线性的，这样在每一区间眇，硪】内乃k j 与岛b ，) 都能表示成 也= c u ix + a f ，l = o ，i 1 川f 与 鼽k ) = 群+ 群，i = 0 , i ， 其中 ，形，彰，= o l ，勺，o ，_ ，) e 都是实数。因为乃k ) 是凸的，劫k ) 是凹的，我 们有酣s c s s f ：且甜钟d ：( f ，) e 9 第三章网络图分段线性分式规划问题模型及有效算法 定义3 1 基本可行解设j o 是( 3 1 ) 的一个可行解，如果存在e 的某个子集 置满足下面条件 1 0 巨是g 的一棵带根生成树。若o ，_ ，) 局，则硝s x ：s 坛。 2 。如果( f ，_ ，) 舞五，畅o 酵，硝，比。j ，那么x 。称为( 3 1 ) 的一个基本可行解。 若存在( f ，) 晶，而砖船，群，屹+ j ，则称x 。是( 3 1 ) 的一个退化的基本可 行解，否则为非退化的基本可行解。由文献臼儿“，可得到下面引理。 引理3 1 存在问题( 3 1 ) 的个最优解是基本可行解。 引理3 2 如果( f ，_ ，) 芒巨，那么 ( f ，肼u 局包含唯一圈。 定义3 2c 的方向与边毡，) 正墨的方向相同。c 0 ) 表示与c 同方向的那些边， c = c 、c 心) ，对任意边g ，) 芒置定义 鸟2 。，磊高一。磊盎，嘞2 。，磊。，吒一。石盘o ，j 覃c “)o ) e c 扣)o ，) e c “) o j k c 佃) 其中白与吒的选取原则是：若( f ，- ，) 巨，则有彬s 戢，那么选取2 气，秽= 吒 若o ，j ) f e e 。则有习= 彬船，钟，鳃+ 。j ，由于此时砖= 矽可由当前值向左 或向右变化( 即减少或增大) 因此当减少时对应的费用系数为馥。、碰。，增大时对 应的费用系数为、彩，所以若( f ，_ ，) 叠晶，c ，( 或c 厶) = 勺，彰( 或础。) - - 4 当c ，= 勺，群= 办时用砖，；分别来表示h ，当罐。2 勺，雄- 。如时用k ，“；分 别来表示九g ，f 定义3 3 检验数当o ，) 仨e 时，定义边( f ，) 的检验数为 s i = 巧一”i z ，= 岣一“；z 其中z 表示当前目标函数值。如果对于( f ，) 芒五，x ，= ，那么s ：定义为0 ， l o 青岛大学硕士学位论文 类似的当而= o 时，巧定义为0 3 2 主要定理及其证明 定理3 1 ( 最优判别准则) 设x o 是( 3 1 ) 的一个非退化的基本可行解。那么。 是( 3 1 ) 的最优解的充要条件是对所有g 力芒罨，都有s o 且o 。 町 o ，考虑 。两种情况都与石。是最优解矛盾。 、j一、j 矿 “ 、-，一、-， 一 “一“ 有 电 、j、j0 佃 c c c盛 力力力g 伉以 啃坞砖砖净 = = 工 矗 ，l 第三章网络图分段线性分式规划问题模型及有效算法 反之，假设是( 3 1 ) 的非退化的基本可行解且满足对所有( f ，) 仨局都 町蛆批糊来证叫是，的最优解。训= 矧并考虑 m i l i s ( x ) - x + g ( x ) f x , s 一x n = q ，i = 1 ，2 一一 j ( ，) e e恤，卜f io s 其最优值设为，) ，只要证明f k ) = o ，- - m s ( x ) 一旯g ( x ) o 。从而对任 黼黼有器筹一雕 z 懒懈显然 i ( x ) 一a + g ( r ) = o ，所以f p ) o 。假设f k ) o 考虑 m i n 也) o ，k 厅 f 勃一= q ，i = 1 , 2 ，甩 ( 3 2 ) s x 4o ，i e 怔k 【o s 嘞s 其中嘞k ) = 乃也) 一r 勖也j g 力e e 我们有g ，) = ( c ，一r 钟b ，+ q y r 雕l 础s 硪。，1 = 0 , 1 ，2 ，x + 也是 ( 3 2 ) 的基本可行解。因为f k ) o 炙；= 砖一豁j 0 o ，这与对所有( f ，歹) 芒蜀都 有s ；o 且s ；o 矛盾。因此f k ) o 是不可能的从而，) = o 。证毕。 3 3 算法分析 由定理知如果当前基本可行解不是最优解，那么至少存在一条边瓴， ) 叠e 使 j o 或s ； 0 1 2 青岛大学硕士学位论文 情形i 若存在也， ) 薯e 。使对 o ，那么应该增加瓴， ) 上的流量使目标函数 怫= x ；+ o ，( f ，) c ( a ) 值减少，设调整后的流量为 = 菇一e ，g 力e c 铆 【砖= 彤，( f ，_ ，) 芒c 为保证调整后的流量仍是基本可行解取9 = b = m i i l ，：， 其中 ，= m i n 幻一矽i p ，k 。( 。) ，：= m i n 协一书l o ，k 。u ) ，：聊g 一舻 如果o 。= i ，那么支撑树中有边o ，) 日其流量达到分段点矽从而成为离基变 量，非基变量h 。成为进基变量如果e 。= ：，那么支撑树中有边( f ，_ ，) 局其流量 达到分段点碳从而成为离基变量，非基变量工。成为进基变量。如果o = ，则非 基变量气 流量增加到珊仍是非基交量。 目标函数值 剖= 矧+ 为 剥。 经过上述改进，我们能够得到新的改进的基本可行解从而继续进行新的迭代。 下面我们考虑如果瓴，五) 的流量增加值e 超过e ，怎样改进使目标函数值继续下降。 ( 1 ) 0 。= 时有边( f ，工) 置其流量达到分段点彬，若值。超过o 。则以， ) 上 的流量会继续减少，从而根据勺与吒的选取原则有c 凹= ，d 凹2 d 而其余勺与 吒不变计算新的础= 一z ( e ；肪，如果趔2 0 ，则e 。是我们能够得到的最大 值即在该非基边上能够增加的最大流值，从而需重新置扩= 勺 ，d p = 噍 。如果 捌 o 则非基边瓴， ) 叠置能够继续增加流量，此时只要在 l = m m 锄一矽i o ，k ( 。) j 中以，l 凹代替砧“就可增加。值减少目标函数值。重复这一 过程直到得到最大的0 。 ( 2 ) o - = a ：时有边o ， ) 互其流量达到分段点馓，若值e 超过0 l 则( f ，只) 上 的流量会继续增加，从而根据c 口与吻的选取原则有珊= 。，础t = 噍 而其余勺与 第三章网络图分段线性分式规划问题模型及有效算法 嘞不变。计算新的s 搿= 砖一z ( 0 知；，如果s 聊o ，则o 是我们能够得到的最大 值即在该非基边上能够增加的最大流值。如果础 o 则非基边以， ) 叠e l 能够继续 增加流量，此时只要在2 = m i i l 如乜一砖b k ( 。) 中以他皇代替础，就可增加e 值减少 目标函数值。重复这一过程直到得到最大的0 。 ( 3 ) 0 。= 3 时边也， ) 仨e l 的流量h 增加到榭，若值e 超过o 任意小， 伉， ) 仨e j 的流量h 超过群管从而根据勺与吒的选取原则有。c l i j t = 气 ， 珊= 噍。而其余勺与办不变。计算新的掣= 砖- z ( o 。- ；，如果s _ ：5 ：) o ，则o 。是 我们能够得到的最大值即在该非基边上能够增加的最大流值。如果删 o ，那么应该减少伉， ) 上的流量使目标函数 心= o - 0 ，( f ，) c ( a ) 值减少，设调整后的流量为 砖= 而o + o ，o ，) c p ) 【一- - 协oo ，_ ，) 薯c 为保证调整后的流量仍是基本可行解取0 = b = m i n a ，a ：， 其中 l = m i l i 幻一酬硎。) ，：= m i n 如一碍b 蚓。) j ，a 3 = 砂 一榭 如果o = ，那么支撑树中有边( f ，j ) e 局其流量达到分段点彬从而成为离基变 量，非基变量吒 成为进基变量若如果o 。= ：，那么支撑树中有边( f ，) 局其流 量达到分段点杖- 从而成为离基变量，非基变量h 成为进基变量。如果e i = ，则 非基变量 流量减少到坩仍是非基变量。 目标函数值 矧= 翻一晶 矧 经过上述改进，我们能够得到新的改进的基本可行解从而继续进行新的迭代。 1 4 青岛大学硕士学位论文 如果瓴， ) 的流量减少值。超过e ，可类似情形1 进行讨论。 定理3 2 如果问题( 3 1 ) 是非退化的，并且存在最优解，那么我们可以通过 有限步的迭代得到其最优解。 证明如果问题( 3 1 ) 是非退化的，则有o 口 气。，按照定理3 1 的证 叽( x 1 ) ，( x 。) ， 因为有有限个基本可行解，所以通过有限步的迭代可得到其 最优解。 3 4 计算步骤 3 4 1 计算步骤 s t e p l 设x o 是( 3 1 ) 的基本可行解， 对每一边g ，) 薯历 计算 j i = 巧一甜i z ，s ；= 砖一“：z ，如果对所有( f ，j ) i e e l ，如果巧_ o r s ；2 0 ，那么由定 理3 ，1 ，x o 是( 3 1 ) 的最优解，停止。 若瓴， ) 叠巨使“ o ，转步3 。 s t e p 2 计算l = m i i l 钯一矽k 。) e c 。) j ，2 = m i i l 协一岛i o 。k 。( 。) j 。 ，= 珊一砂 和o = m i n i ，：，3 如果o = 1 ，有边g ，工) 乓其流量达到分段点矽，如果础 o ，那么置 钆2 出，噍 2 础并转步2 否则转步4 如果0 = a ：，有边( f ，丘) 蜀其流量达到分段点碳，那么置f = 搿， d e j , = 础如果j 搿 o 转步3 否则转步4 。 如果e = 包。如果劣 o 那么置气 = 谐，吒 = 刷并转步3 否则转步4 。 f 砖- - - - x ：+ o ，( f ，_ ，) c 0 ) s t e p 4 调整流量。如果 o ，则 l 嘞i = 司，( f ，) 仨c f 砖= 吆o - 0 ，( f ，_ ，) c ( x ) 弓= 巧o + o ，( f ，_ ，) c o ) i 矗= 彤，( f ，) 正c s t e p 5 修改支撑树，仁；一( f ，_ ，) u 伉， ) 为新的支撑树。转步1 3 4 2 算例 s t 五+ 而= 5 一而+ x 2 = 0 一屯一而= 一5 0 工7 0 而7 0 x 3 7 其中，石“，= 协三麓霸“，= 0 篆茹 青岛大学硕士学位论文 删= 2 x - 1 , 0 x 2 ；删= 学鬈7 圳= 盛二警三删= 0 嚣 解“，x ：，而) = ( 5 ，5 ，o ) 是基本可行解，z = 罢= o 8 8 此时笱= i - 4 - 2 = - 5 ，心= 2 - i - i = 0 ，霹= - 5 ，所以得到最优解“，屯，而) = ，) v l 图3 i 茎婴童望蕉堕垒主垡丝坌垄茎堕鲤星一 4 1 问题模型 第四章增益网络中线性分式转运问题 设g = o ，e ) 是一个连通有向图，对矿的每一个节点e 给定实数q 并且满足 q = o ，每边( 毛d 暑有一个上界气，球，缸口 o ) 是该边上的增益系数 白2 0 和吒o 是给定常数，那么增益网络中运输能力有限制的线性分式转运问 题是： 脚= 器= 鬻 睚矿 磊，吲卅 2 ，一 ( 4 1 ) 1 1 j 勘 耻j h u l j 10 s s 假设对每一个可行解x ， 似) 0 不失一般性，总可假定系数矩阵是行满秩的，因为否则的话可象普通最小费 用流那样添加a t - 变量。任选线性无关的拼列构成基b ，它们对应的图g 中的边构 成g 的子图g a ，与普通网络不同的是g s 不一定是连通的，而且还可能包含着圈! 将基丑所对应的图g 。中的每一个极大连通子图称为g 。的分支。显然按照这些分支 改变口的行与列的次序，总可把占表成块对角阵的形式：b = 其 中每个皿对应着一个分支，记作嚷忙= l ，) 。我们把只有一个圈而没有根弧的连 通图称为单圈拟树。 1 8 青岛大学硕士学位论文 4 2 主要定理与计算 定理4 2 1 增益网络中的基曰相应的图g 。的每个分支g k 只有两种可能：或者 是有一个根弧的树，或者是单圈拟树。 证明显然& 必为子方阵。不然的话毋的列向量( 或行向量) 线性相关，从而 b 中若干列( 或若干行) 线性相关，与b 是基矛盾。这也就是说瓴的节点数与弧数 相等，而g 是连通的，它必有生成树。因此g k 只可能由一棵生成树再添上一条弧 所组成。这也就意味着瓯只能是有一个根弧的树或者是单圈拟树，证毕。 定义4 2 1 设x o 是( 4 1 ) 的一个解，如果存在e 的某些边ei = 1 , 2 , 3 满足： l o 五是g 口的边集。 2 0 # ，d 薯置：巧0 - - 0 , ( i ，) ee 2 ；x ：= ，( l j ) e 易 则x o 是( 4 1 ) 的一个基本可行解。 对于普通网络问题，任意一对节点i 和，之间存在唯一树路。而对于增益网络我 们定义从根节点或从一个圈到达某个节点i 的方向为该迹的方向并称为有向迹，它 是唯一的。在某有向迹上若有弧似力的方向与迹的方向不一致则称其为后向弧，否 则称为前向弧以圈上任一弧( f ，) 的方向为该圈的方向，与其方向一致的弧为前向 弧，否则为后向弧定义了方向的圈为有向圈。无论在有向圈上还是在有向迹上， 流量逆向流经后向弧o ，_ ，) 的费用为詈，增益系数为吉，我们分别用和来 a #a h 表示上面两数，这并不影响下面的计算。 定义4 2 2 v l v 2 崎是g i 中的有向圈，称= q 2 嘶i 为圈增益，它表 示一个单位的流量流经该圈后的流量增益。 由文献“”，可得到下面引理。 引理4 2 2 存在( 4 1 ) 的一个最优解是基本可行解。 设弧( f ，力e 的费用系数是c v ，用乃，来表示节点q ，0 的节点位势。对 第四章增益网络中线性分式转运问题 任意弧( i ，) e i ，由般线形规划的互补松弛性条件知有等式 霄 一a 4 霄i = c h 4 2 1 ) 成立。由定理4 2 1 知g 。的每个分支q 只有两种可能：或者是有一个根弧的树， 或者是单圈拟树。因此我们只要考虑在这两种情况下如何求出节点位势。 先看q 是带根树的情形。设根节点是v ，则有厅，= 0 ，然后由公式( 4 2 1 ) 逐次利用每条弧上已知万值的一端求出另一端点处的节点位势。 再考虑单圈拟树的情形，设q v 2 坼v ，是q 中唯一的有向圈，则节点位势满足 如下方程组： ，# i ， l 嘞 = g 1 2 ，c ，q 。) ( 4 2 2 ) 自g r 黜嗍愀出乃= 坐坠专警逊z 然后由公式( 4 2 1 ) 逐次利用每条弧上已知石值的一端求出另一端点处的节点位 势 若弧( f ，力e 的费用系数是如，则用嵋，来表示节点u ，_ 的节点位势 求法同上。 定义4 2 2 设九= 一一嘞乃一白，= w j 一坳- d 目定义边( f ，歹) 的检验数 是 呤嘞制 定理4 2 2设z o 是( 4 1 ) 的一个基本可行解，如果 ( f ，_ ，) e e 2 ，o ；( f ，_ ，) 岛，岛o ，那么x o 是( 4 1 ) 的最优解。 证明同定理2 2 1 的证明过程，此处略。 由定理4 2 2 知如果存在瓴， ) 易，j o ；或者瓴， ) e 3 ，s 饥 o ，则瓴，五) 的流量可增加，令= ，其余的非基 变量取值不变。设从某根节点或某个有向圈分别到节点和 的有向迹分别用p 和 孽表示，则puq ，a ) uq 构成流量增广迹，我们只要在该迹上调整流量而其余流量 不变。在流量增广迹上考虑节点_ ，我们把从节点_ ，到的有向通路上的各条弧定 义为集合肼弓，把从节点，到 的有向通路上的各条弧定义为集合膨一定义节点 增益乃为：在弧瓴，五) 上一个单位流量所需要的流入节点_ ，的总流量改变量。一旦 乃计算出来，我们就可以计算弧( f ，- ，) 上的流量改变量，把它作为弧以， ) 上的流量 改变量有的一个函数。 若弧( f ) 为前向弧在弧( f ，力上相应的流量增加量她= 筹 ( 4 2 4 ) 此时记岛2 y _ j l ； 若弧g ，) 为后向弧，在弧( f ，) 上相应的流量增加量为。= - y ，a ( 4 2 5 ) 此时记气= 嘶， 于是( 4 2 4 ) 和( 4 2 5 ) 可统一为a f = 毛 ( 4 2 6 ) 关于乃的计算，取决于该节点在基本网络中的位置一个节点有六种可能的位 置每种情况下乃的定义如下 1 节点在前向部分，但不在圈上 ，：士 ( 4 2 7 ) 铲丽 “卫 2 节点，在后向部分，但不在圈上 乃2 最 “2 ( i 砖“ 2 l 第四章增益网络中线性分式转运问题 3 节点，在公共部分，但不在圈上 l 口a 铲面一意 ( 4 2 9 ) 4 节点，在前向部分又在圈上，我们定义屏为前向通路上的圈增益，则 乃。南壶 ( 4 2 1 0 ) 5 节点，在反向部分又在圈上，而磊为该圈增益，则 乃2 一丽r 而a l * j ti 恤) e 村， ( 4 2 1 1 ) 6 节点，在公共部分又在圈上，而孱为该圈增益，则 乃2 南t 赤一黄， 妊j ? l ”n妊j k “i ， 然后计算 妒幽删) 妒曲降忪o ) a = m i n a ，：，九。j 然后将代入( 4 2 6 ) 式求出流量增广迹流量改变量， 其余流量不变。 ( 2 ) 瓴， ) ee 3 ，s e o k i ，- ，) 岛，屯 o ， 如果瓴，五) e ：转s t e p 3 ；如果纯， ) 易转s t e p 4 s t e p s 计瓤= 曲岛删) 妒疵降o 及厶= m i l l 豁。，：，。 。 f 两i = 巧0 + 嘞 ( j ，) p u q 调整流量 x k = 然后转s t e p 【= 砖，0 - ) g p u q ，五) u 窖 s t e 碑计轧= 幽协驴o 妒幽降傺o 第四章增益网络中线性分式转运问题 及= m i n 诠l ，2 ，k j f 矗= 司一磊矗， g 力e p u q 调整流量 戎 ； - a 然后转s t e p l 1 弓= 习，) 萑p u ( i k ，j 。) u q 定理4 3 3 如果问题( 4 1 ) 是非退化的，并且存在最优解，那么我们可以通 过有限步的计算得到其最优解。 证明如果问题( 1 ) 是非退化的，则有o 护 吒 ，容易证明，( x ) 职。) ， 因 为有有限个基本可行解，所以定理是正确的。 青岛大学硕士学位论文 总结 本文用网络规划的方法解决了网络图上容量有限制的线性分式规划及分段线 性分式规划问题，通过不断修改支撑树来改进基本可行解，从而得到了有效算法。 由于增益网络模型具有更广泛的现实意义，我们也考虑了增益网络模型中的线性分 式规划问题，根据增益网络中基口所对应子图g 。的最大连通分支是带根树或单圈 拟树的性质得到了有效算法通过我们的研究扩大了网络规划的应用范围，为进一 步研究网络图上其他非线性费用函数的优化提供了借鉴。 参考文献 参考文献 【l jb ，d c r a v e n , f r a c t i o n a lp r o g r a m m i n g , h e l d e r m a r mv e r l a g , b e r l i n , 1 9 8 8 ， 【2 】e m u n t e a n u ，f r a d o ，c a l c u l u ls a r j e l o rc o l o rm a ie e o n o m i c c l ac u p t o a r e l ed et o p i tf o n t a s m d i is i c e r c e t 撕m 锄e m 烈i c e ，c l u i ，f a s e i o l aa n e x ax i ，1 9 6 0 ，p p 1 4 9 - 1 5 8 【3 】s s c h a i b l e ，f r a c t i o n a lp r o g r a m m i n gi ：d u a l i t y ，m a n a g e s c i a2 2 ( 1 9 7 6 ) 6 5 8 - - 6 6 7 【4 】s s c h a i b l e , a n a l y s ea n da n w e n d u n g a n v o nq u o t i e n t e n p m g r a m m e t hv e r l a ga n t o nh a i n , m e i s e n h e i ma mo l a n , 1 9 7 8 【5 1 a c h a r n e s ，w w c o o p e r , p r o g r a m m i n gw i t hl i n e a rf r a c t i o n a lf u n e t i o n a l s , n a v a lr e s e a r c hl o g i x t i c s q r a r t e r l y 9 ( 3 a n d 4 x 1 9 6 2 ) 1 8 1 - 1 8 6 【6 k s w a m p , l i n e a rf r a c t i o n a lp r o g r a m m i n g , o p e r a t i o nr e s e a r c h1 0 ( 1 9 6 5 ) 1 3 1 1 4 4 【7 k s w a m p ，u p p e rb o u n dp r o b l e mi nl i n e a rf r a c t i o n a lf u n c t i o u a l sp r o g r a m m i n g m e t d k a l 5 ( 1 9 7 7 ) 8 1 8 5 【8 a m a r t o s 。h y p e r b o l i cp r o g r a m m i n g , n a v a lr e a s e a r c hl o g i s t i c sq u a n e r l y l1 ( 1 9 6 4 ) 1 3 5 1 5 5 9 e p a n d e y , as i m p l e xa l g o d t h mf o rp i e c , e w i s e l i n e a rf r a c t i o n a lp r o g r a m m i n gp r o b l e m s , e u r o p e a n ) o t m m io f o p e r a t i o n lr e s e a r c h 8 ( 2 0 0 6 ) 2 4 7 - 2 5 5 1 0 p a 8 0 u d ya n du s 1 l m u r t y , g 忸p l it h e o r yw i t ha p p l i c a t i o n s , t h em a c m i l l a np r e s si nn e w y o r k , ( 1 9 7 6 ) 2 9 【1 1 】张建中、许绍吉线性规划，科学出版社。1 9 9 0 1 2 】x i e ，l t ap r o g r a m m i n gp r o b l e m o nn - c o m p l e x , a n n a l so f d i s e r c t om a t h e m a t i c s1 9 8 0 ， 8 ：2 6 7 - 2 7 4 【1 3 】z h a a g , h a n d i n g , al i n e a rf r a c t i o n a lp r n g r a m m m gp r o b l e mo nn - c o m p l e x j o u r n a lo f a p p l i e d m a t h e m a t i c s ，1 9 9 6 ，i ( 1 9 ) ：1 5 8 - 1 6 1 【1 4 】s e h a i b l es f r a c t i o n a lp r o g r a m m i n g , z e i t s c h r i f lf u ro p e r a t i o n sr e s e a r c h , 1 9 8 3 ，b 2 7 ：3 9t o5 4 1 1 5 】w o