（应用数学专业论文）一类广义规划问题的反问题.pdf

摘要 本文研究了广义上界问题的反问题及广义最大流问题的反问题。 第一章中讨论了广义上界问题的反问题，本章考虑的广义规划问题的反问题是 在一般线性规划反问题的基础上，通过尽可能少的改变目标函数中价值系数的取值， 使得给定的可行解成为所给广义规划问题的最优解。我们利用线性规划的最优性条 件，给出了( g u b ) 问题在模和屯意义下的反问题的数学模型及求解方法。并且在 模意义下我们给出了把( g u b ) 问题的反问题转化为它的对偶问题求解的一种方法， 若在给定的( c u b ) 问题的一个0 1 可行解，并且( g u b ) 问题的一个最优解的所有分 量是在0 与1 2 _ 间的条件下。 第二章中讨论了广义最大流问题的反问题，首先给出在通常情况下的最大流模 型，由于实际生活中网络流的变量通常是有下界变量的，所以我们提出了广义最大 流问题的模型，并提出了( g m f ) 问题修正的f o r d - - f u l k e r s o n ( 1 9 5 6 ) 算法，给出并 证明了反问题有解的充要条件，并从线性规划的角度将( g m f ) 的反问题转化为它的 对偶问题的最小割问题来解决。 关键词：广义上界问题；反问题；对偶问题；广义最大流问题 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 eg e n e r a l i z e du p p e rb o u n d i n gp r o b l e ma n d g e n e r a l i z e dm a x i m u m f l o wp 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 eg e n e r a l i z e du p p e rb o u n d i n gp r o b l e m ，b a s e d o nt h eg e n e r a li n v e r s el i n e a rp r o g r a m m i n gp r o b l e mw ec o n s i d e rt h ei n v e r s eg e n e r a l i z e d l i n e a rp r o g r a m m i n gp r o b l e m w en e e dt 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 g e n e r a l i z e du p p e rb o u n d i n gp r o b l e ma sl e s sa sp o s s i b l e t h a t ak n o w nf e a s i b l es o l u t i o n b e c o m e st h eo p t i m a lo n e t a k i n ga d v a n t a g eo ft h eo p t i m a l i t yc o n d i t i o n so fl i n e a rp r o b l e m ， i ti sp r o p o s e dt h em a t h e m a t i c a lm o d e lo ft h eg e n e r a l i z e di n v e r s e ( g u b ) p r o b l e m su n d e r n o r m sa n d 乞n o r m sa n das i m p l em e t h o dt os o l v ei t u n d e r n o r m s ，w et r a n s l a t e t h ei n v e r s eg e n e r a l i z e du p p e rb o u n d i n gp r o b l e mi n t oi t sd u a lp r o b l e m t os o n ei t e s p e c i a l l y , w ec o n s i d e rt h ec a s ei nw h i c ht h eg i v e nf e a s i b l es o l u t i o na r e 0 1v e c t o r s a n do n eo p t i m a ls o l u t i o no ft h e ( g u b ) p r o b l e mh a sa l lc o m p o n e n t sb e t w e e n0a n d1 ， t h e nt h ei n v e r s e ( g u b ) p r o b l e mc a nb es o l v e dv e r ye a s i l y i nt h es e c o n dc h a p t e r , t h eg e n e r a l i z e dm a x i m u mf l o wp r o b l e mi sd i s c u s s e d f i r s t l y , w ep r e s e n tt h eu s u a lm a x i m u mf l o wp r o b l e mm o d e l b e c a u s ei nr e a l i s t i cl i r et h en e t w o r k f l o wc o n t a i n sl o w e rb o u n dc o n s t r a i n s ，s ow ep r e s e n tt h eg e n e r a l i z e dm a x i m u mf l o w p r o b l e mm o d e l t h em o d i f i e da l g o r i t h mo ft h eg e n e r a l i z e dm a x i m u mf l o wp r o b l e mi s o b t a i n e d ，a n dan e c e s s a r ya n ds u f f i c i e n tc o n d i t i o ni sg i v e n ，a n dt r a n s l a t i n gt h ei n v e r s e g e n e r a l i z e dm a x i m u mf l o wp r o b l e mi n t ot h em i n i m u m c u to fi t sd u a lp r o b l e mt os o l v ei t k e yw o r d s ：g e n e r a l i z e du p p e rb o u n d i n gp r o b l e m ；i n v e r s ep r o b l e m ；d u a l p r o b l e m ；g e n e r a l i z e dm a x i m u m f l o wp r o b l e m 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 张玉夙吼加7 年月与日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密瓯 ( 请在以上方框内打“4 ) 论文作者签名： 导师签名： 张玉凤 、z 叩州 日期力口7 年月岁日 日期：2 伽舞月6 日 3 1 引言 引言 一、关于广义上界问题及其反问题 组合优化问题心朝，典型的组合优化问题有旅行商问题 ( t r a v e l i n gs a l e s m a np r o b l e m - - t s p ) 、最短路问题( s h o r t e s tp a t hp r o b l e m ) 、 最小( 最大) 费用流问题( m i n i m u m ( m a x i m u m ) c o s tf l o wp r o b l e m ) 、图着 色问题( g r a p hc o l o r i n gp r o b l e m ) 等，这些问题的描述非常简单，并且其应 用范围已随着计算机科学的应用和发展而不断扩大和深入，有很强的工程代表 性，特别是涉及到网络规划设计( 如物流信息管理、网络基础设施建设等) 的 研究需求更加迫切。但最优化求解很困难，其主要原因是求解这些问题的算 法需要极长的运作时间与极大的存储空间，以致根本不可能在现有的计算机上 实现，即所谓的“组合爆炸。网络规划设计的关键问题是研究面向网络的组 合优化问题的求解技术，这方面已成为计算机科学领域的一个极为活跃的研究 方向，也正是因为这些问题的代表性和复杂性激起了人们对组合优化理论与算 法的研究兴趣。 随着信息技术的迅猛发展及组合优化问题的科研成果有力的推动了组合优化问 题的反问题的求解技术，使其成为网络规划设计的一个热点。我们知道在组合优化 问题中，模型的所有参数都已给定，我们需要从所有的可行解中寻找一个满足目标 函数的最优( 最大或最小) 解，而组合优化问题的反问题就是通过一系列的调整变 化使一个已知的可行解在新的参数下变为最优解，有时不同参数的调整会引起不同 的费用，我们的目的是用最小的费用使得给定的可行解变为最优解。自1 9 9 0 年比利 时的d b u r t o n 和p h l t a i n t h l 首次把“反问题”引入到组合最优化的研究领域以 来，许多学者对此问题进行了深入地研究，并且很多的优化问题都有了新的研究成 果，如最短路问题的反问题、排序问题的反问题、最大流与最小割问题的反问题、 最小树形图问题的反问题、最大容量问题的反问题、支撑树问题的反问题、动态最 短路问题的反问题、选址问题的反问题等。a h u j a 和o r l i n 睛1 为最优化问题的反问题 提供了很多参考资料，汇编了许多应用实例，并给出了一般反问题和线性规划问题 反问题的算法；j z h a n g 和z l i u 6 j 给出了标准型线性规划反问题的一般形式，根据 最小费用流及分派问题的组合性质，分别给出了求解其相应反问题的强多项式时间 算法，并提出了分派问题的限制反问题以及利用组合性质得到的求解方法。 d b u r t o n ，p h l t o i n t 7 】把网络中弧长的最小调整量问题应用到两点间最短路问题 反问题的计算中，从而使最短路长不超过给定的上界。z h a n g 和l i u 8 ，给出了在网 青岛大学硕士学位论文 络规划和组合优化中最优解是0 - 1 矢量的情形，在模和在乙模下的求解方法。y a n g g l z h a n 9 1 9 】z h a n g 和c a i 1 0 】研究了模下的最小割问题的反问题，x u 幕l z h a n 9 1 1 1 】介绍 了最短路问题的逆问题的可行区域的组合结构。z h a n g 和y a n 9 1 1 2 j 解决了最大容量路 问题的反问题。这些问题都可以归结为最小费用流问题，并且几乎所有的研究都是 运用线性规划的对偶理论来解决问题的。 组合优化问题及其反问题的研究在国民经济和社会发展的宏观决策中具有明显 的应用前景，也为智能软件的决策支持系统的研究提供了一种新的数学模型和求解 思路。线性规划的反问题有其广泛深厚的应用背景如在国民经济宏观调控的线线 规划数学模型中，如果人们期望实现某种经济效益( 如国民经济增长速度或生产总值 等) ，如何适当调整现有的各种费率，以达到我们的目的，且从国民经济稳定发展的 角度，自然要求调整的各种费率如银行利率、政府税率等尽可能有小的改变量这 正是典型的线性规划逆问题的一个应用一般地说，反问题的主要应用是：在某些 情况下，尽管建立了线性规划模型，但目标函数中的费用系数向量很难精确给定如 果根据经验或实验，能得到所需要的最优解，我们希望运用这些已知的信息尽可能 小地调整费用系数，以获得满意的结果。研究广义上界问题的反问题及其广义上界 算法的应用对现实生活中遇到的大型问题的解决有着非常重要的意义。 广义上界问题( g u b 问题) 是一类具有特殊结构的问题，通常情况下直接求解 的基本思想是寻找一个与基阵有关，但阶数降低的满秩方阵，称为工作基，它能代 替基阵完成所有必要的运算，从而可减少存储量与计算工作量，由于( 6 u a ) 约束数p 一般比其他约束数m 的要大很多，而且结构简单，因此d a n t z i g 和v a ns l y k e 1 3 l 早年就 提出了一种使用t n 维的“工作基”的改进的有界单纯形法的算法( 称为g u b 算法) 来解此类问题，成功地在大型机i b m3 7 0 1 6 5 上解决了具有5 0 ，2 1 5 个约束条件( 其 中g u b 约束4 9 ，5 8 8 个) 和2 8 2 ，4 6 8 个变量的特大问题l l 刚。 本文将在一般线性规划问题的反问题研究的基础上研究广义上界问题的反问题。 二、关于广义最大流问题的反问题的研究 在现实生活中，存在着大量的“流”的问题，例如：客流，物质流，信息流， 不胜枚举，广而言之，“流就是将一些“物质从一个地点运到另一个地点。因此， 研究网络流可以优化结构，提高效率，发挥最大的社会效益和经济效益。 现代社会可以说在很大程度上是通过各种网络来管理与控制的，我们可以把一个网 络看成一个自来水管网络，煤气管网络，电力线网络或者是公路网络，铁路网络， 水运交通网络等，都可以归纳为一个交通问题，称为网络流，值得关心的是在这样 一个网络中最大流是多少? 所谓的最大流问题就是指在网络中每条边的容量都确定 2 引言 的情况下，从始点到达网络的终点的最大允许通过的流量及流动的途径如何确定。 在公路网络中的车辆流。供水系统的水流及金融系统中现金流等都存在最大流问题。 例如某公司通过一个单行公路网络把种货物从产地运到销地，选择其中若干条道 路，己知每条道路对这种货物通过数量的限制，公司根据销地对该货物的需求，制 定一个货物运输方案，使运到销地的货物恰好是销地对该货物的最大需求。为确保 公司的经济利润和防止销地市场的供大于求，公司、市场管理部门与公路管理部门 协商，修改道路对该货物通过数量的限制，是该运输方案为最大运输方案，但是修 改限制需投入，而投入与修改量成正比，现在要设计一个修改方案，是上述运输方 案成为最大运输方案，并且修改量最小。 y a n gj i n 和x i ez h e n g l l 5 】讨论了通常情况下的最大流问题的反问题，当反问题有解 时，把反问题转化为一个容量网络的最小割的问题来解决。l o uh u iy u a n 1 6 j 讨论了如 何确定边( 弧) 的最小变动上限以使新网络中的最大流为最小费用，并给出了适用 于一般情况的算法。 本文研究的问题所属的情况是：在实际生活中，在我们通过各种网络来管理 与控制的系统中，如自来水管网络，煤气管网络，电力线网络或者是公路网络，铁 路网络，水运交通网络等这些网络流的初始可行流并不一定是零流，所以本文改进 了一般情况下的最大流模型得到了一个广义的最大流( g m f ) 模型，并提出了 ( g m f ) 问题修正的f o r d - - f u l k e r s o n ( 1 9 5 6 ) 算法，通过修改容量使得所给的网络流 系统达到最大的流量。 3 第一章广义规划问题的反问题 第一章广义规划问题的反问题 本章考虑的广义规划问题的反问题是在一般线性规划反问题的基础上，通过尽 可能少的改变目标函数中价值系数的取值，使得给定的可行解成为所给广义规划问 题的最优解。我们利用线性规划的最优性条件，给出了( g u b ) 问题在模和乙意义下 的反问题的数学模型及求解方法。并且在f 1 模意义下我们给出了把( g u b ) 问题的反 问题转化为它的对偶问题求解的一种方法，若在给定的( g u b ) 问题的一个0 1 可行 解，并且( g u b ) 问题的一个最优解的所有分量是在0 与1 2 间的条件下。 1 1 预备知识 1 1 1 一股线性规划i 司趑的及i 司越 给定一个一般凹问题 ( l p ) m i n c xl a x = 6 ，x 芑o ) 其中，c ，x e r , b e r , a 为m n 阶矩阵。假设x o 为一可行解，我们需要尽可能少的 改变系数向量c 的取值，使得x o 成为c 调整后( l 尸) 的最优解。 若令 r ( x o ) = 彤 m i n 豇i 血；b , x0 ) 一缸。】 贝i j ( l p ) 的逆问题可以表述为 m i n o c 一。f ( x 。) ) 定理1 1 1 蚴设妒为( 己p ) 的一个可行解，, 贝t j x o 成为最优解的充要条件为：存 在向量乃只”，使得对wt 1 2 ，控，满足( 口) 刀p ，s c ，；p ) _ o 辛万p ，一c j 其中， p ，为矩阵4 的第_ 列。 定义向量 4 p j e a o ；勒，e a 一，血；一o p i e a - , 蹦_ q 其中8 i i c j - a r p j p j 彳+ ，其中q c j 一万p ， 其中，彳+ 一 i 万p ， c ，) ，么。= 弓i 万p ，- c ，) ，彳一； 乞i 石p ， 薯 觏觏 巳 0 再 l 且 翟 第一章广义规划问题的反问题 “r o g p p j 搿- - o j - - 印c j , 誊e j + 其中，。a j l z ，ot o ) ，+ 一 j l x ? 0 ) 。 1 2 广义规划问题的介绍 1 2 1 广义规划问题的模型 定义1 2 1n 8 1 所谓的广义上界约束是指这样的一组约束条件： ( 1 ) 其中每个约束都是要求一组之和不超过一给定的上界( 由于变量有非负约束， 故这个上界总是正数) ； ( 2 ) 每个变量最多只能出现在一个这样的不等式约束中。 定义1 2 2 n 蚰带有广义上界约束的凹问题称之为广义上界问题，或简称为 g u b 问题。 显然，通过一下四个步骤： ( 1 ) 将变量重新排列，使出现在同一个g u b 约束中的一组变量排在一起，并将在 所有的g u b 约束中均不出现的变量单独列为一组，排在最前面； ( 2 ) 添加松弛变量，将所有约束化为等式约束； ( 3 ) 将g u b 约束的两边同除以右端项； ( 4 ) 如需要的话，改变变量的尺度，使在g u b 约束中的系数均为1 ； 总可以假定g u b 问题的形式如下1 1 8 1 m i n c o x o + c 洋l + c p xp ( g u b ) s ， 1 p i 气 x o ，x l ，xp 20 这里e = ( c f l ，q ：，c i n i ) 都是行向量，t 是所有分量均为1 的行向量。它们与列向量 x i 有相同的维数强，4 - 是朋矩阵，j 一0 ，1 , 2 p ，b e e “，这罩所有变量分为p + 1 6 暑 霉 p 髟 4 + + 墨一4 + 0 x a 青岛大学硕士学位论文 组。 第0 组变量x 。s ( ，p ) r ，在p + g u b 约束中的系数均为零，对 i - 1 , 2 p ，第f 个变量五一( 气，而：，) 2 在第f 个约束中的系数均为1 ，在其余的 ( r u b ) 约束中的系数均为零。文【4 】给出t 求解( g u b ) 的方法由于( g ) 约束数p 一 般比其他约束数朋的要大很多，而且结构简单，因此d a n t z i g 和v a ns l y k e l l 3 l 早年 就提出了一种使用m 维的“工作基的改进的有界单纯形法的算法( 称为g u b 算法) 来解此类问题，成功地在大型机i b m3 7 0 1 6 5 上解决了具有5 0 ，2 1 5 个约束条件( 其 中g u b 约束4 9 ，5 8 8 个) 和2 8 2 ，4 6 8 个变量的特大问题【1 4 1 。 1 3 广义规划问题的反问题 1 3 1 问题的提出 本文考虑广义上界问题( g u b ) ： m i n c o x o + c 叠i + + c p x p ( c u a ) s 2 i 墨p i1 x b ，x ，xp 0 这里c i = c i ，q ：，c 魄) 都是行向量，t 是所有分量均为1 的行向量。它们与列向量 置有相同的维数穆，4 f 是m 矩阵，i = 0 , 1 , 2 p ，b e e “，这里所有变量分为p + 1 组。 第0 组变量x o ；x o 。，p ) r ，在p 个g u b 约束中的系数均为零，对 f 。1 , 2 p ，第f 个变量置一( 玉。，而：，) r 在第f 个约束中的系数均为1 ，在其余的 ( g u b ) 约束中的系数均为零。 其反问题就是改变目标函数中的价值向量c = ( c f 。，q ：，气) ，使得己知的一可 行解f “= o ，1 ，p ) 关于新的价值向量互= ( 乏，：，毛) 成为一个最有方案，且 6 1 毒 霉 x 4 + 能描 + ka 第一章广义规划问题的反问题 0 互一ei loz o ，1 ，p ) 最小。这里0 e el l 有，l ：和z 。三种不同的选择： ( 1 ) i l e c ： t 荟，p 恳一c i ； c 2 ，u e e l k 4 ；j - 丕1 , 2 名6 一c 矗，2 2 、 一 j i f ， ( 3 ) i i 互一c fi l = m a x l 石。一勺l j m u , l , ，p i - 1 2 冉 本文将考虑在和屯模下的情况，并假定为f a = o ，l p ) 非退化的基本可行 解，即f o = o ，1 ，p ) 中的基变量都不取其上界或下界值。 设f o ；o ，l p ) 是( g u b ) 问题的一个可行但非最优解，要求在某种模的意义 下，尽可能少的调整价值系数c 使其成为新问题的最优解。根据【6 1 ，( g u s ) 的反问 础醉一g ) 4 ( i g u 8 ) 豇 ：r p o j 墨c o j 兀 一c q j 万弓+ q i l i s g 兀气+ q i k l c q j 厶 i j4 _ i 厶i l 2 , - - p _ 以i = 1 ，2 ，p 这里厶t j i 磕= 0 ) ，。一 j lx ：， o ) ；厶t ，i 砖= o ) ， * ，l 碍 0 ) o 一1 , 2 ，p ) 其中既是4 f 的第j y i j ( i o ，1 ，p ) ，石是维数为m 的行向量，q i 是维数为1 的行向 量，l | i l 是向量范数 设乞f f ic + 巳一，且岛，之0 ，i = 0 , 1 ，2 p ，_ | = 1 2 ，啊，这罩岛，分 别是勺增加和减少的量，注意到在我们的模型中岛嘞t o ，岛，不可能同时为j 下， 8 青岛大学硕+ 学位论文 根据【剐，( i g u b ) 问题可表示为： s 1 一孔p o j + x p o j + 一氕p 一 x p o + 岛 砌雌( ”。) 9 1 3 3 l , 模t ( 1 c u b ) 的求解 岛 j 厶u j i j jt 在模意义下，上述模型可写为： ( i g u b l ) 豇 厶u 几 j j o 芝嘞 j 厶u 以i 一1 ，2 ，p c o j j ii l 2 ，p i 一0 1 ，p i 一0 ，1 ，p 砌荟磊厶岛+ 善荟嘞智御- ，。向危 一嚣p o j 七 氕p o j 一冗p 一 氕p 日 + 岛 嘞 它的对偶问题为： 岛 嘞 j l u j i j e j t 厶u 厶 j e j o 吒 ，厶u j ii - l 2 ，p c 盯j 以 i l ，2 ，p i ；0 1 ，p i 。0 ，l ，p m a x c o r x o + c ：y o qx i + c y , s ：t a 戤 a x i l i x i 0s 0s 0s 0s 4 。k = 0 4 。￥ = 0 l jy i ；0 s 1 l jq u j - o s 1 j j n s1 j j iu 厶 s 1 j j i 9 i 一1 ，2 ，p it 1 2 p i = 1 ，2 ，p it 1 ，2 ，p + + 0 0口鹕砒i + + o o ” =口私 一 一 一 而蜘 第一章广义规划问题的反问题 这里 ， 分别是由a 的第p o j ? l j ( j e j 。) 和第既列( j 以，i = l 2 ，p ) 组成的子 矩阵，c ，r ，c 。t ，分别是由c 的第c 0 ，列( j 厶) 和c 的第c j l 列( 以，i = l 2 ，p ) 组 成的子向量。 若我们设 f j j 厶 f _ 厶 z o j 。1 ，一， j e j 。 白。1 吻一蜘 _ 五 则上面的对偶问题又可写为： m a x c t n za c 1 z i ( d i g u b l ) s 1 邻o = 0 4 f 五 = 0 l i z f 一0 0s z o j 墨1 j f 上o - 1s z o i s1 j - ，o 0s z j i s 1 j l - 1s 磊 s1 j e j i i 一1 ，2 ，p i ；1 ，2 ，p i 一1 ，2 ，p i l 2 ，p 这样，在模意义下( g u b ) 问题的反问题( ，g 叩1 ) 的最优解司转化为由它的对 偶问题( d ，g 嘲) 的最优解得到。下面定理1 3 1 考虑在特殊情况下，给出求解( g ) 问题的反问题( 堀咖1 ) 的一个简单方法 定理1 3 ，假设衅( f o ，1 ，p ) ( g u b ) 问题的一个。一1 可行解，且有一个 满足o s 墨s 的最优解f a = o 1 p ) ，是所有分量均为1 的列向量。它们与列 向量x ? 有相同的维数吩设 刀，9 _ 是( d g 珊) 问题的最优解，定义0 一0 ， 口：j m a x0 ，c o j 一万风j ) 其中 j ，。 ， 口：一m a x0 ，c 筝一万。p o 一西t ) 其中 j 以( f 一1 ，2 ，p ) ，则 乃，q ，8 ，口+ ) 是( 形1 ) 问题的最优解。 证明( g u b ) 问题的对偶问题是 加薹仍 一 青岛大学硕士学位论文 二_ _ 二二一一 ( b o y s ) 踉i3sq 2 ，p 我们首先证明 万，9 。，口，口) 是( 佑淞1 ) 的可行解，显然口，口+ o ，因为 刀，鼋) 是 ( d 6 u e ) 问题的最优解，则对任意的j 厶u j _ o ，啊+ - 呵既j 一c 0 另外，对_ j 。由口；的定义知：x p 。j + 口；万p 。+ m a x0 ，c o ，一万+ 风) 苫c o j 同理可证，对，以u l ，有哪毋一西+ 喏s - - j z p u 一西芑勺a 一1 ，2 ，p ) 对j f ，有万p q + 订+ 口；= p o + 西+ m a x0 ，c q 一万p o 一西) 苫勺ot 1 ，2 ，p ) 因此 石，g ，口，口 是( i g u b l ) 的可行解，最优值是荟l a 荟 我们现在证明 筇，g ，0 ，口) 是最优解，为了证明这个结论我们只需要证明 ( 伽嘲) 的对偶问题存在可行解，且有同样的目标函数值善p 荟 因为f 一0 】，p ) 和 万。，譬) 分别是够瑚) 和( 嬲阳) 的最优解，由互补松弛性条 件知： 五( c o j - - j g 胁，k ，+ 蓦荔( c 。既毗k = 。 ( 1 1 ) 因为f “= o ，1 p ) 是0 - 1 向量，且对每一个j e j 。，砖t1 ；每一个 j j i , x 0 = 1 _ - l 2 ，p ) ，由西，西o ；1 ，2 ，p ) 的定义及( d g 珊) 解 万，q + ) 的可行 性，知对每个j j 瓯南q ：j = c o j 一氕p o j ，对j j i ? 奄a ；= c u 一死p 一q ：i tq ；l 2 们 因此， 砉荟。荟口0 + ，砖+ 砉荟噶端 2 o ，+ 善p 善( c 爿毋一矿砖 第一章广义规划问题的反问题 = 盖( c o j - - y r * 既，+ 砉，盖( 勺爿既砒瑚 ( 1 2 ) 综合( 1 1 ) 和( 1 2 ) 两式，我们得到： 笔荟五( c o ) - - ，t * 风，) ( 霹，一，) + 薹，五( c 一石岛一西厶) 似一) 。一口( x ；一x o ) + 石a ( x ：一x ：) 一c - ( x ? 一x ? ) + 万4 ( x ? 一x ? ) + q 。l i ( x ? 一x o ) ( i - - - 1 , 2 ，p ) ；一c s ( x ；一x ；) 一口( f f ) ( i = l 2 ，p ) 因为弓一葛一 要三：兰芑l j 。，e l ，五i = 0 , 1 , - - - , p 所以f f a o ，1 ，p ) 是( d i g u b l ) 的可行解， 且有最优值 一c r ( f f ) ( f = 0 ，1 ，p ) 因此 z r , q ，0 ，口。) 和 f x ? ；0 ，1 ，p ) 分别是 ( i g u b i ) t f t i ( d i g u b l ) 的最优解 1 3 4 l 。模下( i g u b ) 的求解 在l 。模下，反问题( i g u b ) 变成 s l m i n1 ， 一嚣p n i + o o j 一c o j ，j lu j o 死民l + c c o l c o i ， j a a r p o 一曰l t + 岛之- c # ，j e lu j i ，i = 1 , 2 ，”妒 z r p i i + 呸+ 口f f c 矗， j e j i ，i 。1 , 2 ，p v q ，o j 己u j f ，i = 0 ，1 ，2 ，巾 v q j o ，j e j i ， ia 0 , 1 , 2 ，p 吃乏0 ，五u j f ，i = 0 1 ，2 妒 口“20 ， j e j f ，i ；0 ，1 ，2 ，矽 在上述模型中，令 ，代替所有的岛，则最优解不变： m l n ， 1 2 ( 1 3 ) 青岛大学硕士学位论文 s t 叫 +v乏 - - c o ， j 厶u j o 死p a j +v c o j ， j j q 一孔p qq t + v 之一c q ， j l u j i ，i - 1 , 2 ，p 冗p q+ q i i t + v c 4 ， j e j t ，i ；1 , 2 ，p ， 0 当x ? o ；o ，1 ，p ) 不是( g ) 问题的最优解时，调整岛或必有且只有一个为正 值，( 1 3 ) 的最优值l ，必为正值，因此约束条件v 之0 可以省略。即在f 。模下，反问 题( i g u b ) 变成： m i n1 ， 1 i 一兀 + v 芝- c 吒j l u j q c 一，1 啊万p 鳓o j 二嘉i c o y l 芑1 小五苗p i 万岛 +吼厶+y之 c i j ， j e j i ，i = l 2 ，。巾 假设( i g u b 。) 的最优解为印，鼋，v ) ，根据以下定理很容易得到l 模下反问题的最优 解。 定理1 3 2 设弓； c o i + c o f 一 勺 + 勺 一 c ， j 厶u j o 且万p o j c o j ，。， je j o 且万p o ， c q v ， j e j i 盈蠢戳+ q ：i i c 4 其它 则在，。模下，当用虿代替q 时，x ? o o ，1 ，p ) 变为( i g u b ) 的最优解，且此时调 整最小。 证明 显然帜一c _ f | | 。一 ，是反问题( 佑嘁) 的最小调整量，且缸。，g ， ，) 满足约 束： 叫扁，+ v 。苫- c o ，j 厶u j o 万昂j + ，c 0 j ，j 厶 一万+ 岛一西+ v 一c f ，j 己u j ，i u j ii = 1 ，2 ，巾一万见f 一吼i + v 一c f ，厶，= l ，厶巾 兀见，+ 一+ v + 乏 ， j f ，i ；一，2 q i l i c i j j 1 ，p兀见，+ + v 乏 ， j f ，4 ， 1 3 ( 1 4 ) ( 1 5 ) 第一章广义规划问题的反问题 为了证明x ? o a o ，1 p ) y g ( 6 u e ) 问题关于亏的最优解，需要证明下述问题 一弧p o i 咒r j 一氕p q 冗p u +v +v q 3 i + q i i i l ，20 j 厶u j o jo 一焉，j 五u j i ，i1 1 , 2 ，”尹 弓， j e j , ，i ；1 , 2 ，p 的最优值为0 ，因此，只需证明 ，= o 和石一万，q = 鼋。为( i g u b ) 的一个可行解， 只需证明下述条件成立：啊p o 瓦j ，j j - ou j 。 ( 1 6 ) 刀e o ，瓦， 歹厶 ( 1 7 ) 一万+ 耽一西t 瓦，j 三u j i ，i u j i ；1 ，2 ，妒 ( 1 8 ) 一万既一级j 嘞， ，厶 2j ，z ，”少 u 0 7 石既+ 西t 气，_ 以，i 一1 ，2 。矽 ( 1 9 ) 而实际上，当j 厶u j 。，若何p 。j 之一c 。，则磊，即( 1 6 ) 成立，否则 磊t + y 因此有( 1 4 ) ，啊。p 。，：，- - ( c o j + ，) ；瓦，即( 1 6 ) 成立，同理可证( 1 7 ) 亦成立。 当_ 三u j i ，若万p o + 西tsc ；，则弓一勺，即( 1 8 ) 成立，否则，焉。勺+ y 。， 因此有( 1 5 ) 啊+ 既一西一( c ：c + y ) t ，即( 1 8 ) 成立，同理可证( 1 9 ) 亦成立， 证毕。 根据上述定理即可容易得到调整后的价值向量巧，当然这样的虿不是唯一的。 1 4 结论 本文针对广义上界问题( g 瑚) 的反问题进行了研究，并提出了( g 咖) 问题在z 。模 和，。模，。模意义下的反问题( 佑叩) 的数学模型及求解方法；并在某种特殊情况下， 1 4 之 凡 ， v v 之 + + 青岛大学硕士学位论文 我们给出了在模意义下( g 咖) 问题的反问题( ，g 珊1 ) 的最优解可转化为由求它的 对偶问题( d ，g 1 ) 的最优解，类似的可求解在z 。模意义下的情景，对乞模下的反问 题等作者将作进一步的研究。 第二章广义最大流问题的反问题 第二章广义最大流问题的反问题 本章讨论了广义最大流问题的反问题，并提出了( g m f ) 问题修正的f 0 r d f u l k e r s o n ( 1 9 5 6 ) 算法，给出并证明了反问题有解的充要条件，并从线性规划的角 度将( o m f ) 的反问题转化为它的对偶问题的最小割问题来解决。 2 1 广义最大流问题的提出 设g 一 是一个带有发点和收点的容量网络图，其中k 是发点，形是收 点，节点集y - 1 ，2 ，m ) ，a 是有向边，c 是容量网路对应边上容量的集合。通常 情况下网路最大流【1 8 l 【1 9 1 都是采用以下的数学模型： rf i 。1 鼬伽y x , , - t o ，fi 辑i - m 。，川一1 2 1 ) 0 s bs o ，j ) e a 这里的表示弧( f ，j ) 上的流量，且的下界约束为零，但在实际问题中有时会碰到 的下界约束为非零的情况，本章考虑的是将问题( 2 1 ) 作为一个推广而得到的最 rf i 一1 盯m 。毳，- b 麓 2 岛s 嘞墨 a ，) 彳 称( 2 2 ) 式为广义的最大流问题，记为伽，此处f 不一定为零。 1 6 青岛大学硕士学位论文 2 2g m f 问题的解法 定义2 2 1 称满足g 砸问题( 2 2 ) 中的约束条件的变量( ( f ， ) 彳) 的解为 可行流，对应的，称为该可行流的流量。 定义2 2 2 n 町设x ：是g m f 问题( 2 2 ) q h 的- 个可行流，其流量为厂，如果存在一 条从节点h 到节点的链p ，使得在p 的所有前向弧上， i f _ ，则称p 是一条可扩链。 定义2 2 3设gi 是一个网络，s 是y 的一个子集，令st y s ，如 果v , e s ，匕歹，则称( s ，歹) ； ( f ，j ) 彳iu s ， ，司为g 的一个割， 并把 c ( s ，歹) - 伍，酣玎，g 毛称为割( 啦) 的广义容量。其中广义容量最小的割称为 g 的最小割。 定理2 2 1 对于已知的网络流g ，从发点匕到收点k 的流量厂的最大值小于或 等于任何一个割的容量，即m a xf i o 。于是构造一个新流，一 l ( u ，y ，) 彳) 如下： 1 8 青岛大学硕士学位论文 一 厶+ 6 ，若( k ，匕) 彳+ ( p ) 矗一6 ，若( u ，v ) 彳一( p ) ( 2 6 ) 厶，若( 哆，_ ) 硭彳( p ) 从厂到，的过程称为沿p 对厂的增广，易知，f 是g 中流值为f + 6 的可行流，因 此，不是g 中的最大流。 ( 乍) 设g 中不存在厂增广链，记s 是g 中存在关于f 的( 屹，u ) 增广链的顶点u 的 集合，则匕s ，u j 。因此，v ( 吩，v j ) ( s ，亨) ，厶= h ；v ( v ，v i ) ( s ，歹) ，而；岛；则 有问趴2 2 坷妣卜( v ，善司铲( 毒j ) 厶( 爿s j ) ( 筛j ) 。 。h 蠢l i h ，蚤j ) o c ( s ，歹) 从而由定理2 2 2 知，厂是最大流，( s , g ) 是n d 、割。 因此由定理2 2 5 的必要性知，g 中不存在厂增广链。从而根据定理2 3 5 的充 分性的证明，g 中存在最小割( s ，j ) ，使得厂- c ( s ，j ) ，这样就得到