天大运筹学课件1(线性规划,运输问题等)

1、天津大学管理与经济学部天津大学管理与经济学部教师简介张小涛，博士，副教授 研究方向： 计算实验金融，中小企业融资 Email： 什么是运筹学什么是运筹学? ?运筹学的简史运筹学的简史运筹学的分支有哪些运筹学的分支有哪些? ?运筹学研究的一般程序运筹学研究的一般程序课程要求课程要求2022-6-20田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议田忌的一位谋士比较了六种对策后建议 十万个为什么十万个为什么. .数学分册数学分册P.312P.312最早记载的最早记载的对策论对策论范例。范例。2022-6-20123456上上上中中下

2、下下中中下上下中上上下下中下上上中中齐王田忌祥符中祥符中, ,禁火。时禁火。时丁晋公丁晋公主营复宫室主营复宫室, ,患取土远患取土远, ,公乃令凿通衢公乃令凿通衢取土取土, ,不日皆不日皆成巨堑。乃决汴水入堑中成巨堑。乃决汴水入堑中, ,引诸道竹木引诸道竹木排筏及船运杂材排筏及船运杂材, ,尽自堑中入至宫门。尽自堑中入至宫门。事毕事毕, ,却以斥却以斥弃瓦砾灰壤实于堑弃瓦砾灰壤实于堑中中, ,复复为街衢。一举而三役济为街衢。一举而三役济, ,计计省费省费以亿万以亿万计。计。 沈括沈括梦溪笔谈梦溪笔谈. .补笔谈卷二补笔谈卷二. .权智权智2022-6-20据据史记史记记载：汉高祖刘邦称赞张良：

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

4、用越来越被人们所认识。越广泛。其作用越来越被人们所认识。大学里为什么要开设大学里为什么要开设运筹学运筹学呢呢? ?请自己考虑。请自己考虑。2022-6-20运筹学是运用科学的方法（如分析、试验、运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，安排，为决策者提供有依据的最优方案，以实现最有效的管理。以实现最有效的管理。 2022-6-20:经济、工商管理；经

5、济、工商管理；:计算机算法的设计；计算机算法的设计；:数学理论；数学理论；:军事；军事；:工业；农、林、牧、渔业工业；农、林、牧、渔业; ;:医学、生物、理化、遗传；医学、生物、理化、遗传；:工程计划、安排等工程计划、安排等“优化优化”; ;:学习、日常生活、旅游等。学习、日常生活、旅游等。2022-6-20运筹学的发展：三个来源 军 事 管 理 经 济 军事：运筹学的主要发源地古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、

6、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。通通过研究使原先平均击落一架敌过研究使原先平均击落一架敌机要发机要发2000020000发炮弹改善为只要发炮弹改善为只要40004000发炮弹。发炮弹。 管理泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面

7、的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。经济（数理经济学）Von Neumann 与对策论1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。康托洛维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。19571957年起中科院一批数学

8、家作了许多令国际年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。同行称道的工作：如物资调运问题。2020世纪世纪7070年代华罗庚先生在中国大力创导推年代华罗庚先生在中国大力创导推广广“统筹学统筹学”当时就获得第一代领导人的首当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门的凡是讲图论的优化的教科书，多半有专门的一章名：一章名：C Chinese hinese P Postman ostman P Problems,roblems,其中

9、无其中无一例外的要提到管梅谷先生的杰出工作：一例外的要提到管梅谷先生的杰出工作：2022-6-20运筹学在实践中运筹学在实践中的一些应用效果的一些应用效果组织组织应用应用年年每年节约开支（美元）每年节约开支（美元）联合航空公司联合航空公司为满足乘客需求的以最底为满足乘客需求的以最底的成本进行订票出和机场的成本进行订票出和机场的工作班次排程的工作班次排程19861986600600万万CitgoCitgo石油公司石油公司优化炼油运作以及产品的优化炼油运作以及产品的供应配送和营销供应配送和营销1987198770007000万万旧金山警署旧金山警署用计算机系统最优排程和用计算机系统最优排程和巡警设

