《线性规划与单纯形方法精选PPT.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形方法精选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:确定约束条件确定约束条件
2、产品 I II 资源限量设备 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.3
4、102x207.4301x1余料余料合计合计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价值系数；价值系数；b
8、i右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量线性规划模型的一般形式为：线性规划模型的一般形式为：第10页，讲稿共129张，创作于星期三11线性规划模型的紧缩形式线性规划模型的紧缩形式n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量第11页，讲稿共129张，创作于星期三12练习题：是否为线性规划模型？练习题：是否为线性规划模型？第12页，讲稿共129张，创作于星期三131.1.线性不等式的几何意义线性不等式的几何意义 半平面半平面1)1)作出作出LPL
9、P问题的可行域问题的可行域2)2)作出目标函数的等值线作出目标函数的等值线3)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件，生产件，生产
10、II产品产品2件。件。Q3第14页，讲稿共129张，创作于星期三15目标函数目标函数z=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
11、=2x1+4x2当当Z值由小变大时，将与值由小变大时，将与Q2Q3重合重合Q2Q3上任意一点都是最优解上任意一点都是最优解有有无穷多最优解无穷多最优解（多重解）（多重解）Q3(2,3)第17页，讲稿共129张，创作于星期三18例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无界解无界解（“无无有限最优解有限最优解”或或“最优解无界最优解无界”）约束条件过分宽松约束条件过分宽松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域无解（不闭合）一定就会出现无界解吗？可行域无解（不闭合）一定就会出现无界解吗？第18页，讲稿共129张，创作于星期三19例例
12、 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界唯一最优解唯一最优解X*=(1,0)1,0)，对应于点，对应于点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）：）：无可行解无可行解（可行域为空）（
13、可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4无最优解无最优解第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最后交于一个点（一般是最
15、后交于一个点（一般是S的一个顶点），则该点就的一个顶点），则该点就是所求的最优点，若与是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最的一条边界重合，此时边界线上的点均是最优点优点4将最优点所在的两条边界线所代表的方程联立求解，即得最优解将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解，把最优解X*带入目标函数，得最优值带入目标函数，得最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动注意：若是求目标函数最小值，等值线向反方向移动第24页，讲稿共129张，创作于星期三25四、线性规划问题的标准型四、线性规划问题的标准型1.1.标准型标准型（1）目
16、标函数）目标函数：max（2）约束条件：）约束条件：等式等式（3）变量约束：）变量约束：非负非负xj 0（4）资源限量：）资源限量：非负非负bi 0标准型的构成要素标准型的构成要素第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问
17、题均可化为标准型问题均可化为标准型（1）最小转换成最大）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*第28页，讲稿共129张，创作于星期三29（2）不等式约束条件转换成等式约束条件）不等式约束条件转换成等式约束条件（3）变量约束转换）变量约束转换（4）把）把bi 0转换成转换成bi 0第29页，讲稿共129张，创作于星期三30例例5 5 化标准型化标准型可化为可化为1.1.处理决策变量处理决策变量2.2.处理目标函数处理目标函数3.3.约束条件不等式约束条件不等式4.4.处理约束条件右端处理约束条件右端 常数项常数项第30页，讲稿共129张，创作于星期三31例例6 6 化标
18、准型化标准型1.1.处理决策变量处理决策变量2.2.处理目标函数处理目标函数3.3.约束条件不等式约束条件不等式4.4.处理约束条件右端处理约束条件右端 常数项常数项第31页，讲稿共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,x
19、j0,j=1,4,5,6,7最终结果最终结果中间结果中间结果第32页，讲稿共129张，创作于星期三33课堂练习课堂练习第33页，讲稿共129张，创作于星期三34五、标准型五、标准型LPLP问题解的概念问题解的概念第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)
20、为为基向量基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量，记为记为XB=(x1,x2,xm)T，其余的变量称为，其余的变量称为非基变量非基变量，记为，记为XN=(xm+1,xm+2,xn)T。第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线性规划标准型问题解的关系线性规划标准型问题
21、解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解第41页，讲稿共129张，创作于星期三42例例7Max Z=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0六、可行解、基解和基可行解举例六、可行解、基解和基可行解举例非基非基变量变量基变量基变量图中的点图中的点x4,x5x1=4x2=3x3=-2 A基解基解x3,x5x1=2x2=3x4=8B基可行解基可行解x3,x4x1=4x2=2x5=4C基可行解，基可行解，最优解最优解x2,x4x1=4x3=4x5=12D基可行解基可行解x2,x3x1=8x4=-16x5=12E基解基解x
22、1,x5x2=3x3=2x4=16F基可行解基可行解x1,x3x2=4x4=16x5=-4 G基解基解x1,x2x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型标准型第42页，讲稿共129张，创作于星期三43例例8 8第43页，讲稿共129张，创作于星期三44LP标准型问题解的结论标准型问题解的结论根据根据LP的图解法及解的基本概念可知：的图解法及解的基本概念可知：基解对应约束条件的交点；基解对应约束条件的交点；基可行解对应可行域的顶点基可行解对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上
23、某个基可行解一定是最优解，即一定在可行域的顶点上得到得到最优解最优解。第44页，讲稿共129张，创作于星期三45第二节第二节 LPLP问题的基本理论问题的基本理论一、基本概念一、基本概念第45页，讲稿共129张，创作于星期三46判断以下图形哪些是凸集，哪些不是凸集？判断以下图形哪些是凸集，哪些不是凸集？判断下列集合是否凸集？判断下列集合是否凸集？第46页，讲稿共129张，创作于星期三47定理定理1 1 LPLP问题的可行域为一凸集问题的可行域为一凸集。二、基本定理二、基本定理第47页，讲稿共129张，创作于星期三48引理引理线性规划问题的可行解线性规划问题的可行解X=(x1,x2,xn)T是基
24、可行解是基可行解的充要的充要条件为条件为X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数列向量是线性独立的。第48页，讲稿共129张，创作于星期三49定理定理2 2 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。（即：若（即：若X是是LP问题的可行解，则问题的可行解，则“X是是LP问题的基可行解问题的基可行解”等价于等价于“X是是LP问题可行域顶点问题可行域顶点”）因为因为X是基可行解，是基可行解，则其对应的向量组则其对应的向量组a1,a2,am线性无关线性无关(mm时，有时，有xj=xj(1)=xj(2)=0.第49页，讲稿共129张，创作
25、于星期三50第50页，讲稿共129张，创作于星期三51第51页，讲稿共129张，创作于星期三52第52页，讲稿共129张，创作于星期三53定理定理3 3 若可行域有界，则若可行域有界，则LPLP问题的目标函数一定可以在其可行域问题的目标函数一定可以在其可行域的顶点上达到最优。的顶点上达到最优。引理引理若若S是有界凸集，则任何一点是有界凸集，则任何一点XS可表示为可表示为S的顶点的凸组合。的顶点的凸组合。第53页，讲稿共129张，创作于星期三54 线性规划问题的可行域是凸集线性规划问题的可行域是凸集(定理定理1)1)；凸集的顶点对应于基可；凸集的顶点对应于基可行解行解(定理定理2)2)，基可行解
26、，基可行解(顶点顶点)的个数是有限的；若线性规划有最优的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到解，必在可行域某顶点上达到(定理定理3)3)。因此。因此,我们我们可以在有限个基可以在有限个基可行解中寻找最优解。可行解中寻找最优解。由线性代数知，对标准形由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如但如果变量和方程较多，比如m=50，n=100，所有基解有可能达，所有基解有可能达1029个，即使计算机
27、每秒能求解个，即使计算机每秒能求解1亿个这样的方程组，也需要亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。劣于当前解。这就是线性规划的单纯形法。第54页，讲稿共129张，创作于星期三55第三节第三节 单纯形法单纯形法一、基本思想一、基本思想检验解的检验解的最优
28、性最优性结束结束Y枢轴运算（旋转运算）枢轴运算（旋转运算）确定另一个基本可行解确定另一个基本可行解N化化LP问题为标准型，问题为标准型，确定一个初始基本可行解确定一个初始基本可行解化化LP问题为标准型，从可行域的某个基问题为标准型，从可行域的某个基可行解可行解（一个顶点）（一个顶点）开始，转换到另一个基开始，转换到另一个基可行解可行解（另一个顶点）（另一个顶点），并使目标函数值得到，并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。质是逐步迭代（逼近）法。第55页，讲稿共129张，创作于星期三56单纯形法举例单纯形法举
29、例（P20）化为标准型化为标准型二、基本原理举例二、基本原理举例第56页，讲稿共129张，创作于星期三571.初始基可行解的确定初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。定是可行基）。第57页，讲稿共129张，创作于星期三58令非基变量令非基变量x10、x20，得到基可
30、行解及相应的目标函数值，得到基可行解及相应的目标函数值，X(0)(0,0,8,16,12)T，Z(0)0。结论：结论：（1）在标准化的）在标准化的LP问题的约束系数矩阵中，只要存在单位矩问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；阵，就可求得初始基可行解；（2）基变量确定后，目标函数和基变量均可表示成非基变量）基变量确定后，目标函数和基变量均可表示成非基变量的代数和形式（如的代数和形式（如(6)和和(5)），从而便于求出基可行解及相应的目标函），从而便于求出基可行解及相应的目标函数值。数值。第58页，讲稿共129张，创作于星期三592.最优性检验最优性检验考察变换后的目标函数
31、考察变换后的目标函数(6)式，非基变量式，非基变量x1、x2的系数都为正数，的系数都为正数，若让若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。变换成基变量。结论：结论：在非基变量的代数和形式表示的目标函数中，若非基变量的在非基变量的代数和形式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。当前的基可行解不是最优解。第59页，讲稿共129张，创作于星期三60当确定当确定x2为换入变量后，为换入变
32、量后，x1还是非基变量，故还是非基变量，故x10。现在要保。现在要保证证x3、x4、x5 0，即，即(5)当当x2min（8/2，12/4）=3（最小比值规则）（最小比值规则）可保证可保证x5=0则则x5为换出变量。为换出变量。新的基变量为新的基变量为x3、x4、x2，新的可行基为，新的可行基为B1(P3,P4,P2)确定换入变量：确定换入变量：一般选择正系数最大的非基变量为换入变量。一般选择正系数最大的非基变量为换入变量。确定换出变量：确定换出变量：（a）保证换出的变量取值为）保证换出的变量取值为0，变成非基量；，变成非基量；（b）其它的变量取值为非负。）其它的变量取值为非负。3.确定新的基
33、可行解（基变换）确定新的基可行解（基变换）第60页，讲稿共129张，创作于星期三614.旋转迭代旋转迭代基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量量x1、x5的代数和形式。可用高斯消去法实现。的代数和形式。可用高斯消去法实现。令非基变量令非基变量x10、x50，得到新的基可行解及相应的目标函数值，得到新的基可行解及相应的目标函数值，X(1)(0,3,2,16,0)T，Z(1)9。返回至第二步，直至求出最优解。返回至第二步，直至求出最优解。第61页，讲稿共129张，创作于星期三62这时目标函数的表达式是这时目标函数的表达
34、式是z=141.5x30.125x4，当将当将x1定为换入变量后定为换入变量后，继续利用上述方法确定换，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解出变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T，这时目标函数的表达式是这时目标函数的表达式是z=132x3+1/4x5，再经过一次迭代，再得到一个基可行解再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q3 将上述方程组求解过程，将上述方程组求解过程，用列表形式表达，即为线性用列表形式表达，即为
35、线性规划规划单纯形表。单纯形表。第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)2/3三、旋转运算三、旋转运算结论：旋转运算就是矩阵的初等变换，是高斯消元结论：旋转运算就是矩阵的初等变换，是高斯消元第63页，讲稿共129张，创作于星期三64结论：结论：如果如果LPLP问题通过单纯形法迭代到某步时，所
36、有检验数问题通过单纯形法迭代到某步时，所有检验数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-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
37、)XN=Z0+(cj-CBB-1Pj)xjxj为非基变量为非基变量四、检验数公式四、检验数公式第64页，讲稿共129张，创作于星期三65对于线性规划问题对于线性规划问题：MaxZ=CTXAX=b，X0，可用如下三个判别定理，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。来判别线性规划问题是否已经获得最优解或为无界解。判别定理判别定理1 1设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的为线性规划的最优解最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且
38、对于一切为线性规划的一个基可行解，且对于一切jJ（J为非为非基变量的下标集）有基变量的下标集）有j 0，同时有某个非基变量的检验数，同时有某个非基变量的检验数k=0(kJ)，则该线性规划有，则该线性规划有无穷多最优解无穷多最优解；设；设X为线性规划的一个基为线性规划的一个基可行解，且对于一切可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，则该，则该线性规划有线性规划有唯一最优解唯一最优解。判判别别定定理理3 3 设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划划问问题题具
39、具有有无无界界解解（无无最最优优解）解）。第65页，讲稿共129张，创作于星期三66一、步骤一、步骤Step1.化化LP问题为标准型问题为标准型,建立建立初始单纯形表初始单纯形表;Step2.若所有检验数若所有检验数0,则最优解已达到。则最优解已达到。否则否则,计算计算 ,选取选取k 所对应的变量所对应的变量xk 为为进基变进基变量量;Step3.计算计算 ,选取选取l 所对应的变量所对应的变量xl 为为出基变量出基变量;Step4.以以alk为主元素进行为主元素进行旋转运算旋转运算,转转Step2;第四节第四节 单纯形法的步骤单纯形法的步骤第66页，讲稿共129张，创作于星期三67cj CB
40、 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对于上述单纯形表：对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。个初始单位基。（2）从单纯形表中，可立即得到一个基可行解：从单纯形表中，可立即得到一
41、个基可行解：x1=b1,x2=b2,xm=bm,xm+1=xm+2=xn=0（3）用检验数的计算公式很容易计算检验数，并可根据三用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。题无最优解。第68页，讲稿共129张，创作于星期三692.2.进基变量的选择进基变量的选择cj c1c2cm cm+1ckcnCB XB b x1x2 xmxm+1xkxnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1k a1n010a2,m+1a2k a2n 001am,m+1amkamnj
42、-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-CBTB-1b000m+1k n选取选取 所对应的变量所对应的变量xl 为出基变量。为出基变量。第70页，讲稿共129张，创作于星期三714.4.旋转运算旋转运算cj c1cl cm
43、 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二、实例二、实例化为标准型化为标准型第72页，讲稿共129张，创作于星期三73单纯型表算法单纯型表算法 X(0)(0,0,8,16,12)T以以1为主元素进行旋转运算，为主元素进行旋
44、转运算，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主元列主元列主元行主元行0001/43140101600110-1/22X(1)(0,3,2,16,0)T200-3/4016/42/11第73页，讲稿共129张，创作于星期三74此时达到最优
45、解。此时达到最优解。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)(2,3,0,8,0)T以以2为主元素进行旋转运算，为主元素进行旋转运算，x5为为换入变量，换入变量，x4为换出变量为换出变量第74页，讲稿共129张，创作于
46、星期三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对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：刚好相反，如下所示：判别定理
47、判别定理1 1 设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非为非基变量的下标集）有基变量的下标集）有j0，则，则X为线性规划的为线性规划的最优解最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个非基变量的检验数，同时有某个非基变量的检验数k=0(kJ)，则该线性规划有，则该线性规划有无穷多最优解无穷多最优解；设；设X为线性规划的一个基为线性规划的一个基可行解，且对于一切可行解，且对于一切jJ（J为非基变量的下标集）有为非基变
48、量的下标集）有j 0，则该线，则该线性规划有性规划有唯一最优解唯一最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划划问问题题具具有有无无界界解解（无无最优解）最优解）。在进基可行解的转换过程中，进基变量的选取原则是：在进基可行解的转换过程中，进基变量的选取原则是：minj|j 0,而而k对对应列向量应列向量Pk0,则此则此LP问题有问题有无界解无界解.第96页，讲稿共129张，创作于星期三974.4.在最优表中出现某非基变量检验数为在最优表中出现某非基变量检验数为0 0（
49、无穷多最优解）（无穷多最优解）第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,仍可判断线性规划问题有无穷多最优解。仍可判断线性规划问题有无穷多最优解。第98页，讲稿共129张，创作于星期三99例例1 1 某工厂要用三种原材料
50、某工厂要用三种原材料D D、P P、H H混合调配出三种不同规格的产品混合调配出三种不同规格的产品A A、B B、C C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？如何安排生产使利润最大？产品产品名称名称规格要求规格要求单价单价(元元/kg）A原材料原材料D不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料D不少于不少于25%原材料原材料P不超过不超过50%35C不限不限25原材料原材料名称名称每天最多供每天最多供应量应量(kg)单价单价(元元/kg)D10065P10025H6035