《【安全课件】第三章规划论课件.pptx》由会员分享，可在线阅读，更多相关《【安全课件】第三章规划论课件.pptx（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.什么是规划论什么是规划论在生产生活以及军事领域经常会遇到资源在生产生活以及军事领域经常会遇到资源分配问题，不同的分配方案产生的效益是不一分配问题，不同的分配方案产生的效益是不一样的，所以，为了追求最佳效益，必须在不同样的，所以，为了追求最佳效益，必须在不同的分配方案中选择最佳的资源分配方案。规划的分配方案中选择最佳的资源分配方案。规划论就是研究针对不同需求对有限资源进行分配论就是研究针对不同需求对有限资源进行分配的一个运筹学分支。的一个运筹学分支。第三章第三章规划论规划论其中，线性规划是形成最早也是最成熟的一个分支。到其中，线性规划是形成最早也是最成熟的一个分支。到目前为止，它的应用也最广
2、泛，是数学规划及运筹学其他分目前为止，它的应用也最广泛，是数学规划及运筹学其他分支的基础。支的基础。线线性性规规划划整整数数规规划划动动态态规规划划零零一一规规划划非非线线性性规规划划目目标标规规划划2理论分支理论分支理论分支理论分支康脱络维奇论文“生产组织与计划中的数学方法”，1939年。1947年，丹捷格提出了单纯形法第一节第一节线性规划线性规划对对于于一一个个实实际际问问题题，如如果果采采用用线线性性规规划划去去求求解解，应应做做两两方方面面的的工工作作，一一是是把把求求解解问问题题抽抽象象成成能能用用线线性性规规划划来来解解的的数数学学模模型型，这这就就是是数数学学建建模模。二是对这个
3、线性规划进行求解。即二是对这个线性规划进行求解。即数数学学建建模模求求解解1线性规划方法解决问题的过程线性规划方法解决问题的过程3.线性规划的数学模型线性规划的数学模型（1）引例）引例某某军军工工厂厂准准备备用用三三种种原原料料来来制制造造两两种种产产品品，有有关关数数据据如如下表所示。问如何安排生产，以使总利润达到最大化。下表所示。问如何安排生产，以使总利润达到最大化。单位产品产品消耗量原料（公斤）III原料总量A94360B200C310300单位产品利润（元）7122线性规划问题的数学模型线性规划问题的数学模型确确定定目目标标：求求出出生生产产两两种种产产品品的的数数量量各各为为公公斤斤
4、，以以使使总总利利润达到最大。润达到最大。建立数学模型建立数学模型：设设I产品生产产品生产x1公斤，公斤，II产品生产产品生产x2公斤公斤MAX总利润Z7x1+12x2目标是目标是9x1+4x23604x1+5x22003x1+10 x2300 x1，x2，x30建立数学模型：建立数学模型：设设I产品生产产品生产x1公斤，公斤，II产品生产产品生产x2公斤公斤MAX总利润Z7x1+12x2目标是目标是9x1+4x23604x1+5x22003x1+10 x2300 x1，x2，x30以以上上问问题题属属于于线线性性规规划划问问题题，这这类类问问题题从从数数学学上上讲讲所所具有的共同特征是：具有
5、的共同特征是：1）决策变量）决策变量。每一个问题都用一组未知数（x1.x2xn）表示某一方案，这组未知数的一组定值代表一个具体的规划方案。通常要求这些未知数取值是非负。以后我们称这组未知数为决策变量。2）约束条件）约束条件。3）目标函数）目标函数。线性规划问题都有一个目标要求，并且这个目标可以表示为一组未知数的线性函数，称之为目标函数，按研究问题的实际情况目标函数可以是求最小值也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化，而对于成本、费用、支出等指标则希望达到最小化。（2）线性规划问题的共同特征）线性规划问题的共同特征综综合合上上述述这这三三点点，这这类类问问题题都都可可以以
6、用用如如下下数数学学语语言言来描述。来描述。目标函数：目标函数：max(min)Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn（=，）b1a21x1+a22x2+a2nxn（=，）b2am1x1+am2x2+amnxn（=，）bmx1，x2，xn03线性规划问题的标准形式线性规划问题的标准形式（1）线性规划的标准形式是：）线性规划的标准形式是：目标函数：目标函数：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0线性规划的标准形式是：线性规划的标准形
7、式是：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0maxZ=xj0用求和符号表示标准形式，则标准形式可简写为：用求和符号表示标准形式，则标准形式可简写为：3线性规划问题的标准形式线性规划问题的标准形式线性规划的标准形式是：线性规划的标准形式是：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0用矩阵表示标准形式，则标准形式可简写为用矩阵表示
8、标准形式，则标准形式可简写为令C表示由目标函数的系数构成的矩阵，即用A表示由约束条件的系数构成的矩阵，即令X表示由决策变量构成的矩阵，即B表示约束条件向量，即C=(c1，c2，c)；3线性规划问题的标准形式线性规划问题的标准形式线性规划的标准形式是：线性规划的标准形式是：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0用矩阵表示标准形式，则标准形式可简写为用矩阵表示标准形式，则标准形式可简写为maxZ=CXC=(c1，c2，c)；AX=BX03线性规划问题的标准形式线
9、性规划问题的标准形式线性规划的标准形式是：线性规划的标准形式是：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0几点称谓几点称谓决策向量约束方程组的限定向量C=(c1，c2，c)；价值向量约束条件系数矩阵（2）将非标准形化为标准形式将非标准形化为标准形式非标准形式是非标准形式是max(min)Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn（=，）b1a21x1+a22x2+a2nxn（=，）b2am1x1+am2x2+amnxn（=，）bmx1，x
10、2，xn0标准形式是标准形式是：maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0（2）将非标准形化为标准形式将非标准形化为标准形式非标准形式非标准形式minZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0（1）若目标函数求最小值可以把它转化为求负的同一目标函数的最大值，即令Z=-ZminZ=maxZ非标准形式非标准形式maxZ=c1x1+c2x2+
11、cnxna11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0（2）约束方程组中有不等式，这时有两种情况：一种是“”形式的不等式，则可在式子的左端加一非负变量称为“松弛变量”；如：如：x1+x2+x360另外一种是形式的不等式则在左端减一松弛变量使之变为等式约束。如：如：x1+x2+x360（2）将非标准形化为标准形式将非标准形化为标准形式非标准形式是非标准形式是max(min)Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 am1x1+am2x2+a
12、mnxn=bmxk无无非非负负要要求求，xj0，其其余余的的变量大于等于零。变量大于等于零。（3）若决策变量无非负要求令xk=xk-xk,xk,xk0（3）若要求决策变量xj0可令xj=-xjxj0（2）将非标准形化为标准形式将非标准形化为标准形式试将线性规划问题化为标准形式：minz=-x1+2x2-3x3x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1，x20例题例题（2）将非标准形化为标准形式将非标准形化为标准形式4用图解法求解线性规划用图解法求解线性规划线线性性规规划划的的图图解解法法就就是是利利用用解解析析几几何何的的方方法法来来求求解解线线性性规规划划的的问问题题
13、。因因为为只只有有二二维维几几何何空空间间最最为为直直观观，所所以以图图解解法法只只能能用用来来求求解解二二维维线线性性规规划划问问题题，也也就就是是只只有有两两个个决决策策变变量量的的线线性性规规划划问问题题。下下面面我我们们结合实例来讲解线性规划的图解法。结合实例来讲解线性规划的图解法。求解线性规划问题求解线性规划问题maxZ2x1+5x2x14x23x1+2x28x10,x20例题例题把把x1，x2看看作作上上平平面面上上点点的的坐坐标标，在在第第一一象象限限内内用用图图形形将将此此规规划划问问题题的的约约束束条条件件和和目目标标函函数数都都反反映映出来就是出来就是约束条件围成了一个区域
14、，这个凸多边形oabcd内的任一点的坐标都满足约束条件。而凸边形外的点都不能满足约束条件，所以凸多边形内的任一点的坐标都是这个线性规划问题的一个解，我们称之为可行解。凸多边形构成的可行解的全体，称为可行解集（可行域）。满足目标函数的一个可行解的全体z=2x1+5x2是一组平行线，随z的增加不断向上平移，当移到b点时，达到最大值2x1+5x2=19。图解法解题的基本步骤确定可行域确定目标函数移动的方向确定最优解用图解法求解如下线性规划问题用图解法求解如下线性规划问题minZ=2x1+2x2x1-x21x1+2x20 x1，x20练习练习1用图解法求解如下线性规划问题用图解法求解如下线性规划问题m
15、inZ=2x1+2x2-x1+x21x1+x2-2x1，x20练习练习25有关线性规划问题解的概念有关线性规划问题解的概念可行域所有可行解所构成的集合就是可行域对于图解法，可行域就是由约束条件围成的一个凸多边形，我们如果用R表示可行域，则R=x/Ax=b,x0可行解同样，在可行域上的点都满足约束条件所以，我们称这些点为可行解。x=(x1,x2xn)Tx1+x2+x3+x4+x5=55有关线性规划问题解的概念有关线性规划问题解的概念基基设为约束方程组中的mn阶系数矩阵，其秩为m，（秩为m的意思为m行线性无关），又B是中mn非奇异子矩阵（|B|不等于0），则称B是这个线性规划问题的一个基。B=a1
16、1x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0这是它的系数矩阵5有关线性规划问题解的概念有关线性规划问题解的概念基基设为约束方程组中的mn阶系数矩阵，其秩为m，（秩为m的意思为m行线性无关），又B是中mn非奇异子矩阵（|B|不等于0），则称B是这个线性规划问题的一个基。B=B=a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm=（P1，P2，PM）基基变变量量称Pj(j=1,2m)为基向量，与Pj相对应的Xj(j=1,2m)称为基变量基变
17、量。B=a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm=（P1，P2，PM）非基变量非基变量其余变量称为（对应于）的非基变量非基变量。基基本本解解当取定一个基时，令非基变量为0，由克莱姆法则可得对应于该基的唯一解。此解的非零数目不超过个m个，非0分量的数目等于m的基本解称为非退化的，否则称为退化的。a11x1+a12x2+a1mx2+a1nxn=b1a21x1+a22x2+a2mx2+a2nxn=b2am1x1+am2x2+a2mx2+amnxn=bm例如当我们取为基时B=为基时基基本本解解当取定一个基时，令非基变量为0
18、，由克莱姆法则可得对应于该基的唯一解。此解的非零数目不超过个m个，非0分量的数目等于m的基本解称为非退化的，否则称为退化的。a11x1+a12x2+a1mx2+a1nxn=b1a21x1+a22x2+a2mx2+a2nxn=b2am1x1+am2x2+a2mx2+amnxn=bmX=(x1,x2,xm,0,00)基本可行解基本可行解满足非负条件的基本解叫基本可行解，它是基本解又是可行解。基本可行解的数目（非零分量）不大于m，并且都是非负的。一般地说，基本可行解的数目小于基本解的数目，最多是相等。a11x1+a12x2+a1mx2+a1nxn=b1a21x1+a22x2+a2mx2+a2nxn=
19、b2am1x1+am2x2+a2mx2+amnxn=bmx1，x2，xn0基本可行解基本可行解X=(x1,x2,xm,0,00)基本可行解基本可行解满足满足目标函数要求的可行解，称为线性规划问题的最优解。a11x1+a12x2+a1mx2+a1nxn=b1a21x1+a22x2+a2mx2+a2nxn=b2am1x1+am2x2+a2mx2+amnxn=bmx1，x2，xn0最优解最优解X=(x1,x2,xm,0,00)maxZ=c1x1+c2x2+cnxn满足非负条件可行解基本解取定一个基基本可行解最优解满足目标函数要求解之间的关系maxz=x3x1+x2+x3+x4+x5=4x1+x2+x
20、3+x4-x5=4xi0,i=1,2,52理论分支理论分支例题例题1对于约束方程组x1-x2+2x3=1x1+x2+x3=1x1,x2,x30系数矩阵基退化解非退化解2理论分支理论分支例例题题2对于约束方程组系数矩阵基退化解非退化解x1+x2-x3=1x1-x2-x3=2x1,x2,x306线性规划解的性质线性规划解的性质设设是是n维维欧欧氏氏空空间间的的一一个个点点集集，连连接接中中任任意两点意两点X、Y的线段仍在内，则称的线段仍在内，则称为凸集。为凸集。1、凸集的凸集的概念概念XYXY图中每个点都是由n维坐标表示的，这个n维坐标与向量是一致的，而向量是与线性规划问题的解是一致的。=1=u=
21、1-u1u0 xyzZ=x+(y-x)u=(1-u)x+uy任一点的表示方法令XY之间的相对长度为1，XZ之间的长度站整个长度的比例为U，6线性规划问题解的性质线性规划问题解的性质设设集集合合R是是n维维线线性性空空间间，如如果果其其中中任任意意两两点点X和和Y，如如果果对对于于任任意意1u0，都有(1-u)x+uy仍仍然然属属于于R，则可说则可说R为凸集。为凸集。（1）基本概念）基本概念凸集数学表述凸集数学表述顶点顶点设设集集合合R是是一一个个凸凸集集，Z是是这这个个集集合合中中中中的的一一点点，如如果果在在此此集集合合中中找找不不到到两两个个不不同同的的点点X和和Y，使使Z=(1-u)x+
22、uy，1u0成立，则可说成立，则可说Z点为点为S凸集的顶点。凸集的顶点。x1x2x1x2顶点的直观解释顶点的直观解释（2）线性规划问题解的性质定理）线性规划问题解的性质定理定理定理1线性规划问题的可行解集线性规划问题的可行解集R为凸集。为凸集。首首先先，线线性性规规划划问问题题的的可可行行解解X=(x1,x2,xn)是是一一个个n维维向向量量，它它可可以以看看成成是是一一个个由由n个个坐坐标标构构成成的的点点。线线性性规规划划问问题题可可能能有有不不止止一一个个可可行行解解,也也就就是是说说可可能能有有很很多多个个这这样样的的点点，这这些些点点就就构构成成了了一一个个集集合合，很很显显然然这这
23、个个集集合合就就是是一一个个n维维欧欧氏氏空空间间，我我们们要要证明的结论，就是这个集合是一个证明的结论，就是这个集合是一个凸集。凸集。XY线性规划问题所有的解所构成的集合证明这个问题的基本思路也就是，已知X和Y是线性规划问题的两个不同的解，要证明这两个解的连线中间的任意一个点也是线性规划问题的解，也就是(1-u)x+uy也是一个解，也就是它也属于集合R。证明过程设任意X和YR，目标是要证明对于任意1u0,Z=uX+(1-u)YRAZ=A（uX+(1-u)Y）因为X、YR，所以X0，Y0，而且AX=BAY=B=AuX+A(1-u)Y=uB+(1-u)B=B定理定理2凸集的顶点对应于基本可行解凸
24、集的顶点对应于基本可行解。首首先先，线线性性规规划划问问题题的的可可行行解解X=(x1,x2,xn)是是一一个个n维维向向量量，它它可可以以看看成成是是一一个个由由n个个坐坐标标构构成成的的点点。线线性性规规划划问问题题可可能能有有不不止止一一个个可可行行解解,也也就就是是说说可可能能有有很很多多个个这这样样的的点点，这这些些点点就就构构成成了了一一个个集集合，上面已经证明这个集合是一个合，上面已经证明这个集合是一个凸集。凸集。此此定定理理说说，这这个个凸凸集集的的顶顶点点是是基基本本可可行行解解,同样基本可行解也必是这个凸集的顶点同样基本可行解也必是这个凸集的顶点.首首先先还还要要理理解解基
25、基本本可可行行解解的的含含义义,基基本本可可行行解解是是线线性性规规划划问问题题系系数数矩矩阵阵一一个个特特定定的的基基所所对对应应的的可可行行解解.基基本本解解首首先先是是一一个个可可行行解解,然后它还是一个基本解然后它还是一个基本解.可行域R必要性的证明必要性的证明也也就就是是已已知知线线性性规规划划问问题题的的一一个个解解X是是这这个个线线性性规规划划问问题题可可行行解解集集合合(可可行行域域)R的的顶顶点点,要要证证明明X是是此线性规划问题的一个基本可行解此线性规划问题的一个基本可行解.简单地加以分析简单地加以分析在在这这个个问问题题中中,已已经经知知道道了了X线线性性规规划划问问题题
26、可可行行解解集集合合(可可行行域域)R的的顶顶点点,那那么么X就就肯肯定定是是一一个个可可行行解解了了.关键是要如何再证明这个可行解是一个基本解了关键是要如何再证明这个可行解是一个基本解了.可行域RX设设X=(x1,x2,xn)T,中中有有K个个分分量量大大于于0,不失一般性可以设其前不失一般性可以设其前K个分量大于个分量大于0,则则X=(x1,x2,xK,0,0,0)T那么约束条件那么约束条件AX=B中中AX的就可以写成的就可以写成AX=x1X2xK00=(P1,P2,Pk)x1X2xKx1X2xK00=P1P2PkPn=x1X2xK00=x1P1+x2P2+xkPk最终整理结果就是：最终整
27、理结果就是：那么,如果我们能够证明P1,P2,Pk是线性无关的,则由P1,P2,Pk列向量所构成的矩阵=x1P1+x2P2+xkPkx1X2xK00AX=P1P2PkPn中的K个列向量是线性无关的,则说明必然存在一个K阶子矩阵BK是非奇异矩阵,也就说明BK是一个基.这样,也就证明了X是一个基本可行解.所以整个问题就转化为证明向量P1,P2,Pk是线性无关的，用反证法来证明这个问题。P1P2Pk假设P1,P2,Pk是线性相关的,则必然存在K个不全为0的数，y1,y2,yk,使y1P1+y2P2+ykPk=0成立。=x1P1+x2P2+xkPkx1X2xK00AX=P1P2PkPn假设P1,P2,
28、Pk是线性相关的,则必然存在K个不全为0的数，y1,y2,yk,使y1P1+y2P2+ykPk=0成立。=x1P1+x2P2+xkPkx1X2xK00AX=P1P2PkPny1P1+y2P2+ykPk=(P1,P2,Pk)y1y2yK(P1,P2,Pk,0,0)y1y2yK00=AY而=0我们再来看向量XX=(x1,x2,xK,0,0,0)T因为X是可行解，所以X中的每个分量x1,x2,xK都必然大于0，那么就可以取足够小的数，使X+Y0，XY0因为AX=B,AY=0那么A（X+Y）=AX+AY=B+0=B同理A（XY）=B这说明X+Y，XY都分别是线性规划问题的解。而X=1/2（X+Y）+1
29、/2（XY）这说明点X是点（X+Y）和点（XY）的中间点。是中间点就不是顶点。这与已知相互矛盾，说明假设不成立。也就证明向量P1,P2,Pk是线性无关的，进而证明了解X是线性规划问题的一个基本可行解。充分性的证明留给同志们自己课下学习定定理理3如如果果可可行行域域R有有界界，则则线线性性规规划划问问题题的的目标函数一定在其顶点处达到最大值。目标函数一定在其顶点处达到最大值。有界可行域有界可行域R无界可行域无界可行域RABCD用用反反证证法法来来证证明明这这个个问问题题，设设X（1），X（2）X（h）是可行域的顶点，而X（0）不是可行域的顶点，但目标函数却在X（0）处达到了最大值。有界可行域有界
30、可行域RX（1）X（2）X（H）首首先先我我们们来来证证明明X（0）可用其他顶点进行线性表示。即X（0）=u1 X（1）+u2X（2）+uhX（h）,而且u1+u2+uh=1X（0）首先我们来证明X（0）可用其他顶点进行线性表示。即X（0）=u1X（1）+u2X（2）+uhX（h）,而且u1+u2+uh=1有界可行域有界可行域RX（I）X（L）X（Y）X（0）我们以二维可行域为例来证明这个问题。因为X（0）=（1-u1）X（Y）+u1X（K）而X（K）=（1-u2）X（I）+u2X（L）u11-u1X（K）u21-u2最后可得X（0）=（1-u1）X（Y）+u1（1-u2）X（I）+u1u2X
31、（L）可以验证各顶点前的系数之和为1。我们可以将此结论进行一般推广，就可得到首先我们来证明X（0）可用其他顶点进行线性表示。即X（0）=u1X（1）+u2X（2）+uhX（h）,而且u1+u2+uh=1有界可行域有界可行域RX（1）X（2）X（H）X（0）在回到原来的问题上，因为X（0）=u1X（1）+u2X（2）+uhX（h）,而且u1+u2+uh=1，因此，因此Z=CX（0）=C（u1X（1）+u2X（2）+uhX（h）=u1CX（1）+u2CX（2）+uhCX（h）在所有顶点的目标函数值中，必然要有一个最大者，假设它是在所有顶点的目标函数值中，必然要有一个最大者，假设它是X（m）u1CX
32、（m）+u2CX（m）+uhCX（m）=u1CX（m）+u2CX（m）+uhCX（m）=CX（m）最终得到最终得到Z=CX（0）CX（m）这与已知是矛盾的，同时也说明了最优解必然在顶点上取得。定定理理3如如果果可可行行域域R有有界界，则则线线性性规规划划问问题题的的目标函数一定在其顶点处达到最大值。目标函数一定在其顶点处达到最大值。定理定理1线性规划问题的可行解集线性规划问题的可行解集R为凸集。为凸集。定理定理2凸集的顶点对应于基本可行解凸集的顶点对应于基本可行解。定定理理3如如果果可可行行域域R有有界界，则则线线性性规规划划问问题题的的目标函数一定在其顶点处达到最大值。目标函数一定在其顶点处
33、达到最大值。定理定理1线性规划问题的可行解集线性规划问题的可行解集R为凸集。为凸集。定理定理2凸集的顶点对应于基本可行解凸集的顶点对应于基本可行解。三个定理的回忆三个定理的回忆以以上上三三个个定定理理说说明明线线性性规规划划问问题题的的所所有有可可行行解解组组成成一一个个集集合合，也也就就是是可可行行域域，这这个个可可行行域域是是凸凸集集，这这个个有有有有限限个个顶顶点点，线线性性规规划划问问题题每每一一个个基基本本可可行行解解都都对对应应着着可可行行域域的的一一个个顶顶点点，如如果果线线性性规规划划问问题题有有最最优优解解，则最优解必然在顶点上达到。则最优解必然在顶点上达到。以以上上三三个个
34、定定理理说说明明线线性性规规划划问问题题的的所所有有可可行行解解组组成成一一个个集集合合，也也就就是是可可行行域域，这这个个可可行行域域是是凸凸集集，这这个个有有有有限限个个顶顶点点，线线性性规规划划问问题题每每一一个个基基本本可可行行解解都都对对应应着着可可行行域域的的一一个个顶顶点点，如如果果线线性性规规划划问问题题有有最最优优解解，则则最最优优解解必必然然在在顶顶点点上达到。上达到。三个定理三个定理顶点个数=1单纯形法求解线性规划问题的基本思想单纯形法求解线性规划问题的基本思想第二节第二节单纯形法单纯形法123对对于于线线性性规规划划问问题题的的标标准准形形式式，从从可可行行域域中中一一
35、个个基基本本可可行行解解出出发发，寻寻求求使使目目标标函函数数值值有有较较大大增增加加的的另另一一个个基基本本可可行行解解，由由于于基基本本可可行行解解个个数数是是有有限限的的，所所以以经经过过有有限限次次迭迭代代目目标标函函数数值值将将逐逐步步增增大大最最终终达达到到最优。最优。可行域R初始基本可行解初始基本可行解改进基本可行解改进基本可行解结束结束最优最优？单纯形法求解线性规划问题的基本思想123可行域R从以上分析可以看出，应用单纯形法求解线性规划问题，需要解决的三个方面问题是：1、初始基本可行解如何求；2、如何判断是否最优；3、如何求改进的基本可行解。引引例例求解如下线性规划maxZ=2
36、x1+3x22x1+x22X1+3x23X1,x20（1）将上例化为标准形式maxZ=2x1+3x22x1+x2+x3=2X1+3x2+x4=3X1,x2,x3,x40第一步首先要求出其基本可行解来2、找初始基本可行解约束方程的系数矩阵为:此系数矩阵A中的两行很显然是线性独立的，所以它的秩为2，我们可以任意地组合其列向量，从而得到一个基，并求基本解。例如，列向量P3，P4是线性无关的，所以P3，P4组合为矩阵可作为一个基。根据这个基，对照原约束方程组，就可以求出其对应的基本可行解来X（1）=（0，0，2，3），将这个基本可行解代入目标函数表达式，maxZ=2x1+3x2中，得到目标函数值为0，
37、从目标函数的表达式中，直观地看，增加非基变量x2的值，可以是目标函数得到较大的增长，所以应该让非基变量x2变为基变量（进基）x1,仍为非基变量。即令x1=0，同时此例中不能超过二个基变量（因为约束条件的系数矩阵的秩为2，最优解肯定是二为的），还得从x3,x4中换出一个做非基变量（离基）并需保证非负条件，（2）判断基本可行解是否是最优解如果选x3变量出基（也就是使x3变量变为非基变量，非基变量的值为0），根据（1）式得到x2=2，将x2=2代入（2）式得到，x4=-3，这就不满足了第三个约束条件。所以不能选择x3作为出基变量。同样方法，可以验证，选择x4变量作为出基变量是可以的。（3）迭代（也就
38、是求改进的基本可行解）2x1+x2+x3=2（1）X1+3x2+x4=3（2）X1,x2,x3,x40以上选择出基变量的方法可用数学的方法归纳为min2/1,3/3,也就是:minb1/a1j,b2/a2j,b3/a3j,bm/amj在确定了x2进基，x4出基以后，为了求得以x2，x3为基变量的上述新的基本可行解x(1)及目标值z(x(1)，只要对原约束方程进行一次初等变换，即把方程组中第二等式里x2的系数化为1也就是以第二等式里x2的系数化为1，也就是以第二等式中x2的系数为主元进行一次高斯消元，得到2x1+x2+x3=2X1+3x2+x4=3X1,x2,x3,x40也就是以第二个等式中x2
39、的系数为主元进行一次高斯消元，得到1/3x1+x2+1/3x4=15/3x1+x3-1/3x4=11/3x1+x2+1/3x4=1（3）5/3x1+x3-1/3x4=1（4）将上述约束条件，变成关于基变量的表达式：x2=1-1/3x1-1/3x40 x3=1-5/3x1+1/3x40将这个表达式代入目标函数得到：Z=3+x1-x4判断是否是最优解迭代2单纯形法的一般原理单纯形法的一般原理（1）从线性规划的系数矩阵能直接观察到。x1+3x4+2x5=360 x2+4x4+5x5=200 x3+2x4+7x5=300 x1，x2，x30MAXZ7x1+12x2B=（P1，P2，P3）=1、初始基本
40、可行解的确定由以上的引例我们可以看出，对于一个线性规划的问题，为了确定初始基本可行解，首先要找到一个初始可行基，这个可行基最好是一个单位矩阵，主要有三种方法：x1+3x4+2x5=360 x2+4x4+5x5=200 x3+2x4+7x5=300 x1，x2，x30MAXZ7x1+12x2x1+3x4+2x5=360 x2+4x4+5x5=200 x3+2x4+7x5=300 x1，x2，x30B=B=不能直接看出，要调整顺序（2）对于约束条件是“”形式的不等式的情况，经过加非负的松弛变量可以等到一个单位矩阵。MAXZ7x1+12x29x1+4x23604x1+5x22003x1+10 x23
41、00 x1，x2，x30MAXZ7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10 x2+x5=300 x1，x2，x3，x4，x50B=（3）对于约束条件是“”的形式，采用人工造基的方法减去一个非负的松弛变量，再加上一个非负的人工变量总能得到一个单位矩阵。x1+3x4+2x5=360 x2+4x4+5x5=2002x3+2x4+7x5300 x1，x2，x30MAXZ7x1+12x2黑板演示找到了初始基本可行基，也就相应地找到了初始基本可行解。然后就要判断这个解是否是最优解。判断最优时，目标函数必须化成关于非基变量的函数，如果是最优解，停止；反之继续选代。判
42、断最优的标准，就是在目标函数中所有非基变量的系数均为负，如果系数大于零则目标函数还可能增加，因此需要将一个非基变量进基，同时相应地要选择另一个基变量离基。2、最优性检验、最优性检验最优性检验的准则x1+a1m+1xm+1+a1nxn=b1x2+a2m+1xm+1+a2nxn=b2xm+ammxm+1+amnxn=bmx1，x2，xn0maxZ=c1x1+c2x2+cnxnx1=b1-(a1m+1xm+1+a1nxn)x2=b2-(a2m+1xm+1+a2nxn)xm=bm-(amm+1xm+1+amnxn)Z=c1x1+c2x2+cmxm+cm+1xm+1+cnxnZ=(c1b1+c2b2+c
43、mbm)+Z=Z(X0)+令=(j=m+1,m+2,n)接33、迭代（基本可行解的转换）通过检验数就可以确定出哪个非基变量应该变为基变量（这叫做进基），再根据最小比值原则就可以确定出哪个基变量应该变为非基变量（这叫做出基）。有了新的基变量就有了新的基本可行解，新的基本可行解可通过高斯初等变换的方法求得。通过高斯变换将基变量对应的列向量变换为单位列向量，就能直接看出基本可行解。3利用单纯形表解线性规划利用单纯形表解线性规划1、结合实例讲解利用单纯形表解线性规划、结合实例讲解利用单纯形表解线性规划maxz=2x1-x2+x33x1+x2+x360 x1-x2+2x310 x1+x2-x320 x1
44、,x2,x30将它化为标准形式maxz=2x1-x2+x33x1+x2+x3+x4=60 x1-x2+2x3+x5=10 x1+x2-x3+x6=20 x1,x2,x3,x4,x5,x60CBxB2-11000Bx1x2x3x4x5x60 x4311100600 x5112010200 x611-100110j2-11000maxz=2x1-x2+x33x1+x2+x3+x4=60 x1-x2+2x3+x5=10 x1+x2-x3+x6=20 x1,x2,x3,x4,x5,x604、人工变量求可行基的方法、人工变量求可行基的方法例题例题maxz=3x1-x2-x3x1-2x2+x311-4x1
45、+x2+2x332x1-x3=-1x1,x2,x30首先，将它变为标准型首先，将它变为标准型Maxz=3x1-x2-x3x1-2x2+x3+x4=11-4x1+x2+2x3x5=3-2x1+x3=1x1,x2,x3,x4,x501大大M法法2两阶段法两阶段法练习1练习25、在实际求解中会遇到的问题及解决的办法、在实际求解中会遇到的问题及解决的办法maxz=x1+x2x1-2x22x1+x22x1,x20例题maxz=x1+x2x1-2x22x1+x22x1,x20首先要将它化为标准型maxz=x1+x2x1-2x2+x3=2x1+x2+x4=2x1,x20（1）非基变量的检验数为0；在这种情况
46、下最优解不唯一，而最优值不能改进了。（2）检验数相同；可以任选其中一个非基变量进基，选择的不同仅引起选代次数的不同。（3）最小比值相同；进一步选代不一定会立即引起目标函数的改变，只要检验数仍为正，则最终能够得到最优值（4）退化和循环。5、在实际求解中会遇到的问题及解决的办法、在实际求解中会遇到的问题及解决的办法CBxB1100Bx1x2x3x4x5x60 x4311100600 x511201020j2-110001、有时候读书是一种巧妙地避开思考的方法。4月-234月-23Tuesday,April 25,20232、阅读一切好书如同和过去最杰出的人谈话。14:22:2814:22:2814
47、:224/25/2023 2:22:28 PM3、越是没有本领的就越加自命不凡。4月-2314:22:2814:22Apr-2325-Apr-234、越是无能的人，越喜欢挑剔别人的错儿。14:22:2814:22:2814:22Tuesday,April 25,20235、知人者智，自知者明。胜人者有力，自胜者强。4月-234月-2314:22:2814:22:28April 25,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。25四月20232:22:28下午14:22:284月-237、最具挑战性的挑战莫过于提升自我。四月232:22下午4月-2314:22April 25,
48、20238、业余生活要有意义，不要越轨。2023/4/2514:22:2814:22:2825 April 20239、一个人即使已登上顶峰，也仍要自强不息。2:22:28下午2:22下午14:22:284月-2310、你要做多大的事情，就该承受多大的压力。4/25/2023 2:22:28 PM14:22:2825-4月-2311、自己要先看得起自己，别人才会看得起你。4/25/2023 2:22 PM4/25/2023 2:22 PM4月-234月-2312、这一秒不放弃，下一秒就会有希望。25-Apr-2325 April 20234月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Tuesday,April 25,202325-Apr-234月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。4月-2314:22:2825 April 202314:22谢谢大家谢谢大家