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

《【运筹学】教程_课件.ppt》由会员分享，可在线阅读，更多相关《【运筹学】教程_课件.ppt（217页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学Operational Research天津大学管理学院天津大学管理学院教师简介张小涛，博士，副教授 研究方向：计算实验金融，中小企业融资 Email： 运筹学简介运筹学简介什么是运筹学什么是运筹学?运筹学的简史运筹学的简史运筹学的分支有哪些运筹学的分支有哪些?运筹学研究的一般程序运筹学研究的一般程序课程要求课程要求2023/4/4古籍中的运筹问题古籍中的运筹问题田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议田忌的一位谋士比较了六种对策后建议 十万个为什么十万个为什么.数学分册数学分册P.312P.312最早记载的最早记

2、载的对策论对策论范例。范例。2023/4/4古籍中的运筹问题古籍中的运筹问题祥符中祥符中,禁火。时禁火。时丁晋公丁晋公主营复宫室主营复宫室,患取土远患取土远,公乃令凿通衢公乃令凿通衢取土取土,不日皆不日皆成巨堑。乃决汴水入堑中成巨堑。乃决汴水入堑中,引诸道竹木引诸道竹木排筏及船运杂材排筏及船运杂材,尽自堑中入至宫门。尽自堑中入至宫门。事毕事毕,却以斥却以斥弃瓦砾灰壤实于堑弃瓦砾灰壤实于堑中中,复复为街衢。一举而三役济为街衢。一举而三役济,计计省费省费以亿万以亿万计。计。沈括沈括梦溪笔谈梦溪笔谈.补笔谈卷二补笔谈卷二.权智权智2023/4/4“运筹运筹”的出典的出典据据史记史记记载：汉高祖刘邦称

3、赞张良：记载：汉高祖刘邦称赞张良：运筹运筹策策帷帐中，决胜千里外，子房功也。帷帐中，决胜千里外，子房功也。司马迁司马迁史记史记留侯世家留侯世家“筹筹”是古代比算盘还早的计算工具之一。是古代比算盘还早的计算工具之一。“运运筹筹”是计划、安排、比较、决策优化的一个过程。是计划、安排、比较、决策优化的一个过程。英文名：英文名：Operational ResearchOperational Research,港台地区译为：港台地区译为：作业研究作业研究、运作研究运作研究。五十年代末华罗庚。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几

4、十年来随着计算机的普及它的应用越来筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。越广泛。其作用越来越被人们所认识。大学里为什么要开设大学里为什么要开设运筹学运筹学呢呢?请自己考虑。请自己考虑。2023/4/4我国当代数学家在我国当代数学家在运运筹学筹学中的贡献中的贡献19571957年起中科院一批数学家作了许多令国年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。际同行称道的工作：如物资调运问题。2020世纪世纪7070年代华罗庚先生在中国大力创导年代华罗庚先生在中国大力创导推广推广“统筹学统筹学”当时就获得第一代领导人的当时就获得第一代领导人的

5、首肯，在国际数学界被称为是全世界最大而首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。有成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门凡是讲图论的优化的教科书，多半有专门的一章名：的一章名：C Chinese hinese P Postman ostman P Problems,roblems,其中其中无一例外的要提到管梅谷先生的杰出工作：无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题中国邮递员问题(CPP)(CPP)。2023/4/4运筹学运筹学（Operational Research)Operational Research)运筹学是运用科学的方法

6、（如分析、试运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。案，以实现最有效的管理。2023/4/4运筹学的应用运筹学的应用:经济、工商管理；经济、工商管理；:计算机算法的设计；计算机算法的设计；:数学理论；数学理论；:军事；军事；:工业；农、林、牧、渔业工业；农、林、牧、渔业;:医学、生物、理化、遗

7、传；医学、生物、理化、遗传；:工程计划、安排等工程计划、安排等“优化优化”;:学习、日常生活、旅游等。学习、日常生活、旅游等。2023/4/4运筹学的发展：三个来源 军 事 管 理 经 济 军事：运筹学的主要发源地古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系

8、；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了五份题为“Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何

9、打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策管理泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。经济（数理经济学）Von Neumann 与对策论1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。康托洛

10、维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。运筹学的性质和特点v应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。v运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理等方法最优决策管理管理运筹学运筹学的工作程序的工作程序明确问题明确问题问题分类问题分类建立数学模型建立数学模型求解数学模型求解数学模型结果分析结果分析实施实施运筹学的分支运筹学的

11、分支:规划论规划论(分线性、非线性、整数、目标、动分线性、非线性、整数、目标、动态及随机规划等态及随机规划等):图论与网络优化；图论与网络优化；:排队论、存储论、搜索论；排队论、存储论、搜索论；:对策论对策论(博弈论博弈论)、；、；:可靠性理论可靠性理论;:全面质量管理全面质量管理(TQC);(TQC);:计划评审、维修更新理论等。计划评审、维修更新理论等。课程教材：课程教材：胡运权，运筹学教程，北京：清华大学出版社，胡运权，运筹学教程，北京：清华大学出版社，2007；主要参考书：主要参考书：1 丁以中主编，管理科学丁以中主编，管理科学-运用运用Spreadsheet建模和求解，北建模和求解，

12、北京：清华大学出版社，京：清华大学出版社，2003；2 美美弗雷德里克弗雷德里克S希利尔（希利尔（Frederick S Hillier）,任建标译任建标译,数数据、模型与决策（原书名据、模型与决策（原书名 Introduction to Management Science），），北京：中国财政经济出版社，北京：中国财政经济出版社，2004；3谢金星，谢金星，优化建模优化建模LINDO/LINGO软件，清华大学出版社软件，清华大学出版社4 钱颂迪等，运筹学，北京：清华大学出版社，钱颂迪等，运筹学，北京：清华大学出版社，1990；5吴育华吴育华,杜纲杜纲.管理科学基础管理科学基础，天津大学出版

13、社。，天津大学出版社。主要授课内容：主要授课内容：线性规划线性规划:模型与图解法，单纯形法，模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整对偶与灵敏度分析，运输问题，线性整数规划数规划 图论与网络分析图论与网络分析 网络计划网络计划动态规划动态规划 风险型决策风险型决策 排队论排队论随机模拟随机模拟课程基本要求掌握好基本概念、主要模型形式及其特点、适当掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算的建模能力，必要的算法原理及简单的计算具备计算机解题的基本能力具备计算机解题的基本能力认真听课，勤于思考，多看书认真听课，勤于思考，多看书每周四交作业，独

14、立完成每周四交作业，独立完成闭卷考试闭卷考试有问题请有问题请EmailEmail联系联系第一章第一章 线性规划线性规划（Linear Programming，简称，简称LP）1 线性规划的模型与图解法线性规划的模型与图解法一、一、LP问题及其数学模型问题及其数学模型例例1 某工厂可生产甲、乙两种产品，需消耗煤、电、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。最大的生产计划。127单价单价300103油油20054电电36049煤煤资源限制资源限制乙乙甲甲产品产品资源资源甲甲乙乙资源限制资源限制

15、煤煤94360电电45200油油310300单价单价712产品产品资源资源线性规划模型三要素：线性规划模型三要素：（1）决策变量）决策变量 设甲产品生产设甲产品生产x1，乙产品生产，乙产品生产x2（2）目标函数）目标函数 Max Z=7 x1+12x2（3）约束条件）约束条件9 x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.返回Subject To，意为意为“使其满使其满足足”Max（Min）Z=c1 x1+c2 x2+cn xn a11 x1+a12 x2+a1n xn （=,）b1 am1 x1+am2 x2+amn xn （=,）bmx1，x2

16、，xn 0s.t.LP模型的一般形式模型的一般形式矩阵表示矩阵表示Max Z=CXAX bX 0s.t.其中其中:X=(x1,x2,xn)T 为决策变量为决策变量 C=(c1,c2,cn)称为称为价格系数价格系数A=(aij)mn 称为称为技术系数技术系数b=(b1,b2,bm)T 称为称为资源系数资源系数线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定比例性假定可加性假定可加性假定连续性假定连续性假定确定性假定确定性假定线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定：比例性假定：决策变量变化引起的目标决策变量变化引起的目标函数的改变量和决策变量的改变量成比函数的改变量和

17、决策变量的改变量成比例，同样，每个决策变量的变化引起约例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变束方程左端值的改变量和该变量的改变量成比例。量成比例。可加性假定：可加性假定：每个决策变量对目标函数每个决策变量对目标函数和约束方程的影响是独立于其他变量的，和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数目标函数值是每个决策变量对目标函数贡献的总和。贡献的总和。连续性假定：连续性假定：线性规划问题中的线性规划问题中的决策变量应取连续值。决策变量应取连续值。确定性假定：确定性假定：线性规划问题中的线性规划问题中的所有参数都是确定的参数。线性所有参数都是

18、确定的参数。线性规划问题不包含随机因素。规划问题不包含随机因素。例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。水泥水泥(公斤公斤/m2)4000(千工日千工日)147000(千块千块)150000(吨吨)20000(吨吨)110000(千元千元)资源限量资源限量3.518025120大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105砖混住宅砖混住宅人工人工(工日工日/m2)砖砖(块块/m2)钢材钢材(公斤公斤/m2)造价造

19、价(元元/m2)资源资源住宅体系住宅体系 解:设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2,z为总面积,则本问题的数学模型为:前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个个变量，变量，10个约束条件。个约束条件。课堂练习课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其某蓄场每日要为每头牲畜购买饲料，以使其获取所需的获取所需的A、B、C、D四种养分。有关数据如四种养分。有关数据如下表，现饲料可从市场上出售的下表，现饲料可从市场上出售的M、N两种饲料两种饲料中选择，试决定总花费最小的购买方案。（列中选择

20、，试决定总花费最小的购买方案。（列出模型）出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头每头日需日需10587养分养分饲料饲料课堂练习课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其获取所需的某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四四种养分。有关数据如下表，现饲料可从市场上出售的种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选两种饲料中选择，试决定总花费最小的购买方案。（列出模型）择，试决定总花费最小的购买方案。（列出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头日需每头日

21、需10587养分养分饲料饲料答案：答案：设购买设购买M饲料饲料x1，N饲料饲料x20.5 x1+0.1x2100.2x1+0.3x2 50.3x1+0.4x2 8 0.2x2 7x1,x20s.t.Min Z=300 x1+200 x2思考题思考题月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m2解：设 表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。月份 1 2 3

22、4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m215102012经过上面的讨论，得到下面的LP模型：目标函数约束条件二、线性规划的图解法二、线性规划的图解法1.步骤步骤（1）作约束的图形）作约束的图形可行域可行域可行解的集合可行解的集合先作非负约束先作非负约束再作资源约束再作资源约束9x1+4x2=3604x1+5x2=2003x1+10 x2=300公共部分，即为可行域公共部分，即为可行域例：煤电油例例：煤电油例Max Z=7 x1+12x29 x1+4x2

23、3604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.x1x240206080100204060801000（2）作目标函数的等值线）作目标函数的等值线给给z不同的值，作相应直线，判断出不同的值，作相应直线，判断出z增大时，直线的移动方向增大时，直线的移动方向将直线向增大方向移动，直至可行域将直线向增大方向移动，直至可行域边界，交点边界，交点X*即为最优解。即为最优解。7x1+12x2=847x1+12x2=168如：令如：令7 x1+12x2=84 7 x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x24020608

24、0100204060801000X*=（20，24），），Z*=428最优解：最优解：x1=0，x2 =1 最优目标值最优目标值 z =3课堂练习课堂练习图解法求解线性规划图解法求解线性规划0 01 12 23 34 41 12 23 34 4x1x2O O-1-1-2-2(1)(2)(3)2.LP 解的几种情况解的几种情况（1）唯一解）唯一解（2）多重最优解）多重最优解（3）无可行解）无可行解注：出现（注：出现（3）、（）、（4）情况时，建模有问题）情况时，建模有问题（4）无有限最优解）无有限最优解补充知识：凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。在凸集中，

25、点A，B，C，D称为极点（或顶点）。ABCD从图解法中我们了解到以下事实：若LP问题的可行域存在，则可行域一定是凸集。若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。思路：最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）最优解在可行域的极点中找。极点是有限个，若两个极点都是最优解，则两个极点所连线段上的所有点均是最优解）定义：LP问题的可行域的极点（顶点）称为基本可行解。三、三、线性规划应用举例与软件求解线性规划应用举例与软件求解 例例1 1（下料问题）下料问题）某工厂要做某工厂要做100100套钢架，每套用长为套钢架，