10、置巡警设置1989198911001100万万IBMIBM整合备件库存的全国网络整合备件库存的全国网络以改进服务支持以改进服务支持1990199020002000万万施乐公司施乐公司维修用户机器的战略修正维修用户机器的战略修正以缩短反应时间和改进维以缩短反应时间和改进维修人员生产率修人员生产率19751975生产率提高生产率提高50%50%宝洁公司宝洁公司重新设计北美生产和分销重新设计北美生产和分销系统以降低成本、改进市系统以降低成本、改进市场进入速度场进入速度199719972 2亿亿中国中国为满足国家未来能源需求为满足国家未来能源需求的大型项目的优选和排程的大型项目的优选和排程199519

11、954.254.25亿亿美洲航空公司美洲航空公司为机组人员和服务人员优为机组人员和服务人员优化配置航行支线的顺序化配置航行支线的顺序1991199120002000万万IBMIBM重组它的全球供应链，在重组它的全球供应链，在保持最小库存的同时更快保持最小库存的同时更快满足顾客满足顾客20002000第一年第一年7.57.5亿亿美洲航空公司美洲航空公司设计票价结构、订票和协设计票价结构、订票和协调航班的系统来增加收入调航班的系统来增加收入199219925 5亿，更多收入亿，更多收入管理管理运筹学运筹学的工作程序的工作程序明确问题明确问题问题分类问题分类建立数学模型建立数学模型求解数学模型求解数

12、学模型结果分析结果分析实施实施:规划论规划论( (分线性、非线性、整数、目标、动分线性、非线性、整数、目标、动态及随机规划等态及随机规划等) ):图论与网络优化；图论与网络优化；:排队论、存储论、搜索论；排队论、存储论、搜索论；:对策论对策论( (博弈论博弈论) )、；、；:可靠性理论可靠性理论; ;:全面质量管理全面质量管理(TQC);(TQC);:计划评审、维修更新理论等。计划评审、维修更新理论等。课程教材：课程教材：吴育华吴育华,杜纲杜纲. 管理科学基础管理科学基础，天津大学出版社，天津大学出版社， 主要参考书：主要参考书：胡运权，运筹学教程，北京：清华大学出版社，胡运权，运筹学教程，北

13、京：清华大学出版社，2007；钱颂迪等，运筹学，北京：清华大学出版社，钱颂迪等，运筹学，北京：清华大学出版社，1990；美美弗雷德里克弗雷德里克S希利尔（希利尔（Frederick S Hillier）,任建标译任建标译,数据、数据、模型与决策（原书名模型与决策（原书名 Introduction to Management Science），北），北京：中国财政经济出版社，京：中国财政经济出版社，2004；谢金星，谢金星， 优化建模优化建模LINDO/LINGO软件，清华大学出版社软件，清华大学出版社 丁以中主编，管理科学丁以中主编，管理科学-运用运用Spreadsheet建模和求解，北京：建

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

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

16、产品产品资源资源甲甲乙乙资源限制资源限制煤煤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

17、 xn （ =, ）b1 am1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，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 称为称为资源系数资源系数例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积

18、为最大(即求安排各住宅多少m2)，求建造方案。水泥水泥(公斤公斤/m2)4000(千工日千工日)147000(千块千块)150000(吨吨)20000(吨吨)110000(千元千元)资源限量资源限量3.518025120大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105砖混住宅砖混住宅人工人工(工日工日/m2)砖砖(块块/m2)钢材钢材(公斤公斤/m2)造价造价(元元/m2) 资源资源住宅体系住宅体系 解: 设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2, z为总面积,则本问题的数学模型为:0,40000035. 0003. 00045. 014

19、7000210. 0150000180. 0190. 0110. 020000025. 0030. 0012. 0110000120. 0135. 0105. 0.3213211321321321xxxxxxxxxxxxxxxxts321xxxMaxz 前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，个变量，10个约束条件。个约束条件。课堂练习课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其某蓄场每日要为每头牲畜购买饲料，以使其获取所需的获取所需的A、B、C、D四种养分。有关数据四种养分。有关数据如下表，现饲料可从

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

21、买方案。（列出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头日需每头日需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. 步骤步骤（1）作约束的图形）作约束的图形可行域可行域可行解的集合可行解的集合先作非负约束先作非负约束再作资源约束再作资源约束9x1+4x2=3604x1+5x2=2003x1+10 x

22、2=300公共部分，即为可行域公共部分，即为可行域例：煤电油例例：煤电油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.x1x240206080100204060801000（2）作目标函数的等值线）作目标函数的等值线给给z不同的值，作相应直线，判断出不同的值，作相应直线，判断出z增大时，直线的移动方向增大时，直线的移动方向将直线向增大方向移动，直至可行域将直线向增大方向移动，直至可行域边界，交点边界，交点X*即为最优解。即为最优解。7x1+12x2=847x1+12x2=168如：令如：令7 x1 +1

23、2x2=84 7 x1 +12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x240206080100204060801000X*=（20，24），），Z*=428最优解：最优解： x1 = 0， x2 = 1 最优目标值最优目标值 z = 3课堂练习课堂练习图解法求解线性规划图解法求解线性规划 0,)3(22)2(22)1(432min2121212121xxxxxxxxstxxz0 01 12 23 34 41 12 23 34 4x1x2O O-1-1-2-2(1)(2)(3)2. LP 解的几种情况解的几种情况（1）唯一解）唯一解（2）多重最优

24、解）多重最优解（3）无可行解）无可行解注：出现（注：出现（3）、（）、（4）情况时，建模有问题）情况时，建模有问题（4）无有限最优解）无有限最优解补充知识：凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。在凸集中，点A，B，C，D称为极点（或顶点）。ABCD从图解法中我们了解到以下事实：若LP问题的可行域存在，则可行域一定是凸集。若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。思路：最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）最优解在可行域的极点中找。极点是有限个，若两个极点都是最优解，则两

25、个极点所连线段上的所有点均是最优解）定义：LP问题的可行域的极点（顶点）称为基本可行解。第二节 单纯形法 单纯形法是求解线性规划的主要算法，单纯形法是求解线性规划的主要算法，19471947年由美国斯坦福大学教授丹捷格（年由美国斯坦福大学教授丹捷格（G.B.DanzigG.B.Danzig）提出。提出。 尽管在其后的几十年中，又有一些算法问世，尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对但单纯形法以其简单实用的特色始终保持着绝对的的“市场市场”占有率。占有率。1.1.线性规划的标准型线性规划的标准型 用单纯形法求解线性规划的前提是先将模用单纯形法求解线性规

26、划的前提是先将模型化为标准型：型化为标准型：0. .XbAXtsCXMaxz 标准型的特征：标准型的特征：MaxMax型、等式约束、非负约束型、等式约束、非负约束一、单纯形法的预备知识一、单纯形法的预备知识。）（的秩为其中，0,bnmmAnm非标准形式如何化为标准非标准形式如何化为标准1) 1) MinMin型化为型化为MaxMax型型 CXMinzCXMaxz/加负号加负号 因为，求一个函数因为，求一个函数的极小点，等价于求该的极小点，等价于求该函数的负函数的极大点。函数的负函数的极大点。)(xf)(xf*x注意：注意： MinMin型化为型化为MaxMax型求解后，最优解不变，但最优值差负

27、号。型求解后，最优解不变，但最优值差负号。 2) 不等式约束化为等式约束不等式约束化为等式约束分析：分析：以例以例1中煤的约束为例中煤的约束为例3604921 xx之所以之所以“不等不等”是因为左右两边有一个差额，称为是因为左右两边有一个差额，称为“松松弛量弛量”，若在左边加上这个松弛量，则化为等式。而这，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为个松弛量也是变量，记为X X3 3 ，则有，则有36049321xxxX X3 3称为松弛变量。问题：称为松弛变量。问题：它的实际意义是什么？它的实际意义是什么？ 煤资源的煤资源的“剩余剩余”。练习：请将例练习：请将例1的约束化为

