运筹学第一章ppt 线性规划.ppt

《运筹学第一章ppt 线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第一章ppt 线性规划.ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、管理科学与工程系管理科学与工程系 关叶青关叶青 1授课教材：党耀国等授课教材：党耀国等,运筹学运筹学,科学出版社科学出版社绪论绪论第一章第一章 线性规划的数学模型与单纯形法线性规划的数学模型与单纯形法第二章第二章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三章第三章 运输问题运输问题第四章第四章 整数规划整数规划第五章第五章 动态规划动态规划第六章第六章 图论与网络计划图论与网络计划第七章第七章 存储论存储论第八章第八章 决策分析决策分析2绪 论v运筹学释义与发展简史 operational research,operations research,简写O.R.v运筹学研究

2、的基本特征 系统的整体性，多学科的综合性，模型方法的应用性v运筹学在工商管理中的应用v运筹学的主要分支 目录3O.R.O.R.在工商管理中的应用在工商管理中的应用 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。库存管理：多种物资库存量的管理，库存方式、库存量等。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。4 人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。O.R.O.R.在工商管理中的应用在工商管理中的应用5 财务和会计：包括预测、贷

3、款、成本分析、定价、证券管理、现金管理等。其他：设备维修、更新，项目选择、评价，工程优化设计与管理等。O.R.O.R.在工商管理中的应用在工商管理中的应用6一、线性规划问题的数学模型一、线性规划问题的数学模型主要解决以下两类问题：1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务；2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。第第1章章 线性规划的数学模型与单纯形法线性规划的数学模型与单纯形法 1.1 线性规划问题及其数学模型线性规划问题及其数学模型7 I II 资源总量资源总量 设备设备A(h)0 3 15 设备设备B(h)4 0 12原材料