26、每套用长为2.9 m,2.1 2.9 m,2.1 m,1.5 mm,1.5 m的圆钢各一根。已知原料每的圆钢各一根。已知原料每根长根长7.4 m7.4 m，问：应如何下料，可使，问：应如何下料，可使所用原料最省？所用原料最省？例例1 1（下料问题）下料问题）某工厂要做某工厂要做100100套钢架，每套用套钢架，每套用长为长为2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每的圆钢各一根。已知原料每根长根长7.4 m7.4 m，问：应如何下料，可使所用原料最省？，问：应如何下料，可使所用原料最省？方案2.92.11.5余料7.4 m7.4 m2.9m2.

27、9m2.1m2.1m1.5 m1.5 m2010.11200.31110.910300301.10220.20130.80041.4505010103030 2x 2x1 1+x+x2 2+x+x3 3+x+x4 4 100 100 2x 2x2 2+x+x3 3 +3x+3x5 5+2x+2x6 6+x+x7 7 100 100 x x1 1 +x +x3 3+3x+3x4 4 +2x +2x6 6+3x+3x7 7+4x+4x8 8 100 100 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6,x,x7 7,x,x8 8 0 0设设 x x1 1,x,

28、x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6,x,x7 7,x,x8 8 分别为上述分别为上述8 8种方案下料的原材料根数，种方案下料的原材料根数，建立如下的建立如下的LPLP模型：模型：最优解为：最优解为：x x1 1=10,x=10,x2 2=50,x=50,x3 3=0,x=0,x4 4=30,x=30,x5 5=0,x=0,x6 6=0,x=0,x7 7=0,x=0,x8 8=0=0min Z=xmin Z=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6+x+x7 7+x+x8 8s.t.余料1.52.12.9方案2010.11200

29、.31110.910300301.10220.20130.80041.4第二节 单纯形法 单纯形法是求解线性规划的主要算法，单纯形法是求解线性规划的主要算法，19471947年由美国斯坦福大学教授丹捷格（年由美国斯坦福大学教授丹捷格（G.B.DanzigG.B.Danzig）提出。提出。尽管在其后的几十年中，又有一些算法问世，尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对但单纯形法以其简单实用的特色始终保持着绝对的的“市场市场”占有率。占有率。1.1.线性规划的标准型线性规划的标准型 用单纯形法求解线性规划的前提是先将模用单纯形法求解线性规划的前提是先将模型

30、化为标准型：型化为标准型：标准型的特征：标准型的特征：MaxMax型、等式约束、非负约束型、等式约束、非负约束一、单纯形法的预备知识一、单纯形法的预备知识非标准形式如何化为标准非标准形式如何化为标准1)1)MinMin型化为型化为MaxMax型型 加负号加负号 因为，求一个函数因为，求一个函数的极小点，等价于求该的极小点，等价于求该函数的负函数的极大点。函数的负函数的极大点。注意：注意：MinMin型化为型化为MaxMax型求解后，最优解不变，但最优值差负号。型求解后，最优解不变，但最优值差负号。2)不等式约束化为等式约束不等式约束化为等式约束分析：分析：以例以例1中煤的约束为例中煤的约束为例

31、之所以之所以“不等不等”是因为左右两边有一个差额，称为是因为左右两边有一个差额，称为“松松弛量弛量”，若在左边加上这个松弛量，则化为等式。而这，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为个松弛量也是变量，记为X X3 3 ，则有，则有X X3 3称为松弛变量。问题：称为松弛变量。问题：它的实际意义是什么？它的实际意义是什么？煤资源的煤资源的“剩余剩余”。练习：请将例练习：请将例1的约束化为标准型的约束化为标准型解：增加松弛变量解：增加松弛变量则约束化为则约束化为易见，增加的松弛变量的系数恰构成一个单位阵易见，增加的松弛变量的系数恰构成一个单位阵I I。一般地，记松弛变量的向

