运筹学线性规划与单纯形法课件.pptx

1、运筹学线性规划与单纯形法1感谢你的观看2019年5月21日教师：赵玮电话：2感谢你的观看2019年5月21日l数学要求l课程的地位与作用l运筹学概要3感谢你的观看2019年5月21日分支教材章节线性规划一，二，三，四，五，六线性整数规划八统筹法十一&2决策分析十五预测十六网络图论十4感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析5感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包

2、操l建模与案例分析例1、例2，基本概念模型的基本化6感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析基本原理图解法步骤最优解的几种类型7感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环8感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的

3、求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环三种元素算法的比较单纯形法求解思路最优解的搜索迭代过程与检验数迭代与基变换单纯形表计算单纯形表基变换的进一步认识9感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析图解法的灵敏度分析计算机解法的灵敏度分析10感谢你的观看2019年5月21日l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度

4、分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析对偶规划及其经济含义对偶规划基本理论对偶单纯形法算法比较影子价格11感谢你的观看2019年5月21日l基本概念 定义 研究概况l分支定界法的理论与算法基本思想算法与判别准则12感谢你的观看2019年5月21日l人力资源分配的问题例1.某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：班次i时间至少所需人数xi16:00-10:0060 x1210:00-14:0070 x2314:00-18:0060 x3418:00-22:0050 x4522:00-2:0030 x562:00-6:0030 x613感谢你的观看201

5、9年5月21日xi：实际安排司乘人员数 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务员？解：设xi表示第i班次时开始上班的司机和乘务人员数，这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数，例如有x1+x270。又要求这六个班次时开始上班的所有人员最少，既要求x1+x2+x3+x4+x5+x6最小，这样建立如下的数学模型：14感谢你的观看2019年5月21日目标函数：min z=(x1+x2+x3+x4+x5+x6)约束条件：61,03020506070606

6、55443322161jxxxxxxxxxxxxxj15感谢你的观看2019年5月21日l例2.某工厂在计划内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A,B两种原材料的消耗，以及资源的限制，如下表所示。产品资源产品产品资源限制设备(台时)11300台时原材料A(千克)21400千克原材料B(千克)01250千克单位产品利润(元)5010016感谢你的观看2019年5月21日 可以用x1和x2的线性函数形式来表示工厂所要求的最大利润的目标：max z=50 x1+100 x2其中max为最大化的符号（最小化符号为min)；50和100分别为单位产品、的利润。上式称为目标函数。同样

7、也可以用x1和x2的线性不等式来表示问题的一些约束条件。对于台时数方面的限制可以表示为：x1+x2300.同样，原材料的限量可以表示为 2x1+2x2400 x2250 17感谢你的观看2019年5月21日 暂不考虑市场需求。该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少个产品和产品才能使工厂获利最多？这个问题可以用以下的数学模型来加以描述。工厂目前要决策的问题是生产多少个产品和产品，把这个要决策的问题用变量x1、x2来表示，则称x1和x2为决策变量，即决策变量x1=生产产品的数量，决策变量x2=生产产品的数量。18感谢你的观看2019年5月21日 除

8、了上述约束外，显然还应该有x10，x20，因为产品、产品的产量是不能取负值的。综上所述，就得到了例1的数学模型如下：目标函数：max z=50 x1+100 x2 满足约束条件：0,025040023002122121xxxxxxx的约束决策变量的限制充分时的资源限制原料资源不的资源限制原料设备台时约束最佳运行目标获利BAmax19感谢你的观看2019年5月21日l模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。预测模型 评价模型 优化模型 仿真模型 20感谢你的观看2019年5月21日max z=50 x1+100 x2 xj生产产品j的数量0,02504002300212

9、2121xxxxxxx21感谢你的观看2019年5月21日min z=(x1+x2+x3+x4+x5+x6)xj：第j个班次司乘人员数61,0302050607060655443322161jxxxxxxxxxxxxxj22感谢你的观看2019年5月21日lLP四要素s.t：subject约束条件z称为目标函数xj称为决策变量max或min成为优化准则lLP def1：若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划。若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。23感谢你的观看2019年5月21日l

