【运筹学】教程_课件.ppt

运筹学OperationalResearch,天津大学管理学院,教师简介,张小涛，博士，副教授研究方向：计算实验金融，中小企业融资Email：zxtzxttju,运筹学简介,什么是运筹学?运筹学的简史运筹学的分支有哪些?运筹学研究的一般程序课程要求,2020/6/5,古籍中的运筹问题,田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议十万个为什么.数学分册P.312最早记载的对策论范例。,2020/6/5,古籍中的运筹问题,祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事毕,却以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。沈括梦溪笔谈.补笔谈卷二.权智,2020/6/5,“运筹”的出典,据史记记载：汉高祖刘邦称赞张良：运筹策帷帐中，决胜千里外，子房功也。司马迁史记留侯世家“筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。英文名：OperationalResearch,港台地区译为：作业研究、运作研究。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。大学里为什么要开设运筹学呢?请自己考虑。,2020/6/5,我国当代数学家在运筹学中的贡献,1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门的一章名：ChinesePostmanProblems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。,2020/6/5,运筹学（OperationalResearch),运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,2020/6/5,运筹学的应用,经济、工商管理；计算机算法的设计；数学理论；军事；工业；农、林、牧、渔业;医学、生物、理化、遗传；工程计划、安排等“优化”;学习、日常生活、旅游等。,2020/6/5,运筹学的发展：三个来源,军事管理经济,军事：运筹学的主要发源地,古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。,运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了五份题为“ScientistsattheOperationalLevel”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策,管理,泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。,经济（数理经济学）,VonNeumann与对策论1932年，VonNeumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。康托洛维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。,运筹学的性质和特点,应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理等方法最优决策,管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,运筹学的分支,规划论(分线性、非线性、整数、目标、动态及随机规划等)图论与网络优化；排队论、存储论、搜索论；对策论(博弈论)、；可靠性理论;全面质量管理(TQC);计划评审、维修更新理论等。,课程教材：,胡运权，运筹学教程，北京：清华大学出版社，2007；,主要参考书：1丁以中主编，管理科学-运用Spreadsheet建模和求解，北京：清华大学出版社，2003；2美弗雷德里克S希利尔（FrederickSHillier）,任建标译,数据、模型与决策（原书名IntroductiontoManagementScience），北京：中国财政经济出版社，2004；3谢金星，优化建模LINDO/LINGO软件，清华大学出版社4钱颂迪等，运筹学，北京：清华大学出版社，1990；5吴育华,杜纲.管理科学基础，天津大学出版社。,主要授课内容：,线性规划:模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整数规划图论与网络分析网络计划动态规划风险型决策排队论随机模拟,课程基本要求,掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算具备计算机解题的基本能力认真听课，勤于思考，多看书每周四交作业，独立完成闭卷考试有问题请Email联系,第一章线性规划（LinearProgramming，简称LP）,1线性规划的模型与图解法,一、LP问题及其数学模型,例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素：（1）决策变量设甲产品生产x1，乙产品生产x2（2）目标函数MaxZ=7x1+12x2（3）约束条件,9x1+4x23604x1+5x22003x1+10 x2300 x1,x20,s.t.,返回,SubjectTo，意为“使其满足”,LP模型的一般形式,其中:X=(x1,x2,xn)T为决策变量C=(c1,c2,cn)称为价格系数A=(aij)mn称为技术系数b=(b1,b2,bm)T称为资源系数,线性规划问题隐含的假定：比例性假定可加性假定连续性假定确定性假定,线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,连续性假定：线性规划问题中的决策变量应取连续值。确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,例2某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。,解:设今年计划修建砖混、壁板、大模住宅各为x1,x2,x3m2,z为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5x1+0.1x2100.2x1+0.3x250.3x1+0.4x280.2x27x1,x20,s.t.,MinZ=300 x1+200 x2,思考题,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,表1-2,表1-3,单位：100m2,单位；元/100m2,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,二、线性规划的图解法,1.步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10 x2=300,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12x2=168,如：令7x1+12x2=847x1+12x2=168,X*=（20，24），Z*=428,最优解：x1=0，x2=1最优目标值z=3,课堂练习图解法求解线性规划,2.LP解的几种情况,注：出现（3）、（4）情况时，建模有问题,补充知识：凸集,凸集：在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,在凸集中，点A，B，C，D称为极点（或顶点）。,A,B,C,D,从图解法中我们了解到以下事实：若LP问题的可行域存在，则可行域一定是凸集。若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。,思路：最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）最优解在可行域的极点中找。极点是有限个，若两个极点都是最优解，则两个极点所连线段上的所有点均是最优解）,定义：LP问题的可行域的极点（顶点）称为基本可行解。,三、线性规划应用举例与软件求解,例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,2,0,1,0.1,1,2,0,0.3,1,1,1,0.9,1,0,3,0,0,3,0,1.1,0,2,2,0.2,0,1,3,0.8,0,0,4,1.4,2x1+x2+x3+x41002x2+x3+3x5+2x6+x7100 x1+x3+3x4+2x6+3x7+4x8100 x1,x2,x3,x4,x5,x6,x7,x80,设x1,x2,x3,x4,x5,x6,x7,x8分别为上述8种方案下料的原材料根数，建立如下的LP模型：,最优解为：x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0,minZ=x1+x2+x3+x4+x5+x6+x7+x8,s.t.,第二节单纯形法,单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。,1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：,标准型的特征：Max型、等式约束、非负约束,一、单纯形法的预备知识,非标准形式如何化为标准,1)Min型化为Max型,加负号,因为，求一个函数的极小点，等价于求该函数的负函数的极大点。,注意：Min型化为Max型求解后，最优解不变，但最优值差负号。,2)不等式约束化为等式约束,分析：以例1中煤的约束为例,之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3，则有,X3称为松弛变量。问题：它的实际意义是什么？,煤资源的“剩余”。,练习：请将例1的约束化为标准型,解：增加松弛变量,则约束化为,易见，增加的松弛变量的系数恰构成一个单位阵I。,一般地，记松弛变量的向量为Xs，则,问题：松弛变量在目标中的系数为何？,0。,3)当模型中有某变量xk没有非负要求，称为自由变量,则可令,化为标准型。,复习：非齐次线性方程组解,例：解非齐次线性方程组,增广矩阵,（1）,若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。,为基变量。,称,其变量个数=,此方程组的解为,其中,为任意实数。,为非基变量，或自由变量。,称,称非基变量,为0的解（15，24，5，0，0）叫基解。,若对（1）式中的变量再加上非负限制,其解为,由,的非负性知：,（2）,从而,解域为,注意：此时的,已经不是任意实数。,不是自由变量了。,而对于带有非负约束的方程组,解的每个分量都是非负数，就叫做可行解。,如果基解是可行的，就叫基可行解。,基可行解所对应的基称为可行基。,非基,可行最优基基,非可行基,四种形式的基之间的关系为：,基与解的对应关系：,非可行解,可行基本解可行解,基本解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,所对应的解,例如,是可行解。,所对应的解,是基解。,也是可行解，故而是基本可行解。,2.基本概念,（1）可行解与最优解,直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。,（2）基矩阵与基变量,基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。,基向量：基B中的列；其余称非基向量。,基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。,6个。,一般地，mn阶矩阵A中基的个数最多有多少个？,问题：本例的A中一共有几个基？,（3）基本解与基本可行解,可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,称非负的基本解为基本可行解（简称基可行解）。,例4：在上例中,求相应于基B1和B2的基本解，它们是否基本可行解？,上二组概念间的联系：,几种解之间的关系：,问题：基本可行解是可行域中的哪些点？,3.基本定理,（1）线性规划的可行域是一个凸多面体。,（2）线性规划的最优解（若存在的话）必能在可行域的角点获得。,（3）线性规划可行域的角点与基本可行解一一对应。,二、单纯形法的步骤,确定一个初始基可行解,检验这个基可行解是否最优,寻找一个更好的基可行解,停止,Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（2）。,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。,方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构造一个I。,问题：若B0=I，则X0=？,2.最优性检验,问题：用什么检验？,目标。,问题：非最优的特征为何？,判断现行的基本可行解是否最优,假如已求得一个基本可行解,将这一基本可行解代入目标函数，可求得相应的目标函数值,其中分别表示基变量和非基变量所对应的价值系数子向量。,要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：,其中称为非基变量N的检验向量，它的各个分量称为检验数。若N的每一个检验数均小于等于0，即N0，那么现在的基本可行解就是最优解。,定理1：最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。,定理2：无穷多最优解判别定理若是一个基本可行解，所对应的检验向量，其中存在一个检验数m+k=0，则线性规划问题有无穷多最优解。,基本可行解的改进,如果现行的基本可行解不是最优解，即在检验向量中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由可知，这样的变换一定能使目标函数值有所增加。,换入变量和换出变量的确定：,换入变量的确定最大增加原则,假设检验向量，若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若则选取对应的为换入变量，由于且为最大，因此当由零增至正值，可使目标函数值最大限度的增加。,换出变量的确定最小比值原则如果确定为换入变量，方程其中为中与对应的系数列向量。现在需在中确定一个基变量为换出变量。当由零慢慢增加到某个值时，的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：若,则选取对应的基变量为换出变量。,定理3：无最优解判别定理若是一个基本可行解，有一个检验数，但是，则该线性规划问题无最优解。,证：令，则得新的可行解将上式代入因为,故当+时，Z+。,寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。,（基变换）,以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,(2)确定初始基可行解、检验,（3）换基、计算下一个基可行解、再检验，直至最优,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。,回顾单纯形法步骤,单纯形表的主要结构：,问题：第一张表的B-1=？,单位阵I。,检验数的公式是什么？,例5：用单纯形法求解例1,问题：标准模型的A中是否含I？,松弛变量系数恰好构成I。,的计算:,四、单纯形法的实现单纯形表,12,0,0,0,单纯形表:,7,90,的计算:,40,30,枢纽元素,x3,x4,x2,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,即:,即:,30.8,20,100,x3,x1,x2,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,X*=(20,24,84,0,0)TZ*=428,例：,用单纯形法求解,X*=(6,0,8,0)TZ*=-6,注：单纯形表中的信息每一列的含义：B-1(bA)=(B-1b,B-1P1,，B-1Pn)每个表中的B和B-1的查找：B从初表中找；B-1从当前表中找，对应于初表中的I的位置。,以第2个表为例：,终表分析最优基B*和(B*)-1的查找,借助人工变量求初始的基本可行解,若约束方程组含有“”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。,考虑线性规划问题：为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量可得到：,添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量为基变量，即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的。但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。,大M法,大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。,例4、用大M法求解下面的线性规划问题:解：首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予-,-,01-1/2-1/201/21/2,3/2,X2,2,10-1/21/201/2-1/2,1/2,X1,-1,-,-110-1001,1,X2,2,1/2,20-1101-1,1,X6,-M,1/1,-110-1001,1,X7,-M,2/1,11-10010,2,X6,-M,001/23/20-1/2-M-3/2-M,5/2,Z,001/21/21-1/2-1/2,3/2,X5,0,1+2M0-M2+M00-2-2M,2-M,Z,2/1,100110-1,2,X5,0,-12+2M-M-M000,-3M,Z,3/1,0100100,3,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,0100100,3,X2,2,100110-1,2,X4,0,11-10010,2,X2,2,20-1101-1,1,X4,0,-,01-1/2-1/201/21/2,3/2,X2,2,1/2/1/2,10-1/21/201/2-1/2,1/2,X1,-1,-1000-2-M-M,6,Z,-10101-10,1,X3,0,-30200-2-M-M,4,Z,-10101-10,1,X5,0,001/23/20-1/2-M-3/2-M,5/2,Z,3/2/1/2,001/21/21-1/2-1/2,3/2,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,最优解最优值,两阶段法,两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤：求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解,例5、用两阶段法求解例4中的线性规划问题。解：首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下：,由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：,01-1/2-1/201/21/2,3/2,X2,0,10-1/21/201/2-1/2,1/2,X1,0,-,-110-1001,1,X2,0,1/2,20-1101-1,1,X6,1,1/1,-110-1001,1,X7,1,2/1,11-10010,2,X6,1,0000011,0,W,001/21/21-1/2-1/2,3/2,X5,0,-201-1002,1,W,2/1,100110-1,2,X5,0,0-211000,3,W,3/1,0100100,3,X5,0,x1x2x3x4x5x6x7,b,XB,CB,0000011,C,辅助规划所有检验数：,原问题已得一个初始基本可行解，,由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。,-1000-2,6,Z,1001101001-10101,231,X4X2X3,020,-30200,4,Z,20-11011-100-10101,121,X4X2X5,020,001/23/20,5/2,Z,1/2/1/2-3/2/1/2,10-1/21/2001-1/2-1/20001/21/21,1/23/23/2,X1X2X5,-120,x1x2x3x4x5,b,XB,CB,-12000,C,可得最优解，目标函数值maxZ=6，与用大M法的结果完全相同。,单纯形表与线性规划问题的讨论,无可行解,通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。,例6、求解下列线性规划问题解：首先将问题化为标准型令，则,故引入人工变量，并利用大M法求解,C,-3-2-1000-M-M,CB,XB,b,x1x2x3x4x5x6x7x8,0-M-M,x4x7x8,643,1111000010-10-101001-100-101,6/1-3/1,Z,-7M,-6-4M,-15-M,-3+M-2+M-1-2M0-M-M00,0-M-2,x4x7x2,343,1021010-110-10-101001-100-101,3/14/1-,Z,Z,-3+M0-3-M0-M-202-M,-3-M-2,x1x7x2,313,1021010-100-3-1-1-11101-100-101,003-3M3-M-M1-M0-1,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,无最优解,无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解，,可以,可以,例7、试用单纯形法求解下列线性规划问题：解：引入松弛变量x3,x4化为标准型,因但所以原问题无最优解,退化解,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,例8、求解下述线性规划问题：解：引入松弛变量化标准型,0,0,0,-24,2,-80,3,0,Z,-5,-6,0,-42,0,-8,0,5,Z,1,0,0,0,1,0,0,1,x3,2,1,2,0,6,0,-24,1,1,x1,3,3,2,1,30,0,-8,0,3,x5,0,0,-3,0,-42,5,-8,0,0,Z,1,1,0,0,1,0,0,1,x7,0,0,1,0,6,-1,-24,1,0,x1,3,0,-1,1,30,-3,-8,0,0,x5,0,-,1,1,0,0,1,0,0,1,x7,0,0,0,1,0,6,-1,-24,1,0,x6,0,0,0,0,1,36,-4,-32,1,0,x5,0,x7,x6,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-24,2,-80,3,C,第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。,可得最优解，目标函数值maxZ=，,无穷多最优解,无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。最优解集为可行域两个顶点的凸组合：,改进单纯形法的特点利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数据：基本可行解，其相应的目标函数值，非基变量检验数，及其换入变量，设主元列元素，及其换出变量，设利用它们可得到一组新的基变量以及新的可行基1。,改进单纯形法,为基变量下标,为非基变量下标,对任一基本可行解，只要知道，上述关键数据都可以从线性规划问题的初始数据直接计算出来。因此如何计算基本可行解对应的可行基的逆阵成为改进单纯形法的关键改进单纯形法推导出从可行基变换到1时，到的变换公式。当初始可行基为单位矩阵时，变换公式将更具有优越性，因为这样可以避免矩阵求逆的麻烦以下推导从到的变换公式：,假设当前基，,基变换中用非基变量取代基变量可得新基前后二个基相比仅相差一列，且比较以上二式，可得,其中表示第个元素为1，其它元素均为零的单位列向量，为主元列元素。,假设，则,第列（换出变量对应列）,第行,所以由,主元素,改进单纯形法的步骤（1）根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始可行基B的逆阵-1，得初始基本可行解。（2）计算单纯形乘子，得目标函数当前值（3）计算非基变量检验数，若N0，则当前解已是最优解，停止计算；否则转下一步。（4）根据，确定非基变量为换入变量，计算,若0，则问题没有有限最优解，停止计算，否则转下一步。,（5）根据，确定基变量为换出变量。（6）用替代得新基1，由变换公式计算新基的逆阵1-1，求出新的基本可行解其中为变换矩阵，构造方法是：从一个单位矩阵出发，把换出变量在基B中的对应列的单位向量，替换成换入变量对应的系数列向量，并做如下变形，主元素（应在主对角线上）取倒数，其它元素除以主元素并取相反数。重复（2）（6）直至求得最优解。,换入,无界解,换出,最优解,初始基,新基,例9、试用改进单纯形法求解解：（）观察法确定，为基变量为非基变量,（2）计算单纯行乘子目标函数当前值（3）非基变量检验数,(4）选择换入变量故为换入变量。计算,()确定换出变量确定为换出变量，主元素(6)用代替得新可行基为基变量，为非基变量，重复以上步骤，进入第二循环,(1)(2)(3),(4)选择换入变量(5)选择换出变量,主元素(6)用代替得新可行基为基变量，为非基变量，进入第三循环.,(1)(2)(3)非基变量对应的检验数全部非正，故当前解即为最优解，相应的目标函数最优值。,六、单纯形法总结,1、Min型单纯形表与Max型的区别仅在于：令k=minj0的xk进基，当0时最优。,2、解的几种情况及其在单纯形表上的体现（讨论Max型）,唯一最优解,j0,非基0但B-1Pk0,无可行解,用大M法求解，最优基中含有X人,退化解,最优解中某基变量为0,第三节对偶问题与灵敏度分析,一、对偶问题及其模型例7：回顾例1,这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。,例7称为例1的对偶问题，记为（D），例1称为例7的原问题,记为（P）。,对偶模型的一般式,以例7为例，原问题为,（P）,（D）,这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：,原问题（P）对偶问题（D）目标max型目标min型有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵的转置,此外，还有一种情形,例8：写出下面线性规划的对偶规划模型：,例8：写出下面线性规划的对偶规划模型：,minZ=-CXs.T-AX-bX0,对称性定理：对偶问题的对偶是原问题。,maxW=-Ybs.TYACY0,二、对偶问题的性质,弱对偶原理：设和分别是问题（P）和（D）的可行解，则必有,推论：若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。,对偶问题的性质,对偶问题的性质,推论：在一对对偶问题(P)和(D)中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,推论：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题无界。,例1,试估计它们目标函数的界，并验证弱对偶性原理。,（P）,对偶问题的性质,解：,（D）,由观察可知：，分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论可知，W的最小值不能小于10，Z的最大值不能超过40。,对偶问题的性质,考虑,4.对偶定理若（P）有最优解，则（D）也有最优解，且最优值相同。,证：对（P）增加松弛变量，化为,设其最优基为B，终表为,其检验数为,问题：(1)由性质4可知，对偶问题最优解的表达式Y*=？,(2)求Y*是否有必要重新求解（D）？,CBB-1,不必。可以从原问题（P）的单纯形终表获得。,请指出其对偶问题的最优解和最优值。,5.互补松弛定理,y1yiymym+1ym+jyn+m,x1xjxnxn+1xn+ixn+m,对偶问题的变量对偶问题的松弛变量,原始问题的变量原始问题的松弛变量,xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0,直观上,定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。,影子价格,设：B是问题P的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+y*Ibi+y*mbm当bi变为bi+1时（其余右端项不变，也不影响B）,影子价格,目标函数最优值变为：Z*=y*1b1+y*2b2+y*I（bi+1）+y*mbmZ*=Z*Z*=y*i,也