（应用数学专业论文）运输问题的扩展.pdf

摘要 本文研究了平衡运输问题的逆问题、增益网络中运输问题的逆问题及平衡运输 问题的最优护充问题。 第一章中讨论了平衡运输问题的逆问题。本章考虑的是变量有上界限制的平衡 运输问题( 假设存在可行解) 的逆问题，通过尽可能少地改变目标函数中价值系数 的取值，使得给定的运输路线成为最优路线。首先提出逆问题的模型，基于线性规 划问题解的最优性条件，分别在f l 和乙模下提出了有效的解决方法。在f l 模下，应 用对偶理论，把问题转化成有快速解法的最小费用循环流问题：在乙模下，通过对 相应具体模型求解，提供了新的价值向量的构造方法。 第二章中讨论了增益网络中运输问题的逆问题。首先提出增益网络中运输问题 的逆问题的模型，在第一章中对平衡运输问题逆问题研究的基础上，考虑在z ，模下 把问题转化成最小费用循环流问题的来求解。同时讨论了增益网络中运输问题的对 偶问题及求解对偶问题的单纯形方法。 第三章中研究了运输问题的最优扩充问题。本章考虑平衡运输问题中扩充费用 函数为线性函数的情形，首先给出扩充问题的模型，然后把问题转化成参数规划问 题，通过最优解的性质，推导出最优性条件，根据投入预算费用量随参数增大而增 多的关系，通过增大参数取值，提供在预算d 限制下的求解算法。- 关键词：运输问题；逆问题；增益网络；最优扩充 a b s t r a c t t h i sa r t i c l ed i s c u s s e st h ei n v e r s et r a n s p o r t a t i o np r o b l e m sw i t hb o m l d e d v a r i a b l e s ，t h e 1 n v e r s et r a n s p o r t a t i o np r o b l e m si nn e t w o r kw i t h g a i n sa n dt h eo p t i m a le x p a n s i o no f c a p a c i t a t e dt r a n s p o r t a t i o np r o b l e m s i nt h ef i r s tc h a p t e r , w es t u d yt h ei n v e r s et r a n s p o r t a t i o np r o b l e m si n c l u d i n gu p p e r a n d l o w e rb o u n d c o n s t r a i n t s ，s u p p o s i n gt h a tt h eb a s i cf e a s i b l es o l u t i o n sa r ee x i s t e d w en e e d t oa d j u s tt h ec o s tc o e f f i c i e n t so fag i v e n t r a n s p o r t a t i o np r o b l e ma sl e s sa sp o s s i b l es ot h a t ak n o w nf e a s i b l es o l u t i o nb e c o m e st h eo p t i m a lo n e f i r s t l y ，t h ea c c o r d i n gm o d e li s o f f e r e d ，t h e nam e t h o di ss u g g e s t e dw h i c hi sb a s e do nt h eo p t i m a l i t yc o n d i t i o n sf o r t r a n s p o r t a t i o np r o b l e m s ， r e s p e c t i v e l yu n d e rz la n dz 。m e a s u r e s u n d e r ，im e a s u r e ，t h e p r i m a lp r o b l e mi st r a n s f o r m e di n t oam i n i m u mc o s tc i r c u l a t i o np r o b l e mw h i c h h a sm a n v q u i c km e t h o d st os o l v e ；u n d e r 。m e a s u r e ，w ef i n dt h em e t h o dt ob u i l dt h en e wc o s t t o e 筒c i e n t s i nt h es e c o n dc h a p t e r ，w ec o n s i d e rt h ei n v e r s e t r a n s p o r t a t i o np r o b l e m si nn e t w o r kw i t h g a i n s f i r s t l y ，w eg i v et h ea c c o r d i n gm o d e l ，a n dt h e nt r a n s f o r mt h e p r i m a lp r o b l e mi n t oa m i n i m u mc o s tc i r c u l a t i o np r o b l e mu n d e r f l m e a s u r e ，a c c o r d i n gt ot h es t u d yo ft h e 1 n v e r s et r a n s p o r t a t i o np r o b l e m si nt h ef i r s t c h a p t e r t h ed u a lp r o b l e m sa n di n v e r s e p r o b l e m sa b o u tt r a n s p o r t a t i o na r ed i s c u s s e da sw e l la st h es i m p l e xm e t h o df o rs o i v i n g t r a n s p o r t a t i o np r o b l e m si nn e t w o r kw i t hg a i n s i nt h et h i r dc h a p t e r , w es t u d yt h eo p t i m a l e x p a n s i o no fc a p a c i t a t e dt r a n s p o r t a t i o n p r o b l e m s w ea d d r e s st h ep r o b l e mo fa l l o c a t i n gag i v e nb u d g e tt oi n c r e a s et h ec a p a c i t i e s o fa r c si nat r a n s p o r t a t i o n p r o b l e mt om i n i m i z et h ec o s to ff l o wi nt h en e t w o r k t h e c a p a c i t ye x p a n s i o nc o s t so fa r c sa r ea s s u m e dt ob el i n e a rc o n v e xf i m c t i o n s w eu s e p r o p e r t i e so ft h eo p t i m u ms o l u t i o nt of i n dt h eo p t i m a lc o n d i t i o n sa f t e rc o n v e r t i n gt h i s p r o b l e mi n t oap a r a m e t r i cn e t w o r kf l o wp r o b l e m t h er e s u l t i n ga l g o r i t h my i e l d s a i l o p t i m u ms o l u t i o no ft h ec a p a c i t ye x p a n s i o np r o b l e mf o ra l l b u d g e tl e v e l sl e s st h a no r e q u a lt ot h eg i v e nb u d g e t k e yw o r d s ：t r a n s p o r t a t i o np r o b l e m s ；i n v e r s ep r o b l e m s ；n e t w o r kw i t hg a i n s ：t h e o p t i m a le x p a n s i o n 学位论文独创性声明 本人声明，：所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人成果，均已作出明确标注或得到许可。论文内容未包含法律意义上已 属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿承担由此引发的一切责任和后果。 论文作者签名： 卫香确 同期： 形年f 月) - 0 同 ， 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅、以及申请专利等权利。本人离 校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然 为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密曰。 ( 请在以上方框内打“”) 论文作者签名： 导师签名： 掰确 诈承 ( 本声明的版权归青岛大学所有， 同期：a 翊年f 月矿日 同期：w 踌6 月日 未经许可，任何单位及任何个人不得擅自使用) 引言 引言 一、关于平衡运输问题、增益网络中的运输问题及其各自的逆问题 j 组合优化问题i l l 1 2 11 3 1 ，如网络的最短路问题、最小费用支撑树问题、最小( 最 大) 费用流问题等，其应用范围已随着计算机科学的应用和发展而不断扩大和深入， 特别是涉及到网络规划设计( 如网络基础设施建设、网络通信能力和智能路由设计 等问题) 的研究需求更加迫切。网络规划设计的关键问题是研究面向网络的组合优 化问题的求解技术，这方面已成为计算机科学领域的一个极为活跃的研究方向。 近年来，研究组合优化问题的逆问题的求解技术成为网络规划设计的一个热 点。通俗地讲，组合优化问题是从已有的可行解的集合中寻找一个最优( 最大或最 小) 解；而组合优化问题的逆问题就是通过一系列的调整变化使一个已知的可行解 变为最优解，而这种变化又要满足一定的约束条件。b u r t o n 和t o i n t 4 j 首次把“逆 问题”引入到组合优化的研究领域。许多优化问题的逆问题都有了新的研究成果， 如逆最短路问题、逆最大容量问题、逆支撑数问题、逆排序问题、逆最大流与最小 割问题、逆最小费用流问题、逆最小树形图问题等。a h u j a 和o r l i n 5 1 为优化问题 的逆问题提供了很多参考资料，汇编了许多应用实例，并给出了一般逆问题和线性 规划逆问题的算法；a h u j a 和o r l i n l 6 l 运用他们的线性规划的逆问题的算法解决了 网络流问题的逆问题。b u r t o n 和t o i n t l 4 l1 7 1 、b u r t o n ，p u l l e y b l a n k 和t o i n t l s l 研 究了在，模下求解逆最短路的算法，并用非线性规划的技术解决了它。x u 和 z h a n g 们、z h a n g ，m a 和y a n g i 0 1 研究了在，模下求解逆最短路的算法。y a n g 和z h a n g l l l 】 解决了最大容量路问题的逆问题。y a n g 和z h a n g i | 2 j 、z h a n g 和c a i1 1 3 】研究了f 1 模下 的最小割问题的逆问题。这些问题都可以归结为最小费用流问题，并且几乎所有的 研究都是运用线性规划的对偶理论来解决问题的。 组合优化问题及其逆问题的研究在国民经济和社会发展的宏观决策中具有明 显的应用前景，也为智能软件的决策支持系统的研究提供了一种新的数学模型和求 解思路。组合优化问题的逆问题在国民经济和社会发展的宏观决策中有许多应用事 例。比如在国民经济宏观调控中，如果人们期望实现某种经济效益( 如国民经济的 增长速度或生产总值等) ，如何适当调整现有的各种费率，以达到我们的目的，且 从国民经济稳定的角度考虑，自然要求调整的各种费率如银行利率、政府税率等有 尽可能小的该变量。这正是典型的组合优化问题的逆问题的一个应用。一般地说， 逆问题的主要应用是，在某些情况下，尽管建立线性规划的数学模型，但目标函数 中的费用系数向量很难精确给定，根据经验或实验，能得到所需的可行解，我们希 青岛大学硕十学文论文 望运用这些已知的信息尽可能小地调整费用系数，以获得满意的效果。研究平衡运 输问题的逆问题及增益网络中运输问题的逆问题对现实生活中经常遇到的经济建 设、宏观决策等重大问题的解决有重要的意义。 平衡运输问题是网络组合优化问题中的一个比较经典的问题，也是日常生活中 经常遇到的一种网络优化问题。设脚个送货点4 ，4 ，以的送货量分别为 a l ，a 2 ，a m ，肛个收货点旦，岛9 j 9 e 的收货量分别为6 i ，6 2 ，从送货点4 到收 货点雪i 的单位运输费用为乞，同时假设满足 a s = 屯，扛l ，2 ，m ，= l ，2 ，以 i = l = l 这即成为平衡的运输问题。 在一个网络中，假如设弧勺= ( 4 ，e ) ，记从节点4 流入的流量为毛，从p ，流 入节点曰，的流量为而，可能出现x , i 与矗并不相等情况，一般地我们可以表示为 f = q ，毛，其中为非负实数，称为弧e ，的增益系数。当q ，1 时，就称为有增益 的网络。在运输问题中，若收货点b ，收到货物的量与送货点4 ，提供其货物的量不同 ( 原因可能是运输途中的损耗等) ，则此问题即属于增益网络中的运输问题。 本文将在线性规划问题的逆问题研究的基础上研究上述两种运输阅题的逆问 题。 二、关于运输问题的最优扩充问题 随着i n t e r n e t 的发展和计算机应用领域的不断扩展，网络通讯能力的扩充和 扩大为网络优化问题提出了若干新课题。今后的研究工作已越来越重视网络容量的 全局概念，而不只偏重研究任意两点间的最大容量问题，只有从整体上把握网络的 容量( 其反映出网络系统的物流容纳能力和通过能力) ，才能运筹整个网络。随着 社会需求的不断提高以及对费用最优的要求，已有网络能力往往不能满足实际需 要，需要对网络的能力进行扩充和提高。 网络扩充在国民经济中发挥着重要作用，道路改造、电网升级、机器更新都需 要利用网络扩充的知识。网络扩充就是在现有网络的基础上，通过改造网络中部分 或全部弧的容量，来提升网络的容量和性能。如远程会议、多媒体远程教育、电子 商务、实时信息服务、视频点播、网络游戏等都是由一个或多个发送者传送给众多 的被传送者，传送的过程中涉及带宽时效问题，只有合理调整通讯带宽，才能保证 实时效果。在实际中研究带有投资费用限制的网络容量扩充情形才有意义。 f u l k e r s o n t h l 研究了在容量扩充费用函数为线性函数的情况下，如何增加网络 中弧的容量使得整个网络中的流量最大化。b a n s a l 和j a c o b s o n t ”1 ，c h r i s t o f i d e s 2 引言 和b r o o k e r1 1 6 l ，h a m m e r i ”l ，p r i c e t 嵋1 研究的是容量扩充费用函数为非线性函数的情 形。y a n gc h a o 等【i9 】曾对无向网络中带约束的最大容量路的扩充问题进行研究，其 用线性规划的方法提出了这个问题，采用网络规划的方法给出了一个递归算法。l i u z h e n h o n g 等 2 0 l 从网络定位问题的逆问题的角度，对以一点为根的有向通讯网络扩 充问题进行了研究。 本文研究的问题所属的情况是：根据投资者的资金状况和投资能力，一定时期 内投资者只能拿出一定数量的资金改善或新建网络，如何扩充网络的容量使得所需 费用达到最大程度的减少。这种情况在实际中有许多应用，如天然气运输管道系统 网络、污水处理系统网络、道路运输系统网络、电子传输网络等的容量扩充。r k a h u j a ，j l b a t r a 【2 6 】等己研究了转运网络的最优扩充问题，研究把问题转化成参数网 络流规划问题来解决。本文将在其研究的基础上讨论在平衡运输问题中，对给定的 预算d ，如何找到相应的算法来扩充线路的容量使得运输费用达到最大程度的减少。 第章平衡运输问题的逆问题 第一章平衡运输问题的逆问题 本章考虑的是变量有上界限制的平衡运输问题( 假设存在可行解) 的逆问题， 通过尽可能少得改变目标函数中价值系数的取值，使得给定的运输路线成为最优路 线。基于线性规划问题解的最优性条件，在f 1 模下，应用对偶理论，把问题转化成 有快速解法的最小费用循环流问题；在乞模下，通过对相应具体模型求解提供新的 价值向量的构造方法。 1 1 预备知识 1 1 1 平衡运输问题的模型 设m 个送货点4 ，4 ，以的送货量分别为q ，口：，a 。， 刀个收货点 e ，岛，e 的收货量分别为岛，如，饥，从送货点4 到收货点b ，的单位运输费用为 c u ，则变量有上界限制的平衡运输问题的模型可写为( 考虑存在可行解的情况) ： rm” l m i nz ( x ) = c 矿 i 扛司 i嘞- - a i ，f = 1 ，2 ，2 ，m 1乞1 l毛= t ，= l ，2 2 ，门 【0 毛磅，i = l ，2 ，优，= 1 ，2 ，z 胛疗 其中，口= 乞，屯o ，i = 1 ，2 ，m ，= l ，2 ，疗。 j = l 3 = 1 1 1 2 一般线性规划问题的逆问题 给定一个一般l p 问题 ( 尸) m i n c x l a x = 6 ，x 0 其中，g x r ”，b r ”，a 为朋甩阶矩阵。假设妒为一可行解，我们需要尽可能 少地改变系数向量c 的取值，使得妒成为c 调整后( 三p ) 的最优解。 若令 f ( x o ) = 辟r ”m i n 矧彳x = 6 ，x o = & 。 ， 则( 三尸) 的逆问题可以表述为 4 青岛大学硕士学位论文 m i n l i c - 非f ( x 。) 定理1 1 1 1 设p 为( l p ) 的一个可行解，则x o 成为最优解的充要条件为：存 在向量万r j i ，使得对= l ，2 ，刀，满足( a ) 7 r 勺；( b ) # oj 刀e = c j 。 其中，弓为难阵彳的第列。 定义向量 彳。；或e a 一，叫= o e a 。，血? o 其中0 ，= c ，一万p j jjj e a + ，其中9 - - 万e , 一巳 其中，彳+ = e i 万e 巳 ，彳。= e l 万只= c ， ，爿一= e i 万e o 。 1 2 逆运输问题 1 2 1 问题的提出 给定一个变量有上界的线性规划问题( 尸) m i nk l 血= 6 ，o x 0 ，a 为m 玎阶矩阵。假设x o 为一个可行解，我 们要考虑的是，如何尽可能小地调整费用向量c ，使得x o 关于新的费用向量c 成为最 优解。此逆问题可写成下面模型： 引理1 2 1( 尸) 的逆问题可以写为 m i n 氕p js c t + 8 i ， n p 1 2 c l 一9 l ， 兀pj 2 cj 一8 p 其中，z = 协，0 = o j ， 第j 列。 z l j 1 j 0 = ( 品，岛，包) 0 ，- ，u ，= 0 l o x ，0 k j ，了= 0 卜，0 = k j ，万r 册，p j 为矩阵彳的 本文考虑变量有上界的线性运输问题( b t p ) ： 6 青岛火学硕士学位论文 r a i n c 。 l = lj = l = q ，i = 1 ，聊 j = l 嘞- - b j ，= 1 ，门 j - l 0 吒，i = 1 ，朋，= 1 ，z 其中，各变量满足以下条件 a = ( o ，口：，以m ) 7 。0 ，b = ( 6 。，吟一，b 。) 7 0 ， 0 k u + ，i = 1 ，m ，j = 1 ，门 口j = b i = 1 ，聊，= 1 ，门 i = 1 ，= 1 其逆问题即为改变目标函数中的价值向量c ，使得已知的一可行运输方案 x 。= g r , x 0 ，x 。0 。) 关于新的价值向量；成为一个最优方案，且l l - 一c 忆最小。这里 l c - c l i 有，1 2 和，。三种不同选择： ( 1 ) c l i l = 阿l ； ，= i ，。一用 ，= l 一n f、互 ( 2 ) i 叫2 毫i 弘n ) 2j ；j = ， ( 3 ) 卧c 卜m a x l 万1 j 2 i ，胛 j 5 l ，疗 本文将考虑在f 。和f 。模下的情况，并假定x o 为非退化的基本可行解，即x o 中的 基变量都不取其上界值或下界值。 1 2 2 逆运输问题模型 引理1 2 2 设x 。= g ：，x ，石。o 。) 为( b 卯) 的一个可行解，则x 。( b t p ) 的最 优解当且仅当存在向量q i ，甜2 ，“。，v i ，v 2 ，v 。) ，对所有f _ l ，m ， = 1 ，以， 满足 ( 1 ) x ：= 0 ，“，+ v c 口 7 第一章平衡运输问题的逆问题 满足 ( 2 ) 0 x ： 0 。当x ? = 0 时，由( 1 2 ) 知， w ，= 0 ，所以根据( 1 1 ) ，有n a c ，即u ，+ v ，c ，( 1 ) 成立；当0 x ? c ( 3 ) 成立。证毕。 令白= c 口+ 巳一口，色，口口0 ，vf = l ，m ，j = 1 ，n 。其中，p ，为对c 。增 加的量，口dy 9 x , - t c f 减少的量，则可知，8 1 ；c t = 0 。下面讨论中令上= 挺，) l x ；= o ， j = 埏，j t o x ： c o 一口口，( f ，) j u - ) 吼0 ，( f ，) j _ u j 吃o ，( f ，j ) j t j j 0 = 。，q ：，既。) ，口= 证明令 ，口1 2 ，口。) 万= 1 ，“2 ，“。，v 1 ，1 ，2 ，v 。) ， c ! ，= c 仃+ 岛一口 ，岛，o ，vi = l ，朋，j = 1 ，n 由引理1 2 i ，逆问题可写成 8 即 等价于 等价于 m l n j i c - c l | 坼+ v j 勺，( f ，) + v j = c ：f ，( f ，) 坼+ v j i ，( f ，) 了 r a i n j a + 0 1 i 坼+ v j 一岛+ 口- c f j ， + v j 一巴十= 勺， u i 七v j 一9 口+ q j c j ， 色o ，0 ， r a i n 陋+ 6 1 j u l + v j 一9 sc i ， i + v j 一9 q 七a 2c j ， “，+ 丫，+ c o ， 岛0 ， q ，0 ， r a i n f a + o i j 甜f + 一岛c ， “，+ 一岛c 0 ， 甜f + + 0 ， 坼+ 0 + c ， 皖0 ， 芝0 ， 此即定理中所给逆问题的模型。证毕。 1 2 3 ，1 模- f ( z b t p ) 的求解 ：芒e l i 模下，逆问题( 昭开) 变成 9 ( f ，) ( f ，) j ( f ，) 了 i = 1 ，聊，= 1 ， ( ，- ，) ( f ，) ( f ，) 了 ( ，_ ，) z u j ( f ，) 儿j 了 ( f ，) ( f ，) j ( f ，j ) j ( f ，) 了 ( ，j ) _ j u j ( f ，) 儿j 了 ( 佃t p l ) m i n ，巳+ + ，( 心+ ) ( ，j ) e ( ，) ，( f ，) “ 坼+ v j 一巴勺，【f ，j ) + v + 乃一1 2 扩= c f ，( f ，j ) j 甜，+ + c i j ，( f ，) j 岛0 ，( f ，j ) 1 2 , j 2 0 ，0 ，( f ，_ ，) j 0 ，( f ，j ) j 其中，为当( f ，) ，时对c 口的增量，为当( f ，) 厂时对c 的减量，且心巧= 0 。 其对偶问题为 ( d z b 阡1 1 m i n ，c 。凡一e c g y q 一g ：y y ( ，) e z ( ，) ，( , j ) e 一儿一= o ， i = 1 ，2 ，所 j = ，l ，；i 2 ，月 j = l “2o ” ( ，j ) e ( i , j ) e ， f i , j ) e d 一 的一y u 一= o ，= l 川2 一，托 ，= 1 2 ， ( ，) k i ，2 ，一 “i ) e , j 0 y 1 ， 一1 s 1 ， i = i ，2 ，” ( ) e ：7 ( f ，) j u z ( f ，) j 此为最小费用循环流问题。参考文献 2 2 中己给出了求有向网络的最小费用循环流 的强多项式算法。 求出( d i b t p l ) 的最优解歹后，利用对偶原理，即可求出( 姐即) 对应，模下的最 优解拓，；，y ；，口； ，最后求出调整后的向量 一 c2 c i g + 喏， c i , j + 以， c q yq ， c b q b ， c q ( f ，) z ( f ，) ( f ，- ，) k = 0 ( f ，) 沁) ，i 版= 0 ( f ，) j 其它 青岛大学硕士学位论文 即x o 在新的价值向量c 下是最优解。 1 2 4 ，。模下( 佃卯) 的求解 在，。模下，逆问题f f b t p ) 变成2 4 1 m l nw “，+ v j 勺+ 岛，( f ，) z u j 甜，+ 2 c 一，( f ，歹) j u j w 一岛0 ，( f ，) j _ uj w 一0 ，( f ，) j u j 吼0 ， ( i ，) _ ju j 口u 0 ，( f ，j ) uj 在上述模型中，令w 代替所有的巴，则最优值不变： r a i nw + v l 巳+ w ，( f ，) e _ j u j t 一 “，+ c i j w ，( f ，) j u j w 0 ( 1 4 ) 当工。不是( b 卯) 的最优解时，调整量岛或必有且只有一个为f 值，( 1 4 ) 的最优 值w 必为正值，因此约束条件w 0 可以省略。即乙模下，逆问题( 馏冲) 变成 ( i b t p o o ) m i nw j + c ：f c 4 一w ，q ，j ) e 八) j 且“：+ 吒 c ￥ ， 其它 则在乙模下，当用c 代替c 时，z o 变为( b t p ) 的最优解，且此时调整量最小。 证明 显然l i - 一c 忆= w 是逆问题( 凹冲) 的最小调整量，且0 ，v ，w ) 满足约 束 “巧 1 ，则从4 到b j 的流量会增加；反之，若所 o ) 在模下，( 肥变为 ( i g t p ) ( f ，- ，) j u ，+ ( f ，) + ( f ，) 一u ，+ ( f ，j ) ，+ m i n 巳+ e ( y j j + o ) ( i , j ) j 一( ，j ) e j + “，+ 岛丫，一岛勺，( f ，) j 一 坼+ 乃v j + 一l a , j = 巳，( f ，j ) + 岛0 ， ( f ，j ) j 一 心0 ，0 ，( f ，) j + 其中心，分别表示对已的增量和减量，( f ，j ) ej + ， a , i y o = 0 ( 佑印7 ) 的对偶问题可写为 ( d i g t p ) m i n 巳乃+ c c y v ( ，) e 厂( i ，) e ，+ y , s + 虼= o ，i = 1 川2 一，所 = l ，一月= 1 ，- - ，” ( ，) “。 ( i , j ) e j + p o y o + 岛托= o ，j = l 川2 一，聆 i = l ，m i = l ，” ( ，) e ， ( ，。) e ，+ 0 虼1 ， 一1 儿1 ， ( f ，) ，一 ( f ，j f ) ，+ ( d i g t p 7 ) 为增益网络中的最小费用循环流问题，已有较快的求解算法1 2 2 j 。 求得( d i g t p ) 的最优解歹后，根据对偶原理，我们可以确定( 坶即) 的最优解 锈，膨，巧 ，则调整后的向量为 青岛大学硕士学位论文 勺+ 锈，( f ，) ，一 勺+ 以，( f ，) 沁) ，+ | 巧= 0 c 矿一巧，( f ，) ( f ，) ，+ l 成= o c ， 其它 用c 代替( c r p ) 中的价值向量后，所给的基本可行解p 成为( g t p ) 关于新的价值向 量c 的最优解。 2 5 小结 本章利用对偶理论，讨论了增益网络中的运输问题的单纯形解法及其逆问题在 ，。模下的求解算法。 1 6 第二章平衡运输问题的最优扩充 第三章平衡运输问题的最优扩充 这一章考虑平衡运输问题中扩充费用函数为线性函数的情形，研究中把问题转 化成参数规划问题，根据投入预算费用量随参数增大而增多的关系，通过增大参数 取值( 每一步都保持解的最优性) ，提供在预算d 限制下的求解算法。 3 1 预备知识 对于一般变量有上界限制的平衡运输问题 r a i n4 x ) = 勺而 ，= i = l = a f ， f = 1 ，2 ，m = l = b s ， = 1 ，2 ，_ r l ，= l 0 x i j ， i = 1 ，2 ，m ，j = l ，2 ，甩 已有很好的求解算法。其中， 锄 o ，q = = 1 ，2 ，m ，j = 1 ，2 ，刀 i = l m c o 为从发点4 到收点b ，的单位运输费用，f _ 1 ，2 ，m ，j = l ，2 ，门 在现实情况中，由于实际需要，往往要扩充线路的容量，同时扩充费用限制在 预算d 之内。本章将介绍扩充费用函数为线性凸函数的平衡运输问题的最优扩充问 题，研究( 在给定预算d 之内) 如何扩充线路的容量使得运输总费用达到最大程度 的减少。 3 2 扩充模型 本章所讨论的模型为： 1 7 青岛大学硕士学位论文 ( t c e p ) 而= q ， y = l ，2 ，疗 i = 1 o 0 。假设气( o ) = o 。 3 3 模型转换 本苹将把( t c e p ) 转换成参数网络流i 司趑求解。不失一股性，1 嵌设对于( t c e p ) 的 任一最优解( z ，y ) ，( 3 5 ) 中”= ”均成立，则可推知 或= m a x 0 ，巧一磅) ，j - 1 2 一，研，j = 1 2 一，拧 这是因为，d a ( 3 4 ) 儿 m a x 0 ，巧一吒 ，i = 1 2 ，朋，j = l 2 ，门 若存在( ，j ) ，使得盛 m a x 0 ，巧一屯 ，则可构造出另一个最优解( x 。，y 。) ： 岛= ，i = l ，m ，= 1 , - - - , 以 彰= 巧，i = 1 ，r - 1 ，+ l ，聊，= 1 ，s - 1 ，s + l ，z 或= n 凇 o ，一k ， 则，( 3 5 ) 中”= ”不再成立，与假设矛盾。所以 巧= l l 姒 o ，x ：一 ，i = 1 2 一，掰，j f = 1 2 一，玩 在( 3 1 ) 至( 3 6 ) 中，令= m a x 0 ，毛一) ，得下列模型 1 8 m 乙b = 而勺 。川 。俐 l l = 对 、。 币。芦 mm 第二章平衡运输问题的最优扩充 m i n z ( x ) = 勺_ x ：f ， f = lj = l = q ， = l ，打 嘞= 乞， f = i f = 1 ，2 ，m ， = 1 ，2 ，以 ，打n 乞( j c f ) sd ，i = 1 ，2 ，聊，= 1 ，2 ，玎 - ij = 1 0 ， i = 1 ，2 ，m ，= 1 ，2 ，押 其中，毛( 而) 为毛的分段线性凸函数， 毛c 嘞，= ：；麓一心，墨等耋二。 司= o ，弓= 乃 o ，。= ( f ，j ) o x u 吒) ，= ( f ，) i 而，= + t o 下面考虑下列参数规划问题( 脚) ： r a i n w ( x ，口) = 勺嘞一口毛( ) i = 1j = ij i j = i = q ， ，= l = 乞， ，= i j c ：f 0 ， i = 1 ，2 ，m i = l ，2 ，m ，_ ，= l ，2 ，甩 ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) 其中，口0 。 引理3 3 1 假设对v 口，x 陋) 为( p n f p ) 的最优解，则当口满足 m l 毛( 勺) = d 时，x ( 口) ( t c e p ) 的最优解。 i = lj = l 证明 反证? 假设当口满足毛( ) = d 时，x + ) 不是( 卿) 的最优 ，= l = 1 解。设p 为( t c e p ) 的一个最优解，则 1 9 青岛大学硕士学位论文 那么， r 一 卅n e z c ，x ： c ，x o ( , z ) i = 1 t - - | l = l ，t 1 w ( x o , 口+ ) = 勺砖一口d i = 1 = j 勺巧( 口) 一口d = w ( x ，口) 与z ( 口) 是( p f p ) 关于口的最优解矛盾。 所以，当o t 满足e ，( z ，) = d 时，_ c ( 口) 为( t c e p ) 的最优解。 工一一 u 、u 、，7、 ，= i j = l 引理3 3 2 乞( 巧( 口) ) 关于口是单调递增函数。 ，- l j = l 证明 设0 q 口：，石( q ) ，x ( 口：) 分别是( 脚) 关于口。，口：的最优解，则 以下不等式成立 形( x + ，q ) = 勺x ：( q ) - a ，毛( 巧( q ) ) t = lj = lj ij = i c 扩x 0 1 ( a ：) - a ，乞( 巧( 口：) ) f = i = 1 i = lj = l w ( x ，口：) = c ，( 口：) - a ：乞( x ：( a ：) ) ，一，= ii = 1j = l 勺巧( q ) 一口：乞( 巧( q ) ) 两式相加并化简得 毛( 巧( 口。) ) 易( x ：( 口：) ) 因此， 岛( 巧似) ) 关于口是单调递增函数 i = 1j = l 根据上述两个引理，我们可以从c t = 0 开始不断增大口的取值来求解( p n f p ) 问 朋打 题，直至费用达到预算最大值即毛( ) = d 时结束，从而解决( 脚) 问题。 i = l = i 2 0 3 4 最优性条件 设g = ( ，4 ) 为( p n f p ) 相对应的网络图( n 为所有节点的集合，a 为所有弧的 集合) ，把么划分为集合b 1 ，b 2 , u o ，u 1 ，u 2 , 其中，b 1u b 2 为g 的一棵生成树。t i 酉i 定 义( p f p ) 的基本可行结构： 令 勤2 0 ，v ( i ，j ) u o k o ，v ( i ，) u 1 ，v ( i ，) u 2 由此可以确定一组唯一的 毛) 满足( 脚) 中的约束条件。若 毛 继续满足： o x o ，v ( i ，歹) b o k 9 九，v ( i ，) b 则称b ub 2 为( 脚) 的一个可行基，( b 1ub 2 ，u o ，u ，u 2 ) 为( p n f p ) 的一个可行基 结构。当上述两个不等式取严格不等号时，我们定义此解为非退化解。以下将考虑 非退化情形( 与口的取值无关) 。 通常，用( f ，- ，) 表示弧( f ，f ) 所在的不同集合的上标。 下面讨论中把k ， 分为两类：分别记下标集合为 s 。= ( ，i ) i o x 。 - k , k a ) ，s 1 = ( ，j k ) l k x 。“ s ou s = ( f ，州扛1 ，2 ，m ，j = 1 ，2 ，玎 并把巨，( x ，) 带入( p n f p ) 的目标函数中，则( 脚) 问题写成如下形式： 令 ( 尸m 叩1 ) m i n w ( x ，口) = 勺而- a ( p ；而+ 艺勺+ 目) i = 1 = l( ，) s o( ，j ) e s 。 嘞= 口， = l 嘞= q ， ，= l 0 葡， ， k 口x ， f = 1 ，2 ，m ，= 1 ，2 ，甩 ( j ，歹) s o ( f ，- ) s 则上式变为 0 p n f p 砼 m i n w ( y ，口) = c o y u + ，j ) e n ” 均= q + e ， = 1 = b j