《线性规划－程－2次》PPT课件.ppt

第一章线性规划,程斌Email:qccbxn,本章主要内容,线性规划问题及其建模线性规划问题几何求解与解情况分析线性规划标准型线性规划问题求解单纯形法灵敏度分析运输问题计算机求解,一、线性规划问题的提出,在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。线性规划是由丹捷格（G.B.Dantzig）在1947提出的，并提出了求解线性规划的单纯形法，成为运筹学的标志性成就，被誉为线性规划之父。1939年前苏联学者康托洛维奇在解决工业生产组织和规划问题时，已提出类似线性规划的模型，并给出“解乘数法”的求解方法。1960年再次发表最佳资源利用的经济计算,获经济学诺贝尔奖。,例题1：生产计划问题,引例某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？,解题步骤：,1、确定决策变量：设生产A产品X1kg,B产品X2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2360设备约束4X1+5X2200原材料约束3X1+10X2300非负性约束X10X20综上所述，该问题的数学模型表示为：,问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,例题2：车床加工安排问题,解题步骤：,1、确定决策变量：在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x62、确定目标函数：minz=13x1+9x2+10 x3+11x4+12x5+8x63、确定约束条件：工件1、2、3约束X1+X4=400甲车床台时数约束0.4X1+1.1X2+x3800乙车床台时数约束0.5X1+1.2X2+1.3x3900非负性约束Xi0i=1.6综上所述，该问题的数学模型表示为：,目标函数：Max(Min)z=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bmx1，x2，xn0,线性规划的一般形式,二.线性规划问题的图解法,若有线性规划问题：注：此方法只使用于两个决策变量的情况,4x1=16,4x2=12,x1+2x2=8,Q1,Q2,Q3,Q4,可行域,可行域与等值线,4x1=16,4x2=12,x1+2x2=8,Q1,Q2(4,2),Q3,Q4,可行域,可行域：阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），此区域是线性规划问题的解的集合，称为可行域。,等值线,x1,x2,最优解个数情况1.无穷多最优解,上例中求解得到问题最优解是唯一的，但对一般线性规划问题，求解结果可能出现以下几种情况：1、无穷多最优解（多重最优解）若将上例中的目标函数变为maxz=2x1+4x2，目标函数中以参数z的这族等值线与约束条件x1+2x28的边界线平行。当z值由小变大时，将与线段Q2Q3重合。线段Q2Q3上任意一点都使z取得相同的最大值，故这个线性规划问题有无穷多最优解（多重最优解）。,（4,2）,（4,0）,（0,0）,（2,3）,用图解法解下面的例子Maxz=2X1+4X2X1+2X28(1)4X116（2）4X212（3）X1，X20（4）,无穷多最优解,注意：多重解产生的原因，是因为目标函数线与第（1）条约束条件边界线的斜率相等。,(1),(2),(3),(8,0),(0,4),2、无界解Maxz=x1+x2-2x1+x24（1）x1x22（2）x1,x20（3）,（2，0）,（0，4）,（0，0）,无界解（不等于无可行解）在这里需要注意的是，可行域无界不等于问题无界，这要看目标函数的情况。如把该问题中目标函数x1的系数由原来的1改为3/2时，该问题有最优解Z(0,4)4。,3、无可行解Maxz=2x1+3x2x1+2x28(1)4x116(2)4x212(3)-2x1+x24(4)x1,x20(5),（-2，0）,（0，4）,（4，0）,（4，2）,无可行解（约束条件无共同区域）,图解法总结,从图解法中直观地见到，当线性规划问题的可行域非空时，它是有界区域或无界凸多边形区域。若线性规划问题存在唯一最优解，它一定在有界可行域的某个顶点得到；若能在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，此时就有无穷多最优解；可行域为空时则无最优解,可行域的一般情况,线性规划的可行域是凸集线性规划的最优解在极点上,凸集,凸集,不是凸集,可行域和最优解的几种情况,1、可行域封闭唯一最优解,2、可行域封闭多个最优解,3、可行域开放唯一最优解,4、可行域开放多个最优解,5、可行域开放目标函数无界,6、无可行解,多个（2）决策变量时可行域的情况,三个决策变量，最优解在棱角处取到，用图解法无法求解。三个以上决策变量时可行域就为超平面，最优解在相应的棱角处取到。用图解法无法求解。,三.线性规划问题的标准形式,在标准形式中规定各约束条件的右端项bi0，若否则在等式两端同乘以“-1”即可。,线性规划问题的标准形式矩阵表示,实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。,标准型的特点,标准型的特点：1、目标函数求极大2、约束方程全为等式3、变量全为非负4、约束条件右端常数项bi0（I=1,2,m）如何变换为标准型的问题。,化标准形式的一般步骤,化标准形式的一般步骤1、目标函数若为极小化“极大化”2、约束条件的右端项bi0“bi0”3、约束条件为不等式或“=”4、取值无约束（自由）变量“非负变量”5、取值非正变量“非负变量”,B.约束条件标准化,(2)约束条件是类型,如何将一般问题化为标准型：,A.目标函数标准化,左边加非负松弛变量,(1)右端常数bi0,等式两边乘以（-1）,(4)变量符号无约束,(5)变量xi0,引入新变量,(3)约束条件是类型,左边减非负剩余变量,例1将下述规划模型化为标准型:,解：,红色字部分是不符合标准形部分,约束条件第一行中需在左边加非负松弛变量x4,约束条件第二行中需在左边减非负剩余变量x5,约束条件第三行右端常数b30等式两边乘-1,课堂练习1将下列问题化成标准型:,课堂练习2,课堂练习3,化标准形目的是寻求统一的求解办法，这些方法中以单纯形法最为著名有效，还有大M法其中单纯形法几何上的基本原理为最优解在相应的棱角顶点处取到,单纯形法的计算流程图：,初始顶点,新的顶点,最优否？,STOP,Y,N,四.单纯形法,1947年丹捷格提出的单纯形法为求解线性规划问题提供了方便、有效的通用算法。,单纯形法的基本思想,顶点的逐步转移：即从可行域的一个初始顶点（基可行解）开始，转移到另一个顶点（另一个基可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。其中当为m个约束条件n个决策变量时顶点为含n-m个0的n维点。,需要解决的问题：,初始顶点如何找到？为了使目标函数逐步变优，怎么转移顶点？目标函数何时达到最优，判断标准是什么？,单纯形法的计算及示例,化为标准形式,第一步：先把问题标准化。,Cj,x1,x2,x3,x4,XB,b,CB,11101201,2300,34,x3x4,00,cj-zj,2,3,0,0,3/1=3,4/2=2,x3x2,cj-zj,03,x1x2,cj-zj,00-1-1,23,i,1,1/2,0,1/2,2,0,1/2,1,-1/2,1,1/2,0,0,-3/2,1/(1/2)=2,2/(1/2)=4,1,0,2,-1,2,0,1,-1,1,1,列单纯形表,上单纯形表解读,初始顶点为（x1,x2,x3,x4）=(0,0,3,4)，（1,2,3,4）=(2,3,0,0),全为正数,需转移顶点；2最大，选择新加入x2，x2所在列的系数为(1,2),对应b=(3,4),在(3/1,4/2)中4/2小一些，故选第二行为基础行(1/2,1,0,)，故转移到新顶点（x1,x2,x3,x4）=(0,2,1,0)，得（1,2,3,4）=(1/2,0,0,3/2)，正负数都有,需转移顶点；1最大,选择新加入x1,x2所在列的系数为(1/2,1/2),对应b=(1,2),在(1/(1/2),2/(1/2)中1/(1/2)小一些，故选第一行为基础行（1，0，2，1）,故转移到新顶点(x1,x2,x3,x4)=(2,1,0,0),得（1,2,3,4）=(0,0,1,1),都为非负数,故已达最优.,单纯形法计算过程总结：,（1）化标准形，列初始单纯形表，进行最优性判断，不为最优则找初始基变量.方法为在系数表中找m行m列(m为约束条件数)的数表，其中只有m个不同行不同列元素为1，其余为0;若找得到则数表中元素1所对应列的变量就为初始基变量；若找不到就加入新的变量，构造上述数表，而后用大M法,两阶段法。初始检验数为标准形中目标函数里的系数。,（2）计算新检验数j：j为入基变量xi的系数aii变其上下为0时，对行进行倍行加所得的结果。（3）最优性判断：当所有检验数均有j0时，则出现最优解。否则找新的入、出基变量，迭代求解。,最优性判断，j情况及解情况判断,(1)对所有j，当j0，不存在非基变量检验数为0，则只有唯一最优解；(2)对所有j，当j0，但存在某个非基变量检验数k=0，则有无穷多解；若此时最优解为X0，将Xk作为新的入基变量，可求得新解X1，应有最优值z0=z1，则X0、X1连线上所有的点均为最优解，因此该线性规划模型具有无穷多解；(3)若存在某个j0，但对应aij0，则该线性规划模型具有无界解。,（4）迭代中的相关量：a.入基变量：新选入的基变量xi为旧的j中最大的那一列所对应变量。b.出基变量xj为旧的基变量中最小的i所对应变量。c.主元素：旧表中入基变量所在列，与出基变量所在行对应的系数表中元素，在新表中需先将其变为1，然后用其所在行，倍行加其余行，使得这一列元素其余元素变为0，包括计算新检验数j。,利用单纯形表计算课堂练习2,x1=20,x2=24,化标准形为：,五.大M法,它的系数矩阵是：,由于系数矩阵中存在单位阵，很容易找到初始基变量。单位阵为上矩阵的后4行4列,化为标准型：,该问题的系数矩阵为：,在系数矩阵中人为添加两列单位列向量,添加两变量即可,目标函数变为：,引进人工变量，及M非常大正系数,(1),(2),这种处理方法称为大M法，以下则可完全按单纯形法求解。,Cj,-30100-M-M,CB,XB,b,x1,x2,x3,x4,x5,x6,x7,x4x6x7,0-M-M,419,1111000-21-10-1100310001,cj-zj,-2M-3,4M,1,0,0,0,-M,i,4/1=4,1/1=1,9/3=3,x4x2x7,00-M,-21-10-110,3,0,1,3,2,1,1,-1,0,6,6,0,4,0,3,1,-3,cj-zj,6M-3,0,4M+1,0,3M,-4M,0,3/3=1,-,6/6=1,这里为什么不选择x4作为换出变量而选择x7？,x4x2x1,001,1,2/3,0,1,-1/2,1,0,3,1,0,1/2,-1/2,1/6,0,0,0,1/3,1/3,0,0,0,0,-1/2,-1/2,cj-zj,0,0,0,3,-M-3/2,2/3,-M+1/2,-,9,6,Cj,-30100-M-M,CB,XB,b,x1,x2,x3,x4,x5,x6,x7,x4x2x3,001,cj-zj,-3/2,0,0,-M+3/4,1,3/2,0,1,5/2,0,1,0,1/4,-1/2,1/2,0,0,0,-3/4,0,0,0,-1/2,-1/2,3/4,3/2,-1/4,1/4,1/4,-3/4,-M-1/4,(1)当所有的检验数,并且单纯形表基变量没有取值非零的人工变量时，表明已经得到原问题的最优解,大M法判别准则,(2)当所有的检验数,并且单纯形表基变量有取值非零的人工变量时，表明已经得到原问题无可行解,(3)若所解的大M问题有无界解(即有可行解但无最优解),则当人工变量全为零时，原问题无界解；当人工变量不全为零，表明原问题无可行解；,minz=2x1+3x2maxz=-2x1-3x2+0 x3x1+x23标准化s.tx1+x2-x3=3x1+2x2=4x1+2x2=4x10,x20 xj0,(j=1,2,3,4),maxz=-2x1-3x2+0 x3-Mx4-Mx5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5),引进人工变量，及M非常大正系数，模型转变为,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,-2-30-M-M,34,x4x5,-M-M,cj-zj,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,-1/2+M/20-M03/2-M/2,-M-3,24,10-22-1011-11,x1x2,21,cj-zj,00-1-1-M-1-M,-2-3,i,x5,0,原问题化为标准形式后的约束条件,添加了人工变量以后的约束条件,六两阶段法,(1)第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解，若zmin=0，表明原问题有可行解，则可进入第二阶段，求原模型最优解。,0,2/3,Cj,00000-1-1,CB,XB,b,x1,x2,x3,x4,x5,x6,x7,x4x6x7,0-1-1,419,1111000-21-10-1100310001,cj-zj,-2,4,0,0,0,0,-1,i,4/1=4,1/1=1,9/3=3,x4x2x7,00-1,-21-10-110,3,0,1,3,2,1,1,-1,0,6,6,0,4,0,3,1,-3,cj-zj,6,0,4,0,3,-4,0,3/3=1,-,6/6=1,x4x2x1,000,1,0,1,-1/2,1,0,3,1,0,1/2,-1/2,1/6,0,0,0,1/3,1/3,0,0,0,0,-1/2,-1/2,cj-zj,0,0,0,-1,0,-1,说明(1)如果第一阶段求解结果的目标函数最优解为0，表明原线性规划问题存在可行解(2)若第一阶段求解结果目标函数最优解不为0，也就是最优解的基变量中含有人工变量，表明原来的线性规划问题无可行解。,于是根据单纯形表可以看出原问题有可行解，原问题的一个可行解为,3,第二阶段:将第一阶段最终单纯形表中的人工变量去掉，原问题的目标函数引入最终单纯形表，继续迭代,Cj,-30100,CB,XB,b,x1,x2,x3,x4,x5,x4x2x1,031,0001-1/2011/300102/301/2,cj-zj,0,0,3/2,i,-,9,2/3,x4x2x3,001,0,0,5/2,0,0,1,-1/2,0,1,0,3/4,cj-zj,0,0,3/2,0,0,0,-1/4,-3/2,00-3,0,3/2,-1/2,1,-3/4,minz=2x1+3x2maxz=-2x1-3x2+0 x3s.tx1+x23标准化s.tx1+x2-x3=3x1+2x2=4x1+2x2=4x10,x20 xj0,(j=1,2,3,4),maxz=-x4-x5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5),第一阶段：构造判断是否存在可行解的模型,用单纯形法求解，若zmin=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,000-1-1,34,x4x5,-1-1,cj-zj,2,3,-1,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,1/20-10-3/2,-10,24,10-22-1011-11,x1x2,21,cj-zj,000-1-1,00,i,x5,0,第二阶段：将原目标函数引入最终单纯形表，继续迭代maxz=-2x1-3x2+0 x3,Cj,x1,x2,x3,XB,b,CB,10-2011,-2-30,21,x1x2,-2-3,cj-zj,0,-3,-4,当所有时，又对某个非基变量有且可以找到，则该线性规划问题有无穷多最优解。,六.关于解的判别,例7.,标准形式为,用单纯形法计算，得到最终单纯形表为：,从表中可以得到最优解：,它对应的目标函数值为：,在上表中，非基变量的检验数为0，如果将换入基变量，得：,从表中可以得到新的最优解：,因此和连线上所有的点都是最优解，该问题有无穷多最优解。,例8.求解线性规划问题,解：用图解法求解时知道该问题有无界解，,它的标准形为：,用单纯形表求解过程如下：,表中，但列数字为零，因此的取值可无限增大，所以目标函数值也可随之无限增大，说明问题的解无界。,例9.求解线性规划问题,将其化为标准形：,该问题单纯形法求解如下：,当所有时，人工变量仍然留在基变量中，而且不为零，故问题无可行解。,七单纯形法小结,对给定的线性规划问题应首先化为标准形式；选取或构造一个单位矩阵作为基；求出初始可行解并列出初始单纯形表；计算检验数，判断是否最优解；寻找换入及换出变量，构造新的单纯形表；求出最优解。,八灵敏性分析,灵敏性分析：是指目标函数的系数（价值系数Ci）改变，资源（bi）约束改变,增减约束条件,增加约束变量，系数矩阵A中元素aij发生变化时，对整个问题有什么影响。下面只通过例题说明。,最优单纯形表(非基变量),从表中看到3=c3+c3-(c2a13+c1a23)可得到c39/5时，原最优解不变。,例1.价值系数c发生变化：Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x50,例2:下表为最优单纯形表,考虑基变量系数c2发生变化,从表中看到j=cj-(c1a1j+c5a5j+(c2+c2)a2j)j=3,4可得到-3c21时，原最优解不变。,最优单纯形表,从上最优表中得知：原问题等价于MinZ(9/5)x3+(8/5)x4+(1/5)x5对应的第一，二种资源的每变化一单位利润变化8/5，1/5单位，所以此时第一，二种资源对总利润的贡献分别为8/5，1/5,资源对目标的贡献：Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x50,九运输问题,运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量,运输问题网络图,供应地,运价,需求地,供应量,需求量,总供应量60吨,总需求量60吨,供求平衡的运输问题,运输问题线性规划模型,供应地约束,需求地约束,由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3416个，非基变量为1266个。,运输问题的表格表示,运输问题基的表示,m个供应地、n个需求地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；（合理的调运方案中应只在m+n-1个方格中添数）同行同列的基变量不能形成回路；运输表的每一行和每一列中至少有一个基变量。,基在运输表中的表示,运输表中同行同列的变量组成回路,初始基础可行解（一）最小元素法（1）,初始基础可行解最小元素法（2）,初始基础可行解最小元素法（3）,初始基础可行解最小元素法（4）,初始基础可行解最小元素法（5）,初始基础可行解最小元素法（6）,有时只用最小元素法就可得到最优解，本例就是，有的时候不行，就得继续用闭回路法找最优解。Minz=61+313+82+413+212+519=142,找初始基础可行解（二）西北角法,8,13,13,14,6,6,-5,优化非基变量xij的检验数zij-cij闭回路法(1),z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,-5,z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,非基变量xij的检验数zij-cij闭回路法(2),-5,z14-c14=c11-c21+c23c34+c34-c14=6-8+2-10+6-3=-7,-7,-5,非基变量xij的检验数zij-cij闭回路法(3),-5,z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-9,-9,-5,-7,非基变量xij的检验数zij-cij闭回路法(4),-5,z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,非基变量xij的检验数zij-cij闭回路法(5),-5,z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,非基变量xij的检验数zij-cij闭回路法(6),选择进基变量,确定离基变量,x31进基,minx21,x33=min8,6=6,x33离基,+3,-5,-5,-7,-9,11,调整运量,重新计算检验数,确定进基、离基变量,x14进基,minx11,x34=min14,13=13,x34离基,-11,-5,-5,+4,+2,-8,调整运量,重新计算检验数,所有zij-cij”（或“=”（或“=98;2*x1+x2=345.5x1=982x1+x2=600endgin2,lindo程序:,lingo程序:,50桶牛奶,时间:480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/千克，是否应改变生产计划？,每天：,例1加工奶制品的生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),建立模型,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,DORANGE(SENSITIVITY)ANALYSIS?,No,20桶牛奶生产A1,30桶生产A2，利润3360元.,模型求解,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000,原料无剩余,时间无剩余,加工能力剩余40,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUE