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

《第一章运筹学线性规划1001上传.ppt》由会员分享，可在线阅读，更多相关《第一章运筹学线性规划1001上传.ppt（294页珍藏版）》请在三一文库上搜索。

1、运筹学 Operational Research,天津大学管理学院,教师简介,张小涛，博士，副教授 研究方向： 计算实验金融，中小企业融资 Email： ,运筹学简介,什么是运筹学? 运筹学的简史 运筹学的分支有哪些? 运筹学研究的一般程序 课程要求,2019/6/23,古籍中的运筹问题,田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议 十万个为什么.数学分册P.312 最早记载的对策论范例。,2019/6/23,古籍中的运筹问题,祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事

2、毕,却以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。 沈括梦溪笔谈.补笔谈卷二.权智,2019/6/23,“运筹”的出典,据史记记载：汉高祖刘邦称赞张良：运筹策帷帐中，决胜千里外，子房功也。 司马迁史记留侯世家 “筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。 英文名：Operational Research,港台地区译为：作业研究、运作研究。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。 大学里为什么要开设运筹学呢?请自己考虑。,2019/6/2

3、3,我国当代数学家在运筹学中的贡献,1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。 20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。 凡是讲图论的优化的教科书，多半有专门的一章名：Chinese Postman Problems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。,2019/6/23,运筹学（Operational Research),运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济

4、管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,2019/6/23,运筹学的应用,经济、工商管理； 计算机算法的设计； 数学理论； 军事； 工业；农、林、牧、渔业; 医学、生物、理化、遗传； 工程计划、安排等“优化”; 学习、日常生活、旅游等。,2019/6/23,运筹学的发展：三个来源,军 事 管 理 经 济,军事：运筹学的主要发源地,古代军事运筹学思想 中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马

5、、围魏救赵、行军运粮，等等。 国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。,运筹学的正式产生：第二次世界大战 鲍德西（Bawdsey）雷达站的研究 1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。 Blackett备忘录 1941年12月， Blackett应盟国政府的要求，写了五份题为“Scientists at the Oper

6、ational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。 大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁 英国战斗机中队援法的决策,管理,泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等 爱尔朗（Erlong）的排队论公式 19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。,经济（数理经济学）,Von Neum

7、ann 与对策论 1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。 康托洛维奇与“生产组织与计划中的数学方法” 30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。,运筹学的性质和特点,应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。 运筹学的特点 定量化分析

8、多学科交叉，如综合利用了心理学、经济学、物理等方法 最优决策,管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,运筹学的分支,规划论(分线性、非线性、整数、目标、动态及随机规划等) 图论与网络优化； 排队论、存储论、搜索论； 对策论(博弈论)、； 可靠性理论; 全面质量管理(TQC); 计划评审、维修更新理论等。,课程教材：,胡运权，运筹学教程，北京：清华大学出版社，2007；,主要参考书： 1 丁以中主编，管理科学-运用Spreadsheet建模和求解，北京：清华大学出版社，2003； 2 美弗雷德里克S希利尔（Frederick S Hillier）,任

9、建标译,数据、模型与决策（原书名 Introduction to Management Science），北京：中国财政经济出版社，2004； 3谢金星， 优化建模LINDO/LINGO软件，清华大学出版社 4 钱颂迪等，运筹学，北京：清华大学出版社，1990； 5吴育华,杜纲. 管理科学基础，天津大学出版社。,主要授课内容：,线性规划:模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整数规划 图论与网络分析 网络计划 动态规划 风险型决策 排队论 随机模拟,课程基本要求,掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算 具备计算机解题的基本能力 认真听

10、课，勤于思考，多看书 每周一交作业，独立完成 闭卷考试 有问题请Email联系,第一章 线性规划 （Linear Programming，简称LP）,1 线性规划的模型与图解法,一、LP问题及其数学模型,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素： （1）决策变量 设甲产品生产x1，乙产品生产x2 （2）目标函数 Max Z=7 x1 +12x2 （3）约束条件,9 x1 +4x2360 4x1 +5x2 200 3 x1 +10x2 300 x1 , x20,s.t.,返回,Subject To

11、， 意为“使其满足”,LP模型的一般形式,其中: X= (x1,x2, , xn) T 为决策变量 C=(c1,c2, , cn) 称为价格系数 A=(aij)mn 称为技术系数 b= (b1,b2, , bm) T 称为资源系数,线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定,线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。 可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,连

