《模糊数学》课程PPT课件：第5章 模糊线性规划

第5 模糊性规劍

§5.1普通线性规划 线性规划是最优化方法中理论完整、方法成 熟、应用广泛的一个重要分支 线性规划问题的数学模型是将实际问题转化 为一组线性不等式或等式约束下求线性目标函数 的最小(大)值问题,它都可以化为如下标准(矩 阵)形式: min f A=(at)m×n Ax=b b s,t x≥0指x中的每 0 个分量x;≥0 b

线性规划是最优化方法中理论完整、方法成 熟、应用广泛的一个重要分支 . 线性规划问题的数学模型是将实际问题转化 为一组线性不等式或等式约束下求线性目标函数 的最小(大)值问题, 它都可以化为如下标准(矩 阵)形式：       0. , . . min x Ax b cx s t f        n x x x  2 1 x        bm b b  2 1 b A = (aij)m×n c = (c1 , c2 , … , cn ) x≥0指x中的每 一个分量xj≥0

单纯形解法 典型线性规划问题: max f=cx Ax≤b(≥0) y≥0 的单纯形解法是引入m个松弛变量xn1, ··9n+nn 将 原问题化成如下标准形式: min f n+1 c Ax + x B b n+ B st B n+m

单纯形解法 典型线性规划问题：        0. ( 0) . . max x Ax b cx s t f 的单纯形解法是引入m个松弛变量xn+1 , …, xn+m将 原问题化成如下标准形式：          ( , ) 0. , . . min B B x x Ax x b cx s t f           n m n n x x x  2 1 xB

大M单纯形解法 不难将一般的线性规划问题化成如下标准形 式: min f 大M单纯形解法 中的M为足够大的正 Ax=b≥0 s t 数,起“惩罚”作用 x≥0 以便排除人工变量 大M单纯形解法是引入m个人工变量 n+1 9·· nn将原问题变为 minf=cx+M∑ n+1 n+2 ∫Ax+xn=b, B (x,xg)≥0 n+m

大M单纯形解法 不难将一般的线性规划问题化成如下标准形 式：        0. 0, . . min x Ax b cx s t f 大M单纯形解法是引入m个人工变量xn+1 , …, xn+m将原问题变为            ( , ) 0. , . . min 1 B B x x Ax x b cx s t f M x m k n k           n m n n x x x  2 1 xB 大M单纯形解法 中的M为足够大的正 数, 起“惩罚”作用, 以便排除人工变量

§52模糊线性规划 普通线性规划其约束条件和目标函数都 是确定的,但在一些实际问题中,约束条件 可能带有弹性,目标函数可能不是单一的, 必须借助模糊集的方法来处理 模糊线性规划是将约束条件和目标函数 模糊化,引入隶属函数,从而导出一个新的 线性规划问题,它的最优解称为原问题的模 糊最优解

普通线性规划其约束条件和目标函数都 是确定的，但在一些实际问题中，约束条件 可能带有弹性，目标函数可能不是单一的， 必须借助模糊集的方法来处理. 模糊线性规划是将约束条件和目标函数 模糊化，引入隶属函数，从而导出一个新的 线性规划问题，它的最优解称为原问题的模 糊最优解

