模糊规划.ppt

《模糊规划.ppt》由会员分享，可在线阅读，更多相关《模糊规划.ppt（29页珍藏版）》请在课桌文档上搜索。

1、2024/5/8,1,第十讲 模糊线性规划,2024/5/8,2,所谓规划问题，也就是最优化问题。长期以来，最优化思想支配着人类生存和改造世界的活动，才使人类社会得以不断发展。最优问题，在生活、生产和社会行为的各个方面都普遍存在，因此优化是人们普遍的思想。以前解决规划问题的常用的数学方法，叫线性规划这是用线性方程来研究规划问题的方法。经典规划问题的目标函数和约束条件都是明确的，但是，在实际问题中常常碰到模糊的目标函数和约束条件，从面提出了模糊的规划问题，即用模糊集方法来求解模糊最优化问题。,2024/5/8,3,OUTLINE,一、经典线性规划二、模糊线性规划,2024/5/8,4,经典线性规

2、划-概念,先看下面例子。例某工厂生产A,B 两种产品，其情况如下表：,求出该工厂生产A,B 两种产品的最佳方案.,2024/5/8,5,所要求的最佳方案可以归结为求x1,x2使利润最大,且满足约束条件,解 设x1为每天生产的A产品的数量,x2为每天生产的B产品的数量,则每天的利润可以表示为(目标函数)s=1.5x1+1.0 x2,2024/5/8,6,求一组变量(x1,x2,xn)使目标函数最大,且满足约束条件.用矩阵可以表示为,线性规划的一般模型,2024/5/8,7,线性规划的标准形式为(松弛变量在目标函数中的系数为0),为方便求解,需将不等式化为等式(加入松弛变量)(1)若,可加入变量x

3、n+k使得,(2)若,可加入变量xn+k使得,2024/5/8,8,定义2：系数矩阵A的s个列向量Pj1,Pjs线性无关,称这个向量组为线性规划的一个基,记B=Pj1,Pjs.Pjk 对应的自变量xjk称为基变量,或基础解 记xB=xj1,xjs.,如果问题是目标函数的最大值,等价于求目标函数相反数的最小值。因而一般都以求最大值为例.,记Pj表示约束条件系数矩阵A的第j列向量,x(0)表示自变量形成的列向量.,定义1：满足约束条件的x(0)称为线性规划的可行解.是目标函数达到最大值的可行解称为最优解,2024/5/8,9,例如,定义3：基础可行解是指既是可行解又是基础解.,P1和P4线性无关,

4、从而它们对应是基,x1,x4是基变量,2024/5/8,10,线性规划问题的解有以下性质1.线性规划问题的可行解集为凸集 一个凸集A中的点x,如果不能成为A中任何线段的内点,即对任意A中的x(1),x(2),不存在a(0,1),使得x=ax(1)+(1-a)x(2),则称x是A的极点.2.可行解集中的点x是极点的充分必要条件是x为基础可行解;3.线性规划问题的最优值仅在某极点上达到.上述性质的证明见有关”线性规划”的书,根据性质3,求线性规划问题的最优解,只需从可行解集的极点(基础可行解)中去找.,2024/5/8,11,经典线性规划-解法-图解法,约束条件,例 max s=1.5x1+1.0

5、 x2,解首先由约束条件确定可行解区,它由下面四条直线围成,见图的阴影部分.再求目标函数的最优值.考虑直线s=1.5x1+1.0 x2当x1=0,x2=0,s为最小.当s取不同值时,得到一组互相平行的直线,这些直线越远离原点(0,0),s的值(截距)越大.根据性质3,最优点可能是极点(0,6),(5,0),(4,2),经过计算(4,2)为最优点.即x1=4,x2=2为最优解.,2024/5/8,12,经典线性规划-解法-消元法,在某些理想的情况下图解法是非常有效的,然而在大多数实际应用问题中图解法却完全不能用.因为在三维的情况下,用图解法来处理就非常困难;三维以上则肯定不可能的了.此时可用消元

6、法.以前面提到的规划问题为例.首先引入松驰变量,使约束条件不等式成为等式,2024/5/8,13,然而松驰变量没有相应的利润值,因此目标函数可写为,取x3,x4为基变量,则x1,x2为非基变量,即为自由未知量.令x1=x2=0,得x3=10,x4=6.此时s=0.显然这不是最优值.这说明x1,x2作为非基变量是不合适的.若取x1,x4作为基变量,则x2,x3为非基变量.则,带入目标函数，得这里x2的系数为正数,当x2增大s也增大,所以s没有最大值.,2024/5/8,14,取x1,x2为基变量,则x3,x4为非基变量,则,这里非基变量x3,x4的系数为负,而x3,x4非负.因此当它们都为0时s