28、标准型的约束化为标准型0,3001032005436049.21212121xxxxxxxxts解：增加松弛变量解：增加松弛变量则约束化为则约束化为,543xxx0,300 10320054360 49.54321521421321xxxxxxxxxxxxxxts易见，增加的松弛变量的系数恰构成一个单位阵易见，增加的松弛变量的系数恰构成一个单位阵I I。一般地，记松弛变量的向量为一般地，记松弛变量的向量为 Xs，则，则0. .XbAXts0,. .ssXXbIXAXts0. .XbAXts0,. .ssXXbIXAXts问题：松弛变量在目标中的系数为何？问题：松弛变量在目标中的系数为何？ 0

29、0。 3) 3) 当模型中有某变量当模型中有某变量 x xk k 没有非负要求，没有非负要求，称称为自由变量为自由变量, , 则可令则可令 0,/kkkkkxxxxx化为标准型。化为标准型。复习：非齐次线性方程组解例：解非齐次线性方程组5242615552142132xxxxxxxx增广矩阵（1）51001124010261500150A1x2x3x4x5xb若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。为基变量。称,3x,4x5x其变量个数=3)()(ArAr此方程组的解为2152142352624515xxxxxxxx其中,1x2x为任意实数。为非基变量，或自由变量。2

30、x,1x称称非基变量,1x2x为0的解（15，24，5，0，0）叫基解。TX)5 ,24,15, 0 , 0(0若对（1）式中的变量再加上非负限制2152142352624515xxxxxxxx5 , 105242615552142132ixxxxxxxxxi其解为5 , 105262451521521423ixxxxxxxxxi由的非负性知：,3x,4x5x（2）04531x2x5 , 100502624051521521423ixxxxxxxxxi05152 x50521xx0262421xx从而,1x2x解域为注意：此时的,1x2x已经不是任意实数。不是自由变量了。而对于带有非负约束的方

31、程组解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解。基可行解所对应的基称为可行基。 非基可行 最优基基 非 可 行 基四种形式的基之间的关系为：基与解的对应关系： 非可行解可行 基本解 可行解 基本解解与解之间的关系为：基解基可行基基可行解最优基基最优解5 , 100502624051521521423ixxxxxxxxxi, 11x22x所对应的解例如T)2,14,10,2, 1(是可行解。,01x02x所对应的解T)5,24,15,0,0(是基解。也是可行解，故而是基本可行解。2.基本概念（1）可行解与最优解）可行解与最优解；的解，记为可行解：满足全体约束X。，有解则

32、对任可行的，记为最优解：可行解中最优* ,CXCXXX直观上，直观上，可行解是可行域中的点，是一个可行的方案；可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案。最优解是可行域的角点，是一个最优的方案。（2）基矩阵与基变量基矩阵基矩阵(简称基简称基)：系数阵系数阵A中的中的m阶可逆子阵，记阶可逆子阵，记 为为B；其余部分称为非基矩阵，记为；其余部分称为非基矩阵，记为N。基向量：基向量：基基B中的列；其余称非基向量。中的列；其余称非基向量。基变量：基变量：与基向量与基向量Pj对应的决策变量对应的决策变量xj，记其组成的记其组成的 向量为向量为XB；与非基向量对应的变

33、量称非基；与非基向量对应的变量称非基变变 量，记其组成的向量为量，记其组成的向量为XN。1231241432 12 3,0 xxxxxxxx例 ：下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。1231241432123,0 xxxxxxxx例 ：下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。阶可逆子阵有中的，解：本例中，210011221AA 6 6个。个。一般地，一般地，m mn n 阶矩阵阶矩阵A A中基的个数最多有多少个？中基的个数最多有多少个？个。mnC;,100143434311xxXxxPPBB，基变量为，其相应的基向量为。基变量为其相应的基向量为2

34、1212122,1221xxXxxPPBB问题：本例的问题：本例的A A中一共有几个基？中一共有几个基？（3）基本解与基本可行解）基本解与基本可行解.0,0, ,1111bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABkkBkBTkB时，有当取即可表示为约束中的相应地）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称0NbBXbAX可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为称非负的基本解

35、为基本可行解基本可行解（简称基可行解）。（简称基可行解）。例例4：在上例中：在上例中0,321241421321xxxxxxxx 求相应于基求相应于基B1和和B2的基本解，它们是否基本可行解？的基本解，它们是否基本可行解？,31311001,1001,1001111bBBBNN解：是基本可行解。的基本解为相应于基,)3 ,1 ,0 ,0(NTXB,51-573151-525251,51-525251,1-221112bBBBOO不是基本可行解。的基本解为相应于基,0,0)51,-57(2TXB上二组概念间的联系：系数阵系数阵A中可找出若干个基中可找出若干个基B每个基每个基B都对应于一个基本解都

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

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

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

39、若问题：若B0=I，则，则X0=？可行。,000NMMbbBX2. 最优性检验最优性检验问题：用什么检验？问题：用什么检验？ 目标。目标。kBkBkkkBkbkBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目标优。时，当前基可行解为最，则当记 01NBCCBk问题：非最优的特征为何？问题：非最优的特征为何？。至少有某个检验数0kn判断现行的基本可行解是否最优判断现行的基本可行解是否最优 假如已求得一个基本可行解假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中分别表示基变量和其中分别表示基

40、变量和非基变量所对应的价值系数子向量。非基变量所对应的价值系数子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )要判定是否已经达到最大值，只需将要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 称为非基变量称为非基变量N N的检验向量，它的各个分量称为检验数。若的检验向量，它的各个分量称为检验数。若N N的每一个检验数均小的

