1、1运筹学线性规划与单纯形法感谢你的观看2019年7月32教师：赵玮电话：感谢你的观看2019年7月33l数学要求l课程的地位与作用l运筹学概要感谢你的观看2019年7月34分支教材章节线性规划一，二，三，四，五，六线性整数规划八统筹法十一&2决策分析十五预测十六网络图论十感谢你的观看2019年7月35l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析感谢你的观看2019年7月36l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析
2、例1、例2，基本概念模型的基本化感谢你的观看2019年7月37l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析基本原理图解法步骤最优解的几种类型感谢你的观看2019年7月38l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环感谢你的观看2019年7月39l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶
3、规划lLP求解步骤与OR软件包操l建模与案例分析图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环三种元素算法的比较单纯形法求解思路最优解的搜索迭代过程与检验数迭代与基变换单纯形表计算单纯形表基变换的进一步认识感谢你的观看2019年7月310l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软件包操l建模与案例分析图解法的灵敏度分析计算机解法的灵敏度分析感谢你的观看2019年7月311l问题与建模l二维线性规划图解法l计算机解法l极小化下的求解与大M法l灵敏度分析l对偶规划lLP求解步骤与OR软
4、件包操l建模与案例分析对偶规划及其经济含义对偶规划基本理论对偶单纯形法算法比较影子价格感谢你的观看2019年7月312l基本概念 定义 研究概况l分支定界法的理论与算法 基本思想 算法与判别准则感谢你的观看2019年7月313l人力资源分配的问题例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 x6感谢你的观看2019年7月314xi：实际安排司乘人员数 设司
5、机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务员？解：设xi表示第i班次时开始上班的司机和乘务人员数，这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数，例如有x1+x270。又要求这六个班次时开始上班的所有人员最少，既要求x1+x2+x3+x4+x5+x6最小，这样建立如下的数学模型：感谢你的观看2019年7月315目标函数：min z=(x1+x2+x3+x4+x5+x6)约束条件：61,0302050607060655443322161jxxxxxxxxxxxx
6、xj感谢你的观看2019年7月316l例2.某工厂在计划内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A,B两种原材料的消耗，以及资源的限制，如下表所示。产品资源产品产品资源限制设备(台时)11300台时原材料A(千克)21400千克原材料B(千克)01250千克单位产品利润(元)50100感谢你的观看2019年7月317 可以用x1和x2的线性函数形式来表示工厂所要求的最大利润的目标：max z=50 x1+100 x2其中max为最大化的符号（最小化符号为min)；50和100分别为单位产品、的利润。上式称为目标函数。同样也可以用x1和x2的线性不等式来表示问题的一些约束条件。
7、对于台时数方面的限制可以表示为：x1+x2300.同样，原材料的限量可以表示为 2x1+2x2400 x2250 感谢你的观看2019年7月318 暂不考虑市场需求。该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少个产品和产品才能使工厂获利最多？这个问题可以用以下的数学模型来加以描述。工厂目前要决策的问题是生产多少个产品和产品，把这个要决策的问题用变量x1、x2来表示，则称x1和x2为决策变量，即决策变量x1=生产产品的数量，决策变量x2=生产产品的数量。感谢你的观看2019年7月319 除了上述约束外，显然还应该有x10，x20，因为产品、产品的产量是
8、不能取负值的。综上所述，就得到了例1的数学模型如下：目标函数：max z=50 x1+100 x2 满足约束条件：0,025040023002122121xxxxxxx的约束决策变量的限制充分时的资源限制原料资源不的资源限制原料设备台时约束最佳运行目标获利BAmax感谢你的观看2019年7月320l模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。预测模型 评价模型 优化模型 仿真模型 感谢你的观看2019年7月321max z=50 x1+100 x2 xj生产产品j的数量0,025040023002122121xxxxxxx感谢你的观看2019年7月322min z=(x1
9、+x2+x3+x4+x5+x6)xj：第j个班次司乘人员数61,0302050607060655443322161jxxxxxxxxxxxxxj感谢你的观看2019年7月323lLP四要素 s.t：subject约束条件 z称为目标函数 xj称为决策变量 max或min成为优化准则lLP def1：若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划。若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。感谢你的观看2019年7月324l标准化LP模型的特点 目标函数仅限与极大化（或极小化）所有约束条件均由等式表
10、示 所有决策变量限于取非负值 每一约束不等式（或等式）之右端均为非负值感谢你的观看2019年7月325mibmjxbxaxaxabxaxaxabxaxaxat sxcxcxczijmnmnmmnnnnnn1,0,1,0.max221122222121112121112211mibnjxbxatsxczijnjijijnjjj1,01,0.max110.maxXbAXtsCXzmnmmnnTnTnnaaaaaaaaaAbbbbxxxXcccC212222111211,212121),(),(),(其中n：决策变量个数m：约束方程个数感谢你的观看2019年7月326l约束方程的标准化（增加变量个数
11、换取求解难度）感谢你的观看2019年7月327例非标准约束引入变量类型 标准形约束例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=30感谢你的观看2019年7月328ldef2：满足所有约束条件的解x称为LP的可行
12、解，使目标函数z取得最大（小）的可行解x*称为LP的最优解，此时对应的目标函数值z(x*)称为LP的最优值。例1的解可行解（0，0），（50，250），（100，100），（200，0）.最优解（50，250）最优值z=50 x1+100 x2=27500元感谢你的观看2019年7月329l例1（标准化模型）0,2504002300.00010050max321213222112132121sssxxsxsxxsxxtssssxxz感谢你的观看2019年7月330l例2（标准化模型）61,0,302050607060min665554443332221161654321jsxsxxsxxsxx
13、sxxsxxsxxxxxxxxzjj感谢你的观看2019年7月331(利用解析式与平面区域对应关系求解)l基本原理l图解法步骤l最优解的几种类型感谢你的观看2019年7月332解析式平面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+bx2cL3右半平面G1 G2ax1+bx2cL3左半平面G2 0 x15 z=ax1+bx2一族平行直线（
14、等值线族）dtgkdkxbzxbax，截距斜率112感谢你的观看2019年7月333ldef3：满足LP中所有约束条件（不等式或等式约束）的点必在这些约束条件所对应区域所围成的公共区域D内，则称此公共区域D为LP的可行域。l例1 0100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D感谢你的观看2019年7月334l当目标函数z取z1，z2，z3时，直线 有相同的斜率和不同的截距，这一族平行直线称为等值线族；目标函数按优化准则递增（或递减）的方向称为等值线族的法线方向。z=x1+x2=300称为等值线，因直线上
15、的点（0，300），（300，0），（150，150），（100，200）等均具有相等的目标函数值300。bzxbaxbxaxzbzxbaxbxaxzbzxbaxbxaxz312213212212112211感谢你的观看2019年7月335l在平面x1ox2上求出LP的可行域l利用目标函数作等值线族l求出等值线的法线方向l等值线沿法线方向（max准则递增方向，min准则递减方向）移动，并使目标函数z到（max,min)时，其与可行域D相交之点即为最优解 点Bxxx)250,50(),(*2*1*max10050100001005015000100502500010050275002112122
16、13214xxzxxzxxzxxz感谢你的观看2019年7月336l唯一解l无穷多解l无界解l无最优解感谢你的观看2019年7月3370,2504002300.2122121xxxxxxxtsmax z=50 x1+100 x227500)()250,50(),()250,50(*2*1*xzxxxB最优值最优解最优点2112122132141005010000100501500010050250001005027500 xxzxxzxxzxxz0100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D感谢你的观看
17、2019年7月3380,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最优值且位于其中最优解线段中任何点最优点感谢你的观看2019年7月3390,6231.212121xxxxxxtsmax z=x1+x2)(,),(:*2*1*2*1*xxzxxx最优值）（最优解无穷远处之点最优点0123x2-3x1+2x2=6D321x1-x
18、2=1z3=3=x1+x2x1z1=1=x1+x2z2=2=x1+x2感谢你的观看2019年7月340亦无最优点故无最优解可行域GDD210,025040023002122121xxxxxxxmax z=50 x1+50 x20100200300200100300400 x1+x2=3002x1+x2=400 x2=250B(50,250)C(100,200)D1D2350感谢你的观看2019年7月341l图解法的启示与计算机求解思路l需待解决的理论问题l基本概念与理论l算法与求解l退化与循环感谢你的观看2019年7月342l最优解 在可行域D内（或边界）l最优解 在D的顶点或边界达到l求解思
19、路设想：首先搜索D的顶点，然后通过顶点对应的目标值的比较来求解最优解xxx感谢你的观看2019年7月343计算机求解寻找Ax=b,非基变量=0之解（基本解）寻找max z=Cx，Ax=b，x0之解（最优解）寻找Ax=b,非基变量=0，x0之解（基本可行解）图解法（n3）可行点（D内点）顶点目标函数值比较？感谢你的观看2019年7月344ldef4：在 之LP中，若rank(A)=mn，则A（或对A作初等行变换）中必有m个线性武官的列向量，他们够成满秩矩阵B(|B|0)，使有A=(B,N)（或(N,B)或其它），称B为A的一个基，此中N为A中除B外的子阵，相应的决策变量亦有x=(xB,xN)T，
20、此中称xB中各分量为基变量，xN中各分量为非基变量，B中各列称为基向量，N中各列称为非基向量。l满足方程Ax=b，且取非基变量为0时的解称为LP基本解，满足非负条件（x 0）的基本解称为基本可行解，对应的基B称为可行基，满足 的解称为可行解。0 xbAxCxz0 xbAx感谢你的观看2019年7月345l例1.0,2504002300.10050max212212121xxxxxxxtsxxz0,2504002300.10050max321213222112121sssxxsxsxxsxxtsxxz0)250,400,300(.),(max0)0,0,100,(50,C100010001111
21、02154321xbbAxtsxxxxxxCxzATT求A的基，基向量，非基向量，LP的基变量，非基变量，基本解，基本可行解，最优解，102535 CC感谢你的观看2019年7月346A的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 0B10是否基|B|0基变量x1,x2,s1x1,x2,s3x1,s1,s3x2,s1,s3s1,s2,s3s1,s2,s3非基变量s2,s3s1,s2x2,s2
22、x1,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 是否基本可行解 是否可行解 是否最优解2500010000 27500 xxxx感谢你的观看2019年7月347Tx)0,0,25,250,75(1Tnx)200,150,150,50,100(最
23、优解基本可行解基本解可行解最优解基本可行解基本解可行解后述定理后述定理def4def4为基本解，但非可行解（x 0）为可行解，但非基本解xN=0?感谢你的观看2019年7月348最优解基本可行解基本解（在计算机上易于求得）满足满足x0逐个比较逐个比较目标函数值目标函数值感谢你的观看2019年7月349l什么条件下LP的可行域非空？可行域D有何特性？（Th1)l可行域D是否有顶点？顶点有多少个？顶点的数学含义？（Th2)l是否一定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？l基本可行解是否存在？如何判断？（Th4)l基本可行解是否唯一对应D的一个顶点？（Th5)l如何求基本可行
24、解？（Th6)感谢你的观看2019年7月350ldef5：设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,有及感谢你的观看2019年7月351凸集例顶点个数有限有限无限有限无限非凸集例感谢你的观看2019年7月352lTh1：若rank(A)=mn，则LP的可行域 非空且为凸集nmijTnTnnaAbbbxxxxLPbAxt s
25、ccCCxz)(),(0),()(.),(max111101,|),(11njxmibxaxxxDjnjijijn，感谢你的观看2019年7月353lTh2：在LP中，若可行域D为非空凸集时，则D中至少有一个顶点，且顶点个数为有限。lTh3：在LP中，若可行域D为非空凸集且有界时，则LP最优解必在D的顶点上达到。lTh4：在LP中，若有可行解（即D非空），则LP至少有一基本可行解。lTh5：x是LP的基本可行解 x是LP可行域D的顶点uTh1Th5解决了上述问题（1）（5）感谢你的观看2019年7月354l什么条件下LP的可行域非空？可行域D有何特性？（Th1)l可行域D是否有顶点？顶点有多少
26、个？顶点的数学含义？（Th2)l是否一定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？l基本可行解是否存在？如何判断？（Th4)l基本可行解是否唯一对应D的一个顶点？（Th5)l如何求基本可行解？（Th6)感谢你的观看2019年7月355lTh6：见后（基本可行解是否为最优解的判别法则，及无最优解的判别）。lTh7：求解过程中基本可行解迭代准则lTh8：最优解的线性组合lTh9：无穷多组解的判断感谢你的观看2019年7月356l三种主流算法的比较l单纯形法求解思路l最优解的搜索思路l迭代过程与检验数l迭代与基变换l单纯形表计算l基变换的进一步认识感谢你的观看2019年7月357
27、算法名称作者求解思路理论评价1单纯形法G.B.Dantzig(1947)解等式方程,从表面摸索前进Th1Th72橢球法.(1974)解不等式方程略 3内点法N.A.Karmarhart(1954)解等式方程从D内点搜索前进略？感谢你的观看2019年7月358l非主流算法：修正单纯形法，阶段法，M法，对偈单纯形法（均为单纯形发法变型），随机搜索法等。l1l算法复杂性定义：在输入规模均为L的所有可能问题中，在最坏的情况下，算法需要执行的基本运算总次数f(L)，称为该算法的计算时间复杂性，简称复杂性。耗费时间多少仅考虑算法执行的基本运算次数（指+、大小比较、转移指令）满足精度要求下排除计算机性能因素
28、消除LP规模因素评价算法好坏感谢你的观看2019年7月359nmijaAxbAxtscxz)(0.maxnmarank)()0(,N)(B,Ax,1NBNBxbBxbxxB可解出由存在基 空且为凸集非可行域DLP有限个顶点有可行域DLP的顶点上达到最优解在DLP有解凸集且非空D标函数比较）本可行解，并作目逐个搜索顶点（基计算机计算机求解思路求解思路 0)0,(0BxxxbAxB存在基本可行解有限个条件非负满足Bx存在可行解0 xbAx0),0,(BxxbAxB基本解存在，?显然Th1Th4Th6Th5Th2感谢你的观看2019年7月3600|B1E点顶lE点顶B基 0B可行基初始 1B 2Bl
29、B最优解最优性准则直到满足xxl 基本解 00Ex顶点可行解初始基本 1x2xlxA2E点顶lE点顶.解的迭代解的迭代感谢你的观看2019年7月361l枚举所有的顶点作比较是不可行的，因为若 ，则D可能有 个可能顶点（基本解）。m阶子阵nmijaA)(mnCmnC35C39C320C3100C4100C值10841140161700 3921225感谢你的观看2019年7月362l为使计算机能自动变更顶点，注意到两个相邻顶点对应的可行基仅有一个列向量不同的特点（可以证明，高等几何），故在已得到一个顶点（对应一个基本可行解或一个可行解）后，只需变更一个列向量，使其仍为一个基本可行解（顶点）即可。
30、感谢你的观看2019年7月363l若 ，则一顶点的相邻顶点有n个，究竟哪一个相邻顶点作为迭代的首选？这种迭代过程（由一个顶点到另一个顶点）应保证有以下不等式才能是有效的算法：，故需研究判断 的算法。l应寻找这种迭代的终止规则（称为最优性准则）。nRx)(.)()()(210lxzxzxzxz)()(1jjxzxz感谢你的观看2019年7月364l命题：若 ，任取A的m阶子阵，设 则目标函数 必可由非基变量 描述。nmArank)(量为非基变量构成之列向为基变量构成之列向量TnmNTmBxxxxxxx),.(),.,(121mjjjxcxz1)(Nx感谢你的观看2019年7月365l证：rank
31、(A)=m0，则称 是非退化的，若 中有一个或多个基变量分量取0，则称 为退化的，若LP的每一个基本可行解都是非退化的，则称LP为非退化的。),(NBxxx xBxx感谢你的观看2019年7月398l 当采用单纯形法求解时，若在迭代过程中出现了退化的基本可行解，则继续迭代下去可能产生如下三种结果：退化是暂时的，最终得到非退化的最优解（如例5）。最后得到退化的最优解。产生循环（Cycling）,目标函数得不到改善，永远得不到最优解（如例6）。感谢你的观看2019年7月399lTh10：若LP是非退化的，则经过有限步单纯形迭代后，或者能判定LP没有最优解，或者能够求得最优解。l即使基本可行解是非退
32、化的，但在确定出基变量时，若有两个（或两个以上）比值（对应不同行）相等时，当采用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，显然此为退化解。感谢你的观看2019年7月31004)()()(),()1,0,2()1,0,2(),()1,0,2()3()2()1(331321321xzxzxzsxxxxssxxTTBTBTTB均为退化解l 。由上表知此时虽经多次迭代
33、，但目标函数无改进，但由于未产生循环现象，经4次迭代后得最优解：5)()()0,0,1,2,0,1(),()4(321321)4(xzxzsssxxxxxTT感谢你的观看2019年7月31010)()()()()()()()()()()6()5()4()3()2()1()0()0()0()6()6(xzxzxzxzxzxzxzbAbAbAl例6 则由于退化基本可行解而出现了循环现象，可证明例6之LP有最优解，但经过6次迭代有 目标函数未得到改进而未能求得最优解。感谢你的观看2019年7月31020,3422.232max321321312121xxxxxxxxxxtsxxzl例5感谢你的观看2
34、019年7月3103迭代数ixBCBx1x2x3s1s2s3b(i)比值203/20000s101-1010022/1s2020101044/2s3011100133/1zj0000000j203/20001x121-101002/s20021-21000/2s30021-10111/2zj2-20200j023/2-2002x12101/201/2022/(1/2)x20011/2-11/2000/(1/2)s300001-111/zj2010104j001/20-103x121-1010022/1x33/2021-2100/s300001-1111/1zj213/2-13/204j0-10
35、13/204x121-1001-11x33/20210-122s100001-111zj213/201/215j0-100-1/2-1无改进感谢你的观看2019年7月3104l例6.(P97，E.beale给出的循环例）l本例与教材（P97）变量对应表71,010312098.620max73643212121543214143212143jxxxxxxxxxxxxxtsxxxxzj教材（P97）x1x2x3x4x5x6x7本例x4x5x6x7x1x2x3感谢你的观看2019年7月3105ixBiCBix1x2x3x4x5x6x7b(i)比值Cj3/4-201/2-60000 x501/4-8
36、-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-128000 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-
37、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 x7000100011/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循循环环感谢你的观看2019年7月
38、3106B1B2B3B4B5B6B0B0=A(6)=A(0)，b(6)=b(0)感谢你的观看2019年7月3107l为避免循环可用 摄动法（由A.Charnes于1952年提出）也可用布兰德（R.G.Bland）提出的反循环法（1976年）或Dantzig（1954年）提出的字典法来解决。感谢你的观看2019年7月3108lBland法则如下：当所有变量均按x1,x2,xn排序时，若有若干个检验数均为正时，可选其中下标最小的非基变量作为入基变量，即取k=min j|j 0为入基变量之下标，xK为入基变量。若有若干个比值同时达到极小时，可选其中下标最小的基变量为出基变量，即取 为出 基变量下标。
39、min|min0iKiagKgababglik感谢你的观看2019年7月31090,6002125350.32max0,6002125350.32min0,6002125350.32min213212132122111212121321213212112121212112121aasssxxsxxasxasxxtsMaMaxxzsssxxsxxsxsxxtsxxfxxxxxxxtsxxfl 例7.(P85)感谢你的观看2019年7月3110l 解1迭代数ixBCBx1x2s1s2s3a1a2b(i)比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-100112
40、5125/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-2M2a1-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-
41、120100 x1-210101-10250s2000111-1-1125zj-2-3401-40-800j00-40-1-M+4-M感谢你的观看2019年7月3111l人工变量引入的准则：u人工变量的引入应不影响约束条件，也不影响目标函数的求解u为构成基B=I，A中缺K个单位向量就引入K个人工变量（上例缺2个）l人工变量引入后，为不影响约束方程应使 的最优解中人工变量为非基变量（即取 ）l由于人工变量的引入为构成基I=B，故第0次迭代时 已成为基变量，因此在 以后的迭代过程中应尽可能将 从基变量中替换出来而成为非基变量，从而保证基本可行解分量 。LP0jaLPjaja0ja感谢你的观看201
42、9年7月3112l将目标函数设计成下型：即能满足上述要求。这是由于只要 迭代过程中，若基变量含有一个人工变量，则上述设计的目标函数z(x)就不可能达到极大化（max），因此只要不出现退化现象，在经有限次迭代后总可将引入的人工变量一个一个地替换出来，而成为非基变量。因而有 如此的 ，其最优解与LP最优解相同（）。1,)(11MaMxCxzlKKnjjjLPLP)1(0ljaj0jaLP感谢你的观看2019年7月3113lM 1故不必考虑其具体数值。本方法称为大M法来源与此。l若 在某一次迭代中，仍然为基变量，则目标函数 （此时 为基本可行解之一分量应满足非负条件 ），从而使此基本可行解不可能是最
43、优解。约束方程。容易验证满足），（LPxxzxfxzsssxxxTT800)()(800)(01250100250),(32121)(xzja0jaja感谢你的观看2019年7月3114l若采用大M法始终无法将人工变量从基变量替换出来，此时有两种情形：u所有检验数已有 ，此时应认为无解。u上述最优性条件仍未具备，需始终迭代下去，或改用其它方法。0)(ljj感谢你的观看2019年7月3115l例7.解20,6002125350.32min32max32121321211212121sssxxsxxsxsxxtsxxfxxfz感谢你的观看2019年7月3116ixBiCBix1x2s1s2s3b(
44、i)比值-2-30000111-100350100-10125210016000211-100350100-101251010125003x2-301-110225225x1-2100-10125/s3000111125125z(0)-2-33-10-925(0)00-3101x2-301-20-1100 x1-210101250s2000111125z(1)-2-3401-800(1)00-40-1感谢你的观看2019年7月3117800)()(800)(01250100250),(32121xzxfxzsssxxxTT），（感谢你的观看2019年7月3118l为使b0，同时又可形成基B0=
45、I，可在原增广矩阵（A0：b0）基础上作初等行变换以形成人工基B0=I。l 。不可混淆。对应的基变量对应的基变量应对应对应的基变量列中的第一、二、三行形成人工基后100,010,001,332211BBBBBBBBCxCxCxCxii感谢你的观看2019年7月3119l此经一次迭代即可得最优解l将约束方程变形成下述，虽然保证有一个B0=I，但约束方程右端的b(i)0非负条件被破坏，从而使用单纯形法时，获得的可行解虽然是基本解，但非基本可行解。易知此非基本可行解，故采用单纯形法无效。800)()(800)(01250100250),(32121xzxfxzsssxxxTT），（TTTBBBBss
46、sxxxsssxxxxsxxsxsxx)600,125,350,0,0(),(),(),(60021253500302010201)0(3321321211210302010可得相应基本解此时取感谢你的观看2019年7月3120l例8.(P88，无最优解例）l解：引入松弛变量s1，s2，剩余变量s3，人工变量a1，可得上述标准型。0,4030150103.0,4030150103.3020max3020max132121132121121212112112121asssxxasxxsxsxxtsxxxxxxxtsMaxxzxxz感谢你的观看2019年7月3121迭代迭代次数次数i基变基变量量x
47、BiCBix1x2s1s2s3a1b(i)比值比值2030000-M0s103101000150150/10s2010010030/a1-M1100-114040/1z(0)-M-M00M-M-40Mj(0)20+M30+M00-M01x2303/1011/100001515/(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)203
48、03+M/1011+7M/10M-M780-4Mj(0)00-3-M/10-11-7M/10-M0感谢你的观看2019年7月3122l当M0，经二次迭代后，已有 ，按照一般原理下有下述的x(2)=(30,6,0,0,4)T应为最优解，并迭代终止。l .虽然有z(x0)z(x1)z(x2)目标值早增大，但根据大M法原理应将人工变量以基变量xB中替换出来，而i=2时，由上表知a1仍为基变量，故此时应认为无最优解0jj有ix(i)z(x(i)x1ix2is1is2is3ia1i000150 30040-40M1015 030025450-25M23060004780-4M感谢你的观看2019年7月3
49、123l事实上由图解法知该问题无可行解。或将。式可行域，但不满足不等代入)4036630(,406,302221212221xxxxLPxx0102030504010203040D1D2x2x13x1+10 x2=150 x1+x2=40 x1=300,300,4021121xxxxx0,3015010321121xxxxx感谢你的观看2019年7月3124l图解法下的灵敏度分析定义：研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化（局部或全部变动）对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析。由于C，b，A通常表述产品需求，原材料价格，未来的商品售价
50、及企业的加工能力、资源消耗，故在数学建模时的估计有可能出现误差，且未来的环境亦是不确定的，有可能出现变化，因此有必要对应用问题的解作灵敏度分析。x)(xz感谢你的观看2019年7月3125l图解法下的灵敏度分析灵敏度分析通常讨论如下内容：C，b，A变动（局部或全部）后LP最优解是否仍存在？若存在的话，最优解有多大程度的变化？C，b，A在什么范围内变动时能保证LP的原最优解不变？若C，b，A的变动超出上述范围后，如何利用LP的原最优解 来求解变动后的 最优解。这些C，b，A的变动，在出现情况下对决策者有利？在什么情况下对决策者不利？此称为对偶价格研究对象（C的变动对目标最优解的影响）。xLP感谢