7、最大,这时x1=4,x2=2为最优解.,带入目标函数，得,综上所述,有的变量作为基变量所得目标值不一定是最优值.只有在目标函数中所有非基变量的系数均为负数时,这时所得的解才是最优解.因此.将非基变量的系数及基变量的0系数称为检验数.,2024/5/8,15,经典线性规划-解法-单纯形法,根据性质3,最优解可以在基础可行解(即A中的基对应变量)中去找.为此,首先确定A中的一个基,然后,由检验数是否为负来判断目标是不是为最优.如果不是，则要换基,直到检验数均变为负或零为.结合前面的例进行讨论:,2024/5/8,16,首先确定约束方程的系数矩阵的一个基.,系数矩阵中任两列都线性无关,故均可作为基.

8、为方便起见,选单位向量作为基,其对应的基变量为x3,x4,则x1,x2为非基变量(自由变量).令x1=x2=0得基础可行解x=(0,0,10,6),目标值为s=1.5x1+x2=0将检验数”1.5,1,0,0”和目标值“0”放在矩阵的上一行,2024/5/8,17,这时检验数1.5和1都为正,所以目标值不是最优值,故要作基变换.试换x1为基变量.问题是先用x3还是用x4去换？请看下面事实:因为当x2=0(x2仍为非基变量)时,s=1.5x1随x1增大而增大,但它不能无限制地增大,它要满足,因此,x1min5,6=5,取最大可能值x1=5(即用x1的系数去除约束值(10/2,6/1),取其中较小

9、数的结果.把2称为主元素，用框上.用行初等变换把主元素化为1,它所在的列的其它元素为0.,2024/5/8,18,由右表可见,第1,4列为单位向量,故选为基,对应基变量为x1,x4,则x2,x3为非基变量.x2对应的系数(检验数)1/4为正数,所以目标值不是最大.换x2为基变量,因为1/(1/2)5/(1/2)所以取x2对应的第二行元素1/2为主元素作初等变换.,2024/5/8,19,这是检验数都为负数,故所得目标值为.令x3=x4=0,可以解得x1=4,x2=2,对应最优值为s=1.5*4+1*2=8表中目标值为-8,这是因为要将基变量对应的系数化为0而去相反数的原因.,2024/5/8,

10、20,例:使用单纯形表进行操作,2024/5/8,21,最优解X*=（2，3，0，4，0）T，z*=22+53=19。,2024/5/8,22,关于单纯形法的补充说明,1.无穷多最优解与唯一最优解的判别法则 若对某可行解X1,(1)所有检验数j0,且有一个非基变量xk的检验数等于0,则问题有无穷多最优解;(2)所有非基变量的检验数j0,但aik0,i=1,2,m即xk的系数列向量无正分量,则问题无最优解。,2024/5/8,23,模糊线性规划,普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能不是单一的，必须借助模糊集的方法来处理.模糊线性规划是

11、将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的模糊最优解.,2024/5/8,24,设普通线性规划的标准形式为,若约束条件带有弹性，即右端常数bi可能取(bi di,bi+di)内的某一个值，这里的di0，它是决策人根据实际问题选择的伸缩指标.这样的规划称为模糊线性规划.,2024/5/8,25,把约束条件带有弹性的模糊线性规划记为,这里的ti(x)=bi,di 表示当di=0(普通约束)时,ti(x)=bi；当di0(模糊约束)时,ti(x)取(bi-di,bi+di)内的某一个值.,2024/5/8,26,下面将约束条件和目标函数模糊化.,将

12、(2)中带有弹性的约束条件(di0)的隶属函数定义为,而将(2)中普通约束条件(di=0)的隶属函数定义为Ai(x)=1,ti(x)=bi.,其图形如右图,2024/5/8,27,由Ai(x)定义可知，0,1,设普通线性规划(1)和(3)的最优值分别为 f0,f1,记 d0=f 0-f 1,则d00,它为模糊线性规划(2)中目标函数的伸缩指标，d0也可由决策人确定.,定义模糊线性规划(2)中目标函数的隶属函数为,2024/5/8,28,由Gi(x)定义可知，0,1,Gi(x)t0(x)+d0 f0,要求模糊线性规划(2)的模糊最优解x*，则要求使所有约束条件及目标函数的隶属函数尽可能达到最大，即求x*满足Ai(x)及G(x)，且使达到最大值,相当于求解普通线性规划问题,i=1,2,m.,2024/5/8,29,设普通线性规划(4)的最优解为x*,则模糊线性规划(2)的模糊最优解为x*,最优值为t0(x*).,所以，求解模糊线性规划(2)相当于求解普通线性规划(1),(3),(4).此外，再补充两点说明：若要使某个模糊约束条件尽可能满足，只需将其伸缩指标降低直至为0；若模糊线性规划(2)中的目标函数为求最大值，或模糊约束条件为近似大(小)于等于，其相应的隶属函数可类似地写出.,