12、续性假定：线性规划问题中的决策变量应取连续值。 确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,例2 某市今年要兴建大量住宅,已知有三种住宅体系可以 大量兴建，各体系资源用量及今年供应量见下表： 要求在充分利用各种资源条件下使建造住宅的总面积为最 大(即求安排各住宅多少m2)，求建造方案。,解: 设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2, z为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养

13、分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1 +0.1x210 0.2x1 +0.3x2 5 0.3x1 +0.4x2 8 0.2x2 7 x1 , x20,s.t.,Min Z=300 x1 +200x2,思考题,二、线性规划的图解法,1. 步骤,（1）作约束的图形可行域,可行解

14、的集合,先作非负约束 再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10x2=300,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12x2=168,如：令7 x1 +12x2=84 7 x1 +12x2=168,X*=（20，24）， Z*=428,最优解： x1 = 0， x2 = 1 最优目标值 z = 3,课堂练习 图解法求解线性规划,2. LP 解的几种情况,注：出现（3）、（4）情况时，建模有问题,补充知识：凸集,凸集：在点集中任

15、取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,在凸集中，点A，B，C，D称为极点（或顶点）。,A,B,C,D,从图解法中我们了解到以下事实： 若LP问题的可行域存在，则可行域一定是凸集。 若LP问题的最优解存在，则最优解或最优解之一（如果有 无穷多最优解的话）一定是可行域凸集的某个极点（顶 点）。,思路：最优解先在可行域中找。（可行域为空集，则无可 行解，故无最优解。） 最优解在可行域的极点中找。 极点是有限个，若两个极点都是最优解，则两个极点所连 线段上的所有点均是最优解）,定义：LP问题的可行域的极点（顶点）称为基本可行解。,三、 线性规划应用举例与软件求解,例1 （下料问题）

16、 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,例1 （下料问题） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,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 + x4 100 2x2 + x3 + 3x5 + 2x6 + x7 100 x1 + x3+ 3x4 +

17、 2x6 + 3x7 + 4x8 100 x1, x2, x3, x4, x5, x6, x7, x8 0,设 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,min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8,s.t.,第二节 单纯形法,单纯形法是求解线性规划的主要算法，1947 年由美国斯坦福大学教授丹捷格（G.B.Danzig） 提出。 尽管在其后的几十年中，又有一些算法问世， 但单纯形法以其简

18、单实用的特色始终保持着绝对 的“市场”占有率。,1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型：,标准型的特征：Max型、等式约束、非负约束,一、单纯形法的预备知识,非标准形式如何化为标准,1) Min型化为Max型,加负号,因为，求一个函数 的极小点，等价于求该 函数的负函数的极大点。,注意： Min型化为Max型求解后，最优解不变，但最优值差负号。,2) 不等式约束化为等式约束,分析：以例1中煤的约束为例,之所以“不等”是因为左右两边有一个差额，称为“松 弛量”，若在左边加上这个松弛量，则化为等式。而这 个松弛量也是变量，记为X3 ，则有,X3称为松弛变量。问题：

19、它的实际意义是什么？, 煤资源的“剩余”。,练习：请将例1的约束化为标准型,解：增加松弛变量,则约束化为,易见，增加的松弛变量的系数恰构成一个单位阵I。,一般地，记松弛变量的向量为 Xs，则,问题：松弛变量在目标中的系数为何？, 0。,3) 当模型中有某变量 xk 没有非负要求，称 为自由变量, 则可令,化为标准型。,复习：非齐次线性方程组解,例：解非齐次线性方程组,增广矩阵,（1）,若线性方程组没有现成的基，可利用增广矩阵的行初等变换 法找到一组基。,为基变量。,称,其变量个数=,此方程组的解为,其中,为任意实数。,为非基变量，或自由变量。,称,称非基变量,为0的解（15，24，5，0，0）

20、叫基解。,若对（1）式中的变量再加上非负限制,其解为,由,的非负性知：,（2）,从而,解域为,注意：此时的,已经不是任意实数。,不是自由变量了。,而对于带有非负约束的方程组,解的每个分量都是非负数，就叫做可行解。,如果基解是可行的，就叫基可行解。,基可行解所对应的基称为可行基。,非基,可 行 最优基 基,非 可 行 基,四种形式的基之间的关系为：,基与解的对应关系：,非可行解,可 行 基本 解 可行解,基本解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,所对应的解,例如,是可行解。,所对应的解,是基解。,也是可行解，故而是基本可行解。,2.基本概念,（1）可行解与最优解