32、量为一般地，记松弛变量的向量为 Xs，则，则问题：松弛变量在目标中的系数为何？问题：松弛变量在目标中的系数为何？0 0。3)3)当模型中有某变量当模型中有某变量 x xk k 没有非负要求，没有非负要求，称称为自由变量为自由变量,则可令则可令 化为标准型。化为标准型。复习：非齐次线性方程组解例：解非齐次线性方程组增广矩阵（1）若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。为基变量。称其变量个数=此方程组的解为其中为任意实数。为非基变量，或自由变量。称称非基变量为0的解（15，24，5，0，0）叫基解。若对（1）式中的变量再加上非负限制其解为由的非负性知：（2）从而解域为注意

33、：此时的已经不是任意实数。不是自由变量了。而对于带有非负约束的方程组解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解。基可行解所对应的基称为可行基。非基可行 最优基基 非 可 行 基四种形式的基之间的关系为：基与解的对应关系：非可行解可行 基本解 可行解 基本解解与解之间的关系为：基解基可行基基可行解最优基基最优解所对应的解例如是可行解。所对应的解是基解。也是可行解，故而是基本可行解。2.基本概念（1）可行解与最优解）可行解与最优解直观上，直观上，可行解是可行域中的点，是一个可行的方案；可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。最优解是

34、可行域的角点，是一个最优的方案。（2）基矩阵与基变量基矩阵基矩阵(简称基简称基)：系数阵系数阵A中的中的m阶可逆子阵，记阶可逆子阵，记 为为B；其余部分称为非基矩阵，记为；其余部分称为非基矩阵，记为N。基向量：基向量：基基B中的列；其余称非基向量。中的列；其余称非基向量。基变量：基变量：与基向量与基向量Pj对应的决策变量对应的决策变量xj，记其组成的记其组成的 向量为向量为XB；与非基向量对应的变量称非基变；与非基向量对应的变量称非基变 量，记其组成的向量为量，记其组成的向量为XN。6 6个。个。一般地，一般地，m mn n 阶矩阵阶矩阵A A中基的个数最多有多少个？中基的个数最多有多少个？问

35、题：本例的问题：本例的A A中一共有几个基？中一共有几个基？（3）基本解与基本可行解）基本解与基本可行解可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为称非负的基本解为基本可行解基本可行解（简称基可行解）。（简称基可行解）。例例4：在上例中：在上例中求相应于基求相应于基B1和和B2的基本解，它们是否基本可行解的基本解，它们是否基本可行解？上二组概念间的联系：系数阵系数阵A中可找出若干个基中可找出若干个基B每个基每个基B都对应于一个基本解

36、都对应于一个基本解非负的基本解就是基本可行解非负的基本解就是基本可行解几种解之几种解之间的关系：的关系：可行解可行解基本解基本解非可行解非可行解基本可行解基本可行解问题：基本可行解是可行域中的哪些点？问题：基本可行解是可行域中的哪些点？3.基本定理（1 1）线性规划的可行域是一个）线性规划的可行域是一个凸凸多面体。多面体。（2 2）线性规划的最优解（若存在的话）必能在可行）线性规划的最优解（若存在的话）必能在可行 域的域的角点角点获得。获得。（3 3）线性规划可行域的）线性规划可行域的角点角点与与基本可行解基本可行解一一对应。一一对应。二、单纯形法的步骤确定一个初始基可行解确定一个初始基可行解

37、检验这个基可行解是否最优检验这个基可行解是否最优寻找一个更好的基可行解寻找一个更好的基可行解否否是是停停止止 DantzigDantzig的单纯形法把寻优的目标集中在所有基本可行解的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。最优基本可行解的最佳途径。单纯形法的一般步骤如下：单纯形法的一般步骤如下：（1 1）寻找一个初始的基本可行解。寻找一个初始的基本可行解。（2 2）检查现行的基本可行解是否最优，如果为最优，检查现行的基本可行解

38、是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。则停止迭代，已找到最优解，否则转一步。（3 3）移至目标函数值有所改善的另一个基本可行解，移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（然后转会到步骤（2 2）。）。1.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，由于基可行解是由一个可行基决定的，因此，确定初始基可行解确定初始基可行解X X0 0相当于确定一个初始可行基相当于确定一个初始可行基B B0 0。方法：方法：若若A中含中含I，则，则B0=I；若若A中不含中不含I，则可用人工变量法构，则可用人工变量法构 造一个造一个I。问题：若问题：若B0=I，则，