41、每一个检验数均小于等于于等于0 0，即，即N N00，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。-1-1BNX=B b-B NX-1BZ=C B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。则这个基本可行解就是最优解。定理定理

42、2 2：无穷多最优解判别定理：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中存在一个检验数，其中存在一个检验数m+km+k=0=0，则线性规划问题有无穷多最优解。则线性规划问题有无穷多最优解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB=C -C B N0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xn 基本可行解的改进基本可行解的改进 如果现行的基本可行解不是最优解，即在检验向量如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基

43、中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：做法是： 先从检验数为正的非基变量中确定一个换入变量，使它从非基先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量，使它从基变量变成非再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，

44、这样的变换一定能使目标函数值有所增加。可知，这样的变换一定能使目标函数值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x 换入变量和换出变量的确定换入变量和换出变量的确定：l换入变量的确定换入变量的确定 最大增加原则最大增加原则 假设检验向量假设检验向量 ， 若其中有两个以上的检验数为正，那么为了使目标函数值增加得快若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用些，通常要用“最大增加原则最大增加原则”，即选取最大正检验数所对应的非基，即选取最大正检验数所对应的非基变量为换入变量，即若变量为换入变量，即若 则选取对应的

45、则选取对应的 为换入变量，为换入变量， 由于且为最大，由于且为最大， 因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。-1NNBm+1m+2n=C -C B N=(,)jjm+kmax | 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xl 换出变量的确定换出变量的确定 最小比值原则最小比值原则 如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。 当由零慢

