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

《[管理学]第一章 线性规划课件.ppt》由会员分享，可在线阅读，更多相关《[管理学]第一章 线性规划课件.ppt（81页珍藏版）》请在三一办公上搜索。

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

2、筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解结果.,求解结果.,求解结果.,27.12.2022,5,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Resea

3、rch，在美国称为Operations Research。,27.12.2022,6,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。,27.12.20

4、22,7,授课主要内容,目录： 绪论（1）第一章线性规划（12）第二章对偶问题（10）第三章运输问题（6）第五章整数规划（6）第七章动态规划（8）第八章 图与网络分析（8）,上课总课时：51课时 课程设计1周（下学期开学前）,27.12.2022,8,第一章 线性规划及单纯形法,1.1 线性规划问题及其数学模型1.2 图解法1.3 单纯形法原理1.4 单纯形法计算步骤1.5 单纯形法进一步讨论,27.12.2022,9,本章学习要求,能建立实际问题的数学规划模型理解线性规划模型的特点，标准型掌握线性规划的图解法及其几何意义掌握单纯形法原理掌握运用单纯形表计算线性规划问题的步骤及解法能用二阶段法

5、和大M法求解线性规划问题。掌握任何基可行解原表及单纯形表的对应关系,27.12.2022,10,1.1线性规划问题及其数学模型,举例说明线性规划数学模型的标准形式,27.12.2022,11,一、线性规划问题举例说明,生产计划问题配料问题背包问题运输问题指派问题下料问题,27.12.2022,12,例1：美佳公司生产计划问题,1、确定决策变量通常由目标问题分解设x1代表生产种家电数量； x2代表生产种家电数量；,2、分析并表达限制条件，包括约束条件通常由等式或不等式表示。0 x1+5x2156x1+2x224 x1+ x2 5x1 0,x20,3、分析目标是利润最大化MaxZ=2x1+x2,2

6、7.12.2022,13,例2：捷运公司,表12 所需仓库面积,1、确定决策变量通常由目标问题分解每个月有不同的租用方案，共有4个月需要租用仓库。则：,表13 租金与期限的关系,27.12.2022,14,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：,max z=5.24x1+7.30 x2+8.34x3+4.18x

7、4s.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, x40,27.12.2022,15,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,

8、设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,min z=115x1+97x2+82x3+76x4s.t. 3.21x1+4.53x2+2.19x3+1.76x43.20 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x42.10 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x44.30 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1, x2, x3, x40,27.12.2022,16,3. 背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种

9、物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x1，x2，x3件，总价值为z。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元,27.12.2022,17,4. 运输问题（Transportation）,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需

10、求地每吨物资的运输价格如下表：求总运费最低的运输方案。,35吨,25吨,10吨,30吨,20吨,27.12.2022,18,设从两个供应地到三个需求地的运量（吨）如下表：,min z=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,27.12.2022,19,这个问题的最优解表示如下：,最小总运费为：z=330+55

11、+410+815=275元,30吨,5吨,10吨,15吨,27.12.2022,20,5. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：,27.12.2022,21,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,设：,27.12.2022,22,设：,max z

12、=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,1,27.12.2022,23

13、,6. 下料问题 现将1m长的钢切成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),27.12.2022,24,小结,线性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定：比例性假定：每个决策变量对

14、目标函数的贡献与决策变量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例；可加性假定：任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。连续性假定（可除性假定）：允许每个决策变量值使用分数值。确定性假定：已经确切知道每个参数（价值系数，工艺系数，右侧常数）线性规划数学模型三个要素：决策变量目标函数约束条件,27.12.2022,25,课堂习题 P45 1.13 1.14(1)课后作业P46 1.14(2) 1.15,27.12.2022,26,二、线性规划模型标准形式,min(max) z=c1x1+c2x2+cnxns.t. a11x

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

16、1x1+am2x2+amnxn bm x1, x2, , xn 0,27.12.2022,28,3.线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,价值系数,工艺系数矩阵,资源约束,27.12.2022,29,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,MaxZ =CXs.t. AX=b X0,27.12.2022,30,4.线性规划模型总结,线性规划模型的结构目标函数

