（基础数学专业论文）线性规划的灵敏度分析运输问题的灵敏度分析与参数线性规划.pdf

摘要 运输问题求解是线性规划中一类特殊的问题，但在实际中，运输问题中的物 资供应量，物资需求量都有可能会发生波动，若再使用原来的表上作业法则非常 不方便，因此人们对它的灵敏度分析与参数规划产生了极大的兴趣，并进行了长 期深入的研究 本文主要解决了两个问题，第一个是系统讨论了线性规划中的灵敏度分析， 不管是单个还是多个决策变量发生变化，或是多个决策变量中多个系数同时发生 变化时对最优解的影响，并求出其最优区间第二个是利用改进的匈牙利算法， 研究关于运输问题的灵敏度分析与参数线性规划，并给出了相应的思路，方法步 骤并举例加以验证 关键字：线性规划；灵敏度分析；决策变量；系数；运输问题；匈牙利算法； 参数线性规划； a b s t r ac t s o l u t i o no ft r a n s p o r t a t i o np r o b l e mi sa k i n do fs p e c i a lp r o b l e mi nl i n e a rp r o g r a m 一1 n i n g ，i na c t u a l i t yt h es u p p l i e sa n dd e m a n d sc a l lb ec h a n g e d s o i t sn o tc o n v e n i e n tt 一0u s et h et r a n s p o r t a t i o na l g o r i t h mo v e rt h ed e c a d e sy e a r s ，m a n yt h o r o u g h g o i n ga n d p a i n s t a k i n gw o r kh a d b e e nd o n eb ys o m ef a m o u sm a t h e m a t i c i a n sf o ri t se f f e c t i v ea g o - r i t h r r t i nt h i sp a p e r , w em a i n l ys o l v et w op r o b l e m s ，t h ef i r s to n e i st h a tw ed i s c u s st h ei - n f l u e n c eo nt h eo p t i m u ms o l u t i o nw h e n o n eo rm o r ed e c i s i o nv a r i a b l e sc h a n g e ，o rm u h i c o e f f i c i e n t so fm o r ed e c i s i o nv a r i a b l e sc h a n g ea tt h es a l n et i m ea n dm a k e o u tt h e o p t i m u mr a n g e t h es e c o n do n e i sm a i n l ys t u d y i n gs e n s i t i v i t ya n a l y s i sa n dp a r a m e t r i c l i n e a rp r o g r a m m i n ga b o u tt r a n s p o r t a t i o np r o b l e mw i t hd e v e l o p e dh u n g r ya l g o r i t h m , a l s ot h et h o u g h t ，m e t h o d , p r o c e s s ，a n de x a m p l ea r eg i v e n k e yw o r d s ：l i n e a rp r o g r a m m i n g ；s e n s i t i v i t ya n a l y s i s ；d e c i s i o nv a r i a b l e ；c o e f f i c i e n - t ；t r a n s p o r t a t i o np r o b l e m ；h u n g r ya l g o r i t h m ；p a r a m e t r i cl i n e a rp r o g r a m m m g ； 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：琵声碧签字日期：刀以年多月夕日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学伫论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：力魄努鬻滋笔日签字日趟幻加苫年6 月6 日 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 引言 线性规划是运筹学的一个重要分支自1 9 4 7 年d a n m g 提出了般线性规划 问题求解的方法一单纯形法之后，线性规划在理论上趋向成熟，在使用中日益 广泛与深入特别是在电子计算机能处理成千上万个约束条件和决策变量的线 性规划问题之后，线性规划的使用领域更为广泛了从解决技术问题的最优化设 计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可 以发挥作用 在求解线性规划中，我们一般讨论如下这类标准形式 m i nz = u x s t a x = b 工20 我们在讨论线性规划问题时，假定口疗，b ；，c ，都是常数但在大多数实际 问题中，一些数据并不是很精确，往往是估计值和预测值，很有可能进行修改如 市场条件一变，c i 值就会变化；a 扩往往是因工艺条件的改变而改变；b ，是根据 资源投入后的经济效果决定的一种决策选择而针对于资源向量b 发生改变、价 值向量c 发生改变、矩阵a 发生改变、增加新的不等式约束、增加一个等式约束、 减少某个约束条件这种单个决策变量发生改变时，很多研究者已经研究成功并得 出相应的结论了。如文献 3 、 5 、 8 、 9 当我们求解一个线性规划后，不 管是单个还是多个决策变量发生变化，或是多个决策变量中多个系数同时发生 变化时，我们都没有必要从头开始计算考虑某些条件的变化对最优解的影响， 修改原来问题的最优单纯形表，以此得到条件变化后新问题的单纯形表，求出 其最优区间，从而判别所得到的解是否还是新问题的最优解若不是的话，则可 以继续迭代求解 随着社会和经济的发展，运输问题也变得越来越复杂，特别是物流概念的提 硕士毕业论文 出，给运输提出了更高的要求运输问题的研究得益于最优化理论和数学规划 的发展运输问题是特殊的线性规划问题，线性规划方法最早和最富有成果之一 就是把运输问题作为线性规划问题来进行描述和求解，形成了运输问题的现行 传统理论和算法运输问题最初由h i t c h c o c k 和k o o p m a n s 独立提出k o n t e r o f i c h 于1 9 5 8 年对运输问题做了早期的研究许多的问题可以从形式上变成运输问题 进行求解，比如分配问题和转运问题，运输问题自身也有很多的变形形式，比如 广义运输问题等运输问题的解法一般是d a n z i g 的表上作业法、我国管梅谷的 图上作业法等，这些方法就本质而言是单纯形方法但是在实际生活中， 运输问题中的物资供应量，物资需求量都有可能会发生波动，研究运输问题的 灵敏度分析很有实用意义而如果用通常求解运输问题的方法一表上作业法， 首先我们须利用最小元素法或西北角法求出一组基本可行解，再检验此解是否 最优，若不是的话则要进行改进这一过程比较麻烦，编程也过于繁琐若生 产量或销售量中有一个发生，则又得重复此过程，工作量非常大因此我们采用 改进的匈牙利算法研究关于运输问题的灵敏度分析，可以保留有用的数据，则 相对就简便很多了 2 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 1 1 线性规划 l预备知识 线性规划( 简称l p ) 问题是在一组线性的等式或不等式的约束之下，求一 个线性函数最大值或最小值的问题线性模型于1 9 3 9 年被提出，每一个l p 问题 都可以化为如下标准形式： ( 尸) r e _ i n z = c x s t a x = b j o 这里石= ( 五，) r 中每个元素为求解的变量，c = ( q ，巳) 称为价值向量， c j ( j = 1 ，1 ) 称为价值系数，优移为目标函数，a 称为约束矩阵，其中彳= ( q ， ，= ( 三i 三 c m 。时，该解为非退化的基本可行解 定理i 1 3 1 若( 1 1 ) 式中fs0 ，则i 为原问题之最优解。 定理i 2 3 1 若( 1 1 ) 式中的向量f 有分量氕 0 ，而向量瓦0 ，则原问 题无界 定理1 3 3 1 若( l1 ) 式中有厶 o ，且瓦至少有一个i e i ，则能找到基本 可行解元，使西 面 上面三个定理给出了单纯形法的迭代步骤鉴于f 在迭代过程中所起的作 用，我们称f 为检验向量，分量称为检验数 l p 问题的的对偶问题为： p ) m a xw b s 1 w a c w b - - - - c b 的解w = b 1 称为( d ) 的一个基本解，若还满足洲c ，则称w 为( d ) 的一个基本可行解，若w n c n ，则称w 为非退化的基本可行解，否则称为退化 的基本可行解如果原问题( p ) 的一个基本解x 对应的检验向量f = ( 乞，靠) = ( 0 ，曰一n c ) s0 ，则称x 为( p ) 的一个正则解于是可知，原问题的正则解x 与对偶问题的基本可行解w 是一对应的，由同一个基b 所决定，我们称这一基 为正则基，这里w = b 一，x = ( 乏) = ( b ：6 ，且满足岛丑1 c 同单纯形法 一样，求解对偶规划( d ) 可以从( d ) 的一个基本可行解迭代到另一个基本可行解， 使目标函数值增加也就是说，求解原规划( 尸) 可以从( p ) 的一个正则解开始， 4 线性规划的灵敏度分析运输问题的灵敏度分析与参数线性规划 从( 尸) 的一个, - e n 解迭代到另一个正则解，使目标函数值 z = w b = c b b 一1 b - - c x 增加，当迭代到b 。b 0 ，即正则解满足原始可行性时，也就找到了最优解，这 一方法成为对偶单纯形法( d u a ls i m p l e xm e t h o d ) 1 2 运输问题 运输问题最初由h i t c h c o c k 和k o o p m a n s 独立提出的，设有m 个发点嵋，扰。 的发量分别为q ，a m ；n 个收点y 1 ，屹的收量分别为包，包从发点“，到收 点吩的单位费用为勺，我们假设吩= 岛，这称为平衡的运输问题运输问 f 2 1 ，2 1 题的数学模型为 。m i n 勺勃 i = l ，= 1 姓嘞- - - - a t ，i = l ，4 n j = - i 而= 巧， i = l 而0 ，i = 1 ，m ；j = 1 ，以 其中的而表示从发点“，到收点，的流量 硕士毕业论文 2 线性规划的灵敏度分析 考虑l p 问题 n f i nz = 蹦 s t a x = b z 0 假定它的最优单纯形表已经得到如下： zb x n r h s 2 l0 c b b - 、n c nc b b 一1 b 南 o l丑一1 b 一1 b 由这上表可以知道，某些数据值和表中的某些块有关因而当某些数据发生变 化时，只需对上表的某块进行修改，便可以得到新问题的单纯形表，从而能够 进行判别和迭代了 2 1 资源向量6 发生改变 先设6 中有一个分量发生改变，不妨令瓯改变为玩，记魄= 阮一玩，则 fq i 矛= b 一+ b - l ( b - b ) = 万+ 以碥= b + a 瓯i 擘 i - ( 锄 若满足矿2 0 嚣+ 瓦钆0 ，即 ( 表示b 1 中第k 列元素) i = 1 ，m 则最优基不变反之，若反不满足上述条件，最优基发生改变，则建立新问题 的单纯形表，用驴取代原最优表中万的位置，用z o = c 口驴- z 0 + 瓯碥取代原 6 、 j o 一q 嚣一磊 一 ，l mm 一 瓦 一包11 一 ，t 觚m 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 最优表z o 的位置，然后开始迭代记q 的范围为，设厶= 【以，m 】 定义2 1 s l厶的右端点m 的绝对值称为瓯的可行增加，即当魄的最大增 加量不超过m 时，最优基不变 定义2 2 吲厶的左端点m 。的绝对值称为吃的可行减少，即当反的最大减 少量不超过帆时，最优基不变 ，定理2 1 资源向量b 中的多元素同时变化时，若这些变化量占可行增加或 者是可行减少的百分率之和没有超过1 0 0 ，则最优基不变 2 2 价值向量c 发生改变 先设c 中一个分量发生改变，不妨令c 中q 改变为q ，记峨= c k - c k 当五为非基变量时，由表可知只有氕会发生变化：厶- - c 矗瓦一q = 磊一 厶气，故要保持最优解不发生改变，即氕o ，则只需峨【磊，佃) 即可反之， 则最优解发生变化，用炙7 取代原最优表氕的位置，得到新问题的最优单纯形表， 然后开始进行迭代 、当心为基变量时，则白发生改变，白= 白+ ( o ，k ，o ) ，则 、；= c ；爵一c n = c b r + ，。k 一一，霜一“ = 矗+ 靠= “+ q ( 瓦，瓦：，瓦) ( 表示中第k 行元素) 若满足氕o 营白一气，即 a x ( 一岳j 。) 歹 则最优解不发生改变反之，若q 不满足上述条件，最优解发生改变，则建立 新问题的单纯形表，用磊取代原最优表“的位置，且此时z o 发生变化，用 z o - - c b 7 万= 气+ 缸。瓦取代原最优表z o 的位置，然后开始迭代 。 定理2 2 吲价值向量c 中的多元素同时变化时，若这些变化量占可行增加 硕士毕业论文 或者是可行减少的百分率之和没有超过1 0 0 ，则最优解不变 2 3 矩阵a 发生改变 2 3 1 增加新的不等式约束 设原来问题的最优单纯形表为 z + n x n2z 0 x b + n x n = b 现在增加新的约束口”1 x k 。，引入松弛变量+ ：后， ( 2 1 ) ( 2 2 ) 新增加的约束可记为 以；+ 1 + 西+ 1 h + 毛+ l = k + l ( 2 3 ) 其中喀“和1 分别为向量a 肿1 中对应于原问题的b 和n 的两部分，将 寻万一砜代入( 5 ) 中并整理，得 ( 西+ 1 一醒“) h + 。= 吒+ 。一簖+ 1 万 ( 2 4 ) 把( 2 1 ) 式和( 2 2 ) 式中毛+ ，的系数看作0 ，则等式( 2 1 ) ，( 2 2 ) 和( 2 4 ) 给出了新问题的单纯形表，这相当于新增加了一个基变量+ l ，实际计算时若先 将( 2 3 ) 式作为最后一行写在原来单纯形表上，再通过行的初等变换成为典式， 结果相同如果这时有屯+ 一霹+ 1 万0 ，也即原问题的最优解工满足条件 a m + i x * 屯+ 1 ，则己经找到了新问题的最优解，否则得到的是新问题的一个正则 解，可用对偶单纯形法求解 2 3 2 增加一个等式约束 在原问题上增加一个新的等式约束a “1 x = 屯+ 1 ，如果原问题的最优解x 满足 口斛1 工= 屯+ 1 ，则也是新问题的最优解但是这种可能性很小不妨设a 斛1 x 吒+ l ， 则引入人工变量毛+ 。，是新增加的约束成为a 1 + l x + x n + 。= 吒+ 。，然后就能用用两阶 段法求新问题的初始解了 增加等式约束一般地将使约束矩阵的秩增加，故需增加基变量显然增加不 8 线性规划的灵敏度分析运输问题的灵敏度分析与参数线性规划 等式约束也可以看作是增加等式约束，但是此时引入的松弛变量+ 。正好成为基 变量，故可立即得到新问题的一个正则解而增加一个等式约束时没有明显的可 添加的基变量，故需引入人工变量毛+ 。作为基变量，再用两阶段法或大m 法将它 剔除 2 3 3 减少某个约束条件 若原问题中减少一个不等式约束方程，不妨设减少的是第m 个方程，即新问 题的最优基为b ，则原问题可视为新f ；- j 题增加一个不等式约束所得若第m 个 松弛变一问警媲舢= ( 乏。，p = ( 一0 一。：q ， 由此可知原最优解及最优值都不会发生改变若第7 个方程的松弛变量不是原问 题的基变量，则可用对偶单纯形法，将该松弛变量换成基变量，再去掉该基变 量所在行与列，再重新迭代 2 3 4 矩阵a 中某列发生改变 先设a 中第k 列中某一分量发生改变，不妨令元素改变为以，记 q - ( o ，o ) r = a k 一a k 当而为非基变量时，由于此时基不变，故只要以对应的检验数不大于0 ， 则最优解不发生改变 a k = 召- 1 a k 7 = b - 1 ( 吼+ q ) = 瓦+ 最，) 1 e ：= c 再：- c k = c b a k - - c k + a a t k c b b 。f = e + 醵h t 当满足使幺0 ，即 m a ) ( 一盘l 嵋 o ) o ) 则最优解不发生变化若不满足上述条件，则用幺取代原表中幺的位置， 用瓦取代原表中瓦的位置，继续迭代求解 定理2 3 矩阵a 中非基变量对应的某列中多个元素同时变化时，若这些变 化量占可行增加或者是可行减少的百分率之和没有超过1 0 0 ，则最优解不变 9 硕士毕业论文 例1m i n 而- 2 x 2 + x 3 s t 五+ 屯+ 而= 4 3 五一2 x 2 + 五= 6 五，艺，为，0 其对应的最优表为： 毛恐毛 以 z 一83o一3o 恐 411 lo 1 450 。 2l 1 = - - 3 , c b = ( _ 2 ，o ) ，矿= ( 三0 ) ，所以衄。卜主，佃) ，咄。( - - 0 0 ，- t - 0 0 ) ，则当非基 变量一对应的q 由变成( o ) 时，因为坚a g l i + 瓦5 - 3 o ) 4 m i n 一皇i 瓦 o ) a b , m i n ( 一兰 l 匾。 o ) a t口n 广尸 m a x ( 一兰士l m a x 一4 ，一警) = 一1 4 ，她【一3 ，佃) ， a c 2 _ m i n ( 一t - 3 ，一 ) = 3 ，心卜3 ，佃) ，缸m i n ( 一了- 3 ，一孚) = 詈， 若c 由( 1 ，一2 ，l ，o ) 变成( 1 ，o ，2 ，o ) ，6 由( 4 ，6 ) r 变成( 2 ，5 ) r ，因等+ 生字坌s 1 0 0 ， 等+ 等 1 0 0 ，故最优基变量不发生改变 磊l=?曰。1q7一q，_c占曰-ic二。+庸)一ci=幺+口庙， 尸r m 斛一昔i o ) ，a c p 【乞，佃) 彬 一 1 4 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 而且此时最优值z 。不会发生改变反之若不满足上述条件之一，则最优解发生改 变，在原最优表的基础上，用磊代替磊，乞代替厶，且用瓦= b 1 a k = b 一 ( 瓯+ 睹，=瓦+吃；代替原瓦的位置，即可重新迭代 ：当为基变量时，则发生改变，知不变，c b = + ( 0 ，c p ，o ) 白= 7 b 。哆一巳= 【+ ( o ，峰，o ) p _ 1 哆一勺= 乞+ 0 勤 nj l j # k ：当为非基变量时，乞= o ，厶= 7 b 。1 一c ，即 乞7 = ( 一( o ，q ，o ) ) b _ 1 吩- - c y = c n b a y 一勺一气动= 旬一气瓦j p ，j 忌 1 6 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 丘= ( 一( o ，咯，o ) ) b a p 一勺2 男1 一c ，一q 一02 p q 瓦一勺 ( k = c f f b - 1 a ! t c 。= c b t _ _ u ：一c 。，z ：c ；毛= z o - c 五 利用上面的结论修改原最优表，并把原第k 列的单位向量移作+ 。对应的列，把 辅助目标函数放在目标行内，再开始进行迭代 方法二：此时基曰改为b ，由于s 3 = ( t ，厶斗b 一1 口；，k ，l ) ，其中 ( 歹后) 为单位向量，记b q = ( 鼽) 州，若第后个分量g 聃o ，则i b 1 8 7 l o ， 记乓= p 一1 b ) ，故= ( s 3 一= 巨7 b ，因为b - q = l + b 1 唯，则 五= ( 小钆，q ，o l ) = l 矿( o l ，。冲i b - a a , ，。) q = 去( 一，一跏- 小一鼽咿一如) f = 卜j 踟- ( b - 1 趣) 若满足b ，是可行基，即俾，) 一- 6 = 乓b b o ，则修改，为( ，) 二五j c ：当为基变量时，则白发生改变，白= + ( o ，乜，o ) = 白+ 峨， 班白和) 1 a j - - c j 地+ 阮眉吐，嘲如弓一煎专坐， 修改z 。为z o ，= c 日7 e x ：，重新建立新的单纯形表进行迭代。 ：当为非基变量时，则白不改变 ；- c b 曲旷铲c 斌- c i 吒一警叭m ：= c b r 口一c ；= c b e ：i j i ，一c ，一k ，： ? 一挚一k i 占肚 嗲3 az o 为z 。= 乓，重新建立新的单纯形表进行迭代 例3m i n 一2 屯+ 而 s t 一+ 工2 + b = 4 3 玉一2 屯+ = 6 1 7 硕士毕业论文 五，屯，玛，x 42 u 问：c - ) 当恐对应色由( 三) 改变为( 主) ，知由c 川改变为c 2 ，一，时，最优基变 量会不会发生改变? 若发生改变，则求出其最优解? c2 ，当五对应q 由g ) 改妄为( ：) ，乞由2 改变为。时，最优基变量会不发 生改变? 若发生改变，则求出其最优解? c3 ，当? 对应心由( 三 改变为( 三) ，_ 对应q 由。改变为2 时，求出其最 优解? 解：( 1 ) 由上面的结论，我们可以求出使最优基变量不发生改变时a a ，的范 围，因为白b = ( 一2 。) ( 三： = ( 一2 。) ，故此血。，( 哟，佃) ，衄。( 一主，佃) ， h c , e - 3 ，佃) ，乞e - 3 ，4 - o o ) 时，最优基变量不发生改变 ( 2 ) 因为：= 2 满足小于等于m i n 一丁- 3 ，一早) = 3i 又因为 m ：= 尉+ c 2 砑= ( _ 2 。) ( 三) + 2 x = 。 m 笼略+ o ：磋_ ( _ 2 0 ) ( 0 ) 协。一o ， 即a a 。满足做任何条件，最优基变量都不会发生变化 ( 3 ) 法一：构造辅助函数m i l lg = 毛 s t 五+ 2 屯+ 毛+ 黾= 4 3 五一屯+ 五一2 毛= 6 五，屯，毛，五，毛0 a j = ba ：，= ( 三： ( 二) = ( ；) ，= c 刍一c 一2 ，一2 ，= c 。，2 ， ：= 一3 + 2 x l + 2 x 5 = 9 。 = 一3 + 2 x l + 2 x 2 = 3 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 乞= ( 0 ：) ( 二 + 2 = 8 ，= 一8 + 2 x 4 + 2 x 1 4 = 2 8 重新构造新单纯形表如下： 而屯 而花 。黾 z 2 89830 。o g4l。2l00 毛 4l2 ，l0l 矗 1 453210 让也进基，j r 5 出基后，则辅助函数已达最优，可删去g 所对行黾所对列不考虑 屯毛 。? 以 z 1 25o 一1 0 也 2 1 1 l 0 ， 22 、 7 l 。 而 80l 2 2 让进基，x 4 出基后，得到最优表如下： 五而毛五 ， 4 一丝 1 0 ，一z 0o 777 631 x 2 0l 777 1 6 而 1 0 l 2 777 由上表可得最优解x = ( 等，雩，o ，o ) r ，最优值z = 等 芍托莹二：b 一1 吒7 = ( ，三0 。) ( 一2 ， = ( ； _ ( 量：) ，最_ 之： 1 9 硕士毕业论文 = 易b 一1 6 = ( 之： ( 三： ( 三) = ( 詈 ，气= b = c 2 ：；，f ，三、1 = 2 = e b 一1 ：i 委： ( ：三 = 妻主 ，“7 = c 刍_ c = c 5 ， 建立新单纯形表如下： 五恐j c 3以 z 1 2501o 而 2 l l l 0 22 7 ， 而80 1 l 22 一葺进基五出基，得到最优表如下： 一五 一 屯毛 矗 4 ： z oo 1 2l o 777 63 一三 而 0l 777 1 612 葺 lo 7 77 由上零可得最优解x = ( 萼，6 ，0 ，o ) r ，最优值z = 号 2 6a 、b 同时发生改变 设6 中改变为，a 中改变为，记 a b = b 一b = 0 ，一，o ) r ，血i = a i 一陬= ( o ，o ) r 方法一：当以为非基变量时，则b 一1 不发生改变，只要满足0 o ，工7 o ， 则最优基变量就不会变 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 = c s b 一1 a k 一c k = 曰一1 ( q + x = b - l b = b - 1 ( 6 + 6 ) = 石+ 占0 ) 一c k2幺+aatkwtck a一 2 l + 老= a a k t 与满足与使磊7 0 ，x p 0 ，则最优解不变，即 m a ) 【 一盘i m o ) 蟛彬 m a ) 【 一每i 霹 o ) 扛1 ，2 ，聊 而且此时最优值z o 也发生改变毛= c b x 反之若不满足上述条件之一，则最儿肿 发生改变，在原最优表的基础上，用氕代替，代替x ，且用瓦= 曰一1a k = b 。1 ( q + 代 毒，=瓦血髓铳；代替原瓦的位置，用z：代替原zo的位置即可重新迭 当旅为基变量时，则b 。1 发生改变为保持b ，求解下面的辅助问题 n l l n g2 吒+ 1 j t q 五+ + a k t + + 口。毛+ q + 1 - - b 五，+ l 0 分析一下辅助问题可知，如果对五的系数不加考虑的话，则它的系数矩阵和原问 题完全致，只是把五换成了h 。，因而只需令毛+ ，代替t 作基变量， 2 l 、ilnrlj一 睹 0；口；0o；妇；o 硕士毕业论文 瓦= b 一1 a k = b 一1 ( q + =瓦+瓴巧；，下面分两种情况来考虑 第一种情况：当原最优解中= o 时，则可忽略不考虑a 中a 虚改变为， 直接利用2 1 节的结论来求6 中改变为6 ，7 的问题。， 第二种情况：当原最优解中0 时，则由于辅助函数没有达到最优，故原 最优解必定会发生改变 下面分别用c ，万和c 表示原问题、辅助问题和新问题的价值向量，而以f ，2 和f 表示其对应的检验向量，由于万= ( o ，0 ，1 ) e 肿1 ，故在构造辅助问题的第 一张单纯形表时，需要将以+ 。消为零这相当于把上面构造得到的表中的第k 行 元素移到辅助目标函数g 对应的行，再将以+ 。置0 如果要将新问题的目标函数 行也放在上面，则因此时稚已不再是基变量，而_ + 。成为第k 个基变量，故有 7 = 巳+ 1 7 = 0 ，吒= c 县( f ih i k ) 也就是勺= 一( o ，0 ，q ，0 ，0 ) ，故这 时需要重新计算目标函数行：厶= 0 ，“= 白b n c ，即 乞= ( 白一( o ，咯，o ) ) b 一口，一勺= 勺曰一1 乃一巳一q = 旬一q 弓。乃为非基变量，j k ：= c ：b q ：一c t ；c ：夏：一c x = b - t b = b 一( 6 + 6 ) = 工+ 砣) 7 o t = c 罩j 利用上面的结论修改原最优表，并把原第k 列的单位向量移作k ，对应的列，把 辅助目标函数放在目标行内，再开始进行迭代 方法二：此时基b 改变为b 7 ，由于p 叫b ，) = ( ，中b 1 吒，厶，l ) ，其 线性规划的灵敏度分析& 运输问题的灵敏度分析与参数线性规划 中( 后) 为单位向量，i gb 。1 口。7 = ( ) 删，若第尼个分量；e0 ，则ib 一1 b i o ， 记尾= ( 口- 1 8 7 ) ，故：( b ，) 一= 乓b ，因为b 一1 7 = + 刀一1 陬，则 e 7 = “，厶- 1 ，q ，l “，l ) ：l 。朋一( o l ，一，o ，b - 1 a a t ，吼小，o 。) g 姨 q = 去( 一，_ g ( h 妒l ，一跏啪，一g = 厶一去( 衄) 若满足b 是可行基，即( b 5 一b = 乓7 b b 0 ，则修改石为( 石+ ) 7 = 晟b 一b ，修改 检验数厶为乞= ( b ) - 1 乃一0 = c b e , 7 巧- c j = 旬一 毛，重新建立新的单纯形表进行迭代 例4m i n - - 2 x 2 + x s s t 五+ 屯+ 毛= 4 一衄) 毛 g 娃 ，修改z o 为z o = c b 3 玉一2 屯+ = 6 五，屯，焉，0 求c ，当q 由( 习改变为( 1 1 ) ，6 由( 三 改变为( 茎 时的最诜解及最优值 c 2 ，当由( ： 改变为( 二) ，6 由( 三) 改变为( 习时的最优解及最优值 解：c ，爿= c - 2 。，( 三；) ( ：) 一，= - 。，= ( 三；) ( 至) = ( 耋 ， 珥7 = ( 三； ( ：) = ( - 1 ) ，z 7 = c 一2 。，( 言) = _ 4 建立新单纯形表如下： 五而毛 五 z 一4lo一30 五 2 一ll10 硕士毕业论文 x 4 出基五进基，即得最优表如下： 而而屯 也 一u一l z - 700 33 51 而 5 o1 33 21 31 o 33 由上表可得最优解x = ( 3 ，5 ，0 ，o ) r ，最优值z = 一7 ( 2 ) 方法一：构造辅助函数m mg = 鼍 s t 五+ 吒+ 而+ 2 = 2 3 玉一2 屯一心+ 毛= 5 五，屯，毛，毛0 a 4 = b - l a 4 = ( 三? ) ( 二) = ( 量) , c s = c b - e 。，。，= c 2 ，。，幺= 厶= 一3 ， ，= c 一2 。，( 三： ( 二) = 4 ，= ( 三；) ( ；) = ( ；) ，气7 = c 一2 。，( ；) = 4 ， 建立新单纯形表如下： j c i也毛矗毛 z 一4一3 o一340 g95 o 23o 屯 2 l1l 2 0 鼍 95o23l 让五进基，出基后，则辅助函数己达最优，可删去g 所对行屯所对列不考虑 1 j c 2 墨 而 线性规划的灵敏度分析运输问题的灵敏度分析与参数线性规划 由上表可得最优解为：x + = ( ；， ，o ，o ) r ，最优值z = 詈 方法二：伊1 西= ( 三：) ( 三) = ( ； = ( ，日= = 丘曰。1 b 7 = 霄= e 4 s - 1 = 建立新单纯形表如下： 删= - 4 1 , ( ) 盼 ； 五进基丘出基，得到最优表如下： 由上表可得最优解x = ( 詈， ，o ，o ) r ，最优值z = 詈 = 一c = ( 竽，一三) 79 一u z 0o 5 55 l3 7 屯 ol 5 55 9 2 ， 3 l0 555 一、j一 2 3 l； 1 o ，。一 1 2 ，。l l、23一；：一三3 l 0 ，。l 、，bj一，。- 、， 1 o l 3 ，l 、，、 o 1 1 2 ，_ 、， 1 0 ，。，。l 五恐毛矗 1 11 z 800 33 屯 4 71 3 l0 3 5 2 五3 01 33 毛屯毛 以 79 一 z 0o 5 55 137 屯 0l 5 、 55 9 2 3 五 l 0 555 硕士毕业论文 3 运输问题的灵敏