十模糊规划.PPTVIP

* * 第十讲 模糊线性规划 * * 所谓规划问题，也就是最优化问题。长期以来，最优化思想支配着人类生存和改造世界的活动，才使人类社会得以不断发展。最优问题，在生活、生产和社会行为的各个方面都普遍存在，因此优化是人们普遍的思想。以前解决规划问题的常用的数学方法，叫线性规划．这是用线性方程来研究规划问题的方法。经典规划问题的目标函数和约束条件都是明确的，但是，在实际问题中常常碰到模糊的目标函数和约束条件，从面提出了模糊的规划问题，即用模糊集方法来求解模糊最优化问题。 * * OUTLINE 一、经典线性规划 二、模糊线性规划 * * 经典线性规划-概念 先看下面例子。例某工厂生产A,B 两种产品，其情况如下表： A产品需要的工时 B产品需要的工时 机床每天最大可利用工时 机床I 机床II 单件产品利润 2 1 1.5(元) 1 1 1.0(元) 10 6 求出该工厂生产A,B 两种产品的最佳方案. * * 所要求的最佳方案可以归结为求x1,x2使利润最大,且满足约束条件 解 设x1为每天生产的A产品的数量, x2为每天生产的B产品的数量,则每天的利润可以表示为(目标函数) s=1.5x1+1.0x2 * * 求一组变量(x1,x2,…, xn)使目标函数最大,且满足约束条件.用矩阵可以表示为 线性规划的一般模型 * * 线性规划的标准形式为(松弛变量在目标函数中的系数为0) 为方便求解,需将不等式化为等式(加入松弛变量) (1)若 可加入变量xn+k使得 (2)若 可加入变量xn+k使得 * * 定义2： 系数矩阵A的s个列向量{Pj1,…, Pjs}线性无关,称这个向量组为线性规划的一个基, 记B= {Pj1,…, Pjs}. Pjk 对应的自变量xjk称为基变量,或基础解 记xB= {xj1,…, xjs}. 如果问题是目标函数的最大值,等价于求目标函数相反数的最小值。因而一般都以求最大值为例. 记Pj表示约束条件系数矩阵A的第j列向量,x(0)表示自变量形成的列向量. 定义1：满足约束条件的x(0)称为线性规划的可行解.是目标函数达到最大值的可行解称为最优解 * * 例如 定义3：基础可行解是指既是可行解又是基础解. P1和P4线性无关,从而它们对应是基, x1, x4是基变量 * * 线性规划问题的解有以下性质 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,求线性规划问题的最优解,只需从可行解集的极点(基础可行解)中去找. * * 经典线性规划-解法-图解法 约束条件 例 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为最优解. * * 经典线性规划-解法-消元法 在某些理想的情况下图解法是非常有效的,然而在大多数实际应用问题中图解法却完全不能用.因为在三维的情况下,用图解法来处理就非常困难;三维以上则肯定不可能的了.此时可用消元法. 以前面提到的规划问题为例.首先引入松驰变量,使约束条件不等式成为等式 * * 然而松驰变量没有相应的利润值,因此目标函数可写为 取x3,x4为基变量,则x1,x2为非基变量,即为自由未知量. 令x1=x2=0,得x3=10,x4=6. 此时s=0.显然这不是最优值.这说明x1,x2作为非基变量是不合适的. 若取x1,x4作为基变量,则x2,x3为非基变量.则 带入目标函数，得 这里x2的系数为正数,当x2增大s也增大,所以s没有最大值. * * 取x1,x2为基变量,则x3,x4为非基变量,则 这里非基变量x3,x4的系数为负,而x3,x4非负.因此当它们都为0时s最大,这时x1=4,x2=2为最优解. 带入目标函数，得 综上所述,有的变量作为基变量所得目标值不一定是最优值.只有在目标函数中所有非基变量的系数均为负数时,这时所得的解才是最优解.因此.将非基变量的系数及基变量的0系数称为检验数. * * 经典线性规划-