第五讲：模糊线性规划

第5章模糊线性规划§5.1普通线性规划一、线性规划模型的基本形式线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题,它都可以化为如下标准(矩阵)形式：.0x,bAx..cxmaxtsfnxxx21xmbbb21bA=(aij)m×nc=(c1,c2,…,cn)x≥0指x中的每一个分量xj≥0对于线性规划问题：.0x)0(bAx..cxmintsf等价于如下标准形式：.0x,bAx..cxmaxtsf而对于线性规划问题：.0x)0(bAx..cxmaxtsf可通过引入m个松弛变量xn+1,…,xn+m，将原问题化成如下标准形式：.0)x,x(,bxAx..cxmaxBBtsfmnnnxxx21Bx而对于线性规划问题：.0x)0(bAx..cxmintsf可通过引入m个松弛变量xn+1,…,xn+m，将原问题化成如下标准形式：.0)x,x(,bx)1(Ax..cxmaxBBtsfmnnnxxx21Bx二、线性规划模型解的有关概念性规划问题的可行解。是线满足约束条件，则称若定义）（）（001xx为最优解。的可行解称使目标函数达到最大值定义2称为非基变量。称为基变量，其余变量基。与基对应的变量为线性规划问题的一个）（线性无关，则称向量组个列向量有若系数矩阵定义ssjjjjjjPPPBPPPsA,,,,,,32121解称为基础可行解。为基础解。可行的基础为零的向量称基变量非零而非基变量定义4三、线性规划模型解的性质集为凸集；线性规划问题的可行解.1的极点。为任何线段的内点，则称中，如果不能成为中的点一个凸集AxAxA为基础可行解；是是极点的充分必要条件可行解集中的点xx.2必在某极点达到。线性规划问题的最优解.4二、线性规划问题的解法图解法.1单纯形法.2根据性质3，最优解可以在基础可行解中去找。为此，首先确定A中的一个基，然后，由检验数是否为负来判断目标函数是否为最优。如果不是，则要换基，直到检验数均为负或者零为止。0,,,6102..5.1max432142132121xxxxxxxxxxtsxxf求解规划问题例解首先确定约束方程系数矩阵是一个基：6101110011200015.1fxxxx43210005.1),6,10,0,0(04321212143xxxxfxxxxxxx目标函数值为可行解，得基础为非基变量。令，则，，应的基变量为取单位向量作为基，对检验数中1.5，1均为正数，目标值非最优，需换基。换基：为主元素。故因为2,1/62/106101110011200015.1112/12/10502/12/115.704/34/106101110011200015.1检验数中1/4为正数，目标值非最优，需换基。换基：为主元素。故因为2/1),2/1/(1)2/1/(5112/12/10502/12/115.704/34/10221104110185.05.000检验数中没有正数，目标值最优，完成计算：.8,0,2,44321fxxxx得到最优解为§5.2模糊线性规划普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能不是单一的，必须借助模糊集的方法来处理.模糊线性规划是将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的模糊最优解.模糊线性规划的形式为0~..maxxbAxtsCxf立。成等式之间的某个隶属度使不和界于以个模糊集描述的，是由等于”。是“近似小于”表示某种弹性，意思其中“bAxxmbAx10~~为简单计，令”的隶属函数为设模糊集“,,,2,1),(~mixDbAxi)()(1njjijiixafxDiinjjijiinjjijiinjjijiinjjijdbxadbxabbxadbxa1111,0),(11,1.,,2,1ni。是适当选择的弹性参数其中)0(id，若令mDDDD21，来代表约束条件则可用bAxD~的即bAx~).()(1xDxDimi的隶属函数为”。”成为“通约束，这时“就退化为普时，当~),,2,1(0Dmidi.~00fCxfCx集原模糊约束下变成模糊，在条件将目标函数转化为约束为普通线性规划其中0f0..maxxbAxtsCxf的最优值。”的隶属函数为设模糊集“0~fCx)()(1niiixcgxG001001001001,1),(11,0dfxcdfxcffxcdfxcniiiniiiniiiniii围。表示满意程度的摆动范通规划的最优值，后普改为是将约束条件的限其中000ddbbdfiii，采用和模糊目标为兼顾模糊约束GDGDB，使得大隶属原则求最优解进行模糊判决，再用最x)]()([max)(xGxDxBXx}0,)(,)(max{xGxD}0,)(,)(,,)(max{1xGxDxDm于是，综合线性规划为),,2,1(0,0)(1,,2,1,)(11max0101nixfxcdmjbxadiniiiinijijj规划的解。合线性规划即得模糊利用单纯形法求解此综：模糊线性规划求解步骤求解普通线性规划.10..maxxbAxtsCxf；得0f求解普通线性规划给定),,,1(.2midi0..maxxdbAxtsCxf；得00df求解综合线性规划.3),,2,1(0,0)(1,,2,1,)(11max0101nixfxcdmjbxadiniiiinijijj。和得x例甲乙两机械每月最多约能运行分别为400和250个工时。甲机械每工时消耗（维修、折旧等）3元，但获净利润7元；乙机械每工时消耗2元，但获净利润3元。甲乙两机械每月消费总和约不得超过1500元，问如何安排两机械的运行可获得最大利润？解行工时数，分别为甲、乙两机械运、设11xx规划模型：由题意可建立如下模糊0,0250~,400~1500~2337max21212121xxxxxxxxf0,0250~,400~1500~2337max21212121xxxxxxxxf。工时，工时，元的弹性指标分别取模糊约束)(5)(5)(50250~,400~,1500~232121xxxx第一步解普通线性规划问题0,0250,40015002337max21212121xxxxxxxxf.0f求0,0250,40015002337max21212121xxxxxxxxf5,4,3,2,1,0250,40015002337max524132121ixxxxxxxxxxfi用单纯形法：5,4,3,2,1,0250,40015002337max524132121ixxxxxxxxxxfi2501001040001001150000123000037根据模型写出矩阵2501001040001001150000123000037250100104000100130003120280007030250100104000100130003120280007030：中有正数，需继续变换，，，检验数030310015.15.0004000100115005.15.010325005.25.100最优解。为检验数无正数，150,400,3250210xxf第二步解普通线性规划问题0,05250,54005015002337max21212121xxxxxxxxf.00df求5,4,3,2,1,0255,40515502337max524132121ixxxxxxxxxxfi5.167,405,5.33372100xxdf.5.8732505.33375.333700fd第三步解综合线性规划问题),,2,1(0,01)(1,,2,1,)(11max0101nixfxcdmjbxadiniiiinijijj5,50,3250,5.8732100dddfd)2,1(0,01)325037(5.871)250(511)400(511)150023(5011max212121ixxxxxxxi)2,1(0,0132505.87372555405515505023max212121ixxxxxxxi)6,5,4,3,2,1(0,0132505.87372555405515505023max76215241321ixxxxxxxxxxxxi.75.3293,5.0,75.158,5.402***2*1fxx多目标线性规划在相同的条件下,要求多个目标函数都得到最好的满足,这便是多目标规划.若目标函数和约束条件都是线性的,则为多目标线性规划.一般来说,多个目标函数不可能同时达到其最优值,因此只能求使各个目标都比较“满意”的模糊最优解.例2解多目标线性规划问题(P280)：.0,,,64,1023..;32max;2min32132132132123211xxxxxxxxxtsxxxfxxxf⑴解普通线性规划问题：.0,,,64,1023..;2min3213213213211xxxxxxxxxtsxxxf得最优解为x1=0,x2=2,x3=2,最优值为2，此时f2=8.⑵解普通线性规划问题：.0,,,64,1023..;32max3213213213212xxxxxxxxxtsxxxf得最优解为x1=10,x2=0,x3=0,最优值为20，此时f1=10.线性规划问题⑴的最优解为x1=0,x2=2,x3=2,最优值为2,此时f2=8.线性规划问题⑵的最优解为x1=10,x2=0,x3=0,最优值为20，此时f1=10.同时考虑两个目标，合理的方案是使f1∈[2,10],f2∈[8,20],可取伸缩指标分别为d1=10-2=8,d2=20-8=12.如果认为目标f1更重要,可单独缩小d1;如果认为目标f2更重要，可单独缩小d2.⑶再分别将两个目标函数模糊化,变为解普通线性规划问题：.64,1023,81232