10、标准化LP模型的特点目标函数仅限与极大化（或极小化）所有约束条件均由等式表示所有决策变量限于取非负值每一约束不等式（或等式）之右端均为非负值24感谢你的观看2019年5月21日mibmjxbxaxaxabxaxaxabxaxaxat sxcxcxczijmnmnmmnnnnnn1,0,1,0.max221122222121112121112211mibnjxbxatsxczijnjijijnjjj1,01,0.max110.maxXbAXtsCXzmnmmnnTnTnnaaaaaaaaaAbbbbxxxXcccC212222111211,212121),(),(),(其中n：决策变量个数m：约

11、束方程个数25感谢你的观看2019年5月21日l约束方程的标准化（增加变量个数换取求解难度）26感谢你的观看2019年5月21日例非标准约束引入变量类型 标准形约束例1 x1+x2300松弛变量s10 x1+x2+s1=3002x1+x2400s202x1+x2+s2=400 x2250s30 x2+s3=250例2 x6+x160剩余变量s10 x6+x1-s1=60 x1+x270s20 x1+x2-s2=70 x2+x360s30 x2+x3-s3=60 x3+x450s10 x3+x4-s4=50 x4+x520s20 x4+x5-s5=20 x5+x630s30 x5+x6-s6=3

12、027感谢你的观看2019年5月21日ldef2：满足所有约束条件的解x称为LP的可行解，使目标函数z取得最大（小）的可行解x*称为LP的最优解，此时对应的目标函数值z(x*)称为LP的最优值。例1的解可行解（0，0），（50，250），（100，100），（200，0）.最优解（50，250）最优值z=50 x1+100 x2=27500元28感谢你的观看2019年5月21日l例1（标准化模型）0,2504002300.00010050max321213222112132121sssxxsxsxxsxxtssssxxz29感谢你的观看2019年5月21日l例2（标准化模型）61,0,3020

13、50607060min665554443332221161654321jsxsxxsxxsxxsxxsxxsxxxxxxxxzjj30感谢你的观看2019年5月21日(利用解析式与平面区域对应关系求解)l基本原理l图解法步骤l最优解的几种类型31感谢你的观看2019年5月21日解析式平面x1ox2上对应图形1 x=(x1,x2)点P2 x1=a直线L1 x2 L1x1aL1右半平面G1 G2 G1x1aL1左半平面G2 0 a x13 x2=b直线L1 x2 G1x2bL2右半平面G1 b G2 L2x2bL2左半平面G2 0 x14 ax1+bx2=c直线L3 L3 x2 G1ax1+bx2

14、cL3右半平面G1 G2ax1+bx2cL3左半平面G2 0 x15 z=ax1+bx2一族平行直线（等值线族）dtgkdkxbzxbax，截距斜率11232感谢你的观看2019年5月21日ldef3：满足LP中所有约束条件（不等式或等式约束）的点必在这些约束条件所对应区域所围成的公共区域D内，则称此公共区域D为LP的可行域。l例1 0100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D33感谢你的观看2019年5月21日l当目标函数z取z1，z2，z3时，直线 有相同的斜率和不同的截距，这一族平行直线称为等值

15、线族；目标函数按优化准则递增（或递减）的方向称为等值线族的法线方向。z=x1+x2=300称为等值线，因直线上的点（0，300），（300，0），（150，150），（100，200）等均具有相等的目标函数值300。bzxbaxbxaxzbzxbaxbxaxzbzxbaxbxaxz31221321221211221134感谢你的观看2019年5月21日l在平面x1ox2上求出LP的可行域l利用目标函数作等值线族l求出等值线的法线方向l等值线沿法线方向（max准则递增方向，min准则递减方向）移动，并使目标函数z到（max,min)时，其与可行域D相交之点即为最优解 点Bxxx)250,50()

