线性规划建模ppt课件.ppt

线性规划方法,线性规划（Linear Programming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）等等。,一、 应用模型举例,生产计划问题,max f= 5x1 +2x2,求最大利润,三种材料量的限制,生产量非负,运输问题,解：设A1,A2调运到三个粮站的大米分别为x1，x2， x3， x4， x5， x6吨。,题设量可总到下表：,结合存量限制和需量限制得数学模型：,m个产地A1,Am联合供应n个销地B1,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?,一般运输问题,总运价,产量限制,需量限制,运量非负,二、线性规划的数学模型,以上例子表明，线性规划问题具有以下特征： 每一个问题都用一组未知变量（x1，x2，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。 每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。 每一个问题的目标函数和约束条件都是线性的。,即线性规划的数学模型由 决策变量 Decision variables 目标函数 Objective function约束条件 Constraints构成。称为三个要素。,其特征是：1解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或 最小值；2解决问题的约束条件是一组多个决策变量的线性不等式或等式。,由此可以抽象出线性规划问题的数学模型。 一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2,n，目标函数的变量系数用cj表示, cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成,为了书写方便，上式也可写成：,采用矩阵形式可描述为： 在约束条件 AX(，)b X0 下，求未知向量 ，使得Z=CXmax(min) 其中,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用),小结：建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。,三、线性规划问题的基本理论,（一）线性规划的标准形式 在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即,1目标函数求最大值（或求最小值）2约束条件都为等式方程3变量xj非负4常数bi非负,max(或min)Z=c1x1+c2x2+cnxn,或写成下列形式：,或用矩阵形式,通常 x 记为： 称为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。,如果给定的LP问题是极小化问题,即,可化为极大化问题,约束条件不变,其最优解是一致的,但目标函数值的符号相反.,则:,结论:如果问题是求目标函数的最小值,则化为求 f 的最大值;,1.关于目标函数,2.关于约束条件,(1) 如果给定的LP有约束不等式,注意:新引入的变量在目标函数中的系数为0.,(2) 如果给定的LP有约束不等式,3.关于变量,在标准形式中,所有的变量都有非负限制,如果某些变量没有非负限制,则称这些变量为自由的.,两种处理办法:,【例1】将下列线性规划化为标准形,【解】（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以令,(2) 第一个约束条件是号，在左端加入松驰变量 (slack variable) x4，x40,化为等式；,(4)第三个约束条件是号且常数项为负数，因此在左边加入松驰变量x6，x60，同时两边乘以1。,（5）目标函数是最小值，为了化为求最大值，令Z=Z,得到max Z=Z，即当Z达到最小值时Z达到最大值，反之亦然。,(3)第二个约束条件是号，在 左端减去剩余变量(Surplus variable)x5，x50。也称松驰变量,综合起来得到下列标准型,当某个变量xj0时,令x/j=xj 。 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式。,(二)线性规划的解,若x*满足约束条件，则称之为LP问题的可行解。所有可行解的集合称为可行域。使目标函数达到最优值的可行解称为最优解。对给定的LP问题，若存在最优解，则称该LP问题有解，否则称LP问题无解。,线性规划的标准形,几个概念,（）用图解法求解线性规划问题,图解法的步骤：,1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；,2.绘制目标函数图形。先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；,3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。,一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动,x1,x2,O,10,20,30,40,10,20,30,40,(3,4),(15,10),最优解X=(15,10),最优值Z=85,例3,2,4,6,x1,x2,2,4,6,最优解X=(3,1)最优值Z=5,(3,1),min Z=x1+2x2,例4,(1,2),2,4,6,x1,x2,2,4,6,X（2）（3,1）,X（1）（1,3）,(5,5),min Z=5x1+5x2,例5,有无穷多个最优解即具有多重解,通解为,01,当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2),2,4,6,x1,x2,2,4,6,(1,2),无界解(无最优解),max Z=x1+2x2,例6,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解即无最优解,max Z=10 x1+4x2,例7,由以上例题可知，线性规划的解有4种形式：,1.有唯一最优解(例3、例4),2.有多重解(例5),3.有无界解(例6),4.无可行解(例7),1、2情形为有最优解3、4情形为无最优解,从上述几何直观还可看出：,线性规划问题的任意两个可行解联线上的点都是可行解；,线性规划问题的任意两个最优解联线上的点都是最优解；,线性规划问题的最优值若存在，则一定在某个顶点达到。,（）线性规划的有关概念及基本定理,1.线性规划常用的概念：凸集、凸组合、极点（凸点）、可行解、基本解、基本可行解、最优解、基本最优解、基、可行基、最优基。2.线性规划的三个基本定理。,凸集(Convex set)设K是n维空间的一个点集，对任意两点 时，则称K为凸集。,就是以X（1）、X（2）为端点的线段方程，点X的位置由的值确定，当=0时，X=X（2），当=1时X=X（1）,凸组合(Convex combination) 设 是Rn 中的点若存在 使得 成立， 则称X为 的凸组合。,极点(Extreme point) 设K是凸集， ，若X不能用K中两个不同的 点 的凸组合表示为,则称X是K的一个极点或顶点。,X是凸集K的极点是指X不可能是K中某一线段的内点，只能是K中某一线段的端点。,O,设线性规划的标准型 max Z=CX （1.1） AX=b （1.2） X 0 （1.3）式中A 是mn矩阵，mn并且r（A）=m，显然A中至少有一个mm子矩阵B，使得r（B）=m。,基 (basis)A中mm子矩阵B并且有r（B）=m，则称B是线性规划的一个基（或基矩阵basis matrix ）。当m=n时，基矩阵唯一，当mn时，基矩阵就可能有多个，但数目不超过,【例8】线性规划,求所有基矩阵。,【解】约束方程的系数矩阵为25矩阵,容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即,由线性代数知，基矩阵B必为非奇异矩阵并且|B|0。当矩阵B的行列式等于零（即|B|=0）时就不是基,当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basis vector)，其余列向量称为非基向量 （或自由向量）,基向量对应的变量称为基变量(basis variable)，非基向量对应的变量称为非基变量,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,可行解(feasible solution) 满足式（1.2）及（1.3）的解x=（x1,x2，xn)T 称为可行解 。,基本可行解(basis feasible solution) 若基本解是可行解则称为是基本可行解（也称基可行解）。,基本解(basis solution) 对某一确定的基B，令非基变量等于零，利用式（1.） 解出基变量，则这组解称为基的基本解。,最优解(optimal solution) 满足式 （1 .1）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解。,非可行解(Infeasible solution) 无界解 (unbound solution),显然，只要基本解中的基变量的解满足式（1.）的非负要求，那么这个基本解就是基本可行解。,在例5中，对来说，x1，x2是基变量，x3，x4，x5是非基变量，令x3=x4=x5=0，则式（1.）为,对B2来说，x1,x4,为基变量，令非基变量x2,x3,x5为零，由式（1.2）得到 ，x4=4，,因|B1|，由克莱姆法则知，x1、x2有唯一解x12/5,x2=1则 基本解为,由于 是基本解，从而它是基本可行解，在 中x10,因此不是可行解，也就不是基本可行解。,反之，可行解不一定是基本可行解例如 满足式（1.2）（1.3），但不是任何基矩阵的基本解。,基本解为,可行基 基可行解对应的基称为可行基；最优基基本最优解对应的基称为最优基；如上述B3就是最优基，最优基也是可行基。,当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段 的点为最优 解时，Q1点及Q2点是基本最优解,线段 的内点是最优解而不是基本最优解。,基本最优解 最优解是基本解称为基本最优解。例如，满足式（1.1）(1.3)是最优解,又是B3的基本解,因此它是基本最优解。,基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：,基本最优解,基本可行解,可行解,最 优 解,基本解,例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。,【定理1】 若线性规划可行解K非空,则K是凸集。,【定理2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解。,【定理3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的坐标向量。,定理2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。,线性规划的基本定理,定理3描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一极点上达到，若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点 。,若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。,定理2及3还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行解中去寻求。下面将介绍一种有效地寻找最优解的方法。,（）单纯形法求解线性规划问题,单纯形计算方法(Simplex Method)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。,当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。,【例9】用单纯形法求下列线性规划的最优解,【解】化为标准型，加入松驰变量x3、x4则标准型为,系数矩阵A及可行基B1,r(B1)=2，B1是一个初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0,0,40,30)T,以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数 Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作j , j=1,2,n。,本例中1=3,2=4,3=0,4=0。参看表1.4（a）。,最优解判断标准 当所有检验数j0（j=1，n）时，基本可行解为最优解。,当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。,检验数 目标函数用非基变量表达时的变量系数,进基列,出基行,bi /ai2，ai20,i,表1,基变量,1,10,0,0,1/3,0,1/3,10,5/3,1,-1/3,40,5/3,0,-4/3,30,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,将3化为1,乘以1/3后得到,30,18,最优解X=(18，4，0，0)T，最优值Z=70,O,20,30,10,40,(3,4),X(3)=(18,4),最优解X=(18,4),最优值Z=70,X(1)=(0,0),20,10,x2,x1,30,X(2)=(0,10),单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1）。,计算步骤：,1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；,2.判断： （a）若j（j，n）得到最优解； （b）某个k0且aik（i=1，2,m）则线性规划具有无界解(见例1.18)。 （c）若存在k0且aik (i=1,m)不全非正，则进行换基；,第个比值最小 ，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素；,(c）求新的基可行解：用初等行变换方法将aLk 化为,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。,（b）选出基变量 ，求最小比值：,3.换基：（a）选进基变量设k=max j | j 0,xk为进基变量,【例10】 用单纯形法求解,【解】将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，单纯法计算结果如表 2所示 。,表2,1/3,1,5,0,1,20,3,0,17,1,3,75,1/3,0,9,0,2,M,20,25,60,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解X=(25，35/3，0，0，0)T，最优值Z=145/3,【例11】用单纯形法求解,【解】 这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：j0(j=1，n)时得到最优解。容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x4=6+x1x2，并代入目标函数消去x4得,表中j0,j=1,2,5所以最优解为X=(0,5,0,1,11,)最优值 Z=2x12x2x4=251=11极小值问题,注意判断标准,选进基变量时,应选j0的变量xj进基。,表3,【例12】求解线性规划,【解】化为标准型,初始单纯形表为,2=10, x2进基，而a120，a220，没有比值，从而线性规划的最优解无界。由模型可以看出，当固定x1使x2+且满足约束条件，还可以用图解法看出具有无界解。,【例13】求解线性规划,【解】:化为标准型后用单纯形法计算如下表所示,表 (3)中j全部非正,则最优解为:,表 (3)表明,非基变量x3的检验数3=0, x3若增加,目标函数值不变, 即当x3进基时Z仍 等于20。使x3进基 x5出基继续迭代 ,得到表(4)的另一基本最优解,X(1),X(2)是线性规划的两个最优解，它的凸组合,仍是最优解，从而原线性规划有多重最优解。,唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解 。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断: 某个k0且aik（i=1，2,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。,（三） 对偶问题,对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。 前者是由矩阵，右端向量和价值向量 定义的，称之为原问题； 后者也是由相同的数据集合，和构成的，称之为原问题的对偶问题。 一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。,（1）对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。,用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产4/3 吨，乙产品生产8吨，可以使总利润达到最大，为 元。,假设计划期内甲乙两种产品各生产x1 x2 吨，,例1 现在从另一个角度来考虑该工厂的生产问题: 假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。 设 y1 y2 y3 分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润,目标函数：所获租金总额最小,为什么要最小化？,由此可得两个对称的线性规划：,矩阵形式：,（2）对偶定义,1、对称形式（典则形式）的对偶定义,一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。 (4)两个规划模型中的变量皆非负。,标准形式的对偶定义,推导过程：,若原问题是极小化问题，则对偶问题是极大化问题；若原问题是极大化问题，则对偶问题是极小化问题 在原问题和对偶问题中，约束右端向量与目标函数的系数向量恰好互换 对于极小化问题的“”型约束(极大化问题的“”型约束)，相应的对偶变量有非负限制；对于极小化问题的“”型约束(极大化问题的“”型约束)，相应的对偶变量有非正限制；对于原问题的“=”型约束，相应的对偶变量无正负限制 对于极小化问题具有非负限制的变量(极大化问题具有非正限制的变量),在其对偶问题中，相应的约束为“”型约束；对于极小化问题具有非正限制的变量(极大化问题具有非负限制的变量),在其对偶问题中，相应的约束为“”型约束；对于原问题中无正负限制的变量，在其对偶问题中，相应的约束为“=”型约束,对偶规则,【例15】写出下面线性规划的对偶规划模型,练习：写出对偶规划。,（2）对偶理论,对称性：对偶问题的对偶是原问题弱对偶性：若x和y分别是(LP)和(DP)的可行解，则cxby.可行解为最优的充分条件：设x和y分别是(LP)和(DP)的可行解，若cx=by，则x和y分别是(LP)和(DP)的最优解.无界性：若(LP)和(DP)之一为无界解，则其对偶问题无可行解.,对偶定理：若(LP)和(DP)均有可行解，则它们都有最优解，且最优值相同.最优基本可行解之间的关系：若(LP)存在一个对应基B的最优基本可行解，则单纯形乘子 是(DP)的一个最优解.互补松弛性：设x和y分别是(LP)和(DP)的可行解，则x和y分别是(LP)和(DP)的最优解的充要条件为y(Ax-b)=0，且 (c-yA)x=0.,（3） 对偶单纯形法,由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。,对偶单纯形法是求解线性规划的另一的基本方法。由于它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。 不能简单理解为是求解对偶问题的单纯形法。,原始单纯形法从一个基本可行解迭代到下一个基本可行解时，总是保持解的可行性不变，变化的只是检验数 例如对于极大化问题而言，检验向量从部分分量不满足 逐步过渡到 ， 一旦达到 ，也就达到了最优解。由于 ， 是对偶问题的可行解。可以这样理解原始单纯形法的迭代过程：从基本可行解向最优解的迭代过程，是在始终保持原问题可行性的条件下，其对偶解由不可行向可行转化。一旦对偶解也成为可行解时，原问题的可行解即成为最优解。也就是说，当原问题解保持可行性条件下，其最优性条件与对偶解可行这个条件是一致的。,这为我们提供了另一条求解思路：在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行向可行性转化，一旦原问题的解也满足可行性条件，也就达到了最优值。这就是对偶单纯形方法的思路。对偶单纯形法并不需要把原问题转化为对偶问题，而是利用原问题与对偶问题的数据相同，只是所处的位置不同这一特点，直接在反映原问题的单纯形表上进行运算。对偶单纯形法不要求向量 , 处理带剩余变量的一些问题很方便。,（2）确定换出变量 根据 ，确定基变量 xl 作为换出变量。检验 xl 所在行各元素若所有alj 0, 则无可行解，停止计算。否则转入()，,（3）确定换入变量按最小比值原则，若确定非基变量 xk 为换入变量。（4）以alk 为主元进行旋转变换，得新的单纯形表，重复 （2）-（4），直到求得最优解。,对偶单纯形法的计算步骤如下（对于极大化目标函数问题）：（1）根据原始线性规划，列出初始单纯形表，检查b列数字和检验行元素，若b列数字全部非负，检验数全部非负，则已经求得最优解，停止计算。若b列中至少有一个负分量，检验数全部非正，则转入（2）,【例16】用对偶单纯形法求解解：先化为标准型 对偶单纯形允许约束方程右端为负，因此可将方程2，3两端同乘-1，可得含单位矩阵的标准型：,据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：,-5/4,-7/4,0,0,0,-16,-W,-1/4,1/4,0,1,0,2,x2,-2,-1/4,-3/4,0,0,1,4,x1,-3,5/4,3/4,1,0,0,4,x3,0,-2/3,0,0,0,-7/3,-20/3,-W,-1/3,0,0,1,1/3,10/3,x2,-2,1/3,1,0,0,-4/3,-16/3,x4,0,1,0,1,0,1,8,x3,0,0,0,0,-2,-3,0,-W,1,0,0,-3,-1,-10,x5,0,0,1,0,1,-1,-2,x4,0,0,0,1,3,2,18,x3,0,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-2,-3,C,可得最优解,是,是,是,是,否,否,否,否,所有,所有,得到最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以为中心元素进行迭代,以为中心元素进行迭代,停,没有最优解,没有最优解,单纯形法,对偶单纯形法,对偶单纯形法的优点和应用的前提条件,对偶单纯形法的优点是原问题的初始解不要求是可行解，可以从非可行解开始迭代，从而省去了引入人工变量的麻烦。当然对偶单纯形法的应用也是有前提条件的，这一前提条件就是对偶问题的解是基可行解。,五、线性规划的灵敏度分析,1.灵敏度分析的内涵,一个标准形式的线性规划问题可由约束矩阵，右端项向量b，和价值向量完全确定，假如一个线性规划问题对于给定的数据集合，b，有最优解，则最优解。最优目标函数值，其中为最优基。 但是线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。,灵敏度分析主要讨论如下二类问题：线性规划的数据集合在什么范围内波动将不影响最优解或最优基？若最优解发生变化，应如何用最简单的方法找到新的最优解。为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形式，其中B为线性规划问题的最优基：,1. 价值向量C的改变当价值向量由时，最优单纯形表发生变化的只是检验行的有关数据，其中基变量检验数保持为零。非基变量检验数应修改为：,目标函数值应为 。只要变化以后的非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于基变量价值系数的改变量以下分别就价值系数对应非基变量或基变量两种情况加以讨论：,若是非基变量的价值系数，为该价值系数的改变量。那么在最优表中只有 的检验数 发生变化。由 只要 即就可以保持现行最优解仍为最优，由此可以确定价值系数的可变化范围。 若超出稳定范围，那么的检验数 ，当前解已不是最优解。此时必须以修改后的单纯形表出发，重新进行单纯形迭代，直至求出新的最优解。非基变量价值系数的变化，可能使最优基改变，从而导致最优解和最优值的改变。,若是某基变量的价值系数，为价值系数的改变量。由于为基变量，所以在最优表中所有的非基变量检验数均发生了变化，由 只要非基变量检验数： 或即可最优解仍然保持为最优，其中 为原最优表中非基变量检验数，为最优表系数矩阵中基变量所在行中所有非基变量对应的系数。由上式可得到一个联列不等式组，求解该不等式组就可得到价值系数的可变动范围。基变量价值系数的变化，可能使最优基改变，从而导致最优解的改变。而最优值则一定改变。,【例17】 、某工厂用甲乙两种原料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：,问应该怎样组织生产，才能使总利润最大，若产品或的利润产生波动，波动范围多大时，原最优解保持不变？解：设生产，四种产品各万件，则此问题的线性规划模型为：,标准化，引入松弛变量x5,x6， 利用单纯形表求解：,-4 -2/3 0 0 -13/3 -10/3,88,Z,2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3,21,x4x3,1950,0 2 0 2 -3 -10,84,Z,26,1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/2,13/2,x1x3,950,9 8 0 13/2 0 -25,75,Z,1-,3 2 0 3/2 1 -5 0 0 1 1/4 0 1/2,33/2,x5x3,050,9 8 50 19 0 0,0,Z,9/53/2,3 2 10 4 1 0 0 0 2 1/2 0 1,183,x5x6,00,x1 x2 x3 x4 x5 x6,b,XB,CB,9 8 50 19 0 0,C,即最优生产方案是生产产品1万件，产品2万件，不生产,两种产品。可得最大利润为88万元。,最优表：,(1)若产品的利润，有改变量。因为为非基变量，由推得或（万元）时,原最优解不变，最优利润值（万元）也不变。,()若产品的利润 ，有改变量。因为为基变量，由推得,即当或时原最优解不变，最优利润值（万元）,2.右端项向量b的改变当右端项向量b由时，改变的只是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。右端项向量b的波动会使最优解和最优目标函数值发生变化，但原最优解的检验向量仍能保持非正。为了使B可行，只要或若，因为检验向量仍保持非正，因此可用对偶单纯形法再次进行迭代，直到求得新最优解。右端列向量b变化时，最优解和最优值一定改变。因此我们主要讨论右端列向量b变化时，最优基是否改变,【例8】、在例17中，若想增加甲种原料，问增加多少时原最优基不变？,解：设甲种原料的改变量为 ,则由 即,由此可以推得， 即当 时，原最优基不变。此时最优解 或,最优目标函数值 (万元),3.约束矩阵A的改变 约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形：增加或减少一个变量，增加或减少一个约束条件。以下讨论假设原线性规划问题有一个最优解其中为最优基，且约束矩阵被划分为,增加或减少一个变量（1）增加一个新变量假设在获得原线性规划的最优解之后，又发现了一个新变量，其对应的价值系数为，在新的约束矩阵中对应的系数列向量为，于是可得如下新的线性规划问题：,设，则 为新线性规划问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果 ，则含的当前解 是新问题的最优解。否则以为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。,（2）减少一个变量如果必须把某个变量从决策变量中去掉，那么原最优解在新的线性规划中一定发生改变。我们讨论的目标是如何用最小的工作量去寻求新的最优解。如果原最优解中的，则只需将从原最优解中剔除即可保持最优。如果原最优解中的（此时必为基变量），则必须重新计算新的解。为此可建立一个辅助线性规划：,由于约束方程组没有改变，因此原最优解在辅助线性规划中可以作为初始基本可行解用于单纯形算法。如果辅助线性规划最优解的目标函数值为零，则用此最优解剔除以后，可得新的线性规划问题的一个初始基本可行解，经有限次迭代，即可求出新问题的最优解。否则从原来问题中去除 而得到的新的线性规划必定是不可行的。,增加或减少一个约束（1） 增加一个约束如果在原来的线性规划的基础上再加入一个新的约束条件，不妨假设此附加的约束条件为不等式形式，即其中是n维行向量，为右端项系数，于是新的线性规划变成,为了求解有附加约束条件的新问题，可以在附加不等式约束左端加上一个松弛变量 ,并考虑如下线性规划问题：,其中, 是中对应于基变量和非基变量的子向量，由此可以在原来最优基的基础上定义一个新的基。,易证 是非奇异矩阵，其逆阵,按新基可以定义有附加约束条件新问题的一个基本解,该基本解不一定是可行解，因为不一定满足非负条件，但是由于是原线性规划问题的最优解，因此不难证明，即使对有附加约束条件的线性规划是不可行的，但都能保证该线性规划的对偶规划是可行的。,因为对应于的非基变量检验数,结论：如果由新基定义的基本解是非负的。那么该基本解就是有附加约束条件的新线性规划问题的最优解。不满足非负条件。那么至少有一个基变量小于零，此时可用对偶单纯形法求出新问题的最优解。,减少一个约束在原来线性规划的基础上，去掉一个约束条件的情况比较复杂，因为单纯形法是通过旋转运算实现基变换的，线性规划的旋转运算使每行元素成为其它各行元素的线性组合。因此如果要减少一个约束条件，那么原来的运算结果很难加以利用。一般情况下将不得不重头求解减少了一个约束条件的新的线性规划问题，好在减少一个约束条件可以大大地简化计算步骤。,【例9】、在例17中，若考虑生产另一种产品，已知每生产1万件产品要消耗甲原料3公斤，乙原料1公斤，那么，产品的每万件利润为多少时才有利于该种产品投产？若假设该工厂又增加了用电量不超过8千瓦的限制，已知生产，四种产品各1万件分别耗电4，3，5，2千瓦，问此约束是否改变了原最优决策方案？解：（1）设生产产品x7万件，1万件E产品的利润为c7万元，则数学模型变为：,已知 是原问题的最优解，若令，则是现问题的一个可行解，但未必是最优解。 若要产品投产，即 ，则其检验数 ,即 得每万件E产品利润万元时，有利于生产E产品。,由此可的新的最优解，即最优生产方案为生产万件产品和件产品，总利润为万元。,例如当 万元时，代入原线性规划的最优单纯形表，得 增加新变量 的单纯形表， 其中,（） 假设工厂又增加了用电量不超过9千瓦，且生产，四种产品各1万件分别耗电4，3，5，2千瓦用电量限制，则相当于原问题约束方程组增加了一个约束方程 增加松弛变量，得利用原线性规划最优单纯形表，增加一行和一列得一张新表，施行初等变换，使基变量对应的系数列向量为单位矩阵，若变换结果使基变量取了负值，则对应的基不是可行基，要用对偶单纯形法进行了基变换，并求得最优解，否则变换结果已为最优解。,-2,0,1,0,0,-2,-5,2,-1/3,4/3,0,0,1,-1,-4/3,4/3,4/3,-10/3,0,1,0,4,-16/3,2/3,X4x3x5,19500,1,0,-1/2,0,0,2,5/2,-1,0,4/3,-1/6,0,1,-1/3,-1/2,1,0,-10/3,2/3,1,0,4/3,2,2,X4x3x7,19500,1,0,0,2,5,3,4,8,x7,0,0,4/3,-1/6,0,1,-1/3,-1/2,1,x3,50,0,-10/3,2/3,1,0,4/3,2,2,X4,19,-26/3,-10/3,0,0,0,-18,-77/3,z,0,-10/3,-13/3,0,0,-2/3,-4,88,z,0,-10/3,-13/3,0,0,-2/3,-4,88,z,x7,x6,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,19,50,8,9,c,可见增加用电约束以后，最优生产方案是 万件产品， 万件产品，总利润为 万元，比原问题的最大利润减少 。,谢谢大家！,下次再见！,