（运筹学与控制论专业论文）求解一类模糊线性规划问题的方法研究.pdf

人连理l ：大学硕士学位论文 摘要 数学舰划是模糊集理论应用极其广泛的一个领域。本文针对模糊线性规划的一类问 题- 可能性线性规划，以可能性理论为工具，研究了系数为梯形模糊数的可能性线性规 划的求解原理，并给出了具体算法。 本文主要内容包括以下几个方面： ( 1 ) 简要地介绍了模糊数学中基本概念和三大基本定理分解定理，表现定理和扩展定 理，模糊数的概念、性质以及比较两个模糊数的方法。 ( 2 ) 概述了可能性模糊线性规划的模型及其求解的基本方法，并介绍了可能性测度和模 糊积分。 ( 3 ) 在总结经典线性规划、模糊线性规划问题的求解原理的基础上，给出了系数为梯形 模糊数的可能性线性规划的一类求解方法。 ( 4 ) 以分解定理为工具，讨论了多目标线性规划与多目标模糊线性规划的求解问题。 关键词：模糊线性规划：可能性理论：模糊集：模糊数：可能性线性规划 查塑二耋堡塑垡些塑型塑墼塑查鲨塑窒 s t u d y o nas o r to f f u z z y l i n e a r p r o g r a m m i n g a b s t r a c t m a t h e m a t i c a l p r o g r a n m l i n g i so n eo f t h ea r e a st ow h i c h f u z z ys e tt h e o r yh a sb e e na p p l i e d e x t e n s i v e l y t h i sd i s s e r t a t i o ns t u d i e sm a i n l yas o r to f f u z z yl i n e a r p r o g r a m m i n g - p o s s i b i l i s t i c l i n e a r p r o g r a m m i n g b ym e a n so f p o s s i b i l i t yt h e o r y ，p o s s i b i l i s t i cl i n e a rp r o g r a m m i n gw i t h f u z z y 啡z o i 捌n u m b e rc o e f f i c i e n t si sd i s c u s s e d i nt h e f o l l o w i n g ，w e l i s tt h em a i nw o r k si no u r p a p e r ： ( 1 ) w e i n t r o d u c eb r i e f l yt h e c o n c e p t so f f u z z ym a t h e m a t i c s a n dt h r e ef u n d a m e n t a l p r i n c i p l e s d e c o m p o s i t i o nt h e o r e m ，r e p r e s e n t a t i o nt h e o r e ma n de x t e n s i o nt h e o r e m w ea l s op r e s e n t t h ec o n e 印t so f f u z z yn u m b e ra n ds o m e s i m p l ep r o p e r t i e s ( 2 ) w e c o n s i d e rh o wt os o l v e f u z z y m a t h e m a t i c a lp r o g r a m m i n ga n di n t r o d u c et h eb a s i c p r i n c i p l eo f p o s s i b i l i t ym e a s u r ea n df u z z yi n t e g r a l ( 3 ) w eg e n e r a l i z et h ep r i n c i p l e so f h o w t os o l v el i n e a r p r o g r a m m i n g a n d f u z z y l i n e a r p r o g r a m m i n g t h e n m e t h o d sf o r s o l v i n gp o s s i b i l i s t i cl i n e a rp r o g r a m m i n gw i t hf u z z y t r a p e z o i d a ln u m b e r c o e f f i c i e n t sa r e p r o p o s e d ( 4 ) o n b a s i so f t h e d e c o m p o s i t i o nt h e o r e m ，m u l t i - o b j e c t i v el i n e a rp r o g r a m m i n ga n dm u l t i o b j e c t i v ef u z z y l i n e a r p r o g r a m m i n g a r ed i s c u s s e d k e yw o r d s ：f u z z y l i n e a r p r o g r a m m i n g ；p o s s i b i l i t yt h e o r y ；f u z z ys e t ；f u z z yn u m b e r ； p o s s i b i l i s t i el i n e r p r o g r a m m i n g i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：屋】乏超 日期：丝：叵! 大连理工大学硕士学位论文 1 绪论 1 1 引言 不确定性是决策分析中存在的普遍现象，传统的决策理论在解决不确定问题时一般 运用的数学工具是概率统计分析，因此对不确定性问题所建立的数学模型都是单一的随 机模型。这样实际上假定了决策中的不确定事件，不论其性质和表现的形式如何都是认 为受随机因素影响而产生的结果。但是随着对实际问题的深刻认识，特别是在人工智能 方面，从上个世纪6 0 年代，人们已经重新认识和评价概率论的意义，人们也越来越感 到这种把不确定性单纯地等同于随机性的做法是不切实际的。在1 9 6 5 年，z a d e h 提出 了模糊集合的概念，用隶属函数来刻画元素属于集合的程度，将经典集合的二值逻辑 o ，l 推广n o ，1 区间内的连续值逻辑，从而诞生了模糊集合论，提供了对模糊现象 进行定量描述和分析运算的方法。从那时起，模糊集理论便应用到运筹学、管理科学、 人工智能、控制论等许多领域。概率论的产生，把数学的应用范围从必然现象扩大到偶 然现象的领域。模糊数学的产生则把数学的应用范围从清晰现象扩大到模糊现象的领 域。概率论研究和处理随机性，模糊数学研究和处理模糊性。二者都属于不确定数学， 它们之间既有深刻的联系，又有本质的不同。 广义地讲，决策就是运筹。它涉及到运筹学的各个方面，如规划、博弈、排队、 库存、网络等问题都是属于决策科学的范畴。狭义地讲，决策论是研究一类特殊的博弈 活动它以决策者为一方，以环境为另一方的博弈。传统的决策理论按照事物发展的可能 性把决策分为确定的和随机的两种类型，而完全忽略了决策中模糊性的存在。一般来 说，随机性是一种外在因果的不确定性，而模糊性是一种内在结构的不确定性。从信息 论来看，随机性只涉及到信息的量，而模糊性则关系到信息的含义。在现实生活中。模 糊性的存在比随机性的存在更为广泛，尤其在主观的认识领域，模糊性的作用比随机性 的作用更重要。而决策是人们对事物的评价和选择。任何决策理论和方法都是建立在人 类的认识和活动的基础上，反映了人类分析和处理问题的思维过程。因此，决策是一门 科学，但又是一门艺术。后者涉及到社会、心理、主观意愿和工作经验等多方面因素， 这些因素大都具有模糊特征与动态性质，故决策问题中的不确定性虽然包含有随机性的 成分，但更多地表现为模糊性，或者模糊性与随机性的并存。 在1 9 7 0 年，b e l l m a n 和z a d e h 在多目标决策的基础上，提出模糊决策的基本模型。 在该模型中，凡决策者不能精确定义的参数、概念和事件等，都被处理成某种适当的模 糊集合，蕴涵着一系列具有不同置信水平的可能选择。此后，模糊规划就一直是引人注 目的研究领域。z i m m e r m a n n 将这种思想首先应用到数学规划的研究中，并在众多学者 求解一类模糊线性规划问题的方法研究 的共同努力下，使得模糊规划，特别是模糊线性规划得到了迅速发展，建立了一套求解 模糊线性规划的容差法( t o l e r a n c ea p p r o a c h ) ，该法不仅在理论上比较完备，在实际的 模糊决策中也获得了广泛的应用。在1 9 7 8 年，z a d e h 进步提出与模糊集理论相辅相 成的可能性理论，以说明随机性与模糊性的本质区别。这一理论的建立也促进模糊规划 的进一步发展，关于模糊线性规划的研究状况可见r o m m e l f a n g e r 和s l o w i n s k i 的综述 性文献。 清华大学刘宝啶教授对随机规划建立了相关机会规划模型，并根据随机规划的建模 机理，给出了模糊规划的期望值模型，建立了模糊相关机会规划理论。根据对随机规划 与模糊规划的研究，建立了不确定规划理论。由于决策问题中的不确定性可能会包含随 机性、模糊性等多种成分，刘宝碇又给出了r o u 曲变量、随机模糊变量、随机r o u g h 变量、r o u g h 随机变量、模糊r o u g h 变量、r o u g h 模糊变量、b i r a n d o m 变量和 b i f u z z y 等，并通过对其研究，建立了不确定理论及不确定规划理论。汕头大学的曹炳 元教授对模糊几何规划也进行了深入的研究。 尽管不确定理论和不确定规划取得了丰硕的成果，但此领域仍存在大量的尚待探索 的课题。刘宝碇教授在第一届不确定系统年会上指出：从不确定理论内容延伸来将，需 要更深入的数学理论分析：从不确定规划模型的扩充来讲，需要进一步研究不确定环境 下的动态规划和多层规划。从另外一个侧面来看，寻求不确定规划的最优性条件或建立 对偶理论以及如何进行灵敏度分析，都是具有挑战性课题：从不确定规划的计算来讲， 需要设计更有效的基于启发式算法的求解算法；从应用角度来看，可以进一步考虑在模 式识别、排队系统、环境保护、质量控制、风险分析等领域的应用。 从而可见，模糊规划理论是不确定规划理论研究的一个重要方面，对模糊规划的深 入研究将进一步丰富不确定规划的理论。本文研究内容是模糊数学一个重要的分支一线 性规划。 1 2 模糊集的基本概念及基本理论 模糊集是经典集的扩充，本节将阐明如何用经典集来表现模糊集。 一、模糊集 定义1 1 给定了论域x 其上的一个模糊集a 是指，对任何x x ，都指定了一个数 爿( x ) f o , 1 - 与x 对应，它叫做x 对爿的隶属度。这意味着作了一个映射 a ： z 一 o ，1 】 也就是说，一个模糊集一可以表示成序偶 a = f ( x ，a ( z ) ) j z z 2 大连理工大学硕士学位论文 这个映射称为4 的隶属函数。 其中第一分量x 表示论域中的元素，第二分量a ( x ) 为相应的隶属度。x 的模糊集全体 记为，( x ) 。 考虑模糊集a ，b f ( x ) ，隶属函数分别为a ( x ) 和b ( x ) 。 1 、称a 为b 的子集，记为a c b ，如果 4 ( x ) 茎四( z ) ， v x r 2 、称“与b 相等，记为a = b ，如果 4 ( x ) = b ( x ) ， v x r 3 、一的补集彳。的隶属函数定义为 4 。( x ) = 1 4 ( 戈) ，v x r 4 、a 和b 的并4 u b 的隶属函数定义为 ( 一u 口) ( 工) = m a x ( a ( x ) ，占( x ) ) = 4 ( x ) v 四( x ) ，x x 5 、爿与口的交a n b 的隶属函数定义为 ( 4 n b ) ( x ) = r a i n ( 爿( x ) ，占( x ) ) = 爿( x ) a 曰( x ) ， v x r 二、a 一截集 定义1 2 设a ，( z ) ，对任意ze 0 , i 】，记 a 2 = ( x i 彳( x ) 五 称以为a 的丑一截集，丑称为置信水平。又记以= 缸f 爿( x ) 丑 ，称以为彳的丑一强 截集。 彳，的直观意义是，若z 对彳的隶属度达到或超过水平z 者就算作合格成员，那么 这些合格成员的全体便构成a ，它是x 的一个经典子集。 截集具有下列性质： 性质1 ( a u 廖) 2 = 以u b( 4 n 曰) z = a 。n 岛 ( 爿u 曰) = a z u b ( a n b ) = a n b z 证明( 仅证第一式) 州c 脚a ( x ) v b ( x ， - 2 箸丢兰兄 l 斑x a 咄, t 引。山z - 3 求解一类模糊线性规划问题的方法研究 性质2 口 等a 。j a 口，a 。a 口，a 8 三a 口 证明( 仅证第一式) 口 髓) 伽l 爿( 工) 口) = a 。 定义1 3 设彳，( 卫) ，称4 为a 的核， 己f 乍k e r a ；称以为a 的支集，记作s u p 彳；称 a 。一a 。为a 的边界a 三、分解定理 分解定理是模糊数学的基本定理之一，它提供了用经典子集的集合套来构造模糊子 集的可能性。y o t 叙述分解定理，首先引进数z 【0 ，1 】与模糊子集a 的乘积删。 定义1 4 设一f ( x ) ，a o ，1 ，规定州f ( x ) ，它的隶属函数定义为 a 一( x ) = 五 a ( x ) 显然有 1 ) 如 爿 2 a 2 )a b j c a a b 定理1 5 ( 分解定理i ) 设4 f ( 劫，则彳2 e u o a 2 , 证明只要证一( x ) = ( 涮j 】a a d ( x ) ，v x x ( 。基，】删z ) ( x ) 2 。( a , a a a ( x ) ) 2 。澍兄1 a , t = 1 ) 2 梆v 1 l 4 ( x ) a ) 2 4 ( 。) 定理1 6 ( 分解定理i i ) 设4 f ( x ) ，则4 2 甚”州 定理1 7 ( 分解定理d 设a f ( x ) ，令 h ：【0 ，1 _ p ( x ) ，a 【0 , 1 】 满足：a ：h ( a ) a z ，v 旯 0 ，1 ，则 1 ) a 2 。x 。】脯( 丑) 2 ) 2j 胃( ) 日( 如) 3 ) a z 2 3 ( 口) ( 五o ) ， 2 品h ( 盯) 四、表现定律 下面介绍表现定律，它与分解定理并列为模糊数学最基本定理。它从另一个角度来 阐明模糊集是由经典集扩充而来的。 d - 大连理工大学硕士学位论文 定义1 8 令h ： 0 , 1 】_ p ( ) ，a 卜日( 五) 满足： f 、。b 畸f 9 f ( a ) 和，。( b ) 的隶属函数分别定义为 ，( 一) ( j ，) 2 名：，4 ( x ) f “( b ) ( = b ( 厂( 曲) 称f ( a ) 为a 的象，称，。( b ) 为b 的逆象。 六、多元扩展原理 1 、模糊集的卡氏积 作为多元扩展原理的准备，我们引入模糊集的卡氏积的概念。我们知道，普通集 合的卡氏积指的是 a 1x a 2 x 4 = 一而x 矗1 t a l ，i = 1 ，2 ，”) 其特征函数 6 一 大连理： 大学硕士学位论文 ( 爿l a 2 _ 。以) ( x 1 ，z 2 ，x 。) = a k ( 工i ) 定义1 1 1 2 设a f ( x ) ( k = 1 , 2 ，n ) 记 a o a 。”x a n l x ，】五( 掣掣”) 称为4 ”，a ”，a ( ”的卡氏积。 定义的合理性在于 a 1 x a 2 ”x a ”) 现在我们来定义多元扩展原理。设 厂：x = x 1x x 2x x x 。斗y = 五x kx x 匕 ( x 1 ，x 2 ，x 。) l 呻f ( x l ，x 2 ，x n ) = y = ( y i ，y 2 ，一，y 。) 按照扩展原理，厂可诱导出 f ：f ( z ) 斗f ( y ) ， a 卜厂( 一) 2 。x ”矽( 以) ，。：f ( 】，) j ，( x ) ， b 卜厂_ 1 ( 丑) 2 ；k 【o j 1 】k f 。( 岛) 分别与下面两种卡氏积复合 肖i ：f ( x 1 ) x f ( x 2 ) x x f ( x 。) 斗f ( z ) ( 彳( ”，彳( 孙，a ”) l a 1 x a x 4 “1 x ：，( k ) x f ( 疋) x x ，( 匕) f ( 即 ( b ( ”，b 扪，b m ) 1 b 1 x 占( 2 x x b ” 便可得到多元扩展原理 7 求解一类模糊线性规划问题的方法研究 定理1 1 4 f ( a 1 ，爿2 ，- ，爿“) ( y ) 2 ，( ；，v ，_ ) ：y ( 。a ；，a 2 ( x k ) )，【 0 2 ，1 y _ j f - i ( 砂舻) ，哪) ( 加墨( x j ) ( n y ：，y ，) = 几) 1 3 模糊数 如果实数域r 上的模糊子集口满足正则性和凸性，我们称口为模糊数，q , 6 a 的隶属 函数为a ：r j o ，1 。假设口和b 为两个模糊数，隶属函数分别为a ( x ) 和b ( x ) ，由模糊 数的定义和z a d c h 的可能性理论有 p o s a 6 ) = s u p m i n ( a ( x ) ，6 ( y ) ) lx ，y r ，x j ， 其中p o s 表示可能性。类似地，口 b 的可能性定义为 p o s a b = s u p m i n ( a ( x ) ，6 ( y ) ) ix ，y r ，x y ) 日= b 的可能性定义为 p o s a = 6 ) = s u p m i n ( 乜( 曲，6 ( x ) ) lx 尺) 特别地，当b 为清晰数b 时，有 p o s a 6 ) = s u p a ( x ) ix er ，x 6 ) p o s a 6 = s u p a ( x ) f z r ，x 6 ) p o s a = 6 ) = 口( 6 ) 设f ：r r r 为实数域上的二元函数，那么它可以推广到模糊数领域。对两个模 糊数a 和b ，记c = f ( a ，b ) ，根据多元扩展原理，那么c 的隶属函数为 c ( z ) = s u p m i n ( a ( x ) ，6 ( 石) ) lx ，j ，r ，z = f ( x ，y ) )( 1 1 ) 其中2 r 一般地，设f ：r ”呻r 为力维欧几里得空间的实函数，a ，q ，a 。r 为模糊数，记 c = f ( a ，吼，a n ) ，那么其隶属函数为 。( ；) = s u p m i 邬n a ，( z 川z = f ( x 】，上2 ，x n ) x t r ，i = l y ，刀 因此，f ( a ，q ，a 。) b 成立的可能性为 p o s f ( a i ，口l ，口。) b ) = s u p c ( z ) iz r ，z 6 ) 其中隶属函数c ( z ) 由上式给出，即可能性可以表示为 8 大连理工大学硕士学位论文 s u p m 。i n a ，( x ，) lf ( x l ，x 2 ，h ) b _ 胄，i = 1 , 2 ，” 更一般的情况，假设：r ”斗月是n 维欧几里得空间上的实值函数，j = 1 2 ，m 。 则不等式组 ( 口】，0 1 ，口。) b j ，= 1 , 2 ，m 成立的可能性为 p o s f j ( a l ，q ，) 6 ，= 1 ，2 ，m ) 2 s u p r a i n a , ( x ，) i f j ( x , x 2 一，吒) q ，j = 1 ，2 ，棚) 其中b j ，_ ，= l ，2 ，m 为清晰数。 类似地，我们有 p d s 一( 口1 ，q ，- 一，) b j ，= 1 ，2 ，m 2 s m u p ， 嘞q ( t ) ( 气，乇，h ) q ，_ ，= 1 ，2 ，删) 和 p o j f j ( a l ，日1 ，一，口。) b j ，j = 1 , 2 ，m ) 2 。s u p j 。 r a 。i n 。口，( z ，) l f a 一，x ：，x 一盗钆，= 1 ，2 ，晰 下面用梯形模糊数解释上述结果。梯形模糊数记为r = ( 1 ，r 2 ，r 3 ，4 ) ，其中，r 2 , r 3 ，r 4 分别为清晰数，且 b 。，则对任意的z 1 0 时，( x ) 口| 五o 口，a n m 矿 车争了z a ，肘( x ) 口 v 膨( x ) 口 托月 因此， v 五7 彳n m 纠= vm ( x ) = ( 一) 2 ) n ( 爿) 2 品m ( x ) 2 墨( 4 ( x ) ( x ) ) = a 。m ( 内积) 可以认为，万( z ) = m ( 砷反映了z 中元素隶属于竹的可能性，( 彳) 记录了a 与 m 。相交的最高水平。因此在模糊意义下反映了a 与吖相交的可能度。 二、f u z z 5 , 积分 定义2 1 1 给出模糊场( 爿，p ( z ) ，兀) ，h ：x 斗 o ，1 x l 斗 ( z ) ， 1 ) 令h f ( x ) ，日( 工) = 矗( 工) 称日为h 的集合表示。 2 ) h 关于n 的f u z z y 积分定义为 i h 。n ( ) ( - j 日( z ) 。( ) ) = 。茹i 】( z a h ( h z ) ) ( 2 2 2 ) 3 ) a ，c r ) ，称n ( 4 ) = 阻( x ) 。( ) 为模糊事件爿对的可能度。 定理2 1 2 设m 是可能性测度n 的诱导集，a f ( 工) ，则a 对兀的可能度n ( a ) 满 足： 1 )( 彳) = a o m 2 ) n ( 一) ：v 2 1 a n m z 奶( 2 2 3 ) 证明：1 ) 兀( 爿) 2i a ( z ) 。n ( ) = 善j 】( 2 a y i ( a t ) ) 由于n ( a - ) = a a 。m = 品( 4 ( x ) m ( x ) ) ，于是 兀( 4 ) 2 她v1 】( 五 函( 以( x ) m ( x ) ) ) 。洳品( 五 以( z ) m ( z ) ) 2 函“桃v 】( 五“a a ( x ) ) m ( x ) ) 2 硝v ( 4 ( x ) m ( x ) ) = a o m 2 ) v z f a n 鸩彩 口 1 8 大连理工大学硕士学位论文 骨l 矗 d ， n 坂 曹j x ，爿( x ) a 4 ( 工) 口 营f f x ( a ( x ) a m ( x ) ) 口 因此， v i a 2 n m i 辨2 善( 爿( 石) 肘( x ) ) = a o m 下面介绍f u z z y 积分在模糊规划问题中的应用。 模糊规划问题中模糊限制集a 对目标，的可能度。 给出目标函数厂，它的( 无条件) 模糊优越集m ，诱导出p ( x ) 上的可能性测度 兀，其可能性分布石= 晰，。对任一点x z ，在x 处可达到理想目标的可能度为 厅( x ) = 。，( x ) ，即x 隶属于模糊优越集的程度a 对普通限制集4 p ( x ) ，在4 的限制 条件下可达到理想目标的可能度为 n s ( a ) 2 品石( x ) ；v 川4 n ( 吩) z ( 2 2 4 ) 为了实现这种可能度，应该选择最佳点石+ 满足 a ( x + ) a n ：( x ) = x s ( a ) ( z + a r x ( x ) = 石，( 一) ) ( 2 2 5 ) 即 工+ x + l x a ，x ( x + ) = v 万( x ) ) = f 防a ，f ( x ) = m a x f ( x ) = m 对模糊限制集a f ( x ) ，在a 的限制条件下可达到理想目标的可能度为 n ，( 彳) = p ( x ) 。兀，( ) = 茹( 4 ( x ) m ) ) = v 川a z n ( m s ) z ) 为了实现这种可能度，应该选择最佳点x 满足 a f ( x ) = ( a n m s ) ( x + ) = 兰( 4 ( 曲n m ，( z ) ) = f i s ( a ) a 1 9 求解一类模糊线性规划问题的方法研究 3 模糊线性规划 3 1 经典线性规划 在经典规划论中，线性规划是最基本的而且应用较广泛的个分支，其数学模型为 m i n s = c l x t + c 2 x 2 + + q ( 3 1 ) s j a l l x l + a 1 2 x 2 + _ + 口l 矗6 l 吒l 五十a 2 2 x 2 + 十口2 。x n 趣 ( 3 2 ) a m l x l + 2 x 2 + + 。 一般地，在( 3 1 ) ( 3 2 ) 中，记 c = ( c l ，c 2 ，c n ) a = a i ic t l 2 口l ” a 2 1 2 2 2 口2 a m 口月2 a n n n ( 3 1 ) ( 3 2 ) 可记为 如果( 3 2 ) 中某式为 一 x 2 _ ： x n m l n 口 j t 一x b x 0 b = b 1 b 2 ： _ b 。 a k l x l + a k 2 x 2 + + 口蛔x ns b l n ) j n x 变：e x “= b k 一t 0 ，约束改为： l _ l g k l x l + g k 2 x 2 + + 口蛔x 月+ x 月+ l = 6 这样，可以将线性规划问题化为标准形式，即给出 m i n5 = 甜 占f a x = b z 0 2 0 ( 3 3 ) 大连理工大学硕士学位论文 其中 4 = a 1 1a 1 2 4 1 h a 2 1a 2 2 口2 n a h ld h 2 d m 其中r a n k a = m 把满足约束条件的 工2 ： x 月 b = x l ( 0 ) 工2 ( 0 ) ： x n ( o ) b l 6 2 ： _ b 。 ( a x o = b ) a l j a 2 j ： a m l 称为线性规划问题的可行解：对可行解x ”，若x o = 0 或x o 的非零分量 z ，1 “，z j 2 “，勘所对应的系数矩阵彳的列向量p j l ，p ，：，p ，线性无关时，称为基 础可行解；使目标函数取最小值的可行解称为最优解；使目标函数取最小值的基础可行 解称为基础最优解。 线性规划问题的解具有以下性质 定理3 1 线性规划问题的可行解集为凸集。 一个凸集一中的点z ，如果不能成为一中任何线段的内点，也就是说，对 v x ( ”，石t 2 a ，不存在d ( 0 , 1 ) 使x = 甜1 + ( 1 一a ) x ”，则称x 是彳的极点。 定理3 2 可行解集中的点x 是极点充要条件为x 是基础可行解。 定理3 3 线性规划问题的最优值可以在某极点上找到。即可以在某基础可行解上达到。 命题3 3 指出，如果线性规划问题有最优解，只需在基础可行解中去找。线性规划 通常采用单纯形法，就是根据这个原理，由一个基础可行解迭代到另一基础可行解，经 有限次迭代，求得线性规划问题的最优解，或判定它无最优解。 单纯形方法的求解过程： m i nj = 翻 s j a x = b z 0 步骤1 求一个基础可行解i 及其对应的目标值s ( 王) = 面。 对线性方程组a x = b 的增广矩阵施行初等变换( 对行向量) 2 1 求解一类模糊线性规划问题的方法研究 a l iu 1 2 口2 1a 2 2 q 。b i a 2 nb 2 口。la 。2 口。b 第，i 2 ，0 列分别变成 “l 0 0 a l 。b l a 0 o 1 0 a b ：+ a 。i + 0 o 1 a 。+ b 。 由于行向量初等变换不改变列向量线性关系。因此原系数矩阵4 中第，f 2 ，i 。列 向量风，既，巩线l 生无关。我们称一中m 个线性无关列组成一个基，于是 b = ( 鼠，以，巩) 为一个基a 记 工b = ( t ，x b ，一，工)x = ( 一，z 儿，一，z j 删) ( 五) 称。为对应基丑的基变量，x 。为非基变量。对h 自由取值，解出x b ，即得一个可行 解。取x 。：( 0 ，u 0 一，0 ) ，则h = ( 6 + ，6 ：，6 。) ，即得到一个基础可行解i 。对应的目 标值占( i ) = 牙= c d b l + c 。2 6 2 + + + c ，m b , ，+ 。由于x 0 ，要求6 2 0a 上述结果可以由下面矩阵兀出发，对行旌行初等变换得到。 兀= 0 一c 1- - c 2 b l o l l a 1 2 d 2 一日2 】一a 2 2 b 一口i 一口_ 2 0 一c l 一c i 一c i 2 一c t 一c 月 b l ob l i - 1 0 0 b l 。 b 2 0b 2 、0 1 0 6 2 h b m ob 。1 0 - 0 ( 6 。，6 ：。，6 。) = ( 6 i ，6 ：，6 。) 等于基础可行解的基变量x 。 将第零行中一c 。一c 。，一c 。，变成零，即分别以乘第t 行加到第零行，得 丁( b ) = b o ob o l - 0 0 0 b o 。 b l ob 】l 0 0 0 - b l 。 b 2 0b 2 i 0 0 0 b 2 。 b ，o 巩0 0 0 6 。 2 2 ：一 大连理工大学硕士学位论文 称t ( b ) 为对应基b 的单纯形表，显然 b 0 0 = c ，l b i o + c i 2 b 2 0 + - + c i r a b m o = c 孑= s ( i ) 步骤2 检查i 是否是最优基础可行解。 我们来证明i 最优的充要条件是 b o 0 ( k = 1 , 2 ，”) 事实上，i 最优的充要条件是 对任意可行解x ，恒有 j ( 习s ( x ) 铮c 军一c x 0 由于对矩阵的行施行初等变换相当于左乘某矩阵，因此 于是 = d b l b 2 ( 岛 b i lb 1 2 b 2 lb 2 2 b 。1“。2 丽= ( c j l c i 2 ，c 。) = d b = d a x b l 。 b 2 。 b 。 = d 爿 = ( c l c ，c $ r n ) d a x c 芽- c x = 【( c i l ，c i 2 ，c f m ) d a c 扛 ( c t l ，c f 2 ，c h ) d a c = ( c l ，c i 2 ，c ) 6 l lb 1 2 如。6 2 ： k ，： b l 。 屯。 6 l 删 = ( b o i ，b 0 2 ，b o 。) c 2 一c x = b o l x l + b 0 2 x 2 + + b o x 2 3 求解一类模糊线性规划问题的方法研究 b o j l = b o 2 一一b ，= 0 ，因此i 最优的充要条件是 c 2 一c x 5 b o m x j _ 七b o 、h x i 2 + + b o 。i j x i 一曼0 这里( 。，x m 。) = h 为非基变量u 女) 。如果某b o 0 ，令。 0 ，其余 x = 0 ，可得一个可行解x ，此时西一c x = b o j k x 0 ，因此 丽一取0 ；b s 0 ( k = 1 , 2 ，n ) 。 反之，由于x 0 ，显然b 0 ( k = 1 , 2 ，n ) j 麻一“0 所以i 最优的充要条件是6 。0 ( = 1 , 2 ，n ) 。称b 。为检验数。 步骤3 若所得基础可行解非最优，进行基变量的换基迭代。 结合下面的例子介绍如何进行换基迭代。 m i n s = 一6 x 1 一l o x 2 s r 0 1 8 x l + 0 0 9 x 2 + 屯= 7 2 o 0 8 x l + o 2 8 x 2 + 扎= 5 6 x i 0 ，x 2 0 ，b 0 ，z 4 0 r o61 00 0 3 r o = l7 2 o 1 80 0 910i = r ( b ) ， b = ( p 3 ，p 4 ) 1 5 6 o 0 8o 2 80 l j = ( x 3 ，x 。) ，x = ( x l ，x 2 ) ，基础可行解为i = ( 0 ，0 ，7 2 ，5 6 ) 。对应目标 j ( 习= b o 。= 0 。由于检验数中有正数6 ，1 0 因而非最优。进行换基迭代，用非基变量表 示目标与基变量 j = 0 6 x i l o x 2 x 1 = 7 2 0 1 8 z 一o 0 9 x ， x 4 = 5 6 一o 0 8 x l o 2 8 x 2 将x 换为基变量( 检验数6 0 ，= 6 0 ) ，当x ：= 0 时，j = 一6 x ，随而增大而减小，但而 不能无限制地增大，要求 码= 7 2 0 1 8 x i 0( x x 4 = 5 6 一o 0 8 x l 0( z l 因此五sm i n ( 4 0 0 ，7 0 0 ) = 4 0 0 。取五= 4 0 0 ，可得新的基础可行解 。l = 4 0 0 ，。2 = o ，x 3 = 0 ，x 4 = 2 4 2 4 i l = 记一呲弱一吣 o ，因而非最优，类似地由于等面2 4 ，取k 为轴心项，经初等变换得 f 一2 4 0 0 o 7 _ 1 0 o f 吲0 0 oo _ 5 5 7j 现 i 4 0 0lo 5 5 o h 3 5 01o 1 磋7 - 澎l i z 4 o 4 一- jl - o oo ，一，兹j 新的单纯形表中，检验数非正。因而对应的基础可行解薯= 3 5 0 ，吃= 1 0 0 ， 而= = 0 为最优解，对应的目标s = - 3 1 0 0 为最小值。 说明：1 ) 进行换基迭代时，一般在所有检验数6 0 ，中选最左边一个进行代换。 2 ) 对最左的正检验数，对该列所有正的毛( f 。) ，取每( 6 f 。) 中最小者对应的 为轴心项。如果该列中所有b 。曼o ( i o ) ，则问题无最优籍。 3 2 模糊线性规划 在实际问题中，有时约束条件可能带有伸缩性，其模型是： m i n z = c l x l + c 2 屯+ + 巳砖 j j 。 ( 3 4 ) a x 至b 这里至表示一种弹性约束，可读作“近似小于等于”。设z = 工j z 矗”，善o ) ， 2 5 求解一类模糊线性规划问题的方法研究 对每个约束嘞x ，至包，相应地有中一个模糊子集b 与之对应，其隶属函数如 1 = 1 下： d ( z ) = z ( 呀_ ) _ 岛 j = l ( 3 5 ) 岛 6 l + 4 j _ 】 这里一是适当选择的伸缩指标d ，o ( i = 1 , 2 ，卅) 。 令d = d 。nd 2n n d 。f ( z ) ，称为对应约束条件a x 至b 0 ) 的模糊约束 集。当d ，= 0 ( 扛1 , 2 ，研) 时，d 退化为普通约束集，它满足约束条件 a x b ( x 0 ) 。这时约束方程“至”退化为。 我们仅讨论求目标函数的最大值，记作 m a xz = c 茗 占f ( 3 6 ) 爿x 主b 石0 对求最小值问题，可转化为求一z 的最大值。 模糊线性规划( 3 6 ) 的解法步骤如下： 1 先求普通线性规划问题 m a ) 【= = “ j t a x b z 0 的最大值z n ，及 m a xz = 蹦 s f 4 工s b + d 工0 的最大值气+ d 。，其中b + d = ( 6 l + 盔，b 2 + d 2 ，+ d 。) 7 。是严格遵守约束条件 血b ( 此时隶属度d ( x ) = 1 ) 下的目标函数的最大值；+ d 。是当约束条件放松到 血b + d ( 此时隶属度d ( 工) = o ) 下的目标函数的最大值。毛与+ d 。对应d o ) = 1 与 2 6 ” 一 0吩 。川 4。 大连理工大学硕士学位论文 d ( x ) = 0 的两种极端情形，可以适当降低隶属度d ( x ) 使得最优值有所提高，介于与 + d o 之间。 2 构造模糊目标集m f