16、,(*2*1*max1005010000100501500010050250001005027500211212213214xxzxxzxxzxxz35感谢你的观看2019年5月21日l唯一解l无穷多解l无界解l无最优解36感谢你的观看2019年5月21日0,2504002300.2122121xxxxxxxtsmax z=50 x1+100 x227500)()250,50(),()250,50(*2*1*xzxxxB最优值最优解最优点2112122132141005010000100501500010050250001005027500 xxzxxzxxzxxz01002003002001

17、00300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D37感谢你的观看2019年5月21日0,2504002300.2122121xxxxxxxts0100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)Dmax z=50 x1+50 x21500030050)(300),(:*2*1*2*1*2*1*xxzBCxxxxxBC最优值且位于其中最优解线段中任何点最优点38感谢你的观看2019年5月21日0,6231.212121xxxxxxtsmax z=x1+

18、x2)(,),(:*2*1*2*1*xxzxxx最优值）（最优解无穷远处之点最优点0123x2-3x1+2x2=6D321x1-x2=1z3=3=x1+x2x1z1=1=x1+x2z2=2=x1+x239感谢你的观看2019年5月21日亦无最优点故无最优解可行域GDD210,025040023002122121xxxxxxxmax z=50 x1+50 x20100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D1D235040感谢你的观看2019年5月21日l图解法的启示与计算机求解思路l需待解决的理论问题l基

19、本概念与理论l算法与求解l退化与循环41感谢你的观看2019年5月21日l最优解 在可行域D内（或边界）l最优解 在D的顶点或边界达到l求解思路设想：首先搜索D的顶点，然后通过顶点对应的目标值的比较来求解最优解xxx42感谢你的观看2019年5月21日计算机求解寻找Ax=b,非基变量=0之解（基本解）寻找max z=Cx，Ax=b，x0之解（最优解）寻找Ax=b,非基变量=0，x0之解（基本可行解）图解法（n3）可行点（D内点）顶点目标函数值比较？43感谢你的观看2019年5月21日ldef4：在 之LP中，若rank(A)=mn，则A（或对A作初等行变换）中必有m个线性武官的列向量，他们够成

20、满秩矩阵B(|B|0)，使有A=(B,N)（或(N,B)或其它），称B为A的一个基，此中N为A中除B外的子阵，相应的决策变量亦有x=(xB,xN)T，此中称xB中各分量为基变量，xN中各分量为非基变量，B中各列称为基向量，N中各列称为非基向量。l满足方程Ax=b，且取非基变量为0时的解称为LP基本解，满足非负条件（x 0）的基本解称为基本可行解，对应的基B称为可行基，满足 的解称为可行解。0 xbAxCxz0 xbAx44感谢你的观看2019年5月21日l例1.0,2504002300.10050max212212121xxxxxxxtsxxz0,2504002300.10050max3212

21、13222112121sssxxsxsxxsxxtsxxz0)250,400,300(.),(max0)0,0,100,(50,C10001000111102154321xbbAxtsxxxxxxCxzATT求A的基，基向量，非基向量，LP的基变量，非基变量，基本解，基本可行解，最优解，102535 CC45感谢你的观看2019年5月21日A的3阶子阵BjB1 1 1 1 2 1 0 0 1 0B2 1 1 1 2 1 0 0 1 1B3 1 1 0 2 0 0 0 0 1B4 1 1 0 1 0 0 1 0 1B5 1 0 0 0 1 0 0 0 1B6 1 1 0 2 1 1 0 1 0B

22、10是否基|B|0基变量x1,x2,s1x1,x2,s3x1,s1,s3x2,s1,s3s1,s2,s3s1,s2,s3非基变量s2,s3s1,s2x2,s2x1,s2x1,x2x1,x2基向量p1p2p3p1p2p5p1p3p5p2p3p5p3p4p5p2p3p5非基向量p4 p5p3 p4p2 p4p1 p4p1 p2p1 p4基本解(75,250,-25,0,0)T(100,200,0,0,50)T(200,0,100,0,250)T(0,400,-100,0,-100)T(0,0,300,400,250)T(0,400,-100,0,-100)T 是否基本可行解 是否可行解 是否最优解

23、2500010000 27500 xxxx46感谢你的观看2019年5月21日Tx)0,0,25,250,75(1Tnx)200,150,150,50,100(最优解基本可行解基本解可行解最优解基本可行解基本解可行解后述定理后述定理def4def4为基本解，但非可行解（x 0）为可行解，但非基本解xN=0?47感谢你的观看2019年5月21日最优解基本可行解基本解（在计算机上易于求得）满足满足x0逐个比较逐个比较目标函数值目标函数值48感谢你的观看2019年5月21日l什么条件下LP的可行域非空？可行域D有何特性？（Th1)l可行域D是否有顶点？顶点有多少个？顶点的数学含义？（Th2)l是否一