设普通线性规划的标准形式为 in f=to( ){(x)=bx x≥0 (x)=C x1+C2x2+.+Cx t (x)=aix+ ai2x2+..+air 若约束条件带有弹性,即右端常数b可能取 (bi-di, bitd) 内的某一个值,这里的d1>0,它是决策人根据实 际问题选择的伸缩指标.这样的规划称为模糊线 性规划

设普通线性规划的标准形式为            0 ( ) . . min ( ) (1) 0 x x x i i t b st f t        n x x x  2 1 x t0(x) = c1x1 + c2x2 + … + cnxn , t i(x) = ai1x1 + ai2x2 + … + ainxn i = 1, 2, …, m. 若约束条件带有弹性，即右端常数bi可能取 (bi– di , bi + di) 内的某一个值，这里的di＞0，它是决策人根据实 际问题选择的伸缩指标. 这样的规划称为模糊线 性规划

把约束条件带有弹性的模糊线性规划记为 min f=to(x) (2) st ∫t(x)=D,4 0 这里的(x)=bp41表示当l2=0普通约束)时,(x)=b; 当d1>0(模糊约束)时,毛(x)取(b;-d,b;+d4)内的某一个值 请注意模糊线性规划(2)与普通线性规划 min f=to(x (3) b-d1≤1(x)≤b1+d s.t. ≥0 的区别

把约束条件带有弹性的模糊线性规划记为            0 ( ) [ , ] . . min ( ) (2) 0 x x x i i i t b d st f t 这里的t i(x) =[ bi, di] 表示当di = 0(普通约束)时, t i(x) = bi； 当di＞0(模糊约束)时, t i(x) 取(bi - di, bi + di)内的某一个值.               0 ( ) . . min ( ) (3) 0 x x x i i i i i b d t b d st f t 的区别. 请注意模糊线性规划(2)与普通线性规划

下面将约束条件和目标函数模糊化 将(2)中带有弹性的约束条件40)的隶属函 数定义为 A(x)=1-11(x)-b h-≤(x)≤b+d A:(x) 而将(2)中普通约束条 件(l2=0)的隶属函数 定义为 A1(x)=1,t1(x)=b 其图形如右图 o b bi+di ti(x)

下面将约束条件和目标函数模糊化. 将(2)中带有弹性的约束条件(di＞0)的隶属函 数定义为 i i i i i i i i i b d t b d d t b        , ( ) | ( ) | ( ) 1 x x A x 而将(2)中普通约束条 件(di = 0)的隶属函数 定义为 Ai(x) = 1, t i(x) = bi . 其图形如右图

由A1(x)定义可知,V∈[0,1, A1(x)≥分l-d≤1(x)-b≤d-d1 1,2,…,,m 设普通线性规划(1)和(3)的最优值分别为f, f1,记 do=fof1 则dn>0,它为模糊线性规划(2)中目标函数的伸缩 指标,山也可由决策人确定 定义模糊线性规划(2)中目标函数的隶属函数 为 G;(x) f6-t0(x) 60-do≤to(x)≤f6

由Ai(x)定义可知，∈[0, 1], Ai(x)≥  di  - di≤t i(x) - bi≤di - di , i = 1, 2, … , m. 设普通线性规划(1)和(3)的最优值分别为 f0 , f1 , 记 d0 = f 0 - f 1 , 则d0＞0, 它为模糊线性规划(2)中目标函数的伸缩 指标，d0也可由决策人确定. , ( ) . ( ) ( ) 0 0 0 0 0 0 0 f d t f d f t i      x x G x 定义模糊线性规划(2)中目标函数的隶属函数 为

由G(x)定义可知,VA∈|0,1l G;(x)>分>t(x)+4≤f 要求模糊线性规划(2)的模糊最优解x,则要 求使所有约束条件及目标函数的隶属函数尽可能 达到最大,即求x*满足 A1(x)>及Gx)>, 且使λ达到最大值相当于求解普通线性规划问题 max h 10(x)+d0≤f01=1,2,m (4)1s1a10-l≤4(x)-b2≤d1-d x≥0

由Gi(x)定义可知，∈[0, 1], Gi(x)≥  t0 (x) + d0≤ f0 , 要求模糊线性规划(2)的模糊最优解x* ，则要 求使所有约束条件及目标函数的隶属函数尽可能 达到最大，即求x*满足 Ai(x)≥及G(x)≥， 且使达到最大值,相当于求解普通线性规划问题                  0 ( ) ( ) . . max (4) 0 0 0 x x x     i i i i i i d d t b d d t d f st i = 1, 2, …, m