17、 ：max，min约束条件：,=,变量符号：0, 0, Free线性规划的标准形式目标函数：max约束条件：=变量符号：0,MaxZ =CXs.t. AX=b X0,27.12.2022,31,5.线性规划问题的标准化,极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制（Free）的标准化变量小于等于0的标准化,27.12.2022,32,min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 max z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解

18、的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,例如，对于以下两个线性规划问题,Max z=2x1+3x2s.t. x1+x23 x21 (A) x1, x20,Min z=-2x1-3x2s.t. x1+x23 x21 (B) x1, x20,它们的最优解都是x1=2, x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7,27.12.2022,33,2x1+3x2-4x35引进松弛变量(Slack variable) x40 2x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要引进不同的松弛变量。例如： 2x1+

19、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,27.12.2022,34,没有符号限制的变量，用两个非负变量之差表示。例如：min z=x1+2x2-3x3s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10

20、, x2:free, x30先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。Max z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50,变量没有符号限制(Free)的标准化,27.12.2022,35,Max 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

21、)+3x3s.t. 2x1+3(x2-x”2)-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,x50,27.12.2022,36,min z=x1+2x2-3x3s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30max z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5

22、 3x1-2x2+5x3 -x5=8 x10, x20, x3, x4, x50令 x2=-x2，x20, 代入模型max z=-x1+2x2+3x3s.t. 2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10, x20, x3, x4, x50,变量小于等于0的的标准化,27.12.2022,37,课堂习题P43 1.2,27.12.2022,38,1.2 图解法,相关概念和图解法步骤线性规划问题图解法求解的几种结果结论,27.12.2022,39,模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。可行解：一个线性规划问题有解，是指能找出一组xj(

23、j=1,2,n)满足约束条件，称这组xj为问题的可行解。可行域：通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。最优解：可行域中使目标函数为最优的可行解为最优解。图解法的步骤：建立坐标系，确定比例尺；画出各约束条件的边界，定出可行域；画出目标函数的一根等值线，平移得出最优解；算出目标函数最优值。,1.相关概念和图解法步骤,27.12.2022,40,线性规划的图解,max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的

24、最优解是否可能位于可行域的边界上？,27.12.2022,41,唯一最优解无穷多最优解无界解（可行域无界）无解（无可行解）,2.线性规划问题图解法求解的几种结果,1、唯一最优解（封闭）,2、多个最优解（封闭）,3、唯一最优解（开放）,4、多个最优解（开放）,5、目标函数无界（开放）,6、无可行解,27.12.2022,42,线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可行解；若LP的可行域存在，即有可行解，则可行域是一个凸集；若LP的最优解存在，则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该LP有无穷多最优解；用图解法求解LP时，如果可行域封闭，可比较可行域的

25、顶点的目标函数值，得到最优解；注意用图解法如果可以得到封闭的可行域，则定有最优解存在；如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。,3.结论,27.12.2022,43,举例：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无解,27.12.20

26、22,44,课后作业P43 1.1,27.12.2022,45,1.3 单纯形法原理,LP解的相关概念凸集及其顶点几个基本定理单纯形法迭代原理,27.12.2022,46,x3=0,x4=0,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,max 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,

27、x2=0,x1=0,O,A,B,C,D,一.LP解的相关概念,1.可行域，可行解，最优解,27.12.2022,47,LP问题数学模型,因此：可行解：满足（1.7）（1.8）的解称为LP的可行解；可行域：全部可行解的集合；最优解：使目标函数(1.6)达到最大值的可行解,27.12.2022,48,定义1：从n个变量中任取m个变量xi1,xi2,xim，若这m个变量对应的系数列向量Pi1,Pi2,Pim线性无关，即对应系数列向量行列式0， 则称B=(Pi1,Pi2,Pim )为基矩阵，简称基， xi1,xi2,xim为基变量，其余n-m变量为非基变量。定义2：在约束方程(1.7)中，令所有非基变

