模糊规划.ppt

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

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

2、规划2024-5-84经典线性规划-概念n先看下面例子。例某工厂生产A,B 两种产品，其情况如下表：A产品需要的工时B产品需要的工时机床每天最大可利用工时机床I机床II单件产品利润211.5(元)111.0(元)106n求出该工厂生产A,B 两种产品的最佳方案.2024-5-85所要求的最佳方案可以归结为求x1,x2使利润最大,且满足约束条件解 设x1为每天生产的A产品的数量,x2为每天生产的B产品的数量,则每天的利润可以表示为(目标函数)s=1.5x1+1.0 x212121221060,0 xxxxxx 2024-5-86求一组变量(x1,x2,xn)使目标函数最大,且满足约束条件.用矩阵

3、可以表示为线性规划的一般模型11221111221121122222112212OBJECT FUNCTION .Under Condiotns:.0,0,.,0nnnnnnmmmnnmnsc xc xc xa xa xa xba xa xaxbaxaxaxbxxx max s.t.0AxbsCxx 2024-5-87线性规划的标准形式为(松弛变量在目标函数中的系数为0)为方便求解,需将不等式化为等式(加入松弛变量)(1)若11221111221121122222112212OBJECT FUNCTION .Under Condiotns:.0,0,.,0nnnnnnmmmnnmnsc xc

4、xc xa xa xa xba xa xaxbaxaxaxbxxx max s.t.0sCxAxbx 1122.kkknnka xaxa xb可加入变量xn+k使得1122.kkknnn kka xaxa xxb(2)若1122.kkknnka xaxa xb可加入变量xn+k使得1122.kkknnn kka xaxa xxb 2024-5-88定义2：系数矩阵A的s个列向量Pj1,Pjs线性无关,称这个向量组为线性规划的一个基,记B=Pj1,Pjs.Pjk 对应的自变量xjk称为基变量,或基础解 记xB=xj1,xjs.如果问题是目标函数的最大值,等价于求目标函数相反数的最小值。因而一般都

5、以求最大值为例.记Pj表示约束条件系数矩阵A的第j列向量,x(0)表示自变量形成的列向量.定义1：满足约束条件的x(0)称为线性规划的可行解.是目标函数达到最大值的可行解称为最优解2024-5-89例如定义3：基础可行解是指既是可行解又是基础解.12341211,2424PPPP 123412115,(,)242410TTABxxxxxP1和P4线性无关,从而它们对应是基,x1,x4是基变量2024-5-810n线性规划问题的解有以下性质线性规划问题的解有以下性质1.线性规划问题的可行解集为凸集线性规划问题的可行解集为凸集 一个凸集一个凸集A中的点中的点x,如果不能成为如果不能成为A中任何线段

6、中任何线段的内点的内点,即对任意即对任意A中的中的x(1),x(2),不存在不存在a(0,1),使使得得x=ax(1)+(1-a)x(2),则称则称x是是A的极点的极点.2.可行解集中的点可行解集中的点x是极点的充分必要条件是是极点的充分必要条件是x为基为基础可行解础可行解;3.线性规划问题的最优值仅在某极点上达到线性规划问题的最优值仅在某极点上达到.上述性质的证明见有关上述性质的证明见有关”线性规划线性规划”的书的书,根据性根据性质质3,求线性规划问题的最优解求线性规划问题的最优解,只需从可行解集的只需从可行解集的极点极点(基础可行解基础可行解)中去找中去找.2024-5-811经典线性规划

7、-解法-图解法约束条件例 max s=1.5x1+1.0 x212121221060,0 xxxxxx 解首先由约束条件确定可行解区,它由下面四条直线围成,见图的阴影部分.再求目标函数的最优值.考虑直线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-812经典线性规划-解法-消元法1231242106xxxxxx 在某些理想的情况下图解法是非常有效的,然而在大

8、多数实际应用问题中图解法却完全不能用.因为在三维的情况下,用图解法来处理就非常困难;三维以上则肯定不可能的了.此时可用消元法.以前面提到的规划问题为例.首先引入松驰变量,使约束条件不等式成为等式2024-5-81312341.500sxxxx然而松驰变量没有相应的利润值,因此目标函数可写为 12311522xxx取x3,x4为基变量,则x1,x2为非基变量,即为自由未知量.令x1=x2=0,得x3=10,x4=6.此时s=0.显然这不是最优值.这说明x1,x2作为非基变量是不合适的.若取x1,x4作为基变量,则x2,x3为非基变量.则 带入目标函数，得这里x2的系数为正数,当x2增大s也增大,