4、原材料(公斤公斤)2 2 14 利润利润(万元）万元）2 3I,II生产多少生产多少,可获最大利润可获最大利润?解解:设设 计划期内生产产品计划期内生产产品I、II的数量的数量x1、x2 则该问题的数学模型为：则该问题的数学模型为：3x2 15 4x1 12 2x1+2x2 14 x1，x2 0 max S=2x1+3x2例例1.1：（计划安排问题）：（计划安排问题）8例例1.2(成本问题成本问题)油品来源油品来源成分成分AB汽油汽油15%50%煤油煤油20%30%重油重油50%15%其它其它15%5%某炼油厂根据每季度需供应给合同单位汽油某炼油厂根据每季度需供应给合同单位汽油15万吨、煤万吨

5、、煤油油12万吨、重油万吨、重油12万吨。该厂计划从万吨。该厂计划从A，B两处运回原两处运回原油提炼，已知两处的原油成分含量见表油提炼，已知两处的原油成分含量见表12；又已知从；又已知从A处采购的原油价格为每吨（包括运费）处采购的原油价格为每吨（包括运费）200元，元，B处采处采购的原油价格为每吨（包括运费）购的原油价格为每吨（包括运费）290元元,问：该炼油问：该炼油厂该如何从厂该如何从A，B两处采购原油，在满足供应合同的条两处采购原油，在满足供应合同的条件下，使购买成本最小。件下，使购买成本最小。9线性规划模型特点线性规划模型特点:v决策变量：向量决策变量：向量(x1 xn)T,xi非负非

6、负v约束条件：线性等式或不等式约束条件：线性等式或不等式v目标函数：目标函数：Z=(x1 xn)线性式，线性式，求求Z极大或极小极大或极小 满足以上三个条件的数学模型称为满足以上三个条件的数学模型称为 -线性规划数学模线性规划数学模型型10 I II 每天现有工时每天现有工时 搅拌机搅拌机 3 5 15 成型机成型机 2 1 5 烘烘 箱箱 2 2 11 利润利润(千元千元/吨）吨）5 4（资源利用问题）（资源利用问题）某食品厂主要生产某食品厂主要生产I型饼干和型饼干和I I型饼干。根据销售部门提供型饼干。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能的信息可知，目前这两种

7、饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力限制了该种关键设备即搅拌机、成型机、烘箱的生产能力限制了该厂的饼干生产。因为两种饼干的生产都要共用这三种设备厂的饼干生产。因为两种饼干的生产都要共用这三种设备，所以每种饼干究竟应该生产多少才能充分利用现有设备，所以每种饼干究竟应该生产多少才能充分利用现有设备资源，这是一个值得认真研究的重要问题。资源，这是一个值得认真研究的重要问题。11 甲甲 乙乙 丙丙 柑橘林产量（千蒲式耳）柑橘林产量（千蒲式耳）柑橘林柑橘林I 21 50

8、40 275柑橘林柑橘林II 35 30 22 400柑橘林柑橘林III 55 20 25 300加工厂的加工能力加工厂的加工能力 200 600 225（千蒲式耳）（千蒲式耳）（货物调度问题）（货物调度问题）某企业是一家新鲜柑橘产品的种植商和经营商，有某企业是一家新鲜柑橘产品的种植商和经营商，有I、II、II块块大的柑橘林及甲乙丙三个柑橘加工厂（柑橘林到加工厂的距离大的柑橘林及甲乙丙三个柑橘加工厂（柑橘林到加工厂的距离公里信息如红色字体数据）。现该企业与一家地方货车运输公公里信息如红色字体数据）。现该企业与一家地方货车运输公司联系，从柑橘林向加工厂运输柑橘。运输公司按照每蒲式耳司联系，从柑橘

9、林向加工厂运输柑橘。运输公司按照每蒲式耳柑橘运输每公里（记为蒲式耳柑橘运输每公里（记为蒲式耳-公里）的统一价格收费，该企业公里）的统一价格收费，该企业希望确定从各个柑橘林到各个加工厂运输多少蒲式耳，以使所希望确定从各个柑橘林到各个加工厂运输多少蒲式耳，以使所运输的柑橘蒲式耳运输的柑橘蒲式耳-公里的总数最小。公里的总数最小。12max(min)Z=c1x1+c2x2+cnxn x1 X=x2 xn b1 b=b2 bmC=(C1 C2 Cn)a11 a12 a1n令令 A=A=a21 a22 a2n am1 am2 amnmn一般形式：一般形式：a11x1+a12x2+a1nxn (=,(=,)

10、b)b1 1a21x1+a22x2+a2nxn (=,(=,)b)b2 2 am1x1+am2x2+amnxn (=,(=,)b bm mxj j 0(0(j=1,n)s.t.13二、线性规划问题的标准型二、线性规划问题的标准型 目标函数目标函数 max 变量变量 非负非负 约束条件约束条件 等式等式 约束常数约束常数 非负非负14解：引进3个新非负变量x3，x4，x5使不等式变为等式，标准型为：max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 4x1+x4=12 2x1+2x2+x5=14 x1，x2，x3，x4，x50例1.3将例1.1的数学模型化为标准型。ma

11、x Z=2x1+3x2 3x2 15 4x1 12 2x1+2x2 14 x1，x2015解：解：令令x3=x4-x5 添加松弛变量添加松弛变量x6 添加剩余变量添加剩余变量x7 令令S=-SmaxS=x1 2x2+3x4 3x5 x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,x7 0 0 将将 min S=-x1+2x2 3x3x1+x2+x3 7x1-x2+x3 2 2x1，x2 0 0，x3无限制无限制化为标准型。化为标准型。例例1.416 将将 min S=x1+2x2+3x3-2x1+x2+x3 9-3x1+x2+2x3 4 44x1-2x2-3x

12、3 4x1 0，x2 0 0，x3无限制无限制化为标准型。化为标准型。练习：练习：170102030 x2DABCmax S=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0一、线性规划问题的图解法一、线性规划问题的图解法解：解：(1)确定可行域确定可行域 x1 0 0 x1=0=0 (横轴横轴)x2 0 0 x2=0=0 (纵轴纵轴)x1+2x2 30 x1+2x2=30 l1 (0,15)(30,0)3x1+2x2=60 l2(0,30)(20,0)2x2=24203010 x11.2 线性规划问题的图解法及几何意义线性规划问题的图解法及几何

13、意义18(2)求最优解求最优解“等值线法等值线法”解：解：X*=(15 7.5)Smax=9750203010102030 x1x2DABC截距截距S=40 x1+50 x2 =x2=0.8x10.02 SC点点：使：使截距最大截距最大 x1+2x2=30 l1 3x1+2x2=60 l20=40 x1+50 x2 过原点过原点19 max Z=2x1+3x2例1.5解得：最优解解得：最优解B点（点（2，5）。）。最优值最优值 Z=22+35=19唯一最优解唯一最优解20用图解法求解线性规划问题 maxZ=40 x1+80 x2 s.t.x1+2x2 30 3x1+2x2 60 2x2 24

14、x1,x2 0例1.6解：最优解：BC线段B点 X(1)=(6,12)；C点 X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)maxZ=1200 整理得：x1=15-9 x2=7.5+4.5 (0 1)0203010102030 x1x2DABC无穷多解无穷多解21maxZ=2x1+4x2 s.t.2x1+x2 8 -2 x1+x2 2 x1，x2 0例1.7若目标函数由若目标函数由 min Z=2 x1+4 x2,最优解最优解 x1=4，x2=0，即，即(4,0)点点无界解无界解=可行域无界可行域无界 =解：由于可行域无界 无有限最优解-无界解Z=02x1+x2=8-2x1

15、+x2=28246x240 x122max S=3x1+2x2-x1-x2 1 1x1,x2 0 0无可行解无可行解-1x2-1x10总结总结 唯一解唯一解 无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解例例23通过以上各题图解法所得结论可以看出：（1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的；（2）若存在最优解，则一定在可行域的某顶点得到；（3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。（4）若可行域无界，则可能发生最优解无界的情况；（5）若可行域是空集，此时无最优解。上述理论具有普遍意义，对于两个以上变量

16、的线性规划问题都是成立。24 二、线性规划问题的解的概念二、线性规划问题的解的概念1.2 线性规划问题的图解法及几何意义线性规划问题的图解法及几何意义25(m n)r(A)=m,至少有一个至少有一个m 阶子式不为阶子式不为0不失一般性不失一般性,不妨假设不妨假设P1 Pm线性无关线性无关max S=CX AX=b X 0 0A Amn 满秩满秩基阵基阵A中一个子矩阵中一个子矩阵B是可逆矩是可逆矩 阵，阵，则方阵则方阵B称为称为LP问题的一个基阵。问题的一个基阵。a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnPm+1 PnP1 PmBNA

17、=B N 26A=(P1 Pm Pm+1 Pn)=(B N)X=x1 xm xm+1 xn 定义：定义：基向量基向量 非基向量非基向量=(XB XN)T有：有：AX=P1 x1+P2 x2+Pn xn=b定义：定义：基变量基变量 非基变量非基变量BXB+NXN=bBXB=b-NXNXB=B-1 b-B-1N XNAX=b 求解过程：求解过程：A=(B N)X=(XB XN)T XB XN(BN)=bTT目标函数：目标函数：S=CX=CB B-1 b+(CN-CB B-1 N)XN27 1.可行解可行解:满足约束条件的解 X=(x1,x2,xn)称为线性规划问题的可行解；所有可行解的集合称为可行

18、解集或可行域。2.最优解最优解:满足约束条件及目标函数的可行解称为线性规划问题的最优解。最优值最优值 3.基阵基阵:假设 A 是约束方程组的系数矩阵，其秩数为 m，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关的列向量组成，不失一般性，可假设:称 Pj(j=1,2,m)为基向量，与基向量 Pj 相对应的变量xj(j=1,2,m)称为基变量，否则称为非基变量。T若令非基变量若令非基变量 xm+1=xn=0,用高斯消元法用高斯消元法可求出可求出LP标准型的一个解标准型的一个解 X=(x1 x2 xm

19、0 0)T 称称 X 为为基本解基本解.28 为了进一步讨论线性规划问题的解，下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为：方程组(1.9)的一个基是B=(P1,P2,Pm),Pj=(a1j,amj),(j=1,2,m)，设 XB 是对应于这个基的基变量，即：XB=(x1,x2,xm)现若令(1.9)式中的非基变量xm+1=xn=0，并用高斯消去法求出一个解X=(x1,x2,xm,0,0)，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。TTT29

20、4.基本可行解基本可行解:满足非负条件(1.8)的基本解称为基本可行解。由此可见，基本可行解的非0分量的数目不大于m，并且都是非负的。5.可行基阵可行基阵:对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一般地讲，基本可行解的数目要小于基本解的数目，至多相等。以上提到的几种解的概念，可用图14来表示：基解可行解基本可行解30 1.凸集：假设凸集：假设K是是n维欧氏空间的一个点集，若对于维欧氏空间的一个点集，若对于K中的任意中的任意两点两点X1、X2，其连线上的所有点，其连线上的所有点 X1+(1-)X2，(0 1)都在集合都在集合K中，即：中

21、，即：X1+(1-)X2 K (0 1)则称则称K为凸集。为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。凸集。2.凸组合：设凸组合：设X1，X2，Xk是是n维欧氏空间维欧氏空间En中的中的k个个点，若存在点，若存在 1，2，k，且，且0 i 1，i=1,2,k，i=1，使，使X=1X1+2X2+kXk，则称，则称X为由为由X1，X2，Xk所构成的凸组合。所构成的凸组合。按照定义，凡是由按照定义，凡是由x，y的凸组合表示的点都在的

22、凸组合表示的点都在x，y的连线上，而且的连线上，而且反之亦然。反之亦然。3.顶点：顶点：假设假设K是凸集，是凸集，X K；X若不能用不同的两个点若不能用不同的两个点X1、X2 K的线性组合表示为：的线性组合表示为：X=X1+(1-)X2，(0 1)则称则称X为凸集为凸集K的一个顶点（或称为极点）。的一个顶点（或称为极点）。顶点不位于凸集顶点不位于凸集K中的任意不同两点的连线内。中的任意不同两点的连线内。三、基本定理三、基本定理31 定理定理1.1 若线性规划问题存在可行域，则其可行域：D=X|AX=b,X 0 ，是凸集。引理引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所

23、对应的系数列向量是线性无关的。定理定理1.2 线性规划问题的基本可行解对应于可行域的顶点。定理定理1.3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。定理定理1.4 若线性规划问题在k个顶点上达到最优解 （k2），则在这些顶点的凸组合上也达到最优解。32 根据图解法图解法得到如下的结论：（1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。1 (2)线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。(3)如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是

24、线性规划的最优解。虽然可行域的顶点个数是有限的(它们不超过 Cnm 个)，采用“枚举法”可以找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m、n的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。33A=(P1 Pm Pm+1 Pn)=(B N)X=(x1 xm xm+1 xn)T 基向量基向量|非基向量非基向量=(XB XN)T约束方程组：约束方程组：AX=P1 x1+P2 x2+Pn xn=bBXB+N XN=b BXB=b-NXNXB=B-1 b-B-1N XN约束方程：约束方程：AX=b

25、 A=(B N)X=(XB XN)T XB XN(B N)=b目标函数方程：目标函数方程：S=CX=CB B-1 b+(CN-CB B-1 N)XN基基变变量量 非非变变向量向量34 单纯形算法的基本思路是：根据问题的标准型，从可行域中单纯形算法的基本思路是：根据问题的标准型，从可行域中某个基本可行解某个基本可行解(顶点顶点)开始，转换到另一个基本可行解开始，转换到另一个基本可行解(顶点顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。就得到最优解。现在需要解决的问题是：现在需要解决的问题是：(1)为了使目标函

26、数逐步变优，应如何从可行域的一个顶点为了使目标函数逐步变优，应如何从可行域的一个顶点转移到可行域的另一个顶点？转移到可行域的另一个顶点？（2）目标函数何时达到最优值？判断标准是什么？）目标函数何时达到最优值？判断标准是什么？1.3 单纯形算法单纯形算法351确定初始基本可行解确定初始基本可行解对于标准型的线性规划问题(简写为 LP)：或 （1.9）这里 A=(aij)mn，Rank(A)=m。36从中一般可以直接观察到存在一个初始可行基B=(P1,P2,Pm)=（1.10）当线性规划的约束条件均为“=”形式的不等式或等式时，若不存在单位矩阵，就采用构造人造基的办法，即对不等式约束减去一个非负的

27、剩余变量后，再加上一个非负的人工变量；对于等式约束，加上一个非负的人工变量。这样总可以找到一个单位矩阵，关于这个方法将在本章第四节讨论。37 （1.10）式中的P1,P2,Pm称为基向量，其对应的变量称为基变量，模型中其它变量称为非基变量。在约束条件中把非基变量项移到等式的右边得：（1.11）令所有非基变量 ，得 X=(b1,b2,bm,0,0)又由于，故X满足约束条件，所以它是一个基可行解。式(1.11)就是基变量用非基变量表示的形式。T38cjc1ckcmcm+1cjcn CBXBb*x1xkxmxm+1xjxnc1x1b1*100a1m+1a1ja1nClXlbl*010alm+1alj

28、alncmxmbm*001amm+1amjamnCN-CBB-1A000 m+1 j n表13 初始单纯形表39 利用单纯形算法求解例利用单纯形算法求解例11的线性规划问题。的线性规划问题。Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 s.t.4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50cj23000iXBbx1x2x3x4x5x315031005x41240010 x514220017-Z023000例例18解：解：（1）由标准型得到初始单纯形表：）由标准型得到初始单纯形表：3x2+x3 =154x1+x4 =122x1+2x2

29、 x5=14 40 假定已求得(LP)的一个基本可行解 X(0)，为叙述方便,不失一般性，假设：令所有非基变量 ，得 把式(1.12)代入目标函数得：式（1.14）就是目标函数用非基变量表示的形式。(1.12)（1.13）（1.14）2最优性检验最优性检验41令 ，于是 再令 ，则得：（1.15）在式（1.15）中，非基变量的系数 ，称为各非基变量 （）的检验数检验数。42 若 为对应于基 B 的基本可行解，且对于一切 ，有 j 0，则 X 为线性规划问题的最优解。定理定理1.6 无穷多最优解判别定理无穷多最优解判别定理:若 为对应于基 B 的基本可行解，且对于一切 ，有 j 0，又存在某个非

30、基变量的检验数 ，则线性规划问题有无穷多最优解。定理定理1.7 无有限最优解判别定理无有限最优解判别定理：若 为对应于基 B 的基本可行解，有一个 ，而对于有 ，则线性规划问题无有限最优解(也称为无最优解)。以上讨论的都是针对标准型的，即求目标函数极大化问题。当求目标函数极小化时，一种情况如前所述，将其化为标准型；另一种情况是将判别定理中的检验数j 0改为 即可。（0）定理定理1.5 最优解判别定理最优解判别定理:43 由式由式(1.15)可知，当某些非基变量的检验数可知，当某些非基变量的检验数 j 0时，如果时，如果xj增加，则目标函数值还可以增加。当有增加，则目标函数值还可以增加。当有两个

31、或两个以上两个或两个以上 j 0时，那么选哪个非基变量作为时，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加的最快，我们换入变量呢？为了使目标函数值增加的最快，我们一般选择一般选择 j 0中的最大者，即：中的最大者，即：j=max l l 0 j所对应的变量所对应的变量xj为换入变量为换入变量(就是下一个基的基变就是下一个基的基变量量)。3.基变换基变换 （1）换入变量的确定）换入变量的确定44 因为基变量个数总是为m，所以换入一个变量之后还必须换出一个变量。下面我们来考虑如何选择换出变量。确定换出变量的原则是保持解的可行性。这就是说，要使原基本可行解的某一个正分量xj变为0，同时保持

32、其余分量均非负。具体实现是按“最小比例原则”进行，也称原则。若 则选基变量xl为换出变量。（3）旋转运算（迭代运算）在确定了换入变量xj与换出变量xl之后，要把xj和xl的位置对换，就是说，要把xj 所对应的列向量pj变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即可，称alj为旋转元。（2）换出变量的确定）换出变量的确定45 在确定了换入变量xj与换出变量xl之后，要把xj和xl的位置对换，就是说，要把xj 所对应的列向量pj变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即可，称alj为旋转元。（3）旋转运算（迭代运算）46cjc1ckcmcm+1cjcn CBXBb*x1xkxmx

33、m+1xjxnc1x1b1*100a1m+1a1ja1nClXlbl*010alm+1aljalncmxmbm*001amm+1amjamnCN-CBB-1A000 m+1 j n表13 初始单纯形表47 以表13中的元素alj(称为主元素或旋转元素)进行基变换：将第l行每个元素除以 alj，再将第 l行每个元素乘以 aij/alj 加到第 i 行(i=1,2,m,i l)，将第 l 行每个元素乘以 j/alj 加到检验数行，对应的新的目标函数值即为：经过基变换之后，针对于新基 B1 的基本可行解为：48 第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表；第二步：检查对应于非基变量

34、的检验数 k，kIN，(IN为非基变量指标集)，若所有 k 0，kIN，则已得到最优解，停止计算，否则转入下一步；第三步：在所有k 0，kIN 中，若有一个j 对应的系数 列向量 aij 0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据 max kk 0，kIN =j，确定 xj 为换 入变量(即为新基的基变量)，再根据：确定 xl为换出变量(即为新基的非基变量)，转下一步；第五步：以 alj 为主元素进行基变换，转回第二步。单纯形算法的计算步骤单纯形算法的计算步骤:49 利用单纯形算法求解例利用单纯形算法求解例11的线性规划问题。的线性规划问题。Max Z=2x1+3x2+

35、0 x3+0 x4+0 x5 3x2+x3=15 s.t.4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50cj23000iXBbx1x2x3x4x5x315031005x41240010 x514220017-Z023000例例18解：解：（1）由标准型得到初始单纯形表：）由标准型得到初始单纯形表：3x2+x3 =154x1+x4 =122x1+2x2 x5=14 50(2)max1,2=3=2，所以x2为换入变量。(3)因为1=2，2=3都大于0，且p1,p2的坐标有正分量存在因为5与x3那一行相对应，所以x3为换出变量；故x2对应列与x3对应行的相交处的3为主元

36、素；(4)以“3”为主元素进行旋转计算，进行行初等变换，得表15：表15cj23000iXBbx1x2x3x4x5x25011/300 x412400103x5420-2/3012-Z-1520-10051重复以上步骤得表16。表16这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解：X*=(2,5,0,4,0)目标函数的最大值为：Z*=19cj23000iXBBx1x2x3x4x5x25011/300 x44004/31-2x1210-1/301/2-Z-1900-1/30-1T52 利用单纯形算法求解线性规划问题。Max Z=4x1+3x2+0 x3+0 x4+0 x5

37、2x1+2x2+x3=1600 5x1+2.5x2+x4=2500 x1+x5=400 x1,x2,x3,x4,x50 解：（1）由标准型得到初始单纯形表17：表表17 cj43000iXBbx1x2x3x4x5x3160022100800 x4250052.5010500 x540010001400-Z043000例例1953 表18cj43000iXBbx1x2x3x4x5x38000210-2400 x450002.501-5200 x140010001-Z-16000300-4 表19cj43000iXBbx1x2x3x4x5x3400001-0.82200 x22000100.4-2

38、-x140010001400-Z-2200000-1.2254表110cj43000iXBbx1x2x3x4x5x5200000.5-0.41x2600011-0.40-x120010-0.50.40-Z-260000-1-0.40这时，检验数全部小于等于0，即目标函数已达到最大，因此得到最优解：X=(200,600,0,0,200)目标函数的最大值为：Z=2600T55 利用单纯形算法求解线性规划问题。Max Z=2x1+3x2+0 x3+0 x4+0 x5+0 x6 2x1+2x2+x3=12 s.t.x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1，x2，x3，x4，

39、x5,x60解：（1）由标准型得到初始单纯形表：表111cj230000iXBbx1x2x3x4x5x6x3122210006x481201004x516400010 x6120400013-Z0230000例例11056表112cj230000iXBbx1x2x3x4x5x6x3620100-1/23x4210010-1/22x5164000104x23010001/4-Z-920000-3/4 表113cj230000iXBbx1x2x3x4x5x6x32001-201/24x1210010-1/2x58000-4124x23010001/412-Z-13000-201/457在相同 对应

40、的变量中选择下标最大的那个基变量-换出变量；同时如果出现有两个或更多的检验数大于零且相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量，-避免出现“死循环”表114cj230000iXBbx1x2x3x4x5x6x30001-1-1/40 x1410011/40 x64000-21/21x220101/2-1/80-Z-14000-3/2-1/80最优解：X*=(4,2,0,0,0,4)目标函数的最大值为：Z*=14T 相同的问题相同的问题-退化问题退化问题-表表113581.4 单纯形算法的进一步讨论单纯形算法的进一步讨论 (一一)、大、大M法法(二二)、两阶段法、两阶段法初始基

41、本可行解的求法初始基本可行解的求法59解解:令令S=-S 加入松弛变量加入松弛变量x4,剩余变量剩余变量x5求解求解L.P.的最优解的最优解:x1 -2x2+x3 11 11-4x1+x2+2x3 3 3-2x1 +x3=1 1 x1 ,x2,x3 0minS=-3x1+x2+x3+x6+x7,x6,x7-M x6-M x7再加入再加入人工变量人工变量x6,x7(一一)、大、大M法法 例例s.t.x1 -2x2+x3+x4=1111-4x1+x2+2x3 -x5 =3 3-2x1 +x3 =1 1 x1 ,x2,x5 ,0max S=3x1-x2-x3s.t.60 x4111-211000 x

42、63-4120-110 x71-2010001表表13-6MM-13M-10-M00cj3-1-100-M-MXBb*x1x2x3x4x5x6x7x4111-211000 x63-4120-110 x71-2010001-S03-1-100-M-M61cj3-1-100-M-MXBb*x1x2x3x4x5x6x7x4111-211000 x63-4120-110 x71-2010001表表13-6MM-13M-10-M00 x4103-20100-1x610100-11-2x31-2010001表表21M-100-M01-3M62cj3-1-100-M-MXBb*x1x2x3x4x5x6x7x

43、4123001-22-5x210100-11-2x31-2010001表表31000-11-M-1-Mx141001/3-2/32/3-5/3x210100-11-2x390012/3-4/34/3-7/3表表4000-1/3-1/31/3-M2/3-M所有所有 j 0，X*=(4,1,9,0,0,0,0)T S=2 S=-263判定判定无解无解条件：条件：当进行到最优表时，仍有人工变量在当进行到最优表时，仍有人工变量在基中，且基中，且0，则说明原问题无可行解。则说明原问题无可行解。64用两阶段法求解用两阶段法求解L.P的最优解的最优解:解解:加入松弛变量、剩余变量、加入松弛变量、剩余变量、人

44、工变量：人工变量：x6,x7 第一阶段的问题第一阶段的问题min W=x6+x7=max W=-x6-x7 x1 -2x2+x3 11 11-4x1+x2+2x3 3 3-2x1 +x3=1 1 x1 ,x2,x3 0maxS=3x1-x2-x3 x1 -2x2+x3+x4=1111-4x1+x2+2x3 -x5 =3 3-2x1 +x3 =1 1 x1 ,x2,x5 ,0+x6+x7,x6,x7(二二)、两阶段法、两阶段法-例例s.t.s.t.65cj00000-1-1XBb*x1x2x3x4x5x6x7x4111-211000非非单单纯纯形形表表x63-4120-110 x71-20100

45、01-W 000000-1-1XBb*x1x2x3x4x5x6x7x4111-211000 x63-4120-110 x71-2010001-W4-6130-10066cj00000-1-1XBb*x1x2x3x4x5x6x7x4111-211000 x63-4120-110 x71-2010001-W4-6130-100 x4103-20100-1x610100-11-2x31-2010001-W10100-10-3x4123001-22-5x210100-11-2x31-2010001最优表最优表000000-1-167第二阶段的计算问题第二阶段的计算问题 x1 -2x2+x3+x4 =1

46、111-4x1+x2+2x3 -x5 =3 3-2x1 +x3 =1 1 x1 ,x2,x5 0max S=3x1-x2-x3cj3-1-100XBb*x1x2x3x4x5x4123001-2x210100-1x31-20100-S03-1-100s.t.68x141001/3-2/3x210100-1x390012/3-4/3表表2-2000-1/3-1/3cj3-1-100XBb*x1x2x3x4x5x412 3001-2x210100-1x31-20100表表121000-169原问题原问题 max S=Cj xj j=1n xj 0j=1n aij xj=bi(i=1,2,m)两阶段法

47、步骤两阶段法步骤作作辅助问题辅助问题 min W=yi i=1m xj，x人人 0j=1n aij xj+x人人=bi(i=1,2,m)第一阶段：解辅助问题，当进行到最优表时第一阶段：解辅助问题，当进行到最优表时、若若W=0,则得到原问题的一个基本可行则得到原问题的一个基本可行 解，转入第解，转入第2阶段。阶段。第二阶段：用求出的初始基本可行解求最优解。第二阶段：用求出的初始基本可行解求最优解。、若、若W0,则判定原问题无可行解则判定原问题无可行解70max S=2x1+x2 5x1+10 x2 82x1+2x2 1x1，x2 0第第(1)(1)阶段：阶段：min W=x55x1+10 x2-

48、x3+x5=82x1+2x2+x4=1x1 x5 0 x2x1O无可行解无可行解例例:s.t.71 0 0 0 0 1 0 0 0 0 1 b XB x1 x2 x3 x4 x5 8 x5 5 10 -1 0 1 1 x4 2 (2)0 1 0 -5 -10 1 0 0 3 x5 -5 0 -1 -5 1 1/2 x2 1 1 0 1/2 0 最优表最优表 5 0 1 5 0原问题无可行解原问题无可行解72(1)(1)、L.PL.P数学模型及标准型数学模型及标准型maxS=CXAX=b(b 0)X 0(2)(2)、L.PL.P问题解的性质：图解法问题解的性质：图解法总结总结(3)(3)、单纯形

49、法：、单纯形法：1)1)、标准型中有单位基。、标准型中有单位基。2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变 量，使之构成单位基。量，使之构成单位基。求求max S时，目标中时，目标中M MXj 求求min S时，目标中时，目标中M MXj3)3)、判定最优解定理：、判定最优解定理：maxS问题，检验数问题，检验数 j 0minS问题，检验数问题，检验数 j 073建模有问题建模有问题5)5)、退化解问题、退化解问题4)4)、解的几种情况：、解的几种情况：唯一解唯一解无穷多解最优表中无穷多解最优表中非非基变量检验数有为基变量检验数有为0 0者。者。无界

50、解无界解 max,j 0 但但Pj 0 min,j 0 但但Pj 0无可行解最优表中人工变量基变量中，且无可行解最优表中人工变量基变量中，且0 0。74我们以我们以 作为标准型，以作为标准型，以 作为最优解的判别准则。还有其它形式，下作为最优解的判别准则。还有其它形式，下面把几种检验数的表示方法及判别准则汇总于表面把几种检验数的表示方法及判别准则汇总于表126。表126 Max Z=CTXAX=b,X00Min Z=CTXAX=b,X00cj-zj0 00 0zj-cj0 00 0标准型标准型检验数检验数 对于目标函数求极小值的问题采用上述任何一种处理方法，其单纯形法的步骤与求极大值的方法相同