[管理学]第一章线性规划课件.ppt

1、浙江科技学院经济管理学院管工系课堂要求1.要求学生上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学数据、模型、决策，科学出版社。前言运筹学简介 运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模

2、型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。建立模型求解模型修改模型修改模型 运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，

3、Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。授课主要内容目录：绪论（1）p第一章线性规划（12）p第二章对偶问题（10）p第三章运输问题（6）p第五章整数规划（6）p第七章动态规划（8）p第八章 图与网络分析（8）上课总课时：51课时 课程设计1周（

4、下学期开学前）第一章 线性规划及单纯形法1.1 线性规划问题及其数学模型1.2 图解法1.3 单纯形法原理1.4 单纯形法计算步骤1.5 单纯形法进一步讨论本章学习要求n能建立实际问题的数学规划模型n理解线性规划模型的特点，标准型n掌握线性规划的图解法及其几何意义n掌握单纯形法原理n掌握运用单纯形表计算线性规划问题的步骤及解法n能用二阶段法和大M法求解线性规划问题。n掌握任何基可行解原表及单纯形表的对应关系1.1线性规划问题及其数学模型n举例说明举例说明n线性规划数学模型的标准形式线性规划数学模型的标准形式一、线性规划问题举例说明n 生产计划问题n 配料问题n 背包问题n 运输问题n 指派问题

5、n 下料问题例1：美佳公司生产计划问题1、确定决策变量、确定决策变量通常由目标问题分解通常由目标问题分解x1代表生产代表生产种家电数量；种家电数量；x2代表生产代表生产种家电数量；种家电数量；2、分析并表达限制条件，包括约束条件、分析并表达限制条件，包括约束条件通常由等式或不等式表示。通常由等式或不等式表示。0 x1+5x2156x1+2x224 x1+x2 5x1 0,x203、分析目标、分析目标是利润最大化是利润最大化例2：捷运公司表12 所需仓库面积1、确定决策变量、确定决策变量通常由目标问题分解通常由目标问题分解表13 租金与期限的关系1.生产计划问题（Production Plann

6、ing）某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x402.配料问题（Material Blending

7、）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。3.背包问题（Knapsack Problem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。

8、max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元4.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。A1A2B3B2B135吨25吨10吨30吨20吨235478设从两个供应地到三个需求地的运量（吨）如下表：min z=

9、2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13 =35 供应地A1 x21+x22+x23=25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23=20 需求地B3 x11,x12,x13,x21,x22,x230 这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨5.指派问题（Assignment Problem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个

10、人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：项任务个人被指派完成第第项任务个人不从事第第ji1ji0 xij1,0 xn,.,2,1i1xn,.,2,1j1x.t.sxczmax(min)ijn1jijn1iijn1in1jijij张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。设：门课个老师教第第门课个老师不教第第ji1ji0 xij门课个老师教第第门课个老师不教第第ji1ji0

11、 xij设：max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1 (1)x21+x22+x23+x24=1 (2)x31+x32+x33+x34=1 (3)x41+x42+x43+x44=1 (4)x11+x21+x31+x41=1 (5)x12+x22+x32+x42=1 (6)x13+x23+x33+x43=1 (7)x14+x24+x34+x44=1 (8)xij=0,16.下料问题 现将1m长的

12、钢切成A0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？解：将1m的钢分别切成A，B，C三种钢的可能方案如下：设第i种方案进行切割的1m钢的为xi根；minZ=0.1x3+0.1x5+0.1x7 s.t.2x1+x2+x3+x420 2x2+x3+3x5+2x6+x745 x1+x3+3x4+2x6+3x7+5x850 xi 0(i=1,28)线性规划问题要求目标函数和约束方程必须是线性函数，隐含线性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定：如下假定：每个决策变量对目标函数的贡献与决策变

13、量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例；任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。允许每个决策变量值使用分数值。已经确切知道每个参数（价值系数，工艺系数，右侧常数）线性规划数学模型三个要素：课堂习题 P45 1.13 1.14(1)课后作业P46 1.14(2)1.15二、线性规划模型标准形式min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,xn 0(,Fr

14、ee)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：0 x,x,x9x4+x+x8xx+x+x2.t.sxx2+x3=zmin321321132121211.1.一般形式一般形式2.2.线性规划的标准形式线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 3.3.线性规划模型用矩