9、所以s没有最大值.23137.544sxx2024-5-814134234422xxxxxx 取x1,x2为基变量,则x3,x4为非基变量,则 这里非基变量x3,x4的系数为负,而x3,x4非负.因此当它们都为0时s最大,这时x1=4,x2=2为最优解.3480.50.5sxx带入目标函数，得综上所述,有的变量作为基变量所得目标值不一定是最优值.只有在目标函数中所有非基变量的系数均为负数时,这时所得的解才是最优解.因此.将非基变量的系数及基变量的0系数称为检验数.2024-5-815经典线性规划-解法-单纯形法121231241234max 1.5210.6,0sxxxxxs txxxxxxx

10、 根据性质3,最优解可以在基础可行解(即A中的基对应变量)中去找.为此,首先确定A中的一个基,然后,由检验数是否为负来判断目标是不是为最优.如果不是，则要换基,直到检验数均变为负或零为.结合前面的例进行讨论:2024-5-81612341.5100021101011016xxxxs首先确定约束方程的系数矩阵的一个基.系数矩阵中任两列都线性无关,故均可作为基.为方便起见,选单位向量作为基,其对应的基变量为x3,x4,则x1,x2为非基变量(自由变量).令x1=x2=0得基础可行解x=(0,0,10,6),目标值为s=1.5x1+x2=0将检验数”1.5,1,0,0”和目标值“0”放在矩阵的上一行

11、2024-5-81731114110205 660 xxxorxxx 这时检验数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.2024-5-81812341.5100021101011016xxxxs由右表可见,第1,4列为单位向量,故

12、选为基,对应基变量为x1,x4,则x2,x3为非基变量.x2对应的系数(检验数)1/4为正数,所以目标值不是最大.换x2为基变量,因为1/(1/2)5/(1/2)所以取x2对应的第二行元素1/2为主元素作初等变换.123413007.54411105221110122xxxxs 2024-5-819这是检验数都为负数,故所得目标值为.令x3=x4=0,可以解得x1=4,x2=2,对应最优值为s=1.5*4+1*2=8表中目标值为-8,这是因为要将基变量对应的系数化为0而去相反数的原因.123413007.54411105221110122xxxxs 1234000.50.58101140112

13、2xxxxs 2024-5-820n例:使用单纯形表进行操作0,12 4 20 258 2 52 max543215242132121xxxxxxxxxxxxxxxz2024-5-821cj25000比比CBXBbx1x2x3x4x5000 x3x4x5820121502241000100018/220/212/4j25000005x3x4x22143150001100010-1/2-1/21/42/114/5j2000-5/4205x1x4x22431000011-50010-1/221/4j00-20-1/4最优解X*=（2，3，0，4，0）T，z*=22+53=19。2024-5-822

14、关于单纯形法的补充说明关于单纯形法的补充说明n1.无穷多最优解与唯一最优解的判别法则无穷多最优解与唯一最优解的判别法则 若对某可行解若对某可行解X1,(1)所有检验数所有检验数j0,且有一个非基且有一个非基变量变量xk的检验数等于的检验数等于0,则问题有无穷多最优解则问题有无穷多最优解;(2)所有非基变量的检验数所有非基变量的检验数j0,但但aik0,i=1,2,m即即xk的系数列向量无正分量的系数列向量无正分量,则问题则问题无最优解。无最优解。2024-5-823模糊线性规划模糊线性规划 普通线性规划其约束条件和目标函数都是确定普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，

15、约束条件可能带有弹性，的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能不是单一的，必须借助模糊集的方法目标函数可能不是单一的，必须借助模糊集的方法来处理来处理.模糊线性规划是将约束条件和目标函数模糊化，模糊线性规划是将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的它的最优解称为原问题的模糊最优解模糊最优解.2024-5-824设普通线性规划的标准形式为设普通线性规划的标准形式为0)(.)(min)1(0 xxxiibttstf12nxxxxt0(x)=c1x1+c2x2+cnxn,ti(x)=a

16、i1x1+ai2x2+ainxn i=1,2,m.若约束条件带有弹性，即右端常数若约束条件带有弹性，即右端常数bi可能取可能取(bi di,bi+di)内的某一个值，这里的内的某一个值，这里的di0，它是决策人根据实，它是决策人根据实际问题选择的际问题选择的伸缩指标伸缩指标.这样的规划称为这样的规划称为模糊线模糊线性规划性规划.2024-5-825把约束条件带有弹性的模糊线性规划记为把约束条件带有弹性的模糊线性规划记为0,)(.)(min)2(0 xxxiiidbttstf这里的这里的ti(x)=bi,di 表示当表示当di=0(普通约束普通约束)时时,ti(x)=bi；当当di0(模糊约束模糊约束)时时,ti(x)取取(bi-di,bi+di)内的某一个值内的某一个值.0)(.)(min)3(0 xxxiiiiidbtdbtstf的区别的区别.请注意模糊线性规划请注意模糊线性规划(2)与普通线性规划与普通线性规划2024-5-826下面将约束条件和目标函数模糊化下面将约束条件和目标函数模糊化.将将(2)中带有弹性的约束条件中带有弹性的约束条件(di0)的隶属函数定的隶属函数定义为义为