《线性规划与单纯形方法课件.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形方法课件.ppt（129页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于关于线性性规划与划与单纯形方法形方法1现在学习的是第1页，共129页2第一节第一节 线性规划问题及数学模型线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例现在学习的是第2页，共129页3一、实例一、实例例例1 1 生产计划问题生产计划问题(书书P8P8)Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量 设设I I、IIII两种产品的产量分别为两种产品的产量分别为x1,x2 。Step 2:Step 2:确定约束条件确定约束条件产品 I I
2、I资源限量设备 1 2 8台时原料A 4 0 16公斤原料B 0 4 12公斤 利润 2 3问应如何安排生产问应如何安排生产使该厂获利最多使该厂获利最多？现在学习的是第3页，共129页4说明：说明：OBJ 表示表示Objective;s.t.表示表示Subjectto Step 3:Step 3:给出目标函数给出目标函数Step 4:Step 4:整理数学模型整理数学模型现在学习的是第4页，共129页5例例2 下料问题下料问题现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米和米和1.5米的圆钢各一根。已知米的圆钢各一根。已知原料长原料长7.4米，问如何下料，使用的原料最少（
3、余料最少或根数最少）米，问如何下料，使用的原料最少（余料最少或根数最少）？分析：分析：最简单的做法是：每根最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一米长的原材料各截取三种规格的元钢一根，则料头为根，则料头为0.9米，米，100套则浪费材料套则浪费材料90米。关键是要设计套裁方案，米。关键是要设计套裁方案，不能有遗漏。不能有遗漏。现在学习的是第5页，共129页6解解：设：设x1,x2,x3,x4,x5分别代表五种不同的原料用量方案。分别代表五种不同的原料用量方案。0.86.6310 x50.37.1021x40.27.2220 x30.17.3102x207.4301x1余料余
4、料合计合计1.5米米2.1米米2.9米米方案方案余料最少的余料最少的LP模型：模型：现在学习的是第6页，共129页7根数最少的根数最少的LP模型：模型：料头最省根数最少解1:x1=30,x2=10,x4=50;料头Z=16,根数90。可以做100套钢架，无圆钢剩余。与解1相同解2:x1=100,x3=50;料头Z=10,根数150。可以做100套钢架,但余1.5m圆钢300根。与解1相同现在学习的是第7页，共129页8LPLP是数学规划的一个重要分支，数学规划着重解决资源的优是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：化配置，一般可以表达成以下
5、两个问题中的一个：（1 1）当资源给定时，要求完成的任务最多；）当资源给定时，要求完成的任务最多；（2 2）当任务给定时，要求为完成任务所消耗的资源最少。）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标若上述问题的目标约束都能表达成变量的线性关系，则这类约束都能表达成变量的线性关系，则这类优化问题称优化问题称LPLP问题。问题。LP LP是一种解决在线性约束条件下追求最大或最小的线性目标函数是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。的方法。现在学习的是第8页，共129页9 目标函数目标函数用决策变量的用决策变量的线性函数线性函数来表示。按问题的不同，要求来表
6、示。按问题的不同，要求目标函数实现最大化和最小化。目标函数实现最大化和最小化。每一个问题变量都用一组每一个问题变量都用一组决策变量决策变量（x1,x2,xn）表示某一表示某一方案，这组决策变量的值代表一个具体方案，这些变量是方案，这组决策变量的值代表一个具体方案，这些变量是非非负负且连续且连续的。的。存在一定的存在一定的约束条件约束条件，这些约束条件可以用一组，这些约束条件可以用一组线性等式线性等式或或线性不等式线性不等式来表示。来表示。结论：结论：线性规划是研究在一组线性不等式或线性等式约束下，线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。使得某
7、一线性目标函数取最大或最小的极值问题。二、线性规划问题（二、线性规划问题（LPLP问题）的共同特征问题）的共同特征现在学习的是第9页，共129页10Max(Min)Z=c1x1+c2x2+cnxn (1)a11x1+a12x2+a1nxn(=,)b1 a21x1+a22x2+a2nxn(=,)b2s.t.(2)am1x1+am2x2+amnxn(=,)bm xj0,j=1,2,，n(3)(1)目标函数；目标函数；(2)约束条件；约束条件；(3)决策变量非负决策变量非负n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术
8、系数；xj决策变量决策变量线性规划模型的一般形式为：线性规划模型的一般形式为：现在学习的是第10页，共129页11线性规划模型的紧缩形式线性规划模型的紧缩形式n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量现在学习的是第11页，共129页12练习题：是否为线性规划模型？练习题：是否为线性规划模型？现在学习的是第12页，共129页131.1.线性不等式的几何意义线性不等式的几何意义 半平面半平面1)1)作出作出LPLP问题的可行域问题的可行域2)2)作出目标函数的等值线作出目标函数的等值线3
9、)3)移动等值线到可行域边界得到最优点移动等值线到可行域边界得到最优点2.2.图解法步骤图解法步骤三、两变量线性规划问题的三、两变量线性规划问题的图解法图解法现在学习的是第13页，共129页144x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例例3（书（书P8）：）：Q2(4,2)Z=2x1+3x2做目标函数做目标函数2x1+3x2的等值线，与的等值线，与阴影部分的边界相交于阴影部分的边界相交于Q2(4,2)点，点，表明最优生产计划为：生产表明最优生产计划为：生产I产产品品4件，生产件，生产II产品产品2件。件。Q3现在学习的是第14页，共129页15目标函数目标函数z=
10、ax1+bx2的值的值递增递增的方向与系数的方向与系数a、b有关有关a0,b0a0X1X2a0,b0,b0z=ax1+bx2目标函数等值线：目标函数等值线：ax1+bx2=k移项移项x2=-a/bx1+k/b目标函数等值线在纵轴目标函数等值线在纵轴上的截距为上的截距为k/b现在学习的是第15页，共129页16例例4 4Z=36现在学习的是第16页，共129页17例例 用图解法求解线性规划问题用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当当Z值由小变大时，将与值由小变大时，将与Q2Q3重合重合Q2Q3上任意一点都是最优
11、解上任意一点都是最优解有有无穷多最优解无穷多最优解（多重解）（多重解）Q3(2,3)现在学习的是第17页，共129页18例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无界解无界解（“无无有限最优解有限最优解”或或“最优解无界最优解无界”）约束条件过分宽松约束条件过分宽松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域无解（不闭合）一定就会出现无界解吗？可行域无解（不闭合）一定就会出现无界解吗？现在学习的是第18页，共129页19例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界唯一最优解唯一最优解X*=(1,0)1,0
12、)，对应于点，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00现在学习的是第19页，共129页20例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无穷多最优解无穷多最优解对应对应于点于点B沿着沿着OB向右上方发出的向右上方发出的射线上的所有点射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00现在学习的是第20页，共129页21例例（书（书P11P11）：）：无可行解无可行解（可行域为空）（可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4无最优解无最优解现在学习
13、的是第21页，共129页223.3.图解法的作用图解法的作用 能解决少量问题能解决少量问题 揭示了线性规划问题的若干规律揭示了线性规划问题的若干规律解的类型解的类型可行域类型可行域类型唯一最优解唯一最优解无穷多最优解无穷多最优解最优解无界最优解无界（无有限最优解）（无有限最优解）无解无解（不存在可行域）（不存在可行域）非空有界非空有界无界无界空集空集规律规律1 1：现在学习的是第22页，共129页23规律规律2 2：线性规划问题的可行域为凸集线性规划问题的可行域为凸集线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到最优解可在凸集的某顶点处达到 现
14、在学习的是第23页，共129页24 小结：图解法的基本步骤：小结：图解法的基本步骤：1在直角坐标系作出可行域在直角坐标系作出可行域S的区域（一般是一个凸多边形）的区域（一般是一个凸多边形）2令目标函数值取一个已知的常数令目标函数值取一个已知的常数k，作等值线：，作等值线：c1x1+c2x2=k3对于对于max问题，让目标函数值问题，让目标函数值k由小变大，即让等值线进行平移，由小变大，即让等值线进行平移，若它与可行域若它与可行域S最后交于一个点（一般是最后交于一个点（一般是S的一个顶点），则该点就是的一个顶点），则该点就是所求的最优点，若与所求的最优点，若与S的一条边界重合，此时边界线上的点均
15、是最优点的一条边界重合，此时边界线上的点均是最优点4将最优点所在的两条边界线所代表的方程联立求解，即得将最优点所在的两条边界线所代表的方程联立求解，即得最优解最优解X*，把最优解，把最优解X*带入目标函数，得最优值带入目标函数，得最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动注意：若是求目标函数最小值，等值线向反方向移动现在学习的是第24页，共129页25四、线性规划问题的标准型四、线性规划问题的标准型1.1.标准型标准型（1）目标函数）目标函数：max（2）约束条件：）约束条件：等式等式（3）变量约束：）变量约束：非负非负xj 0（4）资源限量：）资源限量：非负非负bi 0
16、标准型的构成要素标准型的构成要素现在学习的是第25页，共129页262.2.线性规划标准型的紧缩形式线性规划标准型的紧缩形式现在学习的是第26页，共129页273.3.线性规划标准型的向量和矩阵表达式线性规划标准型的向量和矩阵表达式矩阵式矩阵式:MaxZ=CTXs.t.AX=bX0 n向量式向量式:MaxZ=cjxjj=1ns.t.Pjxj=bj=1xj 0,j=1,2,.,n现在学习的是第27页，共129页284.所有所有LP问题均可化为标准型问题均可化为标准型（1）最小转换成最大）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*现在学习的是第28页，共129页29（2）不等
17、式约束条件转换成等式约束条件）不等式约束条件转换成等式约束条件（3）变量约束转换）变量约束转换（4）把）把bi 0转换成转换成bi 0现在学习的是第29页，共129页30例例5 5 化标准型化标准型可化为可化为1.1.处理决策变量处理决策变量2.2.处理目标函数处理目标函数3.3.约束条件不等式约束条件不等式4.4.处理约束条件右端处理约束条件右端 常数项常数项现在学习的是第30页，共129页31例例6 6 化标准型化标准型1.1.处理决策变量处理决策变量2.2.处理目标函数处理目标函数3.3.约束条件不等式约束条件不等式4.4.处理约束条件右端处理约束条件右端 常数项常数项现在学习的是第31
18、页，共129页32MaxZ=x1+2x2+3x4-3x5+0 x6+0 x7s.t.x1-x2+x4-x5+x6=7x1+x2+x4-x5-x7=2-3x1-x2+3x4-3x5=5 x20,xj0,j=1,4,5,6,7MaxZ=x1+2x2+3(x4-x5)+0 x6+0 x7s.t.x1-x2+(x4-x5)+x6=7x1+x2+(x4-x5)-x7=2-3x1-x2+3(x4-x5)=5 x20,xj0,j=1,4,5,6,7最终结果最终结果中间结果中间结果现在学习的是第32页，共129页33课堂练习课堂练习现在学习的是第33页，共129页34五、标准型五、标准型LPLP问题解的概念问
19、题解的概念现在学习的是第34页，共129页35（1）（2）（3）约束系数矩阵：约束系数矩阵：x1x2x3x4x5例：例：现在学习的是第35页，共129页36约束系数矩阵：约束系数矩阵：可能可能的基矩阵是的基矩阵是A中任意三个列的组合，共中任意三个列的组合，共10个。个。现在学习的是第36页，共129页37令令B=(P1,P2,Pm)且且|B|0，则称，则称Pj(j=1,2,m)为为基向量基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量，记为记为XB=(x1,x2,xm)T，其余的变量称为，其余的变量称为非基变量非基变量，记为，记为XN=(xm+1,xm+2,xn)T。现
20、在学习的是第37页，共129页38现在学习的是第38页，共129页39现在学习的是第39页，共129页40B1=(P1,P2)：基基令：令：XB1=(x1,x2)x1=0，x2=2X=(0,2,0,0)XB1=(0,2)对应于对应于B1的基解为的基解为也是基可行解也是基可行解现在学习的是第40页，共129页41线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解现在学习的是第41页，共129页42例例7Max Z=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0六、可行解、基解和基可行解举
21、例六、可行解、基解和基可行解举例非基非基变量变量基变量基变量图中的点图中的点x4,x5x1=4x2=3x3=-2A基解基解x3,x5x1=2x2=3x4=8B基可行解基可行解x3,x4x1=4x2=2x5=4C基可行解，基可行解，最优解最优解x2,x4x1=4x3=4x5=12D基可行解基可行解x2,x3x1=8x4=-16x5=12E基解基解x1,x5x2=3x3=2x4=16F基可行解基可行解x1,x3x2=4x4=16x5=-4G基解基解x1,x2x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型标准型
22、现在学习的是第42页，共129页43例例8 8现在学习的是第43页，共129页44LP标准型问题解的结论标准型问题解的结论根据根据LP的图解法及解的基本概念可知：的图解法及解的基本概念可知：基解对应约束条件的交点；基解对应约束条件的交点；基可行解对应可行域的顶点基可行解对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上得到某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解最优解。现在学习的是第44页，共129页45第二节第二节 LPLP问题的基本理论问题的基本理论一、基本概念一、基本概念现在学习的是第45页，共129页46判断以下图形哪些是凸集，哪些不是凸集？判断以下图形
23、哪些是凸集，哪些不是凸集？判断下列集合是否凸集？判断下列集合是否凸集？现在学习的是第46页，共129页47定理定理1 1 LPLP问题的可行域为一凸集问题的可行域为一凸集。二、基本定理二、基本定理现在学习的是第47页，共129页48引理引理线性规划问题的可行解线性规划问题的可行解X=(x1,x2,xn)T是基可行解是基可行解的充要条的充要条件为件为X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数列向量是线性独立的。现在学习的是第48页，共129页49定理定理2 2 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。（即：若（即：若X是是LP问题的
24、可行解，则问题的可行解，则“X是是LP问题的基可行解问题的基可行解”等价于等价于“X是是LP问题可行域顶点问题可行域顶点”）因为因为X是基可行解，是基可行解，则其对应的向量组则其对应的向量组a1,a2,am线性无关线性无关(mm时，有时，有xj=xj(1)=xj(2)=0.现在学习的是第49页，共129页50现在学习的是第50页，共129页51现在学习的是第51页，共129页52现在学习的是第52页，共129页53定理定理3 3 若可行域有界，则若可行域有界，则LPLP问题的目标函数一定可以在其可行域的顶问题的目标函数一定可以在其可行域的顶点上达到最优。点上达到最优。引理引理若若S是有界凸集，
25、则任何一点是有界凸集，则任何一点XS可表示为可表示为S的顶点的凸组的顶点的凸组合。合。现在学习的是第53页，共129页54 线性规划问题的可行域是凸集线性规划问题的可行域是凸集(定理定理1)1)；凸集的顶点对应于基可；凸集的顶点对应于基可行解行解(定理定理2)2)，基可行解，基可行解(顶点顶点)的个数是有限的；若线性规划有最优的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到解，必在可行域某顶点上达到(定理定理3)3)。因此。因此,我们我们可以在有限个基可可以在有限个基可行解中寻找最优解。行解中寻找最优解。由线性代数知，对标准形由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，
26、问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如如果变量和方程较多，比如m=50，n=100，所有基解有可能达，所有基解有可能达1029个，即使计算机每秒能求解个，即使计算机每秒能求解1亿个这样的方程组，也需要亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证
27、下一步得到的检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。解不劣于当前解。这就是线性规划的单纯形法。现在学习的是第54页，共129页55第三节第三节 单纯形法单纯形法一、基本思想一、基本思想检验解的检验解的最优性最优性结束结束Y枢轴运算（旋转运算）枢轴运算（旋转运算）确定另一个基本可行解确定另一个基本可行解N化化LP问题为标准型，问题为标准型，确定一个初始基本可行解确定一个初始基本可行解化化LP问题为标准型，从可行域的某个基可问题为标准型，从可行域的某个基可行解行解（一个顶点）（一个顶点）开始，转换到另一个基可行开始，转换到另一个基可行
28、解解（另一个顶点）（另一个顶点），并使目标函数值得到改善，并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。逐步迭代（逼近）法。现在学习的是第55页，共129页56单纯形法举例单纯形法举例（P20）化为标准型化为标准型二、基本原理举例二、基本原理举例现在学习的是第56页，共129页571.初始基可行解的确定初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典型要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵的系数列向量
29、构成单位矩阵，该矩阵B0是是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。是可行基）。现在学习的是第57页，共129页58令非基变量令非基变量x10、x20，得到基可行解及相应的目标函数值，得到基可行解及相应的目标函数值，X(0)(0,0,8,16,12)T，Z(0)0。结论：结论：（1）在标准化的）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；就可求得初始基可行解；（2）基变量确定后，目标函数和基变量均可表示成非基变量的代）基变量确定后，目标
30、函数和基变量均可表示成非基变量的代数和形式（如数和形式（如(6)和和(5)），从而便于求出基可行解及相应的目标函数值。），从而便于求出基可行解及相应的目标函数值。现在学习的是第58页，共129页592.最优性检验最优性检验考察变换后的目标函数考察变换后的目标函数(6)式，非基变量式，非基变量x1、x2的系数都为正数，若的系数都为正数，若让让x1、x2取正值，则目标函数值会增大。因此，应将非基变量取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。变换成基变量。结论：结论：在非基变量的代数和形式表示的目标函数中，若非基变量的系数（称在非基变量的代数和形式表示的目标函数中，若非基
31、变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。是最优解。现在学习的是第59页，共129页60当确定当确定x2为换入变量后，为换入变量后，x1还是非基变量，故还是非基变量，故x10。现在要保。现在要保证证x3、x4、x5 0，即，即(5)当当x2min（8/2，12/4）=3（最小比值规则）（最小比值规则）可保证可保证x5=0则则x5为换出变量。为换出变量。新的基变量为新的基变量为x3、x4、x2，新的可行基为，新的可行基为B1(P3,P4,P2)确定换入变量：确定换入变量：一般选择正系数最
32、大的非基变量为换入变量。一般选择正系数最大的非基变量为换入变量。确定换出变量：确定换出变量：（a）保证换出的变量取值为）保证换出的变量取值为0，变成非基量；，变成非基量；（b）其它的变量取值为非负。）其它的变量取值为非负。3.确定新的基可行解（基变换）确定新的基可行解（基变换）现在学习的是第60页，共129页614.旋转迭代旋转迭代基变量确定后，旋转迭代就是把目标函数和基变量均表示成基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量非基变量x1、x5的代数和形式。可用高斯消去法实现。的代数和形式。可用高斯消去法实现。令非基变量令非基变量x10、x50，得到新的基可行解及相应的目标函，
33、得到新的基可行解及相应的目标函数值，数值，X(1)(0,3,2,16,0)T，Z(1)9。返回至第二步，直至求出最。返回至第二步，直至求出最优解。优解。现在学习的是第61页，共129页62这时目标函数的表达式是这时目标函数的表达式是z=141.5x30.125x4，当将当将x1定为换入变量后定为换入变量后，继续利用上述方法确定换出，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T，这时目标函数的表达式是这时目标函数的表达式是z=132x3+1/4x5，再经过一次迭代，再得到一个基可行解再经过一次迭代，再得到一个基可行
34、解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q3 将上述方程组求解过程，用将上述方程组求解过程，用列表形式表达，即为线性规列表形式表达，即为线性规划划单纯形表。单纯形表。现在学习的是第62页，共129页63以以x2为主元素为主元素以以x1为主元素为主元素例例2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)x1+1/2x2+x3=5(1)0 x1+3/2x2-2x3=-9(2)(2)-(1)3/2,(1)/2x1+0 x2+5/3x3=80 x1+x2-4/3x3=-6(1)-(2)/3,(2
35、)2/3三、旋转运算三、旋转运算结论：旋转运算就是矩阵的初等变换，是高斯消元结论：旋转运算就是矩阵的初等变换，是高斯消元现在学习的是第63页，共129页64结论：结论：如果如果LPLP问题通过单纯形法迭代到某步时，所有检验数问题通过单纯形法迭代到某步时，所有检验数0,0,则该则该LPLP问问题已得到最优解。题已得到最优解。MaxZ=CXs.t.AX=bX0若若cj-CBB-1Pj=j0,则则ZZ0,Z0即为最优解即为最优解.(基变量的检验数必为基变量的检验数必为0)令令A=(B,N),X=XB,C=(CB,CN)XN由由AX=b(B,N)XB=bBXB+NXN=bB-1BXB+B-1NXN=B
36、-1bXNXB=B-1bB-1NXN(2)将将(2)式代入目标函数得式代入目标函数得Z=CX=(CB,CN)XB=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN XN=CBB-1b+(CN-CBB-1N)XN=Z0+(cj-CBB-1Pj)xjxj为非基变量为非基变量四、检验数公式四、检验数公式现在学习的是第64页，共129页65对于线性规划问题对于线性规划问题：MaxZ=CTXAX=b，X0，可用如下三个判别定理，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。来判别线性规划问题是否已经获得最优解或为无界解。判别定理判别定理1 1设设X为线性规划的一个基可行
37、解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为为非基变量的下标集）有非基变量的下标集）有j0，则，则X为线性规划的为线性规划的最优解最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，同时有某个非基变量的检验数，同时有某个非基变量的检验数k=0(kJ)，则该线性规划有，则该线性规划有无穷多最优解无穷多最优解；设；设X为线性规划的一个基可为线性规划的一个基可行解，且对于一切行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，则该线，则该线性规划
38、有性规划有唯一最优解唯一最优解。判判别别定定理理3 3 设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划划问问题题具具有有无无界界解解（无无最最优解）优解）。现在学习的是第65页，共129页66一、步骤一、步骤Step1.化化LP问题为标准型问题为标准型,建立建立初始单纯形表初始单纯形表;Step2.若所有检验数若所有检验数0,则最优解已达到。则最优解已达到。否则否则,计算计算 ,选取选取k 所对应的变量所对应的变量xk 为为进基变量进基变量;Step3.计算计算 ,选取选取l 所对应的变量所对应的变
39、量xl 为为出出基变量基变量;Step4.以以alk为主元素进行为主元素进行旋转运算旋转运算,转转Step2;第四节第四节 单纯形法的步骤单纯形法的步骤现在学习的是第66页，共129页67cj CB XB b x1x2 xmxm+1xnj基可行解：基可行解：x1=b1,x2=b2,xm=bm,xm+1=xm+2=xn=01.1.初始单纯形表初始单纯形表c1c2cm cm+1cnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1n010a2,m+1a2n 001am,m+1amn000m+1n-CBTB-1b现在学习的是第67页，共129页68对于上述单纯形表：对于上述单纯形表：
40、（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。单位基。（2）从单纯形表中，可立即得到一个基可行解：从单纯形表中，可立即得到一个基可行解：x1=b1,x2=b2,xm=bm,xm+1=xm+2=xn=0（3）用检验数的计算公式很容易计算检验数，并可根据三用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。题无最优解。现在学习的是第68页，共129页692.2.进基变量的选择进基变量的选择cj c1c2cm cm+1ckcnC
41、B XB b x1x2 xmxm+1xkxnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1k a1n010a2,m+1a2k a2n 001am,m+1amkamnj-CBTB-1b000m+1k n选取选取 所对应的变量所对应的变量xk 为进基变量。为进基变量。现在学习的是第69页，共129页703.3.出基变量的选择出基变量的选择cj c1cl cm cm+1ckcnCB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 bl bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amn1 l mj-C
42、BTB-1b000m+1k n选取选取 所对应的变量所对应的变量xl 为出基变量。为出基变量。现在学习的是第70页，共129页714.4.旋转运算旋转运算cj c1cl cm cm+1ckcn CB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 bl bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amnjckxkbl/alk01/alk 0al,m+1/alk1aln/alk b11-a1k/alk 0a1,m+10a1nbm0-amk/alk1am,m+10amn现在学习的是第71页，共129页72二、实例二、实
43、例化为标准型化为标准型现在学习的是第72页，共129页73单纯型表算法单纯型表算法 X(0)(0,0,8,16,12)T以以1为主元素进行旋转运算，为主元素进行旋转运算，x1为换入变量，为换入变量，x3为换出变量为换出变量0 q qi300 x5 x2 x3 x40 x4 x3XB b s sj0 x1CB2cjx1cjx2x3x4x514 020410001000123000b816 12XBx3x4x5CB000以以4为主元素进行旋转运算，为主元素进行旋转运算，x2为换入变量，为换入变量，x5为换出变量为换出变量s sj23000q qi8/212/44x23主元列主元列主元行主元行000
44、1/43140101600110-1/22X(1)(0,3,2,16,0)T200-3/4016/42/11现在学习的是第73页，共129页74此时达到最优解。此时达到最优解。X*=(4,2),maxZ=14。0 q qi300 x5 x2 x3 x40 x4 x23 XB b s sjx1CB2cj0 q qi300 x5 x2 x3 x4x23 x1XB b s sj2x1CB2cj0001/4310-201/40 x120110-1/2220-412808/212x500-21/2140101/40401/2-1/800210-3/2-1/800X(3)(4,2,0,0,4)TX(2)(
45、2,3,0,8,0)T以以2为主元素进行旋转运算，为主元素进行旋转运算，x5为换入变量，为换入变量，x4为换出变量为换出变量现在学习的是第74页，共129页754x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解 基基可行解可行解 迭代迭代 顶点顶点 相邻的顶点相邻的顶点迭代迭代 图解法：图解法：单纯形表算法：单纯形表算法：现在学习的是第75页，共129页76对于极小化问题，其最优解的判
46、定定理和进基变量的选取和极大对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：化问题刚好相反，如下所示：判别定理判别定理1 1 设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的为线性规划的最优解最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非为非基变量的下标集）有基变量的下标集）有j0，同时有某个非基变量的检验数，同时有某个非基变量的检验数k=0(kJ)，则该线性规划有，则该线性规划有
47、无穷多最优解无穷多最优解；设；设X为线性规划的一个基可行解，为线性规划的一个基可行解，且对于一切且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，则该线性规划有，则该线性规划有唯一最优解唯一最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划划问问题题具具有有无无界界解解（无无最最优优解）解）。在进基可行解的转换过程中，进基变量的选取原则是：在进基可行解的转换过程中，进基变量的选取原则是：minj|j 0,而而k对应对应列向量列向量Pk0,则此则此LP问题
48、有问题有无界解无界解.现在学习的是第96页，共129页974.4.在最优表中出现某非基变量检验数为在最优表中出现某非基变量检验数为0 0（无穷多最优解）（无穷多最优解）现在学习的是第97页，共129页98CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-360000-10 x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj034000结论：结论：若线性规划问题存在某非基变量检验数为若线性规划问题存在某非基变量检验数为0,而其对应列向量而其对应列向量Pk0,仍仍可判断线性
49、规划问题有无穷多最优解。可判断线性规划问题有无穷多最优解。现在学习的是第98页，共129页99例例1 1 某工厂要用三种原材料某工厂要用三种原材料D D、P P、H H混合调配出三种不同规格的产品混合调配出三种不同规格的产品A A、B B、C C。已知产品的规格要求、单价和原材料的供应量、单价。该。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？厂应如何安排生产使利润最大？产品产品名称名称规格要求规格要求单价单价(元元/kg）A原材料原材料D不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料D不少于不少于25%原材料原材料P不超过不超过50%35
50、C不限不限25原材料原材料名称名称每天最多供每天最多供应量应量(kg)单价单价(元元/kg)D10065P10025H6035第六节第六节 应用举例应用举例解：解：设设A中中D、P、H的含量为的含量为x11、x12、x13B中中D、P、H的含量为的含量为x21、x22、x23 C中中D、P、H的含量为的含量为x31、x32、x33现在学习的是第99页，共129页100用单纯形法计算得结果：每天生产用单纯形法计算得结果：每天生产A A产品产品200kg,200kg,分别需要原料分别需要原料:D:D为为100kg;P100kg;P为为50kg;H50kg;H为为50kg.50kg.总利润收入总利润