（运筹学与控制论专业论文）带有区间值模糊关系方程约束的线性规划.pdf

大连理工大学硕士学位论文 摘要 目前，关于模糊关系方程的理论研究已越来越多的应用于解决实际问题当中，如 系统分析，决策理论，模糊推理，模糊控制等等。作为模糊关系方程的推广，区间值 模糊关系方程在反映日常推理的模糊性和不确定性中更有优势。随着在模糊环境下 的优化问题在日常经济生活中的广泛应用，如何用简捷有效的方法解决模糊优化问 题，尤其是近年出现的模糊关系约束的优化问题已成为广大学者关注的热点之一，但 是，带有区间值模糊关系方程约束的线性规划方面的研究还是空白。本文研究了约束 为m a x o m i n 和m a x - p r o d u c t 的区间值模糊关系方程的线性规划。下面。简要介绍一下本 文的主要工作。 1 在第二章中，首先介绍了区间值模糊关系方程，并引入一些基本定义，然后再分 别介绍m a x - m i n 及m a x - p r o d u c t 区间值模糊关系方程的算法，并给出了算例，为第 三、第四章线性规划问题的求解提供了理论基础。 2 在第三章中探讨了带有m a x - r a i n 区间值模糊关系方程约束的线性规划。首先研究 了权向量的作用，然后转化为0 1 整数规划求解。本章最主要的工作是给出了化简 原问题的几个定理，基于定理，给出了求解该问题的算法。数值算例说明该算法 是有效的，且本文算法在计算量和化简原问题方面要优于文1 2 】和 3 】中的算法。 3 第四章探讨了带有m a x - p r o d u c t 又间值模糊关系方程约束的线性规划。首先研究了 权向量的作用，然后转化为0 1 整数规划求解。在本章定理的基础上，给出了求解 该问题的算法，数值算例说明该算法是有效的。 关键词：模糊关系不等式；线性规划；m a x - r a i n 模糊合成算子；m a x - p r o d u c t 模糊 合成算子；区间值 i 大连理工大学硕士学位论文 s o l v i n gi n t e r v a l - v a l u e df u z z yr e l a t i o ne q u a t i o n sw i t hal i n e a r o b j e c t i v ef u n c t i o n a b s t r a c t a tp r e s e n t ，o nt h et h e o r yo ff u z z yr e l a t i o ne q u a t i o nh a sb e e nu s e dm o r ea n dm o r eo f p r a c t i c a lp r o b l e m s ，s u c ha ss y s t e ma n a l y s i s ，d e c i s i o n - m a k i n gt h e o r y , f u z z yr e a s o n i n g ， f u z z yc o n t r o la n d8 0o n w i t hd e e pr e s e a r c ho ft h ef u z z yr e l a t i o ne q u a t i o n a st h eg e n e r - a l i z a t i o no ff u z z yr e l a t i o ne q u a t i o n i n t e r v a l - v a l u e df u z z yr e l a t i o ne q u a t i o nt or e f l e c tt h e d a i l yr e a s o n i n go fa m b i g u i t ya n du n c e r t a i n t y a r em o r ea d v a n t a g e s h o wt os o l v et h i sk i n d o fp r o b l e m si nt h ew a yo fc o n v e n i e n ta n de f f i c i e n t ，e s p e c i a l l yi nr e c e n ty e a r s ? t h eo p t i m i z a - t i o np r o b l e mc o n s t r a i n e df u z z yr e l a t i o nh a sb e c o m eah o tp o i n to fr e s e a r c h h o w e v e r t h e s t u d yw i t hi n t e r v a l - v a l u e df u z z y 1 ， r e l a t i o ne q u a t i o n so ft h ei n e a rp r o g r a m m i n g i sb l a n k inthis p a p e rt w oo p t i m i z a t i o nm o d e l sw i t hl i n e a ro b j e c t i v ef u n c t i o n ss u b j e c tt oas y s t e m o fi n t e r v a l v a l u e df u z z yr e l a t i o ne q u a t i o n sw i t hm a x - m i na n dm a x - p r o d u c ta r ep r e s e n t e d i nw h a tf o l l o w s w ew i l l i n t r o d u c et h em a i nr e s u l t so ft h ep a p e rb r i e f l y 1 i nt h es e c o n dc h a p t e r ，f i r s t ，i n t e r v a l v a l u e df u z z yr e l a t i o ne q u a t i o ni si n t r o d u c e da n d s o m eb a s i cd e f i n i t i o n sa r eg i v e n t h e nw ei n t r o d u c et h ea l g o r i t h m so fm a x - r a i na n d m a x - p r o d u c ti n t e r v a l - v a l u e df u z z y r e l a t i o ne q u a t i o n sr e s p e c t i v e l y t w oe x a m p l e s a r ep r o v i d e dt oi l l u s t r a t et h ep e r f o r m a n c e so fo u ra l g o r i t h m sf i n a l l y f o rs o l v i n gt h e l i n e a rp r o g r a m m i n gp r o b l e mo ft h et h i r da n df o u r t hc h a p t e rp r o v i d e sat h e o r e t i c a l b a s i s 2 t h et h i r dc h a p t e rd i s c u s s e sa no p t i m i z a t i o nm o d e lw i t hal i n e a ro b j e c t i v ef u n c t i o n s u b j e c tt oas y s t e mo fm a x - r a i ni n t e r v a l - v a l u e df u z z yr e l a t i o ne q u a t i o n s w ee x a m i n e t h ee f f e c to ft h ec o s tc o e 伍c i e n tf i r s t n e x t ，w ec o n v e r tt h ep r o b l e mt oa ne q u i v a l e n t p r o b l e mi n v o l v i n g0 - 1i n t e g e rp r o g r a m m i n g t h em a i nc o n t e n t so ft h i sc h a p t e r a r et h a t ：s o m et h e o r e m sa r eg i v e nt os i m p l i f yt h eo r i g i n a lp r o b l e m w ep r o p o s ea m e t h o dt os i m p l i f y i t h ew o r ko fc o m p u t i n g t w o n u m e r i c a le x a m p l e sa r cp rovidedtol l u s t r a t et h ep e r f o r m a n c eo fo u rp r o c e d u r en u m e r i c a le x a m p l e ss h o wt h a tt h e a l g o r i t h mi se f f e c t i v e i np a r t i c u l a r w ep o i n to u tt h a t o u rp r o c e d u r ei s b e t t e r t h a n 【2 a n df 3 3 i nt h es e n s eo fc o m p u t a t i o nc o m p l e x i t yi ns o l v i n gl i n e a ro b j e c t i v e o p t i m i z a t i o ns u b j e c tt of u z z yr e l a t i o ne q u a t i o n i i i 带有区间值模糊关系方程约束的线性规划 3 t h ef o u r t hc h a p t e rf o c u s e so na l lo p t i m i z a t i o nm o d e lw i t hal i n e a ro b j e c t i v ef u n c t i o n s u b j e c tt oas y s t e mo fm a x - p r o d u c ti n t e r v a l - v a l u e df u z z yr e l a t i o ne q u a t i o n s w b e x a m i n et h ee f f e c to ft h ec o s tc o e 伍c i e n tf i r s t n e x t w ec o n v e r tt h ep r o b l e mt oa n e q u i v a l e n tp r o b l e mi n v o l v i n g0 - 1i n t e g e rp r o g r a m m i n g b a s e do nt h et h e o r e m so f t h i sc h a p t e r ，w ep r o p o s eam e t h o dt os i m p l i f yt h ew o r ko fc o m p u t i n g t h en u m e r i c a l e x a m p l es h o w st h a tt h ea l g o r i t h mi se f f e c t i v e k e yw o r d s ：f u z z yr e l a t i o ni n e q u a l i t y ；l i n e a rp r o g r a m m i n g ；m a x - r a i nf u z z yc o m p o s i t i o n ；m a x - p r o d u c tf u z z yc o m p o s i t i o n ；i n t e r v a l - v a l u e d i v 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，再校攻读学位期 间论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学 校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版， 可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：带有区间值模糊关系方程约束的线性规划 作者签名：蕴：翌蛭日期：旦年三月上日 导师签名：二 墨l 魄孕年上月二日 4 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所取 得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含 其他人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过 的成果。与我一nt - 作的同志对本研究所做的贡献均已在论文中做了明确的说明 并表示了谢意 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：带有区间值模糊关系方程约束的线性规划 作者签名： 蕴鍪坚日期：皇笾年互月厶日 大连理工大学硕士学位论文 1 绪论 不确定性是客观世界中广泛存在的一种现象，随着对实际问题的研究不断深入， 特别是在人工智能方面，人们认识到客观世界的不确定性并不唯一的表现为随机性， 模糊性也是普遍存在的不确定现象，因此，模糊数学的产生是人们对客观实际认识发 展的必然。美国控制论专家l a z a d e h 于1 9 6 5 年在杂志i n f o r m a t i o na n dc o n t r o l 上的著 名论文( ( f u z z ys e t s ) ) 标志着模糊集合理论的诞生。模糊集合理论在数学领域本身以及 许多的实用领域都得到了广泛的应用。到了2 0 世纪的9 0 年代，已经形成了具有完整体 系和鲜明特点的模糊拓扑学，模糊分析学，以及模糊逻辑理论等，模糊数学的实际应 用已经涉及到了国民经济的各个领域，比如地质勘探、医学、军事、经济学、工业控 制等。 模糊关系是模糊数学理论中的一个重要分支，模糊关系方程是模糊数学的一个基 本课题，它对于模糊数学具有基本的理论意义，是模糊推理、模糊控制的个重要的 理论基础。模糊关系方程理论为探讨模糊关系的结构与求解提供了解决方案。大部分 模糊推理系统都可以通过模糊关系方程实现。不同类型的模糊关系方程对应不同的模 糊关系合成算法。近年来，国内外在这方面开展了许多研究工作。 关于模糊关系方程的解法，从问题提出到上个世纪9 0 年代后期，一直是许多学者 关注的问题。s a n c h e z n 指出，若模糊关系方程解集不空，则存在一个最大解，并给出 了解存在的充要条件及最大解的求解方法。1 9 8 2 年，c z o g a l a l 4 】对模糊关系方程的解集 结构做了进一步研究，给出了极小解的概念，并证明了模糊关系方程的解集可由极小 解和最大解确定。在此基础上，给出了求解模糊关系方程极小解的算法。但不足之处 是，算法虽然能求得所有的极小解，但同时也可能得到部分其他解。1 9 8 4 年h i g a s h i n 修i e t c z o g a l a 算法中部分不妥之处，并给出了满足如下条件 b l b _ 2 k 的模糊关系方程的极小解算法。对这类模糊关系方程，汪培庄1 7 】于1 9 8 4 年给出了模糊关 系方程极小解个数的确定方法。罗承忠【8 】给出了极小解的筛选方法。关于模糊关系方程 的其他研究成果，见f 9 ，1 0 ，1 1 ，1 2 ，1 3 ，t 4 等。 z a d e h l 2 7 首次提出区间值模糊关系方程，随着对模糊关系方程的深入研究，研究 定义在区间值上的模糊关系方程已成为人们感兴趣的课题之一。作为模糊关系方程的 推广，区间值模糊关系方程在反映日常推理的模糊性和不确定性中更有优势，很多学 者对此方面进行了研究( f 1 ，2 8 2 9 ，3 0 ，3 1 ，3 2 3 3 】) 。文【2 8 】讨论了区间值上的模糊关系 方程解的定义，并用符号定义法求出其全体解集。文【1 在研究了区间值模糊关系方程 的可行域后，把它转化为模糊关系不等式进行求解，并给出了一个有效的算法来求解 其解集。文1 2 9 介绍了区间值模糊关系方程的三种解集，容许解集，统一解集和控制解 集，并通过相关的模糊关系不等式给得出其解集。 1 带有区间值模糊关系方程约束的线性规划 随着在模糊环境下的优化问题在日常经济生活中的广泛应用，模糊优化问题显得 日趋重要。如何用简捷有效的方法解决模糊优化问题，已成为广大学者关注的热点。 应用模糊优化模型解决实际问题，不仅能够避免经典优化模型在处理某些实际问题时 的僵化和死板，而且也能有效的避免由于经典优化对数据取舍所带来的信息丢失，因 此该类优化具有良好的发展前景。 近几年，研究带有模糊关系方程约束的优化问题成为模糊优化研究领域的热点之 一，得到了迅速发展。f a n g l 2 】首先提出了带有模糊关系方程约束的线性规划问题， r a i nc t x s t zoa = b ( 1 1 ) 其中，a = ( ) m x n ，a i 【0 ，1 】，c 7 已m ，。= 【z 1 ，x 2 ，。m j t ，z i 【0 ，1 j ， = 1 ，m ，歹= 1 ，礼，b = 【b l ，6 2 ，b 住 【0 ：1 】n ，“o ”代表一般的m a x - m i n 模糊合成 算子。f a n g 2 把( 1 1 ) 等价地转化为如下的两个子问题， m l n s t m m s t 銎1c f 鼢 z0a = b 銎1c + x i zoa = b ( 1 2 ) ( 1 3 ) 其中，c _ = 曲 q ，o ) ，寸= m a x q ，o ) 。i = 1 ，仇，具体方法见文【2 】。 w u 【1 5 】通过设置最优值的一个上界改进了文| 2 j 的算法，数值实验表明，设置上界非 常有效，减少了很大的计算量。w u l 3 和g u 0 1 16 】通过给出最优必要条件，提出了一些规 则来化简优化问题。实例表明，利用这些规则，可以把一些1 0 维的问题化为2 维问题。 尽管这样，一些较大规模的问题( 文f 3 1 中的1 4 维问题) 仍然不可解，这主要是因为，当 实现算法时，解集分支的节点太多( 超过2 0 0 ，0 0 0 ) ，因此，化简优化问题的规模和减少 计算量仍是一个值得探讨的问题。 有许多学者研究了带有其他模糊算子模糊关系方程约束的线性规 划，其中包括，m a a x - p r o d u c t ( 【1 7 ，1 8 ) ，“m a x - t i l o r m ”( 1 9 ，2 0 ，2 1 2 2 ，2 3 ) ， m a x - a v e r a g e ( 1 2 4 ，2 5 ) ，“m a x o m ；u 和m a x - a v e r a g e 的凸组合”( f 2 6 ) 。这些带有不同算子的模 糊关系方程约束的解集结构是类似的，故解决它们的算法也是类似的。 目前，研究带有区间值模糊关系方程约束的线性规划还是空白。本文在上述工作 的基础上，研究了约束为两种模糊算子( m a x - r a i n 和m a x - p r o d u c t )区间值模糊关系方 程的线性规划。首先把区间值模糊关系方程转化为模糊关系不等式，提出了求模型的 有效算法。下面简要介绍本文的主要结果。 第二章首先介绍区间值模糊关系方程，并引入一些基本定义，然后再分别介 绍m a x o m i n 及m a x - p r o d u c t 区间值模糊关系方程的算法，并给出了算例，为第三、第四 章线性规划问题的求解提供了理论基础。 2 大连理工大学硕士学位论文 在第三章中首次探讨了带有m a x - r a i n 区间值模糊关系方程约束的线性规划。本章首 先研究了权向量的作用，然后通过把区间值模糊关系方程转化为模糊关系不等式，再 转化为0 1 整数规划求解。本章最主要的工作是给出了化简原问题的几个定理，基于定 理，给出了求解该问题的算法。数值算例说明该算法是有效的，且本文算法在计算量 和化简原问题方面要优于文f 2 1 和 3 】中的算法。 第四章探讨了带有m a x - p r o d u c t 区间值模糊关系方程约束的线性规划。首先研究了 权向量的作用，然后转化为o 1 整数规划求解。在本章定理的基础上，给出了求解该问 题的算法，数值算例说明该算法是有效的。 3 大连理工大学硕士学位论文 2 区间值模糊关系方程 这一章主要内容如下，首先介绍区间值模糊关系方程，并引入一些基本定义，然 后再分别介绍m 躲l i n 及m 辑p r o d u c t 区间值模糊关系方程的算法，主要是叙述如何对 它们进行求解，并分别给出一个算法，最后用两个算例说明如何使用这两个算法。 2 1基本定义 令查= ( 幺) n 和5 = ( j ) n 表示两个钆维实向量，其中岛瓦，歹= 1 ，l ，在这种情 况下，称b 石并定义一个区间向量b 7 = 陋，】全 6 = ( 6 j ) 竹l b b 6 ) 。如果b b b ， 称实向量b 是区间向量矿的一个元素，记为6 矿。令丛= ( 鱼f ) m n 和a = ( 勘) m n 表 示两个m 刀维实矩阵，其中乌f 瓦，i = 1 ；m ，歹= 1 ，n 。在这种情况下， 称a 才并定义一个区间矩阵a ，= 出，司全 月= ( 口巧) m nia a a 。如 果a a 孟1 ，所以删除圣3 。 6 。极小解为亳1 = ( 0 5 ，0 4 ，o ) ，圣2 = ( o ，o 。4 ，0 。5 ) 。解集为m ( 月j ，矿) = 童1 z 圣 u 铲z 圣) = ( 【o ，1 o ，【o 4 ：o 8 】，f 0 ，o 7 ) 。 2 3 m a x p r o d u c t 区间值模糊关系方程 m a x - p r o d u c t 区间值模糊关系方程是以下形式的方程， z a j = 矿 其中“”代表m a x - p r o d u c t 模糊合成算子。用；汨j ，矿) 代表方程( 2 1 0 ) 的解集。 2 3 1m a x p r o d u c t 区间值模糊关系方程解的结构 式( 2 。l o ) 等价与下列不等式， z a 查， z a b ， z f 0 ：1 】m 其中，【a ，- 】= a 。，陋，- 】= b 1 是给定的。 定义 其中 圣= 万 石= ( 硝 弓) k z ， 3 动劬2 偏1 ，= 1 ，2 ，m ) ，j = 1 ：2 ，n 。 8 锄 b ， 砀b ， ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 大连理工大学硕士学位论文 定理2 9 如果p ( 月7 ，矿) d ，则岔是p ( a 7 ，6 7 ) 的最大解。 证明：对于任意歹j ，有v 讵j ( 勘奶) = v 斛( 八j ，( 奶，媚) 硝) v 讵凡 瓦) 奶) 弓，所以有才石。 对于任意z 。( 月7 ，矿) ，有z 一a 石及对于任意歹j 有v 饱，( ) 巧，所以 对于任意i ，歹j ，有舭s 弓，则现瓦；巧劬，有$ t j j ( 两劬) = 筑，对 于任意i ，均成立，所以有x 岔。 当。( 月j ，b 7 ) 仍，则至少存在一个z 满足z 一a 一b ，z 页石，而由z 可 知圣丛查。 综上所述，可知圣是口( 月，b i ) 的最大解。 口 推论2 1 0 e p ( 4 ，b 7 ) 0 。当且仅当圣- 一a 一b 。 证明：当金一a 一b ，可知童p ( 以，矿) ，则有p ( a ，矿) d 。 当口( 月，矿) 仍时，由定理2 9 可知圣p ( 月j ，矿) ，则有岔丛b 。 口 引理2 1 1 如果z e 口( a j ，6 7 ) ，则对于任意i 1 ，歹j ，有轨奶弓，并且存 在i o z ，使得。硒鸟o j 之鸟。 证明：由z 才云，可得出对于任意j j ，有v 吲( 毛动) 弓，因此，对于任意歹 j ，t ，有两s 弓。由z 丛一b ，可得出对于任意j j ，有v 叫( 鼢鳓) 岛， 则对于任意0 j 一定存在i o j ，有z i 。吼。j2 岛。 口 当p ( 月7 ，矿) 仍时，圣可被求出，定义指标集 乃= i ，i 毛垒巧2 乌) ，v 歹z 五= 【j ji 筑垒巧马) ，v i ， 和 a = 厶尼厶 ( 2 1 3 ) ( 2 1 4 ) 由引理2 1 1 可得它们的定义是合理的，另外，给定，= ( ，办，厶) ，则有f 人当且 仅当，j ，坳j 。 给定f 人，定义 巧= j ji 乃= t ) ，i ， ( 2 1 5 ) 和f ：a 一冗m ，使得对于任意i ，有 w ) ： 嬲坞俺) 劳舡 ( 2 1 6 ) 1 0 巧= d 下面来看。( 月7 ，b 7 ) 和f ( a ) = r ( f ) if a ) 的关系， 带有区间值模糊关系方程约束的线性规划 定理2 1 2 假定已( 月j ，矿) 口， ( 1 ) ，人，则尸( 厂) p ( 月7 ，6 j ) ； ( 2 ) 对于任意z 岛( a j ，矿) ，可知一定存在，a 使得f ( ，) z 。 证明： ( 1 ) 给定，人，由j j ，乃乃可知金，j 句，j b _ j ，所以金乃之查j g i # ，歹乃。 由鼻的定义，对于任意i 歹，如果乃= 留，则有只( ，) = 0 磊，否则有尻( ，) = m 。a x b ，& 墨氟，可由对于任意歹易，- b - 当j 圣t 得知。由v 涮( 毛葡) sb 对于 任意j j 均成立，所以有v t ，( 只( ，) 砀) s6 j 成立，助j 。 另外，由毋的定义可推出歹哆，有如( ，) 鸟垒助，坳j ，所以如( 厂) 垒助 幺，j 。则有v 斛( 只( ，) 。垒巧) 马。 由此可知v i j ( 只( ，) 砀) 弓，v 列( 只( ，) 垒巧) 乌，j ，所以有f ( ，) p ( 月j ：矿) ( 2 ) 对于任意z 口( 月7 ，矿) ，可知z 奎且v 叫( 丑) 马，坳j ，则对于任 意歹j ，存在如，使得。弓级岛，所以z b 查j 缆。 另外，圣p ( 月，矿) 可推出岔幻瓦瓦，w j 。令- 厂= ( ，1 ，厶) 且乃= t f ，j ，则厂a 。对于任意i i ，如果j ；= d ，则有只( 厂) = 0s 妣，否 则r ( ，) = m ，。a ：x 。b , a “，= 鼍彗鸟戤j 。可知只( ，) 戤，因 此l z ( f ) z ? 。 口 用硌( a 7 ，矿) 表示方程( 2 1 0 ) 所有极小解的集合，则有， p ( a j ，矿) = u z i 圣墨z 岔 ， ( 2 1 7 ) 孟戈。似7 ，6 7 ) 由定理2 1 2 很容易得出： 推论2 1 3 矗( 月，矿) cf ( 人) ce p ( 月7 ，6 j ) 。 这个推论把计算。( a 7 ，6 j ) 的极小解缩小为一个相对小的集合f ( 人) 。另外，如 果z ，z ，f ( h ) r x 7 z ，则z 7 砖( a 7 ，矿) 。由定理2 1 2 ，删除f ( 人) 中所有的。7 ，就确 定了毫( 月j ，矿) 。 2 3 2求解m 辨p r o d u c t 区间值模糊关系方程的算法 下面给出一个算法来求解方程( 2 1 0 ) 。 1 0 大连理工大学硕士学位论文 第一步： 第二步： 第三步： 第四步： 第五步： 第六步： 运用公式( 2 1 2 ) 求出方程( 2 1 0 ) 的最大解岔。 检验可行性。如果子丛查，继续。否则，停止，。( 月7 ：b ，) = 仍。 计算指标集乃及a 。 由式( 2 1 6 ) 计算f ( y ) 。一 删除拟极小解。 得出极小解及解集。 2 3 3 实例 0 2 ，0 3 0 1 ，0 2 0 2 ，0 3 】 给出的算法求解此算例。 0 4 ，0 5 、 0 5 ，0 6 】i 及6 ，= ( 【o 1 ，o 2 ，【0 3 ，o 4 ) ，则可得丛= 0 4 ，0 6 】 0 30 5 、 0 20 6 i ? b = ( o 。1 ，o 。3 ) ，否= ( 0 2 ，o 4 ) 。下面就用上一小节 0 30 6 | 1 由计算知，圣= 万 5 = ( ，；，；) 。 2 因为圣- a b ，所以p ( 4 j ，6 j ) d 。 3 计算得出 = _ 1 ，3 ) ，如= 2 ) ，所以人= ( 1 ，2 ) ，( 3 ，2 ) 。 4 。运用公式( 2 。1 6 ) 可以得出，1 = ( 1 ，2 ) ，2 = ( 3 ，2 ) ，则有日( 歹1 ) = 0 5 ，易( ，1 ) = 暑，乃( ，2 ) = 0 6 ，凡( ，2 ) = 0 5 。 5 得出极小解为孟1 ；( o 5 ，0 6 ，o ) ，孟2 = ( o ，0 6 ，0 5 ) 。解集为已( 月7 ，矿) = 圣1 z 圣) u 圣2 z 圣) = ( 【o ，；】? 【0 6 ，；】，【07 ； ) 。 1 1 = 才 = ， ，、liiij， a 垂；l 触 叭叭 给 2 1 2 m m n ，f 大连理工大学硕士学位论文 3 带有m a x m i n 区间值模糊关系方程约 束的线性规划 令c = ( c l ，( 概) 冗m 表示m 维向量，其中q 代表分量。t 的权重，i = 1 ，m 。以 前研究的优化问题为， r a i n z = 墨1c i x i s t z 。a = b 0 觑1 本章在上一章第二节详细地介绍了方程( 2 2 ) 解的基础上， 为( 2 2 ) 的线性规划， m i l l z = ：lc i x i s t z0a ，= 6 j 0 z t 1 ( 3 1 ) 主要是求解约束 ( 3 2 ) 本章首先研究了权向量的作用，然后转化为m 1 整数规划求解问题( 3 2 ) 。特别地， 在这一节还给出了化简问题( 3 2 ) 的几个定理，使问题变得简单，接着给出了求解此问 题的一个算法，特另u 地，此算法也适合优化问题( 3 1 ) ，最后给出了两个算例来说明此 算法。 从已有的知识可知，可以重置向量b 和c ，使它们的分量单调递减，在本章中，不妨 姚和c 中的分量满足递减性质，即乱1 b _ 2 之鲧，1 2 1 c 2 之c , n 。 3 1 权向量c 的作用 本节考虑权重系数的作用，m ( a ，b 7 ) d 时，很容易得到下面两种特殊的情况， 引理3 1 如果f ：i 0 ，v f i ，则童是问题( 3 2 ) 的最优解。 证明：当m ( a 7 ，b ，) 仍时，因为o 。圣，比m ( 月，b i ) ，因此有c z t 出t ， 则圣是问题( 3 2 ) 的最优解。 口 引理3 2 如果q 0 ，v i j r ，则存在m a * m i n 区间值模糊关系方程( 2 2 ) 的一个极小解 是问题( 3 2 ) 的最优解。 证明：由公式( 2 5 ) ，v x m ( 月7 ，6 7 ) 存在圣o ( 月j ，矿) ，使得圣o 。s 圣，因 此c 圣吾c z t 如t ，选择圣使得西t = m i n c ：圣tl 圣定n ( a 7 ，6 7 ) ) ，则c z t c 圣苫 c 5 c “，v x m ( 月j ，b i ) 。 口 1 3 带有区间值模糊关系方程约束的线性规划 通过这两种特殊情况，现在来考虑一般情形。给定任意权向量c = ( c 1 ，) 冗m ，定义c ，= ( 西，厶) 和( ! ，7 = ( c ；，c ：1 ) ，使得 和 = 。ci q 0 ， q 0 ， c ；，= 三 q o ，耽：1 ，仇( 3 3 ) q 0 ， 显然，c = c ，+ 且d 0 ， ，圣t + 岔t = z t + o t ：c z t ， 所以矿是问题f 3 。2 ) 的最优解并有最优值z = 凹“。 口 通过公式( 2 4 ) 得出式( 2 2 ) 的最大解并不是问题，利用上一章中求解方程( 2 2 ) 的算 法可以求出它的极小解的集合，进而就能通过定理3 3 解决问题( 3 4 ) 。但是求解阶数相 对大一些的方程的极小解的集合却是一件非常繁锁复杂的工作，因此在下一节，提 出0 1 整数规划模型及有关可以化简问题的定理来解决问题( 3 4 ) 。 1 4 大连理工大学硕士学位论文 3 20 1 整数规划及分枝界定法 由推论2 8 可知( a 7 ，矿) cp ( 人) ，当c ：o 时，i = l ，m ，解决问题( 3 4 ) 就等 价地转化为寻求一个f a ，使得 ：1c t i f i ( f ) = 如f 。a 忡mic ：e ( 川 由式( 2 6 ) 中的易，定义 fo 或1 2t 0 i 易， i 隹易 ( 3 7 ) ( 3 8 ) 考虑下面m 1 整数规划问题： r a i n z = 銎，( c ：m 哂j 岛) ) ：s t 銎1 。= 1 ，j ，( 3 9 ) z 巧= 0 或1 ，v i ，j z 、7 = 0 ，v i ，j _ b i 譬如 给定问题( 3 9 ) 的一个可行解，通过式( 3 8 ) 的约束知道，对于任意的j j ，存在唯 一确定的i 乃使得祝，= 1 。如果定义，= ( ，a ) 且乃= i ，= 1 ，则厂人， 另一方面，对于任意厂人，通过式( 3 8 ) 的定义知，它与问题( 3 9 ) 的一个可行解相联 系，有銎，c ：e ( ，) = 圣1 m a 弓j 【马z 巧) ，因此，解决问题( 3 4 ) 就等价地转化为求 解m 1 整数规划问题( 3 9 1 。 有很多种方法求解整数规划问题，本章采用分枝界定法来解决问题( 3 9 ) 。分枝界 定法是对整数规划问题列举了所有的解。具体应用是，一开始，选择一个约束对原始 问题进行分枝，然后转化为几个子问题，每个子问题用一个节点来代表，然后对每个 节点再增加新的约束，则又产生了新的子问题，它们又用新的分枝来表示。注意到，