24、定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？l基本可行解是否存在？如何判断？（Th4)l基本可行解是否唯一对应D的一个顶点？（Th5)l如何求基本可行解？（Th6)49感谢你的观看2019年5月21日ldef5：设D为Rn中一点集，若对则称D为凸集。几何意义：凸集D内的任两点联线上的点仍在D内（含边界）ldef6：设D为Rn中一点集，则称z为凸集D的顶点。几何意义：凸集D的任何顶点都不可能在D内任两点的联线上。DxxzDxDx)2()1()2()1()1(,10,有及DxxzDxDxDz)2()1()2()1()1(,10,有及50感谢你的观看2019年5月21日凸集例顶点

25、个数有限有限无限有限无限非凸集例51感谢你的观看2019年5月21日lTh1：若rank(A)=mn，则LP的可行域 非空且为凸集nmijTnTnnaAbbbxxxxLPbAxt sccCCxz)(),(0),()(.),(max111101,|),(11njxmibxaxxxDjnjijijn，52感谢你的观看2019年5月21日lTh2：在LP中，若可行域D为非空凸集时，则D中至少有一个顶点，且顶点个数为有限。lTh3：在LP中，若可行域D为非空凸集且有界时，则LP最优解必在D的顶点上达到。lTh4：在LP中，若有可行解（即D非空），则LP至少有一基本可行解。lTh5：x是LP的基本可行解

26、 x是LP可行域D的顶点uTh1Th5解决了上述问题（1）（5）53感谢你的观看2019年5月21日l什么条件下LP的可行域非空？可行域D有何特性？（Th1)l可行域D是否有顶点？顶点有多少个？顶点的数学含义？（Th2)l是否一定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？l基本可行解是否存在？如何判断？（Th4)l基本可行解是否唯一对应D的一个顶点？（Th5)l如何求基本可行解？（Th6)54感谢你的观看2019年5月21日lTh6：见后（基本可行解是否为最优解的判别法则，及无最优解的判别）。lTh7：求解过程中基本可行解迭代准则lTh8：最优解的线性组合lTh9：无穷多组

27、解的判断55感谢你的观看2019年5月21日l三种主流算法的比较l单纯形法求解思路l最优解的搜索思路l迭代过程与检验数l迭代与基变换l单纯形表计算l基变换的进一步认识56感谢你的观看2019年5月21日算法名称作者求解思路理论评价1单纯形法G.B.Dantzig(1947)解等式方程,从表面摸索前进Th1Th72橢球法.(1974)解不等式方程略 3内点法N.A.Karmarhart(1954)解等式方程从D内点搜索前进略？57感谢你的观看2019年5月21日l非主流算法：修正单纯形法，阶段法，M法，对偈单纯形法（均为单纯形发法变型），随机搜索法等。l1l算法复杂性定义：在输入规模均为L的所有