21、,直观上，可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案。,（2）基矩阵与基变量,基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。,基向量：基B中的列；其余称非基向量。,基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。, 6个。,一般地，mn 阶矩阵A中基的个数最多有多少个？,问题：本例的A中一共有几个基？,（3）基本解与基本可行解,可见：一个基本解是由一个基决定的。 注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,称非负的基本解为基本可

22、行解（简称基可行解）。,例4：在上例中,求相应于基B1和B2的基本解，它们是否基本可行解？,上二组概念间的联系：,几种解之间的关系：,问题：基本可行解是可行域中的哪些点？,3.基本定理,（1）线性规划的可行域是一个凸多面体。,（2）线性规划的最优解（若存在的话）必能在可行 域的角点获得。,（3）线性规划可行域的角点与基本可行解一一对应。,二、单纯形法的步骤,确定一个初始基可行解,检验这个基可行解是否最优,寻找一个更好的基可行解,停止,Dantzig的单纯形法把寻优的目标集中在所有基本可行解 （即可行域顶点）中。 其基本思路是从一个初始的基本可行解出发，寻找一条达到 最优基本可行解的最佳途径。

23、单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。,方法：若A中含I，则B0=I； 若A中不含I，则可用人工变量法构 造一个I。,问题：若B0=I，则X0=？,2. 最优性检验,问题：用什么检验？, 目标。,问题：非最优的特征为何？,判断现行的基本可行解是否最优,假如已求得一个基本可行解,将这一基本可行解代入目标

24、函数，可求得相应的目标函数值,其中 分别表示基变量和 非基变量所对应的价值系数子向量。,要判定 是否已经达到最大值，只需将 代入目标函数，使目标函数用非基变量 表示，即：,其中 称为非基变量N的检验向量，它的各个分量称为检验数。若N的每一个检验数均小于等于0，即N0，那么现在的基本可行解就是最优解。,定理1：最优解判别定理 对于线性规划问题 若某个基本可行解所对应的检验向量 ， 则这个基本可行解就是最优解。,定理2：无穷多最优解判别定理 若 是一个基本可行解，所对应的检验向量 ，其中存在一个检验数m+k=0， 则线性规划问题有无穷多最优解。,基本可行解的改进,如果现行的基本可行解不是最优解，即

25、在检验向量 中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是： 先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。 由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所增加。,换入变量和换出变量的确定：,换入变量的确定 最大增加原则,假设检验向量 ， 若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若 则选

26、取对应的 为换入变量， 由于 且为最大， 因此当 由零增至正值， 可使目标函数值 最大限度的增加。,换出变量的确定 最小比值原则 如果确定 为换入变量，方程 其中 为中与 对应的系数列向量。 现在需在 中确定一个基变量为换出变量。 当 由零慢慢增加到某个值时， 的非负性可能被打破。 为保持解的可行性，可以按最小比值原则确定换出变量： 若,则选取对应的基变量 为换出变量。,定理3：无最优解判别定理 若 是一个基本可行解，有一个检验数 ， 但是 ，则该线性规划问题无最优解。,证：令 ，则得新的可行解 将上式代入 因为 , 故当+时，Z+。,寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基

27、可行解，相当于从上一个基B0变换为下一个新的基B1，因 此，本步骤也称为基变换。,（基变换）,以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,(2) 确定初始基可行解、检验,（3）换基、计算下一个基可行解、再检验，直至最优,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。,回顾单纯形法步骤,单纯形表的主要结构：,问题：第一张表的B-1=？,单位阵I。,检验数的公式是什么？,例5：用单纯形法求解例1,问题：标准模型的A中是否含I？,松弛

28、变量系数恰好构成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)T Z*=428,例：,用单纯形法求解,X*=(6,0,8,0)T

29、Z*= -6,注：单纯形表中的信息 每一列的含义： B-1(b A)=(B-1b, B-1 P1,， B-1 Pn) 每个表中的B和B-1的查找： B从初表中找； B-1从当前表中找，对应于初表中的I的位置。,以第2个表为例：,终表分析最优基B* 和(B*)-1的查找,借助人工变量求初始的基本可行解,若约束方程组含有“”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。 因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。 加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问