46、慢增加到某个值时，当由零慢慢增加到某个值时， 的非负性可能被打破。的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小比值原则确定换出变量： 若若B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)=min|(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。 xlBX 定理定理3 3：无最优解判别定理：无最优解判别定理 若若 是一个基

47、本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是，则该线性规划问题无最优解。但是，则该线性规划问题无最优解。1B bX=0-1m+kB P0m+k0证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 , , 故当故当+时，时，Z+Z+。-1-1-1-1Bm+km+km+kX =B b-B PxB b-B Pm+1-1-1Bm+1m+knBm+knxZ=C B b+(, )C B b+x m+kx,(0) m+k0寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基解，相当于从上一个基B0

48、变换为下一个新的基变换为下一个新的基B1，因，因此，本步骤也称为基变换。此，本步骤也称为基变换。（基变换）（基变换）0NNMNbBzz可行：改善：基变换的原则）变换的方法：（nklPPPP,N进基进基出基出基进基；对应的令保证“改善”进基kkP0可决定出基。由保证“可行”出基011kBNXBbBX 称作检验比。i 以例以例1 1为例，可按上述单纯形法的步骤求出其最优解，其为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 2

49、1127xxMaxz(2) (2) 确定初始基可行解、检验确定初始基可行解、检验;00,300)(0,0,360,2,00)(360,200,3,0100TTXbBB111;,5OPP向量为再计算检验比确定出基量为计算检验数确定进基向（3 3）换基、计算下一个基可行解、再检验，直至最优）换基、计算下一个基可行解、再检验，直至最优;50,0)(0,24,240,)(240,50,30,1051411111TTXbBB;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正

50、，当问题：当模型规模较大时，计算量很大。问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。事实上，单纯形法的实现是在单纯形表上完成的。三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。式，是单纯形法的具体实现。110101100)()(000BmBbBmBCbBuBikiiijBBjjmi nM回顾单纯形法步骤回顾单纯形法步骤bBN需计算ABN需计算,AbB1内容是因此，单纯形表的主体 121110AbBAbBAbB 即单纯形表的主要结构：单纯形表的主要结构： X CABNbBN问题：第一张表的

51、问题：第一张表的B-1=？单位阵单位阵I。检验数的公式是什么？检验数的公式是什么？jBjjPBCcN在哪里？jPBN列中的第jAB1 例5：用单纯形法求解例10,3001032005436049.21212121xxxxxxxxts21127xxMaxz将模型化为标准型：解：增加松弛变量,543xxx 0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz问题：标准模型的问题：标准模型的A中是否含中是否含I？松弛变量系数恰好构成松弛变量系数恰好构成I。的计算的计算:XBCBB-1bx1x2x3x4x5四、单纯形法的实现四、单纯

52、形法的实现单纯形表单纯形表例例：煤电油例：煤电油例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单纯形表单纯形表:71111PBCcB 77 0 , 0 , 0 349x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单

53、纯形表单纯形表例例：煤电油例：煤电油例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单纯形表单纯形表:790的计算的计算:11111)()(kPBbB 904360 4030 x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法

54、的实现单纯形表单纯形表例例：煤电油例：煤电油例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单纯形表单纯形表:7904030 枢纽枢纽元素元素x5x4x3x2x1B-1bCBXBx3x4x500036020030094345101000100

55、0112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为主元进行初等行变换为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.2即即:1111PBCcB 74 . 3 12,0,0 3 .05 .28 .7x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为主元进行初等行变换为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.2即即:

56、5155PBCcB 02 . 1 12,0,0 1 .05 .04 .030.820100 x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为主元进行初等行变换为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.230.820100 x3x1x2071224010-0.12 0.16201000.4 -0.284001-3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x

57、5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 以以 为主元进行初等行变换为主元进行初等行变换2.5x3x1x2071224010-0.12 0.16201000.4 -0.284001-3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31

58、000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 X*=(20,24,84,0,0)T Z*=428例：例：用单纯形法求解用单纯形法求解Min S= - x1 +2x2x1 - x2 - 2x1 +2x2 6x1 , x20s.t.化为标准型化为标准型Max S = x1 -2x2-x1 + x2 +x3 = 2x1 +2x2 +x4= 6x1 , ,x40s.t.XBCBB-1bx1x2x3x4x302-1110不考虑不考虑x406120161-2x3080311x11612010-40-1X*=(6,0,8,0)T Z*= -6x3x1x2

59、071224010 -0.120.16201000.4 -0.284001 -3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001 -0.5240 7.8010 -0.43.4000 -1.230.820100注：单纯形表中的信息注：单纯形表中的信息每一列的含义：每一列的含义：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn)每个表中的每个表中的B和和B-1的查找：的查找： B从初表

60、中找；从初表中找； B-1从当前表中找，对应于从当前表中找，对应于初表中的初表中的I的位置。的位置。 ),(243PPPB 1000510401 以第以第2个表为例：个表为例： 1B 1 . 0005 . 0104 . 001终表分析终表分析最优基最优基B* 和和(B*)-1的查找的查找 ),(213*PPPB 1030540491 16. 012. 002 . 04 . 0016. 112. 31 1*)(Bx3x1x2071224010 -0.120.16201000.4 -0.284001 -3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x50