28、量为0，根据克莱姆法则，则(1.7)有唯一解。令xi1 1 ,xi2 2,xim m，称 为一组基解。基可行解：满足（1.8）中的基解为基可行解，即基解中每一分量均非负。可行基：基可行解对应的基。退化解：基变量中有分量为0的解。线性规划的基可行解就是可行域的顶点。,2.基，基变量，非基变量；基解，基可行解，可行基,27.12.2022,49,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,max 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=

29、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是基解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,27.12.2022,50,1.maxZ=2x1+3x2 x1 +x35 x1+2x2 +x4 10 x2 + x5 4 xi 0,最优解为x1 2，x24， x3 3，Z19,27.12.2022,51,二 . 凸集和顶点,1.凸集如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x

30、2的连线可以表示为： 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为凸集的顶点。,27.12.2022,52,三.几个基本定理,定理1：若线性规划问题存在可行解，则问题的可行域是凸集,引理：线性规划问题的可行解X(x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。,27.12.2022,53,定理2：线性规划问题

31、的基可行解X对应线性规划问题可行域的顶点。分两步：1）顶点基可行解 2）基可行解顶点反证法：1）假设X0是可行域的顶点，X0不是基可行解，X0的前k个分量大于0，其余为0，因不是基可行解，则存在,所以X0不是可行域的顶点，与假设矛盾，则X0必为基可行解。,27.12.2022,54,2）假设X0是基可行解，X0不是顶点。假设X0是一个基可行解，设X0的前m个分量为正，令X0=(x1,x2,xm,0,0)T,因为不是顶点，则X0可以表示成另外两个点X(1)，X(2)的凸组合，且P1,Pm线性无关。,所以X不能表示成可行域中另外两点的凸组合，与假设相矛盾，则X必为可行域的顶点。,27.12.202

32、2,55,定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。X0为LP的最优解，Z*=CX0，如果X0不是基可行解，则定有X(1)X0-ta , X(2)=X0+ta为可行解，则有CX(1)=CX0+tCaCX0CX(2)=CX0-tCaCX0则必有tCa=0所以X0 ，X(1) ，X(2)均为最优解，如果X(1) ，X(2)不是基可行解，继续下去，则必可以找到基可行解为最优解。,27.12.2022,56,四.单纯形法迭代原理,迭代基础：如果LP存在最优解，则一定有一个基可行最优解，且对应LP可行域的顶点。（可行，基解，最优）,1.确定初始基可行解,基解，可行解,27.12.20

33、22,57,2.最优性检验和解的判别,非基变量检验数,27.12.2022,58,由检验数可以判断解的最优性情况（1）因为所有Xj0，当所有j0,且所有aik0(Pj0), i=1,2,m，则该问题无界。,（4）因为所有Xj0，当存在j0时，则该基可行解不是最优解，需要寻找另一个基可行解；,27.12.2022,59,3.基变换,变换目的：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。,换入变量的确定k0,aik 至少一个大于0，若k=Maxj| j0,则xk为换入变量。换出变量的确定令xk=0,xj=0,j=m+1,n,jk则xi=bi-

34、aik 0，i=1,m当aik 0时，可任取；当aik 0时，,则xl为换出变量。系数变换,27.12.2022,60,以alk为主元进行初等行变换,27.12.2022,61,习题1.8；1.6,27.12.2022,62,1.4 单纯形法计算步骤,求初始基可行解最优性检验基变换,27.12.2022,63,单纯形法原理单纯形法总结,STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。转STEP 1。STEP 1 将目标函数和基变量分别用非基变量表示。转STEP 2。STEP 2 如果目标函数中所有非基变量的检验数全部为非正数，则已经获得最优解，如果全为负数，则为唯一最优解，运算终

35、止。 ；如果有为0的非基变量检验数，则有无穷多最优解。运算终止。如果有某非基变量检验数为正，且工艺系数全非正，则无界，运算终止。 否则，选取检验数为正数最大的非基变量进基。转STEP 3。STEP 3 选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，转STEP 1。,27.12.2022,64,一.求初始基可行解,1.当约束条件为“”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初始基可行解。2.当约束条件为“时，直接在约束不等式左边减去非负的剩余变量，此情况下很难找到一个单位矩阵，为求出初始基可行解，为此需要引入人工变量，以

36、方便构成初始基可行解的一个基。 为了不改变问题的性质，对引入人工变量Xi”的线性规划问题，需要在目标函数中减去MXi”,M为足够大的正数，称罚因子，促使Xi”最终必为0。3.当约束条件为”=“时，同样需要引入人工变量，以方便构成初始基可行解的一个基。目标函数需要减去罚因子。,27.12.2022,65,二.最优性检验,（1）若所有j0,且所有aik0(Pj0), i=1,2,m，则该问题无界，计算终止。（4）当存在j0时，且有aik0,继续第三步；,27.12.2022,66,三.基变换,用单纯形法按上述步骤求解时，可采用表格形式，这样更直观，易于避免错误，该表格称为单纯形表。,27.12.2

37、022,67,例,j,2,1,0,0,0, ,-,4,5, ,x1入，x4出,j,0,1/3,0,-1/3,0, ,x2入，x5出,3,12,3/2, ,j,0,0,0,-1/4,-1/2,所以：X*=(x1,x2,x3)T=(7/2,3/2,15/2)T Z*=17/2,27.12.2022,68,例:1.4(1),j,10,5,0,0, ,3,8/5, ,x1入,x4出,j,0,1,0,-2, ,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2)T Z*=35/2, ,对应0,对应A,对应B,27.12.2022,69,课堂作业1