30、题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。,考虑线性规划问题： 为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为 初始可行基，在每个约束方程组的左端加上一个人工变量 可得到：, 添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量 为基变量， 即可得到一个初始的基本可行解 这样的基本可行解对原线性规划没有意义的。 但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代

31、出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。 此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。,大M法,大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-。这

32、样只要基变量中还存在人工变量，目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。,例4、用大M法求解下面的线性规划问题: 解： 首先将原问题化为标准型 添加人工变量 ，并在目标函数中分别赋予-,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-,-1 1 0 -1 0 0 1,1,X2,2,1/2,2 0 -1 1 0 1 -1,1,X6,

33、-M,1/1,-1 1 0 -1 0 0 1,1,X7,-M,2/1,1 1 -1 0 0 1 0,2,X6,-M,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,Z,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,1+2M 0 -M 2+M 0 0 -2-2M,2-M,Z,2/1,1 0 0 1 1 0 -1,2,X5,0,-1 2+2M -M -M 0 0 0,-3M,Z,3/1,0 1 0 0 1 0 0,3,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,0 1 0 0 1 0 0,3,X2,2

34、,1 0 0 1 1 0 -1,2,X4,0,1 1 -1 0 0 1 0,2,X2,2,2 0 -1 1 0 1 -1,1,X4,0,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1/2/1/2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-1 0 0 0 -2 -M -M,6,Z,-1 0 1 0 1 -1 0,1,X3,0,-3 0 2 0 0 -2-M -M,4,Z,-1 0 1 0 1 -1 0,1,X5,0,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,Z,3/2 /1/2,0 0 1/2 1/2 1 -1/2 -1

35、/2,3/2,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,最优解 最优值,两阶段法,两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。 两阶段法的步骤： 求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。 如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。 求原问题的最优解。在第一阶段已

36、求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解,例5、用两阶段法求解例4中的线性规划问题。 解：首先将问题化为标准型 添加人工变量x6,x7,并建立辅助线性规划如下：,由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,0,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,0,-,-1 1 0 -1 0 0 1,1,X2,0,1/2,2 0 -1 1 0 1 -1,1,X6,1,1/1,-1 1 0 -1 0 0 1,1,X7,1,2/1,1 1 -1 0 0 1 0,2,X6,1,0

37、 0 0 0 0 1 1,0,W,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,-2 0 1 -1 0 0 2,1,W,2/1,1 0 0 1 1 0 -1,2,X5,0,0 -2 1 1 0 0 0,3,W,3/1,0 1 0 0 1 0 0,3,X5,0,x1 x2 x3 x4 x5 x6 x7,b,XB,CB,0 0 0 0 0 1 1,C,辅助规划所有检验数：,原问题已得一个初始基本可行解，,由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组 该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用

38、单纯形表求解。,-1 0 0 0 -2,6,Z,1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1,2 3 1,X4 X2 X3,0 2 0,-3 0 2 0 0,4,Z,2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1,1 2 1,X4 X2 X5,0 2 0,0 0 1/2 3/2 0,5/2,Z,1/2/1/2 - 3/2/1/2,1 0 -1/2 1/2 0 0 1 -1/2 -1/2 0 0 0 1/2 1/2 1,1/2 3/2 3/2,X1 X2 X5,-1 2 0,x1 x2 x3 x4 x5,b,XB,CB,-1 2 0 0 0,C,可得最优解 ，目

39、标函数值maxZ=6， 与用大M法的结果完全相同。,单纯形表与线性规划问题的讨论,无可行解,通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。 人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。,例6、求解下列线性规划问题 解： 首先将问题化为标准型 令 ，则,故引入人工变量 ， 并利用大M法求解,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,

40、0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,6/1 - 3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0 -M -2,x4 x7 x2,3 4 3,1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,3/1 4/1 -,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3 -M -2,x1 x7 x2,3 1 3,1 0 2 1 0 1 0 -1 0 0 -3 -1 -1

41、 -1 1 1 0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,无最优解,无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。 判别方法：无最优解判别定理 在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在

42、某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解，,可以,可以,例7、试用单纯形法求解下列线性规划问题： 解：引入松弛变量x3,x4化为标准型,因 但 所以原问题 无最优解,退化解,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。 遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一

43、个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点， 解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,例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,-

44、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=，,无穷多最优解,无穷多最优解判别原理： 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。 例：最优表： 非基变量检验 数 ， 所以有无穷多 最优解。 最优解集为可行域两个顶点的凸组合：,改进单纯形法的特点 利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数