模煳数学05 线性规划.pptVIP

第 5 节模糊线性规划 §5.1 普通线性规划 单纯形解法 大M单纯形解法 §5.2 模糊线性规划 多目标线性规划 * * 线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支 . 线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题, 它都可以化为如下标准(矩阵)形式： A = (aij )m×n c = (c1 , c2 , … , cn ) x≥0指x中的每一个分量xj ≥0 典型线性规划问题： 的单纯形解法是引入m个松弛变量xn+1 , …, xn+m将原问题化成如下标准形式： 不难将一般的线性规划问题化成如下标准形式： 大M单纯形解法是引入m个人工变量xn+1 , …, xn+m将原问题变为 大M单纯形解法中的M为足够大的正数, 起“惩罚”作用, 以便排除人工变量. 普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能不是单一的，必须借助模糊集的方法来处理. 模糊线性规划是将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的模糊最优解. 设普通线性规划的标准形式为 t0(x) = c1x1 + c2x2 + … + cnxn , ti (x) = ai1x1 + ai2x2 + … + ainxn i = 1, 2, …, m. 若约束条件带有弹性，即右端常数bi可能取 (bi – di , bi + di ) 内的某一个值，这里的di＞0，它是决策人根据实际问题选择的伸缩指标. 这样的规划称为模糊线性规划. 把约束条件带有弹性的模糊线性规划记为 这里的ti (x) =[ bi, di ] 表示当di = 0(普通约束)时, ti (x) = bi；当di＞0(模糊约束)时, ti (x) 取(bi - di, bi + di )内的某一个值. 的区别. 请注意模糊线性规划(2)与普通线性规划 下面将约束条件和目标函数模糊化. 将(2)中带有弹性的约束条件(di＞0)的隶属函数定义为 而将(2)中普通约束条件(di = 0)的隶属函数定义为 Ai (x) = 1, ti (x) = bi . 其图形如右图 由Ai (x)定义可知，??∈[0, 1], Ai (x)≥? ? di ? - di≤ti (x) - bi≤di - di ?, i = 1, 2, … , m. 设普通线性规划(1)和(3)的最优值分别为 f0, f1 , 记 d0 = f 0 - f 1 , 则d0＞0, 它为模糊线性规划(2)中目标函数的伸缩指标，d0也可由决策人确定. 定义模糊线性规划(2)中目标函数的隶属函数为 由Gi (x)定义可知，??∈[0, 1], Gi (x)≥? ? t0 (x) + d0?≤ f0, 要求模糊线性规划(2)的模糊最优解x*，则要求使所有约束条件及目标函数的隶属函数尽可能达到最大，即求x* 满足 Ai (x)≥?及G(x)≥?， 且使?达到最大值,相当于求解普通线性规划问题 i = 1, 2, …, m. 设普通线性规划(4)的最优解为x*, ? , 则模糊线性规划(2)的模糊最优解为x*, 最优值为t0 (x*). 所以，求解模糊线性规划(2)相当于求解普通线性规划(1), (3), (4). 此外，再补充两点说明： ① 若要使某个模糊约束条件尽可能满足，只需将其伸缩指标降低直至为0； ② 若模糊线性规划(2)中的目标函数为求最大值，或模糊约束条件为近似大(小)于等于，其相应的隶属函数可类似地写出. 例1 解模糊线性规划问题(P275)： 在相同的条件下,要求多个目标函数都得到最好的满足,这便是多目标规划. 若目标函数和约束条件都是线性的,则为多目标线性规划. 一般来说,多个目标函数不可能同时达到其最优值,因此只能求使各个目标都比较“满意”的模糊最优解. *