38、.4(1)课后作业P43 1.4（2）,27.12.2022,70,1.5 单纯形法的进一步讨论,一、人工变量法（大M法）约束条件：“” 减一个剩余变量后，再加一个人工变量“” 加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。,27.12.2022,71,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =

39、4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,标准化及变形,27.12.2022,72,单纯形表,j,-3-2M,4M,1,0,0, ,3,x2入，x6出,-M,0,4,1, ,j,6M-3,0,4M+1,0,-4M, ,-,x1入，x7出,3M,0,1,1, ,j,0,0,3,0,-M-3/2, ,9,x3入，x1出,3/2,-M+1/2,3/2,-, ,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2,27.12.2022,73,二、两阶段法第一阶段暂

40、不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,27.12.2022,74,求解辅助问题，得到辅助问题的最优解,引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,MaxW=0?,原问题

41、没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,MaxW=-x6-x7 x1+ x2+ x3+x4 =4-2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,27.12.2022,75,(第一阶段）单纯形表1,j,-2,4,0,0,0, ,3,x2入，x6出,-1,0,4,1, ,j,6,0,4,0,-4, ,x1入，x7出,3,0,1,1, ,j,0,

42、0,0,0,-1,0,-1,所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。,27.12.2022,76,（第二阶段）单纯形表2,j,0,0,3,0,3/2, ,-,9,3/2, ,x3入，x1出,j,-9/2,0,0,0,-3/4,所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2,27.12.2022,77,目标函数极小化时解的最优性判别；退化解的判别；无可行解的判别；无界的判别；无穷多最优解的判别；唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解；,最优解中基变量有取值为0的值时；,最优解中人工变量

43、为非0的基变量时；,存在某个k0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,27.12.2022,78,j,40,45,0,25,100/3,40, 3 ,x2入，x3出,j,0,0,0,-5,因为j全0,且1=0,则有无穷多最优解。 所以：X*=(0,80/3,20,0,0),Z*=1700,例:,0,-10,27.12.2022,79,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因为2=2,且ai2全0所以：无界,例:,27.12.2022,80,例:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：唯一最优解；无穷多最优解；退化解；无界；无可行解；X3换入，x2换出,A40,a20, a30a40,a50, x4或x2为人工变量，a60 ；x1为人工变量a60A40,a4a5;a6/a12a10 a60 a1 0,27.12.2022,81,课后作业P43 1.7,