15、阵和向量表示线性规划模型用矩阵和向量表示max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 nmnmmnnPPPaaaaaaaaaA21212222111211m21bbbbTncccc21n21xxxX价值系数工艺系数矩阵资源约束线性规划模型用矩阵和向量表示（续）线性规划模型用矩阵和向量表示（续）nnnnxcxcxcxxxcccCXZ22112121nmn22m11mnn2222121nn1212111n21mn2m1mn22221n11211xax

16、axaxaxaxaxaxaxaxxxaaaaaaaaaAX因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ =CXs.t.AX=b X0 4.4.线性规划模型总结线性规划模型总结线性规划模型的结构n目标函数：max，minn约束条件：,=,n变量符号：0,0,Free线性规划的标准形式n目标函数：maxn约束条件：=n变量符号：0FreeXbAXtsCXz,0)(),(.max(min)MaxZ =CXs.t.AX=b X0 5.5.线性规划问题的标准化线性规划问题的标准化n 极小化目标函数转化为极大化n 小于等于约束条件转化为等号约束n 大于等于约束条件转化为等号约束n 变量没有符号限

17、制（Free）的标准化n 变量小于等于0的标准化 min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 max z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。例如，对于以下两个线性规划问题Max z=2x1+3x2s.t.x1+x23 x21 (A)x1,x20Min z=-2x1-3x2s.t.x1+x23 x21 (B)x1,x20它们的最优解都是x1=2,x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7 2x1+3

18、x2-4x35引进(Slack variable)x40 2x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要引进不同的松弛变量。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8将不等式约束变为等式约束。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去剩余变量剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8没有符号限制的变量，用表示。例如：min z=x1+2x2-3x3s.t.2x1+3x

19、2-4x35 3x1-2x2+5x38 x10,x2:free,x30先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x2:free,x3,x4,x50Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10,x2:free,x3,x4,x50然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Max z=-x1-2(x2-x”2)+3x3s.t.2x1+3(x2-x”2)-

20、4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1,x2,x”2,x3,x4,x50整理，得到标准形式：Max z=-x1-2x2+x”2+3x3s.t.2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1,x2,x”2,x3,x4,x50min z=x1+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x20,x30max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x20,x3,x4,x50令 x2=-x2，x20,代入模

21、型max z=-x1+2x2+3x3s.t.2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10,x20,x3,x4,x50课堂习题P43 1.21.2 图解法n相关概念和图解法步骤相关概念和图解法步骤n线性规划问题图解法求解的几种结果线性规划问题图解法求解的几种结果n结论结论模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。：一个线性规划问题有解，是指能找出一组：一个线性规划问题有解，是指能找出一组xj(j=1,2,n)满足约束条件，称这组满足约束条件，称这组xj为问题的可行解。为问题

22、的可行解。通常线性规划问题总是含有多个可行解，全部可行通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。解的集合为可行域。可行域中使目标函数为最优的可行解为最优解。可行域中使目标函数为最优的可行解为最优解。建立坐标系，确定比例尺；建立坐标系，确定比例尺；画出各约束条件的边界，定出可行域；画出各约束条件的边界，定出可行域；画出目标函数的一根等值线，平移得出最优解；画出目标函数的一根等值线，平移得出最优解；1.算出目标函数最优值。算出目标函数最优值。1.相关概念和图解法步骤线性规划的图解max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优

23、解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3-2 -1 0 x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？2.线性规划问题图解法求解的几种结果线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可行解；若LP的可行域存在，即有可行解，则可行域是一个凸集；若LP的最优解存在，则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该LP有无穷多最优解；用图解法求解LP时，如果可行域封闭，可比较可行域的顶点的目标函数值，得到最优解；用图解法如果可以得到封闭的可行域，则定有

24、最优解存在；如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。3.结论举例：1.maxZ=2x1+x2 5x215 6x1+2x2 24 x1+x2 5 x1,x20唯一最优解2.maxZ=x1+x2 -2x1+x2 4 x1-x2 2 x1,x20无界解 3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1,x20无穷多最优解 4.maxZ=x1+x2 x1+x2 1 2x1+2x24 x1,x20无解课后作业P43 1.11.3 单纯形法原理nLP解的相关概念解的相关概念n凸集及其顶点凸集及其顶点n几个基本定理几个基本定理n单纯形法迭代原理单

25、纯形法迭代原理x3=0 x4=0max z=x1+2x2s.t.x1+x2 3 x2 1 x1,x2 0max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x4 0 x1=0,x2=0 x3=3,x4=1x1=0,x4=0 x2=1,x3=2x2=0,x3=0 x1=3,x4=1x3=0,x4=0 x1=2,x2=1x1=0,x3=0 x2=3,x4=-2x2=0 x1=0OABCD一.LP解的相关概念1.可行域，可行解，最优解可行域，可行解，最优解LPLP问题数学模型问题数学模型)8.1(,1,0)7.1(,1,)6.1(11njxmibxaxcMax

26、Zjinjjijnjjj因此：满足（1.7）（1.8）的解称为LP的可行解；：全部可行解的集合；：使目标函数(1.6)达到最大值的可行解0XbAXCXMaxZ：从n个变量中任取m个变量xi1,xi2,xim，若这m个变量对应的系数列向量Pi1,Pi2,Pim线性无关，即对应系数列向量行列式0，则称B=(Pi1,Pi2,Pim)为基矩阵，简称，xi1,xi2,xim为，其余n-m变量为。：在约束方程(1.7)中，令所有非基变量为0，根据克莱姆法则，则(1.7)有唯一解。令xi1 1,xi2 2,xim m，称 为一组。：满足（1.8）中的基解为基可行解，即基解中每一分量均非负。：基可行解对应的基

27、。：基变量中有分量为0的解。2.基，基变量，非基变量；基解，基可行解，可行基基，基变量，非基变量；基解，基可行解，可行基mjmimiiijnjxxx,1,0,111max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40 x1=0,x2=0 x3=3,x4=1基可行解x1=0,x4=0 x2=1,x3=2基可行解x2=0,x3=0 x1=3,x4=1基可行解x3=0,x4=0 x1=2,x2=1基可行解x1=0,x3=0 x2=3,x4=-2是基解，但不是可行解OABx3=0 x4=

28、0 x2=0 x1=0CD可行域1.maxZ=2x1+3x2 x1 +x35 x1+2x2 +x4 10 x2 +x5 4 xi 0最优解为x1 2，x24，x3 3，Z191.凸集 如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：x1（1）x2(01)数学解析式为：x1 C，x2 C，有x1（1）x2C(01)，则C为凸集。2.顶点 如果集合C中不存在任何两个不同的点x1，x2，使x为这两点连线上的一个点，称x为顶点。对任何x1 C，x2 C，不存在x=x1（1）x2(01)，则称x为凸集的顶点。若线性规划问题存在可行解，则问

29、题的可行域是凸集线性规划问题的可行解X(x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。)2()1()2()1(,0,/XXCXCXXbAXXC且证明：令可行域00)2()2()1()1(XbAXXbAX则10)1()2()1(XXX令：bAXAXAXXXA)2()2()1()2()1()1(AX则为凸集CCX线性规划问题的基可行解线性规划问题的基可行解X对应线性规划问题可行域的顶点。对应线性规划问题可行域的顶点。分两步：分两步：1）顶点）顶点基可行解基可行解 2）基可行解）基可行解顶点顶点反证法：反证法：1）假设）假设X0是可行域的

30、顶点，是可行域的顶点，X0不是基可行解，不是基可行解，X0的前的前k个分量大于个分量大于0，其余为其余为0，因不是基可行解，则存在，因不是基可行解，则存在)0,0,00211kkiiiiP（设，使不全为nkjxxkjtxxkjtxxtXXtXXjjjjjjjj,10,1,1)2()1(0)2(0)1(0)2(0)1(令0,)2()1(XX充分小时，且当 tbtXAAXbtXAAX)()(0)2(0)1()2()1(0)2()1(2121,XXXXX为可行解，且所以所以X0不是可行域的顶点，与假设矛盾，则不是可行域的顶点，与假设矛盾，则X0必为基可行解。必为基可行解。2）假设）假设X0是基可行解

31、，是基可行解，X0不是顶点。不是顶点。假设假设X0是一个基可行解，设是一个基可行解，设X0的前的前m个分量为正，令个分量为正，令X0=(x1,x2,xm,0,0)T,因为不是顶点，则因为不是顶点，则X0可以表示成另外可以表示成另外两个点两个点X(1)，X(2)的凸组合，且的凸组合，且P1,Pm线性无关。线性无关。线性无关mTmTmPPPbAXbAXbAXXXXXXX,)0,0,()0,0,(21)2()1(0)2()2(1)2()1()1(1)1(0,)2()1(0均，又因XXX)2()1(0XXX所以所以X不能表示成可行域中另外两点的凸组合，与假设相不能表示成可行域中另外两点的凸组合，与假设

32、相矛盾，则矛盾，则X必为可行域的顶点。必为可行域的顶点。10)1()2()1(0XXX令：若线性规划问题有最优解，一定存在一个基可行解是最优解若线性规划问题有最优解，一定存在一个基可行解是最优解。X X0 0为为LPLP的最优解，的最优解，Z Z*=CX=CX0 0，如果，如果X X0 0不是基可行解，则定有不是基可行解，则定有X X(1)(1)X X0 0-ta,X-ta,X(2)(2)=X=X0 0+ta+ta为可行解，则有为可行解，则有CXCX(1)(1)=CX=CX0 0+tCa+tCaCXCX0 0CXCX(2)(2)=CX=CX0 0-tCa-tCaCXCX0 0则必有则必有tCa

33、=0tCa=0所以所以X X0 0，X X(1)(1)，X X(2)(2)均为最优解，如果均为最优解，如果X X(1)(1)，X X(2)(2)不是基可行解，继续下去，不是基可行解，继续下去，则必可以找到基可行解为最优解。则必可以找到基可行解为最优解。1.确定初始基可行解确定初始基可行解njxbxaxaxbxaxaxbxaxaxxcxcxcMaxZjmnmnmmmmnnmmnnmmnn,2,10112211221111112211mmTmTmBbcbcbcZbbbxxxX221102121),(),(则基解，可行解2.最优性检验和解的判别最优性检验和解的判别Zmixaxabxninmimii代

34、入目标函数,1,11非基变量检验数 nmjjjjnmjmiijijmiiiminmjjijinmjjjmiiinnmmnmnmmmmmnnmmnnmmnnxZxaccbcxacxcbcxcxcxaxabcxaxabcxaxabcxcxcxc10111111111112112221111112211)()()()(由检验数可以判断解的最优性情况由检验数可以判断解的最优性情况（1 1）因为所有）因为所有X Xj j0 0，当所有，当所有j j00,0,且所有且所有a aikik0(P0(Pj j0),i=1,2,m0),i=1,2,m，则该问题无界。则该问题无界。该问题无界为一可行解证明：令)1(

35、0010)1()1(,1,1,00CXMMZxZxZCXXmixabxkjnmjxMxkkknmjjjkikiijk（4 4）因为所有因为所有Xj0，当存在，当存在j0时，则该基可行解不是最优解，需要寻找另一个基可时，则该基可行解不是最优解，需要寻找另一个基可行解；行解；3.基变换基变换lklikikiikiabaabmiab0|min,1,njxbxaxaxaxbxaxaxaxbxaxaxaxbxaxaxaxjmnmnkmkmmmmlnklkmlmlnnkkmmnnkkmm,2,1011ln1122211221111111以alk为主元进行初等行变换mlmnmkmmlklmnkmnkmbbb

36、baaaaaaaaaaaaA211ln1221211111000010000100001211ln1212211110100100000100001mlmnmmmllmllnmlnmlbbbbaaaaaaaaaaaaA习题1.8；1.61.4 单纯形法计算步骤n求初始基可行解求初始基可行解n最优性检验最优性检验n基变换基变换单纯形法原理单纯形法总结STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。找到一个初始的基础可行解，确定基变量和非基变量。转转STEP 1。STEP 1 将目标函数和基变量分别用非基变量表示。将目标函数和基变量分别用非基变量表示。转转STEP 2。STEP 2

37、如果如果目标函数中所有非基变量的检验数全部为非正数，目标函数中所有非基变量的检验数全部为非正数，则则已经获得最优解，已经获得最优解，如果如果全为负数，则为全为负数，则为唯一最优解，唯一最优解，运算运算终止终止。；如果如果有为有为0的非基变量检验数，则有的非基变量检验数，则有无穷多最优无穷多最优解解。运算终止运算终止。如果如果有某非基变量检验数为正，且工艺系有某非基变量检验数为正，且工艺系数全非正，则无界，数全非正，则无界，运算终止运算终止。否则否则，选取检验数为正数最大的非基变量进基。，选取检验数为正数最大的非基变量进基。转转STEP 3。STEP 3 选择最小比值对应的基变量离基，进行系数初

38、等行变换，选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，得新的基可行解，转转STEP 1。（1）若所有）若所有j0,且所有且所有aik0(Pj0),i=1,2,m，则该问题，则该问题无界，计算终止。无界，计算终止。（4）当存在）当存在j0时，且有时，且有aik0,继续第三步；继续第三步；计算非基变量检验数用jjm1iijijjZcacc转转第第二二步步；，得得一一新新的的基基可可行行解解，为为主主元元进进行行初初等等行行变变换换以以为为换换出出变变量量，则则若若比比值值为为换换入入变变量量，计计算算最最小小则则lkllklikikikjjaxabaabxMax,0min0|

39、k用j21000 -45 x1入，x4出j01/30-1/30 x2入，x5出3123/2 j000-1/4-1/2j10500 38/5 x1入,x4出j010-2 x2入,x3出3/24j00-5/14-25/14 0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2对应0对应A对应B课堂作业1.4(1)课后作业P43 1.4（2）1.5 单纯形法的进一步讨论一、人工变量法（大一、人工变量法（大M法）法）约束条件：约束条件：“”减一个剩余变量后，再加一个人工变量减一个剩余变量后，再加一个人工变量“”加一个人工变量加一个人工变量目标函数：目标函数：人工变量的系数为人工

40、变量的系数为“M”，即罚因子，即罚因子若线性规划问题有最优解则人工变量必为若线性规划问题有最优解则人工变量必为0。MaxZ=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3增加人工变量后，线性规划问题中就存在一个增加人工变量后，线性规划问题中就存在一个B B为单位矩阵，为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。后面可以根据我们前面所讲的单纯形法来进行求解。MaxZ=-3x1+x3-Mx6-Mx7 x1+x2+x3+x4 =4 -2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7标准化及变形

41、j-3-2M 4M100 3x2入，x6出-M041j6M-304M+10-4M -x1入，x7出3M011j0030-M-3/2 9x3入，x1出3/2-M+1/23/2-j-9/2000-M+3/4-3/4-M-1/4二、两阶段法 第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将

42、目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。求解辅助问题，得到辅助问题的最优解引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化MaxW=0?原问题没有可行解。把辅助问题的最优解作为原问题的初始基础可行解用单纯形法求解原问题，得到原问题的最优解否否是是两阶段法的算法流程图MaxZ=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3MaxW=-x6-x7 x1+x2+x3+x4 =4-2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7j-24000

43、 3x2入，x6出-1041j6040-4 x1入，x7出3011j0000-10-1j00303/2 -93/2 x3入，x1出j-9/2000-3/4目标函数极小化时解的最目标函数极小化时解的最优性判别；优性判别；退化解的判别；退化解的判别；无可行解的判别；无可行解的判别；无界的判别；无界的判别；无穷多最优解的判别；无穷多最优解的判别；唯一最优解的判别唯一最优解的判别.三、单纯形法计算中的几个问题三、单纯形法计算中的几个问题j4045025100/340 3 x2入，x3出j000-5例例:012023310032254540321321321321xxxxxxxxxtsxxxZ,.max

44、0-100 x,x50 xx100 x2xs.t.xxmaxZ21212121j1100-50 x1入，x4出j020-1例例:例:下表为一极大化问题对应的单纯形表下表为一极大化问题对应的单纯形表讨论在讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解取何值的情况下，该表中的解为：为：唯一最优解；唯一最优解；无穷多最优解；无穷多最优解；退化解；退化解；无界；无界；无可行解；无可行解；X3换入，换入，x2换出换出A40,a50,a20,a30a40,a50,x4或x2为人工变量，a60；x1为人工变量a60A40,a4a5;a6/a12a10 a60 a1 0课后作业P43 1.7