28、可能问题中，在最坏的情况下，算法需要执行的基本运算总次数f(L)，称为该算法的计算时间复杂性，简称复杂性。耗费时间多少仅考虑算法执行的基本运算次数（指+、大小比较、转移指令）满足精度要求下排除计算机性能因素消除LP规模因素评价算法好坏58感谢你的观看2019年5月21日nmijaAxbAxtscxz)(0.maxnmarank)()0(,N)(B,Ax,1NBNBxbBxbxxB可解出由存在基 空且为凸集非可行域DLP有限个顶点有可行域DLP的顶点上达到最优解在DLP有解凸集且非空D标函数比较）本可行解，并作目逐个搜索顶点（基计算机计算机求解思路求解思路 0)0,(0BxxxbAxB存在基本可

29、行解有限个条件非负满足Bx存在可行解0 xbAx0),0,(BxxbAxB基本解存在，?显然Th1Th4Th6Th5Th259感谢你的观看2019年5月21日0|B1E点顶lE点顶B基 0B可行基初始 1B 2BlB最优解最优性准则直到满足xxl 基本解 00Ex顶点可行解初始基本 1x2xlxA2E点顶lE点顶.解的迭代解的迭代60感谢你的观看2019年5月21日l枚举所有的顶点作比较是不可行的，因为若 ，则D可能有 个可能顶点（基本解）。m阶子阵nmijaA)(mnCmnC35C39C320C3100C4100C值10841140161700 392122561感谢你的观看2019年5月2

30、1日l为使计算机能自动变更顶点，注意到两个相邻顶点对应的可行基仅有一个列向量不同的特点（可以证明，高等几何），故在已得到一个顶点（对应一个基本可行解或一个可行解）后，只需变更一个列向量，使其仍为一个基本可行解（顶点）即可。62感谢你的观看2019年5月21日l若 ，则一顶点的相邻顶点有n个，究竟哪一个相邻顶点作为迭代的首选？这种迭代过程（由一个顶点到另一个顶点）应保证有以下不等式才能是有效的算法：，故需研究判断 的算法。l应寻找这种迭代的终止规则（称为最优性准则）。nRx)(.)()()(210lxzxzxzxz)()(1jjxzxz63感谢你的观看2019年5月21日l命题：若 ，任取A的m

31、阶子阵，设 则目标函数 必可由非基变量 描述。nmArank)(量为非基变量构成之列向为基变量构成之列向量TnmNTmBxxxxxxx),.(),.,(121mjjjxcxz1)(Nx64感谢你的观看2019年5月21日l证：rank(A)=m0，则称 是非退化的，若 中有一个或多个基变量分量取0，则称 为退化的，若LP的每一个基本可行解都是非退化的，则称LP为非退化的。),(NBxxx xBxx97感谢你的观看2019年5月21日l 当采用单纯形法求解时，若在迭代过程中出现了退化的基本可行解，则继续迭代下去可能产生如下三种结果：退化是暂时的，最终得到非退化的最优解（如例5）。最后得到退化的最

32、优解。产生循环（Cycling）,目标函数得不到改善，永远得不到最优解（如例6）。98感谢你的观看2019年5月21日lTh10：若LP是非退化的，则经过有限步单纯形迭代后，或者能判定LP没有最优解，或者能够求得最优解。l即使基本可行解是非退化的，但在确定出基变量时，若有两个（或两个以上）比值（对应不同行）相等时，当采用min准则选出基变量时，仍有可能使新的基本可行基成为退化解，如i=0时，xB0=(2,4,3)T为非退化解，出现min比值=min2/1,4/2,3/1=2/1或4/2，此时可选s1或s2 作出基变量。由上表当选s1为出基变量时，经基变换由i=1之表知有xB0=(2,0，1)T

33、，显然此为退化解。99感谢你的观看2019年5月21日4)()()(),()1,0,2()1,0,2(),()1,0,2()3()2()1(331321321xzxzxzsxxxxssxxTTBTBTTB均为退化解l 。由上表知此时虽经多次迭代，但目标函数无改进，但由于未产生循环现象，经4次迭代后得最优解：5)()()0,0,1,2,0,1(),()4(321321)4(xzxzsssxxxxxTT100感谢你的观看2019年5月21日0)()()()()()()()()()()6()5()4()3()2()1()0()0()0()6()6(xzxzxzxzxzxzxzbAbAbAl例6 则由

34、于退化基本可行解而出现了循环现象，可证明例6之LP有最优解，但经过6次迭代有 目标函数未得到改进而未能求得最优解。101感谢你的观看2019年5月21日0,3422.232max321321312121xxxxxxxxxxtsxxzl例5102感谢你的观看2019年5月21日迭代数ixBCBx1x2x3s1s2s3b(i)比值203/20000s101-1010022/1s2020101044/2s3011100133/1zj0000000j203/20001x121-101002/s20021-21000/2s30021-10111/2zj2-20200j023/2-2002x12101/2

35、01/2022/(1/2)x20011/2-11/2000/(1/2)s300001-111/zj2010104j001/20-103x121-1010022/1x33/2021-2100/s300001-1111/1zj213/2-13/204j0-1013/204x121-1001-11x33/20210-122s100001-111zj213/201/215j0-100-1/2-1无改进103感谢你的观看2019年5月21日l例6.(P97，E.beale给出的循环例）l本例与教材（P97）变量对应表71,010312098.620max7364321212154321414321214

36、3jxxxxxxxxxxxxxtsxxxxzj教材（P97）x1x2x3x4x5x6x7本例x4x5x6x7x1x2x3104感谢你的观看2019年5月21日ixBiCBix1x2x3x4x5x6x7b(i)比值Cj3/4-201/2-60000 x501/4-8-1910000/(1/4)x601/2-12-1/2301000/(1/2)x7000100011/j(0)3/4-201/2-6000z(x(0)=01x13/41-32-4364000/x60043/2-15-21000 x7000100011/j(1)047/2-33-300z(x(1)=02x13/4108-84-12800

37、0 x2-20013/8-15/4-1/21/4000 x70001000111j(2)002-18-1-10z(x(2)=03x31/21/801-21/2-3/2100/x2-20-3/64103/161/16-1/8000 x70-1/80021/23/2-1112/21j(3)-1/40032-30z(x(3)=04x31/2-5/256102-6000 x4-6-1/416/3011/3-2/3000 x705/2-5600-2611/j(4)1/2-16001-10z(x(4)=05x50-5/4281/201-300/x4-61/6-4-1/6101/3000 x70001000

38、11/j(5)7/4-44-1/20020z(x(5)=06x501/4-8-1910000/(1/4)x601/2-12-1/2301000/(1/2)x7000100011/j(6)3/4-201/2-6000z(x(6)=0循循环环105感谢你的观看2019年5月21日B1B2B3B4B5B6B0B0=A(6)=A(0)，b(6)=b(0)106感谢你的观看2019年5月21日l为避免循环可用摄动法（由A.Charnes于1952年提出）也可用布兰德（R.G.Bland）提出的反循环法（1976年）或Dantzig（1954年）提出的字典法来解决。107感谢你的观看2019年5月21日l

39、Bland法则如下：当所有变量均按x1,x2,xn排序时，若有若干个检验数均为正时，可选其中下标最小的非基变量作为入基变量，即取k=min j|j 0为入基变量之下标，xK为入基变量。若有若干个比值同时达到极小时，可选其中下标最小的基变量为出基变量，即取 为出 基变量下标。min|min0iKiagKgababglik108感谢你的观看2019年5月21日0,6002125350.32max0,6002125350.32min0,6002125350.32min213212132122111212121321213212112121212112121aasssxxsxxasxasxxtsMaM

40、axxzsssxxsxxsxsxxtsxxfxxxxxxxtsxxfl 例7.(P85)109感谢你的观看2019年5月21日l 解1迭代数ixBCBx1x2s1s2s3a1a2b(i)比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-1001125125/1s302100100600600/2zj-2M-MMM0-M-M-475Mj-2+2M-3+M-M-M0001a1-M01-1101-1225225/1x1-2100-1001125/s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250j0-3+M-MM-2002-2

41、M2a1-M01/2-10-1/2105050/(1/2)x1-211/2001/200300300/(1/2)s2001/2011/20-1175175/(1/2)zj-2-M/2-1M0M/2-1-M0-50M-600j0M/2-2-M0-M/2-10-M3x2-301-20-120100 x1-210101-10250s2000111-1-1125zj-2-3401-40-800j00-40-1-M+4-M110感谢你的观看2019年5月21日l人工变量引入的准则：u人工变量的引入应不影响约束条件，也不影响目标函数的求解u为构成基B=I，A中缺K个单位向量就引入K个人工变量（上例缺2个）

42、l人工变量引入后，为不影响约束方程应使 的最优解中人工变量为非基变量（即取 ）l由于人工变量的引入为构成基I=B，故第0次迭代时 已成为基变量，因此在 以后的迭代过程中应尽可能将 从基变量中替换出来而成为非基变量，从而保证基本可行解分量 。LP0jaLPjaja0ja111感谢你的观看2019年5月21日l将目标函数设计成下型：即能满足上述要求。这是由于只要 迭代过程中，若基变量含有一个人工变量，则上述设计的目标函数z(x)就不可能达到极大化（max），因此只要不出现退化现象，在经有限次迭代后总可将引入的人工变量一个一个地替换出来，而成为非基变量。因而有 如此的 ，其最优解与LP最优解相同（）

43、。1,)(11MaMxCxzlKKnjjjLPLP)1(0ljaj0jaLP112感谢你的观看2019年5月21日lM 1故不必考虑其具体数值。本方法称为大M法来源与此。l若 在某一次迭代中，仍然为基变量，则目标函数 （此时 为基本可行解之一分量应满足非负条件 ），从而使此基本可行解不可能是最优解。约束方程。容易验证满足），（LPxxzxfxzsssxxxTT800)()(800)(01250100250),(32121)(xzja0jaja113感谢你的观看2019年5月21日l若采用大M法始终无法将人工变量从基变量替换出来，此时有两种情形：u所有检验数已有 ，此时应认为无解。u上述最优性条

44、件仍未具备，需始终迭代下去，或改用其它方法。0)(ljj114感谢你的观看2019年5月21日l例7.解20,6002125350.32min32max32121321211212121sssxxsxxsxsxxtsxxfxxfz115感谢你的观看2019年5月21日ixBiCBix1x2s1s2s3b(i)比值-2-30000111-100350100-10125210016000211-100350100-101251010125003x2-301-110225225x1-2100-10125/s3000111125125z(0)-2-33-10-925(0)00-3101x2-301-2

45、0-1100 x1-210101250s2000111125z(1)-2-3401-800(1)00-40-1116感谢你的观看2019年5月21日800)()(800)(01250100250),(32121xzxfxzsssxxxTT），（117感谢你的观看2019年5月21日l为使b0，同时又可形成基B0=I，可在原增广矩阵（A0：b0）基础上作初等行变换以形成人工基B0=I。l 。不可混淆。对应的基变量对应的基变量应对应对应的基变量列中的第一、二、三行形成人工基后100,010,001,332211BBBBBBBBCxCxCxCxii118感谢你的观看2019年5月21日l此经一次迭代

46、即可得最优解l将约束方程变形成下述，虽然保证有一个B0=I，但约束方程右端的b(i)0非负条件被破坏，从而使用单纯形法时，获得的可行解虽然是基本解，但非基本可行解。易知此非基本可行解，故采用单纯形法无效。800)()(800)(01250100250),(32121xzxfxzsssxxxTT），（TTTBBBBsssxxxsssxxxxsxxsxsxx)600,125,350,0,0(),(),(),(60021253500302010201)0(3321321211210302010可得相应基本解此时取119感谢你的观看2019年5月21日l例8.(P88，无最优解例）l解：引入松弛变量s

47、1，s2，剩余变量s3，人工变量a1，可得上述标准型。0,4030150103.0,4030150103.3020max3020max132121132121121212112112121asssxxasxxsxsxxtsxxxxxxxtsMaxxzxxz120感谢你的观看2019年5月21日迭代迭代次数次数i基变基变量量xBiCBix1x2s1s2s3a1b(i)比值比值2030000-M0s103101000150150/10s2010010030/a1-M1100-114040/1z(0)-M-M00M-M-40Mj(0)20+M30+M00-M01x2303/1011/10000151

48、5/(3/10)s201001003030/1a1-M7/100-1/100-112525/(7/10)z(0)9-7/10M303+M/100M-M450-25Mj(0)11+7/10M0-3-M/100-M02x230011/10-3/10006X1010010030a1-M00-1/10-7/10-114z(0)20303+M/1011+7M/10M-M780-4Mj(0)00-3-M/10-11-7M/10-M0121感谢你的观看2019年5月21日l当M0，经二次迭代后，已有 ，按照一般原理下有下述的x(2)=(30,6,0,0,4)T应为最优解，并迭代终止。l .虽然有z(x0)z

49、(x1)z(x2)目标值早增大，但根据大M法原理应将人工变量以基变量xB中替换出来，而i=2时，由上表知a1仍为基变量，故此时应认为无最优解0jj有ix(i)z(x(i)x1ix2is1is2is3ia1i000150 30040-40M1015 030025450-25M23060004780-4M122感谢你的观看2019年5月21日l事实上由图解法知该问题无可行解。或将。式可行域，但不满足不等代入)4036630(,406,302221212221xxxxLPxx0102030504010203040D1D2x2x13x1+10 x2=150 x1+x2=40 x1=300,300,40

50、21121xxxxx0,3015010321121xxxxx123感谢你的观看2019年5月21日l图解法下的灵敏度分析定义：研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化（局部或全部变动）对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析。由于C，b，A通常表述产品需求，原材料价格，未来的商品售价及企业的加工能力、资源消耗，故在数学建模时的估计有可能出现误差，且未来的环境亦是不确定的，有可能出现变化，因此有必要对应用问题的解作灵敏度分析。x)(xz124感谢你的观看2019年5月21日l图解法下的灵敏度分析灵敏度分析通常讨论如下内容：C，b，A变动（局部