模糊规划.ppt

2019/4/6,1,第十讲 模糊线性规划,2019/4/6,2,所谓规划问题，也就是最优化问题。长期以来，最优化思想支配着人类生存和改造世界的活动，才使人类社会得以不断发展。最优问题，在生活、生产和社会行为的各个方面都普遍存在，因此优化是人们普遍的思想。以前解决规划问题的常用的数学方法，叫线性规划这是用线性方程来研究规划问题的方法。经典规划问题的目标函数和约束条件都是明确的，但是，在实际问题中常常碰到模糊的目标函数和约束条件，从面提出了模糊的规划问题，即用模糊集方法来求解模糊最优化问题。,2019/4/6,3,outline,一、经典线性规划 二、模糊线性规划,2019/4/6,4,经典线性规划-概念,先看下面例子。 例某工厂生产a,b 两种产品，其情况如下表：,求出该工厂生产a,b 两种产品的最佳方案.,2019/4/6,5,所要求的最佳方案可以归结为求x1,x2使利润最大,且满足约束条件,解 设x1为每天生产的a产品的数量, x2为每天生产的b产品的数量,则每天的利润可以表示为(目标函数) s=1.5x1+1.0x2,2019/4/6,6,求一组变量(x1,x2, xn)使目标函数最大,且满足约束条件.用矩阵可以表示为,线性规划的一般模型,2019/4/6,7,线性规划的标准形式为(松弛变量在目标函数中的系数为0),为方便求解,需将不等式化为等式(加入松弛变量) (1)若,可加入变量xn+k使得,(2)若,可加入变量xn+k使得,2019/4/6,8,定义2： 系数矩阵a的s个列向量pj1, pjs线性无关,称这个向量组为线性规划的一个基, 记b= pj1, pjs. pjk 对应的自变量xjk称为基变量,或基础解 记xb= xj1, xjs.,如果问题是目标函数的最大值,等价于求目标函数相反数的最小值。因而一般都以求最大值为例.,记pj表示约束条件系数矩阵a的第j列向量,x(0)表示自变量形成的列向量.,定义1：满足约束条件的x(0)称为线性规划的可行解.是目标函数达到最大值的可行解称为最优解,2019/4/6,9,例如,定义3：基础可行解是指既是可行解又是基础解.,p1和p4线性无关,从而它们对应是基, x1, x4是基变量,2019/4/6,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,求线性规划问题的最优解,只需从可行解集的极点(基础可行解)中去找.,2019/4/6,11,经典线性规划-解法-图解法,约束条件,例 max s=1.5x1+1.0x2,解首先由约束条件确定可行解区,它由下面四条直线围成,见图的阴影部分. 再求目标函数的最优值.考虑直线 s=1.5x1+1.0x2 当x1=0, x2=0, s为最小.当s取不同值时,得到一组互相平行的直线,这些直线越远离原点(0,0),s的值(截距)越大.根据性质3, 最优点可能是极点(0, 6),(5,0),(4,2),经过计算(4,2) 为最优点.即x1=4, x2=2为最优解.,2019/4/6,12,经典线性规划-解法-消元法,在某些理想的情况下图解法是非常有效的,然而在大多数实际应用问题中图解法却完全不能用.因为在三维的情况下,用图解法来处理就非常困难;三维以上则肯定不可能的了.此时可用消元法. 以前面提到的规划问题为例.首先引入松驰变量,使约束条件不等式成为等式,2019/4/6,13,然而松驰变量没有相应的利润值,因此目标函数可写为,取x3,x4为基变量,则x1,x2为非基变量,即为自由未知量. 令x1=x2=0,得x3=10,x4=6. 此时s=0.显然这不是最优值.这说明x1,x2作为非基变量是不合适的. 若取x1,x4作为基变量,则x2,x3为非基变量.则,带入目标函数，得 这里x2的系数为正数,当x2增大s也增大,所以s没有最大值.,2019/4/6,14,取x1,x2为基变量,则x3,x4为非基变量,则,这里非基变量x3,x4的系数为负,而x3,x4非负.因此当它们都为0时s最大,这时x1=4,x2=2为最优解.,带入目标函数，得,综上所述,有的变量作为基变量所得目标值不一定是最优值.只有在目标函数中所有非基变量的系数均为负数时,这时所得的解才是最优解.因此.将非基变量的系数及基变量的0系数称为检验数.,2019/4/6,15,经典线性规划-解法-单纯形法,根据性质3,最优解可以在基础可行解(即a中的基对应变量)中去找.为此,首先确定a中的一个基,然后,由检验数是否为负来判断目标是不是为最优.如果不是，则要换基,直到检验数均变为负或零为. 结合前面的例进行讨论:,2019/4/6,16,首先确定约束方程的系数矩阵的一个基.,系数矩阵中任两列都线性无关,故均可作为基.为方便起见,选单位向量作为基,其对应的基变量为x3,x4,则x1,x2为非基变量(自由变量).令x1=x2=0得基础可行解x=(0,0,10,6),目标值为 s=1.5x1+x2=0 将检验数”1.5,1,0,0”和目标值“0”放在矩阵的上一行,2019/4/6,17,这时检验数1.5和1都为正,所以目标值不是最优值,故要作基变换. 试换x1为基变量. 问题是先用x3还是用x4去换？请看下面事实: 因为当x2=0(x2仍为非基变量)时,s=1.5x1随x1增大而增大,但它不能无限制地增大,它要满足,因此,x1min5,6=5,取最大可能值x1=5(即用x1的系数去除约束值(10/2,6/1),取其中较小数的结果.把2称为主元素，用框上.用行初等变换把主元素化为1 ,它所在的列的其它元素为0.,2019/4/6,18,由右表可见,第1,4列为单位向量,故选为基,对应基变量为x1,x4,则x2,x3为非基变量.x2对应的系数(检验数)1/4为正数,所以目标值不是最大. 换x2为基变量,因为1/(1/2)5/(1/2)所以取x2对应的第二行元素1/2为主元素作初等变换.,2019/4/6,19,这是检验数都为负数,故所得目标值为. 令x3=x4=0,可以解得x1=4, x2=2, 对应最优值为 s=1.5*4+1*2=8 表中目标值为-8,这是因为要将基变量对应的系数化为0而去相反数的原因.,2019/4/6,20,例:使用单纯形表进行操作,2019/4/6,21,最优解x*=（2，3，0，4，0）t，z*=22+53=19。,2019/4/6,22,关于单纯形法的补充说明,1. 无穷多最优解与唯一最优解的判别法则 若对某可行解x1,(1)所有检验数j0,且有一个非基变量xk的检验数等于0,则问题有无穷多最优解;(2)所有非基变量的检验数j0,但aik0,i=1,2,m即xk的系数列向量无正分量,则问题无最优解。,2019/4/6,23,模糊线性规划,普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能不是单一的，必须借助模糊集的方法来处理. 模糊线性规划是将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的模糊最优解.,2019/4/6,24,设普通线性规划的标准形式为,若约束条件带有弹性，即右端常数bi可能取 (bi di , bi + di ) 内的某一个值，这里的di0，它是决策人根据实际问题选择的伸缩指标. 这样的规划称为模糊线性规划.,2019/4/6,25,把约束条件带有弹性的模糊线性规划记为,这里的ti (x) = bi, di 表示当di = 0(普通约束)时, ti (x) = bi；当di0(模糊约束)时, ti (x) 取(bi - di, bi + di )内的某一个值.,2019/4/6,26,下面将约束条件和目标函数模糊化.,将(2)中带有弹性的约束条件(di0)的隶属函数定义为,而将(2)中普通约束条件(di = 0)的隶属函数定义为 ai (x) = 1, ti (x) = bi .,其图形如右图,2019/4/6,27,由ai (x)定义可知，0, 1,设普通线性规划(1)和(3)的最优值分别为 f0, f1 , 记 d0 = f 0 - f 1 , 则d00, 它为模糊线性规划(2)中目标函数的伸缩指标，d0也可由决策人确定.,定义模糊线性规划(2)中目标函数的隶属函数为,2019/4/6,28,由gi (x)定义可知，0, 1,gi (x) t0 (x) + d0 f0,要求模糊线性规划(2)的模糊最优解x*，则要求使所有约束条件及目标函数的隶属函数尽可能达到最大，即求x* 满足 ai (x)及g(x)， 且使达到最大值,相当于求解普通线性规划问题,i = 1, 2, , m.,2019/4/6,2