39、则X0=？2.最优性检验最优性检验问题：用什么：用什么检验？目目标。问题：非最优的特征为何？问题：非最优的特征为何？n判断现行的基本可行解是否最优判断现行的基本可行解是否最优 假如已求得一个基本可行解假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中其中分别表示基变量和分别表示基变量和非基变量所对应的价值系数子向量。非基变量所对应的价值系数子向量。要判定是否已经达到最大值，只需将要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即：其中其中 称为非

40、基变量称为非基变量N N的的检验向量，它的各个分量称为检验数。若检验向量，它的各个分量称为检验数。若N N的每一个检验数均小于的每一个检验数均小于等于等于0 0，即，即N N00，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。则这个基本可行解就是最优解。定理定理2 2：无穷多最优解判别定理：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中存在一个检验

41、数，其中存在一个检验数m+km+k=0=0，则线性规划问题有无穷多最优解。则线性规划问题有无穷多最优解。n 基本可行解的改进基本可行解的改进 如果现行的基本可行解不是最优解，即在检验向量如果现行的基本可行解不是最优解，即在检验向量 中中存存在在正正的的检检验验数数，则则需需在在原原基基本本可可行行解解的的基基础础上上寻寻找找一一个个新新的的基基本本可可行行解解，并并使使目目标标函函数数值值有有所所改改善善。具具体体做法是：做法是：先先从从检检验验数数为为正正的的非非基基变变量量中中确确定定一一个个换换入入变变量量，使使它它从从非非基基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它

42、的值从零增至正值），再再从从原原来来的的基基变变量量中中确确定定一一个个换换出出变变量量，使使它它从从基基变变量量变变成成非非基变量（将它的值从正值减至零）。基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所增加。可知，这样的变换一定能使目标函数值有所增加。换入变量和换出变量的确定换入变量和换出变量的确定：l换入变量的确定换入变量的确定 最大增加原则最大增加原则 假设检验向量假设检验向量 ，若其中有两个以上的检验数为正，那么为了使目标函数值增加得快若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常

43、要用些，通常要用“最大增加原则最大增加原则”，即选取最大正检验数所对应的非基，即选取最大正检验数所对应的非基变量为换入变量，即若变量为换入变量，即若 则选取对应的则选取对应的 为换入变量，为换入变量，由于且为最大，由于且为最大，因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。l 换出变量的确定换出变量的确定 最小比值原则最小比值原则 如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。当由零慢慢增加到某个值时，当由零

44、慢慢增加到某个值时，的非负性可能被打破。的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小比值原则确定换出变量：若若则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。定理定理3 3：无最优解判别定理：无最优解判别定理 若若 是一个基本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是，则该线性规划问题无最优解。但是，则该线性规划问题无最优解。证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 ,故当故当+时，时，Z+Z+。寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行由于基可行解与基对应

45、，即寻找一个新的基可行解，相当于从上一个基解，相当于从上一个基B0变换为下一个新的基变换为下一个新的基B1，因，因此，本步骤也称为基变换。此，本步骤也称为基变换。（基变换）（基变换）进基进基出基出基 以例以例1 1为例，可按上述单纯形法的步骤求出其最优解，其为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型(2)(2)确定初始基可行解、检验确定初始基可行解、检验（3 3）换基、计算下一个基可行解、再检验，直至最优）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。问题：当模型规模较大时，计算量

46、很大。事实上，单纯形法的实现是在单纯形表上完成的。事实上，单纯形法的实现是在单纯形表上完成的。三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。式，是单纯形法的具体实现。回顾单纯形法步骤回顾单纯形法步骤单纯形表的主要结构：单纯形表的主要结构：问题：第一张表的问题：第一张表的B-1=？单位阵单位阵I。检验数的公式是什么？检验数的公式是什么？例5：用单纯形法求解例1问题：标准模型的问题：标准模型的A中是否含中是否含I？松弛变量系数恰好构成松弛变量系数恰好构成I。的计算的计算:XBCBB-1bx1x2x3x4x5四、单纯形法的实现

47、四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1+12x29 x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1+12x29

48、x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:790的计算的计算:4030 x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1+12x29 x1+4x23604x1+5x2 2003 x1+10 x2 3

49、00 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 枢纽枢纽元素元素x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.

50、8010-0.43.4000-1.2即即:x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.2即即:30.820100 x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等