运筹学教程课件

《运筹学教程课件》由会员分享，可在线阅读，更多相关《运筹学教程课件（217页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

5、广推广“统筹学统筹学”当时就获得第一代领导人的当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。有成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门凡是讲图论的优化的教科书，多半有专门的一章名：的一章名：C Chinese hinese P Postman ostman P Problems,roblems,其中其中无一例外的要提到管梅谷先生的杰出工作：无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题中国邮递员问题(CPP)(CPP)。2024/9/18运筹学运筹学（Operational Resea

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

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

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

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

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

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

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

13、1990；5吴育华吴育华,杜纲杜纲. 管理科学基础管理科学基础，天津大学出版社。，天津大学出版社。主要授课内容：主要授课内容： 线性规划线性规划:模型与图解法，单纯形法，模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整对偶与灵敏度分析，运输问题，线性整数规划数规划 图论与网络分析图论与网络分析 网络计划网络计划动态规划动态规划 风险型决策风险型决策 排队论排队论随机模拟随机模拟课程基本要求掌握好基本概念、主要模型形式及其特点、适当掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算的建模能力，必要的算法原理及简单的计算具备计算机解题的基本能力具备计算机解题

14、的基本能力认真听课，勤于思考，多看书认真听课，勤于思考，多看书每周四交作业，独立完成每周四交作业，独立完成闭卷考试闭卷考试有问题请有问题请Email联系联系第一章第一章 线性规划线性规划（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 +10x2 300x1 , x20s.t.返回Subject To， 意为意为“使其满使其满足足”Max （Min） Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a1

16、2 x2 + + a1n 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 称为称为资源系数资源系数线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定比例性假定可加性假定可加性假定连续性假定连续性假定确定性假定

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

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

19、大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105砖混住宅砖混住宅人工人工(工日工日/m2)砖砖(块块/m2)钢材钢材(公斤公斤/m2)造价造价(元元/m2) 资源资源住宅体系住宅体系 解: 设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2, z为总面积,则本问题的数学模型为: 前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个个变量，变量，10个约束条件。个约束条件。课堂练习课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其某蓄场每日要为每头牲畜购买饲料，以使其获取所需的获取所

20、需的A、B、C、D四种养分。有关数据如四种养分。有关数据如下表，现饲料可从市场上出售的下表，现饲料可从市场上出售的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 +200x2思考题思考题月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7

22、300单位：100m2单位；元/100m2解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。 月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m215102012经过上面的讨论，得到下面的LP模型：目标函数约束条件二、线性规划的图解法二、线性规划的图解法1. 步骤步骤（1）作约束的图形）作约束的图形可行域可行域可行解的集合可行解的集合先作非负约束先作非负约束再作资

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

24、7x1+12x2=847x1+12x2=168如：令如：令7 x1 +12x2=84 7 x1 +12x2=1689x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（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）无

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

26、点均是最优解）定义：LP问题的可行域的极点（顶点）称为基本可行解。三、三、 线性规划应用举例与软件求解线性规划应用举例与软件求解 例例1 1 （下料问题）下料问题） 某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为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

27、,2.1 m,1.5 m的圆钢各一根。已知原料每的圆钢各一根。已知原料每根长根长7.4 m7.4 m，问：应如何下料，可使所用原料最省？，问：应如何下料，可使所用原料最省？方案2.92.11.5余料7.4 m7.4 m2.9m2.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

28、 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,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

29、=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.31110.910300301.10220.20130.80041.4第二节 单纯形法 单纯形法是求解线性规划的主要算法，单纯形法是求解线性规划的主要算法，19471947年由美国斯坦福大学教授丹捷格（年由

30、美国斯坦福大学教授丹捷格（G.B.DanzigG.B.Danzig）提出。提出。 尽管在其后的几十年中，又有一些算法问世，尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对但单纯形法以其简单实用的特色始终保持着绝对的的“市场市场”占有率。占有率。1.1.线性规划的标准型线性规划的标准型 用单纯形法求解线性规划的前提是先将模用单纯形法求解线性规划的前提是先将模型化为标准型：型化为标准型： 标准型的特征：标准型的特征：MaxMax型、等式约束、非负约束型、等式约束、非负约束一、单纯形法的预备知识一、单纯形法的预备知识非标准形式如何化为标准非标准形式如何化为标准1)

31、1) MinMin型化为型化为MaxMax型型 加负号加负号 因为，求一个函数因为，求一个函数的极小点，等价于求该的极小点，等价于求该函数的负函数的极大点。函数的负函数的极大点。注意：注意： MinMin型化为型化为MaxMax型求解后，最优解不变，但最优值差负号。型求解后，最优解不变，但最优值差负号。 2) 不等式约束化为等式约束不等式约束化为等式约束分析：分析：以例以例1中煤的约束为例中煤的约束为例之所以之所以“不等不等”是因为左右两边有一个差额，称为是因为左右两边有一个差额，称为“松松弛量弛量”，若在左边加上这个松弛量，则化为等式。而这，若在左边加上这个松弛量，则化为等式。而这个松弛量也

32、是变量，记为个松弛量也是变量，记为X X3 3 ，则有，则有X X3 3称为松弛变量。问题：称为松弛变量。问题：它的实际意义是什么？它的实际意义是什么？ 煤资源的煤资源的“剩余剩余”。练习：请将例练习：请将例1的约束化为标准型的约束化为标准型解：增加松弛变量解：增加松弛变量则约束化为则约束化为易见，增加的松弛变量的系数恰构成一个单位阵易见，增加的松弛变量的系数恰构成一个单位阵I I。一般地，记松弛变量的向量为一般地，记松弛变量的向量为 Xs，则，则问题：松弛变量在目标中的系数为何？问题：松弛变量在目标中的系数为何？ 0 0。 3) 3) 当模型中有某变量当模型中有某变量 x xk k 没有非负

33、要求，没有非负要求，称称为自由变量为自由变量, , 则可令则可令 化为标准型。化为标准型。复习：非齐次线性方程组解例：解非齐次线性方程组增广矩阵（1）若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。为基变量。称其变量个数=此方程组的解为其中为任意实数。为非基变量，或自由变量。称称非基变量为0的解（15，24，5，0，0）叫基解。若对（1）式中的变量再加上非负限制其解为由的非负性知：（2）从而解域为注意：此时的已经不是任意实数。不是自由变量了。而对于带有非负约束的方程组解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解。基可行解所对应的基称为可行基。 非基可行

34、 最优基基 非 可 行 基四种形式的基之间的关系为：基与解的对应关系： 非可行解可行 基本解 可行解 基本解解与解之间的关系为：基解基可行基基可行解最优基基最优解所对应的解例如是可行解。所对应的解是基解。也是可行解，故而是基本可行解。2.基本概念（1）可行解与最优解）可行解与最优解直观上，直观上，可行解是可行域中的点，是一个可行的方案；可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案。最优解是可行域的角点，是一个最优的方案。（2）基矩阵与基变量基矩阵基矩阵(简称基简称基)：系数阵系数阵A中的中的m阶可逆子阵，记阶可逆子阵，记 为为B；其余部分称为非基矩阵，记为；

35、其余部分称为非基矩阵，记为N。基向量：基向量：基基B中的列；其余称非基向量。中的列；其余称非基向量。基变量：基变量：与基向量与基向量Pj对应的决策变量对应的决策变量xj，记其组成的记其组成的 向量为向量为XB；与非基向量对应的变量称非基变；与非基向量对应的变量称非基变 量，记其组成的向量为量，记其组成的向量为XN。 6 6个。个。一般地，一般地，m mn n 阶矩阵阶矩阵A A中基的个数最多有多少个？中基的个数最多有多少个？问题：本例的问题：本例的A A中一共有几个基？中一共有几个基？（3）基本解与基本可行解）基本解与基本可行解可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的

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

37、基本可行解是可行域中的哪些点？问题：基本可行解是可行域中的哪些点？3.基本定理（1 1）线性规划的可行域是一个）线性规划的可行域是一个凸凸多面体。多面体。（2 2）线性规划的最优解（若存在的话）必能在可行）线性规划的最优解（若存在的话）必能在可行 域的域的角点角点获得。获得。（3 3）线性规划可行域的）线性规划可行域的角点角点与与基本可行解基本可行解一一对应。一一对应。二、单纯形法的步骤确定一个初始基可行解确定一个初始基可行解检验这个基可行解是否最优检验这个基可行解是否最优寻找一个更好的基可行解寻找一个更好的基可行解否否是是停停止止 DantzigDantzig的单纯形法把寻优的目标集中在所有

38、基本可行解的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。最优基本可行解的最佳途径。 单纯形法的一般步骤如下：单纯形法的一般步骤如下： （1 1）寻找一个初始的基本可行解。寻找一个初始的基本可行解。 （2 2）检查现行的基本可行解是否最优，如果为最优，检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。则停止迭代，已找到最优解，否则转一步。 （3 3）移至目标函数值有所改善的另一个基本可行解，移至目标函

39、数值有所改善的另一个基本可行解， 然后转会到步骤（然后转会到步骤（2 2）。）。 1.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，由于基可行解是由一个可行基决定的，因此，确定初始基可行解确定初始基可行解X X0 0相当于确定一个初始可行基相当于确定一个初始可行基B B0 0。方法：方法：若若A中含中含I，则，则B0=I； 若若A中不含中不含I，则可用人工变量法构，则可用人工变量法构 造一个造一个I。问题：若问题：若B0=I，则，则X0=？2. 最优性检验最优性检验问题：用什么：用什么检验？目目标。问题：非最优的特征为何？问题：非最优的特征为何？n判断现行的基本可行解是否最优判断现

40、行的基本可行解是否最优 假如已求得一个基本可行解假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中其中分别表示基变量和分别表示基变量和非基变量所对应的价值系数子向量。非基变量所对应的价值系数子向量。要判定是否已经达到最大值，只需将要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即： 其中其中 称为非基变量称为非基变量N N的的检验向量，它的各个分量称为检验数。若检验向量，它的各个分量称为检验数。若N N的每一个检验数均小于的每一个检验数均小于等于

41、等于0 0，即，即N N00，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。则这个基本可行解就是最优解。定理定理2 2：无穷多最优解判别定理：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中存在一个检验数，其中存在一个检验数m+km+k=0=0，则线性规划问题有无穷多最优解。则线性规划问题有无穷多最优解。n 基本可行解的改进基本可行解的改进 如果现行

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

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

44、若 则选取对应的则选取对应的 为换入变量，为换入变量， 由于且为最大，由于且为最大， 因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。l 换出变量的确定换出变量的确定 最小比值原则最小比值原则 如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。 当由零慢慢增加到某个值时，当由零慢慢增加到某个值时， 的非负性可能被打破。的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小

45、比值原则确定换出变量： 若若则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。 定理定理3 3：无最优解判别定理：无最优解判别定理 若若 是一个基本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是，则该线性规划问题无最优解。但是，则该线性规划问题无最优解。证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 , , 故当故当+时，时，Z+Z+。寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基解，相当于从上一个基B0变换为下一个新的基变换为下一个新的基B1，因，因此，本步骤也称

46、为基变换。此，本步骤也称为基变换。（基变换）（基变换）进基进基出基出基 以例以例1 1为例，可按上述单纯形法的步骤求出其最优解，其为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型(2) (2) 确定初始基可行解、检验确定初始基可行解、检验（3 3）换基、计算下一个基可行解、再检验，直至最优）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。事实上，单纯形法的实现是在单纯形表上完成的。三、单纯形表 单纯形表是基于单

47、纯形法的步骤设计的计算格单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。式，是单纯形法的具体实现。回顾单纯形法步骤回顾单纯形法步骤单纯形表的主要结构：单纯形表的主要结构：问题：第一张表的问题：第一张表的B-1=？单位阵单位阵I。检验数的公式是什么？检验数的公式是什么？例5：用单纯形法求解例1问题：标准模型的问题：标准模型的A中是否含中是否含I？松弛变量系数恰好构成松弛变量系数恰好构成I。的计算的计算:XBCBB-1bx1x2x3x4x5四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1 +12x29 x1 +4x23604x1 +

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

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

50、+x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 枢纽枢纽元素元素x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.2即即:x5x4x3x2x1B-

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

52、4000-1.230.820100 x3x1x2071224010-0.12 0.16201000.4 -0.284001-3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表: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

53、1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.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

54、= 6x1 , ,x40s.t.XBCBB-1bx1x2x3x4x302-1110不考虑不考虑x406120161-2x3080311x11612010-40-1X*=(6,0,8,0)T Z*= -6x3x1x2071224010 -0.120.16201000.4 -0.284001 -3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030x3x4x20012300.31000.1502.5001 -0.5240 7.8010 -0.43.4000 -1

55、.230.820100注：单纯形表中的信息注：单纯形表中的信息每一列的含义：每一列的含义：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn)每个表中的每个表中的B和和B-1的查找：的查找： B从初表中找；从初表中找； B-1从当前表中找，对应于从当前表中找，对应于初表中的初表中的I的位置。的位置。 以第以第2个表为例：个表为例：终表分析终表分析最优基最优基B* 和和(B*)-1的查找的查找x3x1x2071224010 -0.120.16201000.4 -0.284001 -3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x500036

56、0200300943451010001000112000单纯形表单纯形表:7904030x3x4x20012300.31000.1502.5001 -0.5240 7.8010 -0.43.4000 -1.230.820100注：单纯形表中的信息注：单纯形表中的信息p借助人工变量求初始的基本可行解借助人工变量求初始的基本可行解 若若约约束束方方程程组组含含有有“”不不等等式式，那那么么在在化化标标准准形形时时除除了了在在方方程程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。式左端减去剩余变量，还必须在左端加上一个非负的人工变量。因因为为人人工工变变量量是是在在约约束束方方程程已已为为

57、等等式式的的基基础础上上，人人为为的的加加上上去去的的一一个个新新变变量量，因因此此加加入入人人工工变变量量后后的的约约束束方方程程组组与与原原约约束束方方程程组组是是不不等价的。等价的。加加上上人人工工变变量量以以后后，线线性性规规划划的的基基本本可可行行解解不不一一定定是是原原线线性性规规划划的的问问题题的的基基本本可可行行解解。只只有有当当基基本本可可行行解解中中所所有有人人工工变变量量都都为为取取零零值值的的非非基基变变量量时时，该该基基本本可可行行解解对对原原线线性性规规划划才才有有意意义义。因因为为此此时时只只需需去去掉掉基基本本可可行行解解中中的的人人工工变变量量部部分分，剩剩余

58、余部部分分即即为为原原线线性性规规划划的的一一个个基本可行解而这正是我们引入人工变量的主要目的。基本可行解而这正是我们引入人工变量的主要目的。 考虑线性规划问题：考虑线性规划问题： 为了在约束方程组的系数矩阵中得到一个为了在约束方程组的系数矩阵中得到一个m m阶单位矩阵作为阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量初始可行基，在每个约束方程组的左端加上一个人工变量 可得到：可得到： 添添加加了了m m个个人人工工变变量量以以后后，在在系系数数矩矩阵阵中中得得到到一一个个m m阶阶单单位位矩矩阵阵，以该单位矩阵对应的人工变量以该单位矩阵对应的人工变量 为基变量，为基变量，

59、即可得到一个初始的基本可行解即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的。这样的基本可行解对原线性规划没有意义的。但但是是我我们们可可以以从从X X(0)(0)出出发发进进行行迭迭代代，一一旦旦所所有有的的人人工工变变量量都都从从基基变变量量迭迭代代出出来来，变变成成只只能能取取零零值值的的非非基基变变量量，那那么么我我们们实实际际上上已已经经求求得得了了原线性规划问题的一个初始的基本可行解。原线性规划问题的一个初始的基本可行解。此此时时可可以以把把所所有有人人工工变变量量剔剔除除，开开始始正正式式进进入入求求原原线线性性规规划划最最优优解解的过程。的过程。n 大大M法法

60、 大大M M法法首首先先将将线线性性规规划划问问题题化化为为标标准准型型。如如果果约约束束方方程程组组中中包包含含有有一一个个单单位位矩矩阵阵I I，那那么么已已经经得得到到了了一一个个初初始始可可行行基基。否否则则在在约约束束方方程程组组的的左左边边加加上上若若干干个个非非负负的的人人工工变变量量，使使人人工工变变量量对对应应的的系系数数列列向向量量与与其其它它变变量量的的系系数数列列向向量量共共同同构构成成一一个个单单位位矩矩阵阵。以以单单位位矩矩阵阵为为初初始基，即可求得一个初始的基本可行解。始基，即可求得一个初始的基本可行解。 为为了了求求得得原原问问题题的的初初始始基基本本可可行行解

61、解，必必须须尽尽快快通通过过迭迭代代过过程程把把人人工工变变量量从从基基变变量量中中替替换换出出来来成成为为非非基基变变量量。为为此此可可以以在在目目标标函函数数中中赋赋予予人人工工变变量量一一个个绝绝对对值值很很大大的的负负系系数数- -。这这样样只只要要基基变变量量中中还还存存在在人工变量，目标函数就不可能实现极大化。人工变量，目标函数就不可能实现极大化。 以以后后的的计计算算与与单单纯纯形形表表解解法法相相同同，只只需需认认定定是是一一个个很很大大的的正正数数即即可可。假假如如在在单单纯纯形形最最优优表表的的基基变变量量中中还还包包含含人人工工变变量量，则则说说明明原原问问题题无无可可行

62、行解解。否否则则最最优优解解中中剔剔除除人人工工变变量量的的剩剩余余部部分分即即为为原原问问题题的的初初始基本可行解。始基本可行解。例例4 4、用大、用大M M法求解下面的线性规划问题法求解下面的线性规划问题: :解：解： 首先将原问题化为标准型首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予- - -01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1-110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M001/23/20-1/2-M

63、-3/2-M5/2Z001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50-12+2M-M-M000-3MZ3/101001003X50X1x2x3x4x5x6x7bXBCB-12000-M-MC01001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50001/23/20-1/2-

64、M-3/2-M5/2Z3/2/1/2001/21/21-1/2-1/23/2X50X1x2x3x4x5x6x7bXBCB-12000-M-MC最优解最优解 最优值最优值n两阶段法两阶段法 两两阶阶段段法法引引入入人人工工变变量量的的目目的的和和原原则则与与大大M M法法相相同同，所所不不同同的的是是处理人工变量的方法。处理人工变量的方法。两阶段法的步骤：两阶段法的步骤：l 求求解解一一个个辅辅助助线线性性规规划划。目目标标函函数数取取所所有有人人工工变变量量之之和和，并并取取极极小小化化；约约束束条条件件为为原原问问题题中中引引入入人人工工变变量量后后包包含含一一个个单单位位矩矩阵阵的的标标准

65、准型型的约束条件。的约束条件。 如如果果辅辅助助线线性性规规划划存存在在一一个个基基本本可可行行解解，使使目目标标函函数数的的最最小小值值等等于于零零，则则所所有有人人工工变变量量都都已已经经“离离基基”。表表明明原原问问题题已已经经得得了了一一个个初初始始的的基基本本可可行行解解，可可转转入入第第二二阶阶段段继继续续计计算算；否否则则说说明明原原问问题题没没有有可可行行解，可停止计算。解，可停止计算。l 求求原原问问题题的的最最优优解解。在在第第一一阶阶段段已已求求得得原原问问题题的的一一个个初初始始基基本本可可行行解的基础上，继续用单纯形法求原问题的最优解解的基础上，继续用单纯形法求原问题

66、的最优解例例5 5、用两阶段法求解例、用两阶段法求解例4 4中的线性规划问题。中的线性规划问题。解：首先将问题化为标准型解：首先将问题化为标准型添加人工变量添加人工变量x x6 6,x,x7 7, ,并建立辅助线性规划如下：并建立辅助线性规划如下：由于辅助线性规划的目标函数是由于辅助线性规划的目标函数是极小化，因此最优解的判别准则极小化，因此最优解的判别准则应为：应为：01-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10-110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110

67、W001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X500-2110003W3/101001003X50x1x2x3x4x5x6x7bXBCB0000011C辅助规划所有检验数：辅助规划所有检验数：原问题已得一个初始基本可行解，原问题已得一个初始基本可行解，由由上上表表可可知知，通通过过若若干干次次旋旋转转变变换换，原原问问题题的的约约束束方方程程组组已已变变换成包含一个单位矩阵的约束方程组换成包含一个单位矩阵的约束方程组该该约约束束方方程程组组可可作作为为第第二二阶阶段段初初始始约约束束方方程程组组，将将目目标标函函数数则则还原成原问题的目标函数，

68、可继续利用单纯形表求解。还原成原问题的目标函数，可继续利用单纯形表求解。-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020001/23/205/2Z1/2/1/2-3/2/1/210-1/21/2001-1/2-1/20001/21/211/23/23/2X1X2X5-120x1x2x3x4x5bXBCB-12000C可得最优解可得最优解 ，目标函数值，目标函数值maxZmaxZ=6=6，与用大与用大M M法的结果完全相同。法的结果完全相同。p单纯形表与线性规划问题的讨论单纯形表与线性规划问题的

69、讨论 n无可行解无可行解 通通过过大大法法或或两两阶阶段段法法求求初初始始的的基基本本可可行行解解。但但是是如如果果在在大大法法的的最最优优单单纯纯形形表表的的基基变变量量中中仍仍含含有有人人工工变变量量，或或者者两两阶阶段段法法的的辅辅助助线线性性规规划划的的目目标标函函数数的的极极小小值值大大于于零零，那那么么该该线线性性规规划划就就不不存存在可行解。在可行解。 人人工工变变量量的的值值不不能能取取零零，说说明明了了原原线线性性规规划划的的数数学学模模型型的的约约束束条条件件出出现现了了相相互互矛矛盾盾的的约约束束方方程程。此此时时线线性性规规划划问问题题的的可可行行域域为为空空集。集。例

70、例6 6、求解下列线性规划问题、求解下列线性规划问题解：解：首先将问题化为标准型首先将问题化为标准型令，则令，则故引入人工变量，故引入人工变量，并利用大并利用大M M法求解法求解C-3-2-1000-M-MCBXBbx1x2x3x4x5x6x7x80-M-Mx4x7x86431111000010-10-101001-100-1016/1-3/1Z-7M-6-4M-15-M-3+M-2+M-1-2M0-M-M000-M-2x4x7x23431021010-110-10-101001-100-1013/14/1-ZZ-3+M0-3-M0-M-202-M-3-M-2x1x7x23131021010-

71、100-3-1-1-11101-100-101003-3M3-M-M1-M0-1在在以以上上最最优优单单纯纯形形表表中中，所所有有非非基基变变量量检检验验数数都都小小于于零零，但但在在该该表表中中人人工变量工变量x7=1为基变量，所以原线性规划不存在可行解。为基变量，所以原线性规划不存在可行解。n无最优解无最优解 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行

72、解的目无最优解则是指线性规划问题存在可行解，但是可行解的目 标标函函数数达达不不到到最最优优值值，即即目目标标函函数数在在可可行行域域内内可可以以趋趋于于无无穷穷大大（或者无穷小）。无最优解也称为有限最优解，或无界解。（或者无穷小）。无最优解也称为有限最优解，或无界解。 l判别方法：判别方法：无最优解判别定理无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题的系数

73、列向量的全部系数都为负数或零，则该线性规划问题 无最优解，无最优解，可以可以可以可以例例7 7、试用单纯形法求解下列线性规划问题：、试用单纯形法求解下列线性规划问题：解：引入松弛变量解：引入松弛变量x x3 3,x,x4 4化为标准型化为标准型C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因因但但所以原问题所以原问题无最优解无最优解n 退化解 当当线线性性规规划划问问题题的的基基本本可可行行解解中中有有一一个个或或多多个个基基变变量量取取零零值值时时，称此基本可行解为退化解。称此基本可行解为退化解。 产产生生的的原原因因：在在单

74、单纯纯形形法法计计算算中中用用最最小小比比值值原原则则确确定定换换出出变变量量时时，有有时时存存在在两两个个或或两两个个以以上上相相同同的的最最小小比比值值，那那么么在在下下次次迭迭代代中中就就会会出现一个甚至多个基变量等于零。出现一个甚至多个基变量等于零。遇遇到到的的问问题题：当当某某个个基基变变量量为为零零，且且下下次次迭迭代代以以该该基基变变量量作作为为换换出出变变量量时时，目目标标函函数数并并不不能能因因此此得得到到任任何何改改变变（由由旋旋转转变变换换性性质质可可知知，任任何何一一个个换换入入变变量量只只能能仍仍取取零零值值，其其它它基基变变量量的的取取值值保保持持不不变变）。通通过

75、过基基变变换换以以后后的的前前后后两两个个退退化化的的基基本本可可行行解解的的坐坐标标形形式式完完全全相相同同。从从几几何何角角度度来来解解释释，这这两两个个退退化化的的基基本本可可行行解解对对应应线线性性规规划划可可行行域域的同一个顶点，的同一个顶点，解解决决的的办办法法：最最小小比比值值原原则则计计算算时时存存在在两两个个及及其其以以上上相相同同的的最最小小比比值值时时，选选取取下下标标最最大大的的基基变变量量为为换换出出变变量量，按按此此方方法法进进行行迭迭代代一一定定能避免循环现象的产生（摄动法原理）。能避免循环现象的产生（摄动法原理）。例例8 8、求解下述线性规划问题：、求解下述线性

76、规划问题：解：解：引入松弛变量引入松弛变量化标准型化标准型000-242-8030Z-5-60-420-805Z10001001x3212060-2411x13321300-803x500-30-425-800Z11001001x700106-1-2410x130-1130-3-800x50-11001001x7000106-1-2410x60000136-4-3210x50x7x6x5x4x3x2x1bXBCB000-242-803C第第一一次次迭迭代代中中使使用用了了摄摄动动法法原原理理，选选择择下下标标为为6的的基基变量变量x6离基。离基。可得最优解可得最优解，目标函数值，目标函数值ma

77、xZ=，n 无穷多最优解无穷多最优解 无穷多最优解判别原理：无穷多最优解判别原理：若若线线性性规规划划问问题题某某个个基基本本可可行行解解所所有有的的非非基基变变量量检检验验数数都都小小于于等等于于零零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：例：最优表：非基变量检验非基变量检验数，数，所以有无穷多所以有无穷多最优解。最优解。最优解集为可行域两个顶点的凸组合：最优解集为可行域两个顶点的凸组合：C12000CBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23

78、/1-Z80000-1n改进单纯形法的特点改进单纯形法的特点 利利用用单单纯纯形形表表求求解解线线性性规规划划时时，每每一一次次迭迭代代都都把把整整个个单单纯纯形形表表计计算一遍，事实上我们关心的只是以下一些数据：算一遍，事实上我们关心的只是以下一些数据：l基本可行解基本可行解 ，其相应的目标函数值，其相应的目标函数值 ，l非基变量检验数非基变量检验数 ，及其换入变量，及其换入变量 ， 设设主元列元素主元列元素 ，及其换出变量，及其换出变量 ，设设 利用它们可得到一组新的基变量以及新的可行基利用它们可得到一组新的基变量以及新的可行基1 1。p改进单纯形法改进单纯形法为基变量下标为基变量下标为非

79、基变量下标为非基变量下标对对任任一一基基本本可可行行解解，只只要要知知道道，上上述述关关键键数数据据都都可可以以从从线线性性规规划划问问题题的的初初始始数数据据直直接接计计算算出出来来。因因此此如如何何计计算算基基本本可可行行解解对应的可行基的逆阵成为改进单纯形法的关键对应的可行基的逆阵成为改进单纯形法的关键改进单纯形法推导出从可行基变换到改进单纯形法推导出从可行基变换到1 1时，到时，到的的变变换换公公式式。当当初初始始可可行行基基为为单单位位矩矩阵阵时时，变变换换公公式式将将更更具具有有优优越性，因为这样越性，因为这样可以避免矩阵求逆的麻烦可以避免矩阵求逆的麻烦以下推导从到的变换公式：以下

80、推导从到的变换公式：假设当前基假设当前基， 基变换中用非基变量取代基变量基变换中用非基变量取代基变量可得新基可得新基前后二个基相比仅相差一列，且前后二个基相比仅相差一列，且比较以上二式，可得比较以上二式，可得 其中表示第个元素为其中表示第个元素为1 1，其它元素均为零的单位列向量，其它元素均为零的单位列向量，为主元列元素。为主元列元素。 假设假设 ，则则第列第列（换出变量对应列（换出变量对应列 ）第行第行所以由所以由主元素主元素n改进单纯形法的步骤改进单纯形法的步骤（1 1）根据给出的线性规划问题的标准型，确定初始基变量和初始）根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始

81、可行基可行基。求初始可行基B B的逆阵的逆阵-1-1，得初始基本可行解得初始基本可行解。 （2 2）计算单纯形乘子）计算单纯形乘子 ，得目标函数当前值，得目标函数当前值（3 3）计算非基变量检验数，计算非基变量检验数，若若N N00，则当前解已是最优解，停止计算；否则转下一步。则当前解已是最优解，停止计算；否则转下一步。（4 4）根据，确定非基变量为换入变量，根据，确定非基变量为换入变量，计算计算, ,若若0 0，则问题没有有限最优解，停止计算，则问题没有有限最优解，停止计算，否则转下一步。否则转下一步。（5 5） 根据根据 ，确定基变量，确定基变量 为换出变量。为换出变量。 （6 6） 用替

82、代用替代 得新基得新基1 1，由变换公式由变换公式计算新基的逆阵计算新基的逆阵1 1-1-1，求出新的基本可行解求出新的基本可行解 其中为变换矩阵，构造方法是：其中为变换矩阵，构造方法是： 从一个单位矩阵出发，把换出变量从一个单位矩阵出发，把换出变量 在基在基B B中的对应列的单位中的对应列的单位 向量，替换成换入变量向量，替换成换入变量 对应的系数列向量对应的系数列向量 ，并做如下变形，并做如下变形， 主元素主元素 （应在主对角线上）取倒数，其它元素除以主元素（应在主对角线上）取倒数，其它元素除以主元素 并取相反数。并取相反数。重复（重复（2 2）（）（6 6）直至求得最优解。）直至求得最优

83、解。 换入换入无界解无界解换出换出最优解最优解初始基初始基新基新基 例例9 9、试用改进单纯形法求解、试用改进单纯形法求解解：解：（）观察法确定（）观察法确定，为基变量为基变量 为非基变量为非基变量 （2 2）计算单纯行乘子）计算单纯行乘子 目标函数当前值目标函数当前值 （3 3）非基变量检验数）非基变量检验数(4(4）选择换入变量选择换入变量 故故 为换入变量。计算为换入变量。计算( () )确定换出变量确定换出变量确定确定 为换出变量，主元素为换出变量，主元素(6) (6) 用用 代替代替 得新可行基得新可行基 为基变量，为基变量， 为非基变量，为非基变量， 重复以上步骤，进入第二循环重复

84、以上步骤，进入第二循环(1)(1)(2)(2)(3)(3)(4) (4) 选择选择 换入变量换入变量(5)(5) 选择选择 换出变量换出变量, ,主元素主元素(6) (6) 用用 代替代替 得新可行基得新可行基 为基变量，为基变量， 为非基变量，为非基变量， 进入第三循环进入第三循环. . (1)(1) (2) (2) (3) (3) 非基变量对应的检验数全部非正，非基变量对应的检验数全部非正， 故当前解故当前解 即为最优解，即为最优解， 相应的目标函数最优值相应的目标函数最优值 。六、单纯形法总结六、单纯形法总结1、Min型单纯形表与型单纯形表与Max型的区别仅在于：型的区别仅在于： 令令

85、k=minj 0的的xk进基，当进基，当 0时最优。时最优。2、解的几种情况及其在单纯形表上的体现（讨论、解的几种情况及其在单纯形表上的体现（讨论Max型）型）唯一唯一最优解最优解j 0,非基非基0但但B-1Pk 0无可行解无可行解用大用大M法法求解，最求解，最优基中含优基中含有有X人人退化解退化解最优解最优解中某基中某基变量为变量为0第三节 对偶问题与灵敏度分析一一、对偶问题及其模型、对偶问题及其模型例例7：回顾例：回顾例1 这时有另一家厂商这时有另一家厂商提出要购买其煤、电、提出要购买其煤、电、油全部资源，并希望花油全部资源，并希望花费尽量少。试建立购买费尽量少。试建立购买者的线性规划模型

86、。者的线性规划模型。例例7称为例称为例1的对偶问题，记为的对偶问题，记为（D），例），例1称为例称为例7的原问题的原问题,记为（记为（P）。）。对偶模型的一般式对偶模型的一般式以例以例7为例，原问题为为例，原问题为（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：具有十分对称的对应关系： 原问题（原问题（P P） 对偶问题对偶问题 （D D） 目标目标max型型 目标目标min型型 有有n个变量（非负）个变量（非负） 有有n个约束（大于等于）个约束（大于等于） 有有m个约束个约束 （小于等于）（小于等于）

87、 有有m个变量（非负）个变量（非负） 价格系数价格系数 资源向量资源向量 资源向量资源向量 价格系数价格系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转置技术系数矩阵的转置此外，还有一种情形 原问题（原问题（P P） 对偶问题对偶问题 （D D） 第第j个变量为自由变量个变量为自由变量 第第j个约束为等式约束个约束为等式约束 第第i个约束为等式约束个约束为等式约束 第第i个变量为自由变量个变量为自由变量例例8：写出下面线性规划的对偶规划模型：写出下面线性规划的对偶规划模型：例例8：写出下面线性规划的对偶规划模型：写出下面线性规划的对偶规划模型：min Z= - CXs.T - AX- bX 0

88、对称性定理：对称性定理：对偶问题的对偶是原问题。对偶问题的对偶是原问题。 min W= Y bs.T YA C Y 0max Z=C s.T AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W = -Ybs.T YA C Y 0二、对偶问题的性质弱对偶原理：弱对偶原理：设设 和和 分别是问题（分别是问题（P P）和（和（D D）的的可行解，则必有可行解，则必有推论推论：若若 和和 分别是问题（分别是问题（P P）和（和（D D）的可行的可行解，则解，则 是（是（D D）的目标函数最小值的一的目标函数最小值的一个下界；个下界； 是（是（P P）的目标函数最大值的一的目标函数最大值的

89、一个上界。个上界。 对偶问题的性质关于无界性有如下结论：关于无界性有如下结论：问题无问题无界界无可无可行解行解无可无可行解行解问题无问题无界界对偶问对偶问题题原问题原问题无界无界如：如：（原）（原）无可无可行解行解（对）（对）对偶问题的性质推论推论：在一对对偶问题在一对对偶问题(P)(P)和和(D)(D)中，若其中一个问题可行但目中，若其中一个问题可行但目标函数无界，则另一个问题不标函数无界，则另一个问题不可行；反之不成立。这也是对可行；反之不成立。这也是对偶问题的无界性。偶问题的无界性。推推论论：在在一一对对对对偶偶问问题题（P P）和和（D D）中中，若若一一个个可可行行（如如P P），而

90、而另另一一个个不不可可行行（如如D D），则则该该可可行行的的问题无界。问题无界。例例1 1 试估计它们目标函数的界，并验证弱对偶性原理。试估计它们目标函数的界，并验证弱对偶性原理。（P P）对偶问题的性质解：解：（D D）由观察可知：由观察可知： ， ，分别是（，分别是（P P）和和（D D）的可行解。的可行解。Z Z=10 =10 ，W W=40=40，故有，故有 ，弱对偶定理成立。由推论弱对偶定理成立。由推论可知，可知，W W 的最小值不的最小值不能小于能小于1010，Z Z 的最大值不能超过的最大值不能超过4040。对偶问题的性质（P）（D）考虑考虑4.对偶定理 若（P）有最优解，则（

91、D）也有最优解， 且最优值相同。证：对（证：对（P）增加松弛变量，）增加松弛变量， 化为化为设其最优基为设其最优基为B，终表为，终表为其检验数为其检验数为问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =？ (2) 求求Y*是否有必要重新求解（是否有必要重新求解（ D）？）？ CBB-1 不必。可以从原问题（不必。可以从原问题（P）的单纯形终表获得。的单纯形终表获得。例如，已知例如，已知的终表为的终表为请指出其对偶问题的最优解和最优值。请指出其对偶问题的最优解和最优值。5.互补松弛定理y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m 对偶问题

92、的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0直观上直观上定定义义：在在一一对对 P 和和 D 中中，若若 P 的的某某个个约约束束条条件件的的右右端端项项常常数数bi 增增加加一一个个单单位位时时，所所引引起起的的目目标标函函数数最最优优值值Z* 的的改改变变量量y*i称称为为第第i个个约约束条件的影子价格，又称为边际价格。束条件的影子价格，又称为边际价格。

93、影子价格CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1设：设：B是问题是问题 P的最优基，由前式可知，的最优基，由前式可知， Z*=CB B-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*mbm Z*= Z* Z* = y*i 也可以写成：也可以写成：即即y*i 表示表示Z*对对 bi的变化率。的变化率

94、。其其经经济济意意义义是是：在在其其它它条条件件不不变变的的情情况况下下，单单位位资资源源变变化化所所引引起起的的目目标标函函数数的的最最优优值值的的变变化化。即即对对偶偶变量变量yi 就是第就是第 i 个约束条件的影子价格。个约束条件的影子价格。也也可可以以理理解解为为目目标标函函数数最最优优值值对对资资源源的的一一阶阶偏偏导导数（但问题中所有其它数据都保持不变）。数（但问题中所有其它数据都保持不变）。若若第第 i 种种资资源源的的单单位位市市场场价价格格为为mi ，当当yi mi 时时，企企业业愿愿意意购购进进这这种种资资源源，单单位位纯纯利利为为yimi ，则则有有利利可可图图；如如果果

95、yi 0。例11：在例1（煤电油例）中，其单纯形终表如下：（3）甲产品的价格在何范围内变化时，现最优解不变？）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格解：甲产品的价格c1是基变量的价格系数。是基变量的价格系数。例例11：在例：在例1（煤电油例）中，其单纯形终表如下：（煤电油例）中，其单纯形终表如下：（4）若现又考虑一新产品丙，其资源单耗为）若现又考虑一新产品丙，其资源单耗为10，2，5， 售价为售价为6.5，问该产品是否可投产？，问该产品是否可投产？故丙产品可以投产。故丙产品可以投产。首先将线性规划与经济问题联系起来的是首先将线性规划与经济问题联系起来的是 T.G.Koop

96、man（库普曼）和（库普曼）和 L.V.Kamtorovich（康脱罗维奇）（康脱罗维奇）二人因此而共同分享了二人因此而共同分享了19751975年的第年的第7 7届诺贝尔经届诺贝尔经济学奖。济学奖。求解线性规划的计算机软件举例LINDO、EXCELLINDO可以从下面的网址下载：可以从下面的网址下载：WWW.L LINDOLINDO由美国芝加哥大学开发，可求解线性规划和线性由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。整数规划等。其可按自然格式输入模型，使用方便。输入例输入例 ：MAX 2X+3Y ？ST ？4X+9Y9 ？7X+6Y0 时时0， 不

97、选择第不选择第j 种方式，即种方式，即xj=0 时时令令 yj =设第设第j 种生产方式的产量为种生产方式的产量为xj 于是该问题可表示为：于是该问题可表示为： xj M yj例、例、生产三种型号的防寒服，其消耗资源及单件成本如表。生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。此外，每种防寒服不管生产多少，都要支付一定的固定费用。 型号型号资源资源小小中中大大资源限制资源限制尼龙绸尼龙绸1.51.71.81500尼龙棉尼龙棉1.31.51.61000劳动力劳动力44.553500设备设备2.83.84.22800单件成本单件成本13121

98、0固定费用固定费用120150180今要生产今要生产500件防寒服，确定总费用最低的生产方式。件防寒服，确定总费用最低的生产方式。 型号型号资源资源小小中中大大资源限制资源限制尼龙绸尼龙绸1.51.71.81500尼龙棉尼龙棉1.31.51.61000劳动力劳动力44.553500设备设备2.83.84.22800单件成本单件成本131210固定费用固定费用1201501801， 选择第选择第j 种方式种方式0， 不选择第不选择第j 种方式种方式令令 yj =Min Z=13x1+12x2+10x3+120y1+150y2+180y3st1.5x1+1.7x2+1.8x315001.3x1+1

99、.5x2+1.6x31000 4x1+4.5x2+5x335002.8x1+3.8x2+4.2x32800X1+x2+x3= 500xiMyi (i=1,2,3)xi0; yi=0或或14. 背包问题背包问题问题描述问题描述已知：已知：一个背包最大容量为一个背包最大容量为b公斤；有公斤；有m件物品供选择，每件物品供选择，每件物品重件物品重ai公斤，价值为公斤，价值为ci（i=1,m）。）。问题：问题：携带哪些物品可使总价值最大？携带哪些物品可使总价值最大？一般模型一般模型s.t.1， 物品物品i被选中被选中 0，物品，物品i没被选中没被选中 xi=例：例：一个徒步旅行者要在背包中选择一些最有价

100、值的物品携一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带带。他最多能带115kg的物品，现有的物品，现有5件物品，分别重件物品，分别重54、35、57、46、19kg，其价值依次为，其价值依次为7、5、9、6、3。问携带哪些物。问携带哪些物品可使总价值最大？品可使总价值最大？解：解：模型为：模型为：s.t.5. 消防队问题消防队问题 某城市的消防总部将全市划分为某城市的消防总部将全市划分为11个防火区，设有个防火区，设有4个个消防救火站。下图消防救火站。下图表示消防站，表示消防站，111表示防火区域，表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消图中连线表示

101、各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？应关闭哪个消防站？123456789101112341， 保留第保留第i个消防队个消防队 0， 撤消第撤消第i个消防队个消防队解：解：令令 xi=min z= x1+x2+x3+x4 x1+x2 1x1+x2 1x1 1x1 +x3 1 x3 1x1 +x3+x41x1 +x41x1+x2 +x41x1 +x41 x41 x3+x41xi=0或或 1，i=1, ,4则模型为则模型为课堂练习课堂练习: 某市为方便学生上学，拟在新建的居民

102、小区增设某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表所示，问为覆盖所有小区至少应建多小区编号如表所示，问为覆盖所有小区至少应建多少所小学？少所小学？备选校址代号备选校址代号覆盖的居民小区编号覆盖的居民小区编号ABCDEF1、5、71、2、51、3、52、4、53、64、66 6 运输问题运输问题一、运输问题的提出一、运输问题的提出生产某种产品，生产某种产品， m m个产地：个产地：A A1 1, ,，A Am m, ,产量：产量：a a1 1, ,，a am m n n个销地：个销地：B B1 1

103、, ,，B Bn n, ,销量：销量：b b1 1, ,，b bn n已知：已知：A Ai i至至B Bj j的运输单价为的运输单价为c cijij问题：确定问题：确定A Ai i运往运往B Bj j的数量的数量x xijij，使总运费最低？使总运费最低？二、运输问题的表示二、运输问题的表示网络图网络图运输表运输表线性规划模型线性规划模型A2A3B2A1B3B4B1运输问题网络图运输问题网络图a2=125a3=100b1=80b2=65b3=70b4=85a1=75供供应应量量供应地供应地运价运价需需求求量量需求地需求地464513654867352416690791995682388685运

104、输问题的表格表示运输问题的表格表示运输问题线性规划模型运输问题线性规划模型产量约束产量约束销量约束销量约束三、运输问题的分类三、运输问题的分类产销平衡问题：产销平衡问题：a ai i= b= bj j产销不平衡问题：产销不平衡问题：供大于求：供大于求：ai bj供不应求：供不应求：ai bj一、运输问题的提出一、运输问题的提出二、运输问题的表示二、运输问题的表示三、运输问题的分类三、运输问题的分类四、运输问题的求解四、运输问题的求解表上作业法表上作业法五、产销不平衡问题五、产销不平衡问题 六、应用举例六、应用举例四、运输问题的求解四、运输问题的求解表上作业法表上作业法确定初始可行调运方案确定初

105、始可行调运方案最小元素法最小元素法判别当前可行方案是否最优判别当前可行方案是否最优闭回路法闭回路法对现有方案进行调整对现有方案进行调整 闭回路法闭回路法用最小元素法确定初始可行调运方案用最小元素法确定初始可行调运方案 最小元素法的基本思想：就近尽量满足供应最小元素法的基本思想：就近尽量满足供应31 346 301 040303 030036453销量销量8410720134630810229109520101产量产量戊戊丁丁丙丙乙乙甲甲 销地销地产地产地例：最小元素法求解下面运输问题的初始解例：最小元素法求解下面运输问题的初始解4543113用闭回路法进行最优性检验用闭回路法进行最优性检验 1

106、 1、找空格的闭回路、找空格的闭回路：以某空格为起点，用水平线或垂以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一直线向前划，只能在碰到某一数字格时才能转弯，按照这一规则继续前进，直到回到起始的空格为止。规则继续前进，直到回到起始的空格为止。 31 34 6 32 2、根据闭回路计算空格的检验数：、根据闭回路计算空格的检验数：检验数检验数 = = 奇数顶点的单位运价之和奇数顶点的单位运价之和 偶数顶点的单位运价之和偶数顶点的单位运价之和 31 346 3121-11012检验数的检验数的经济含义：经济含义：当由产地当由产地Ai往销地往销地Bj增运一个增运一个单位

107、货物单位货物时所引起时所引起的总运输的总运输成本的变成本的变化数化数结论：若所有检验数都大于等于结论：若所有检验数都大于等于0 0，则当前方案最优，则当前方案最优31 346 3-11211012对现有方案进行调整对现有方案进行调整 在负的检验数中选择绝对值最大的空格，在方案表中从该空在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标上格出发，沿着其闭回路依次标上“+q+q”、 “-q-q”，+q-q+q-q 其中其中q q表示最大调整量，它的取值为标表示最大调整量，它的取值为标“-q-q”的数字中最小的数值。的数字中最小的数值。于是于是q=min3,1 =1q=m

108、in3,1 =1调整后的方案为调整后的方案为 31 3 56 2022191236453销量销量8410720134630810229109520101产量产量戊戊丁丁丙丙乙乙甲甲 产地产地销地销地例：检验下表所给可行解的最优性例：检验下表所给可行解的最优性45431131017111230121 所给可行解的最优所给可行解的最优所有检验数都大于等于所有检验数都大于等于0 0五、产销不平衡问题五、产销不平衡问题1. 产大于销产大于销 （ ） 模型：模型：增加增加松弛变量松弛变量运输表：运输表：B1BnBn+1A1x11x1nx1,n+1a1Amxm1xmnxm,n+1amb1bnbn+1实际意

109、义：实际意义：虚设一虚设一 个销地个销地运价为零运价为零2. 产小于销产小于销 （ ） 模型：模型：增加增加松弛变量松弛变量运输表：运输表：实际意义：实际意义：虚设一虚设一 个产地个产地B1BnA1x11x1na1Amxm1xmnamAm+1xm+1，1xm+1,nam+1b1bn 六、应用举例（六、应用举例（生产与储存问题生产与储存问题） 例例、某厂按合同规定须于当年每个季度末分别提供、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果度的生产能力及生产每台柴油机的成本如

110、右表。如果生产出来的柴油机当季不交货，每台每积压一个季度生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用需储存、维护等费用0.15万元。万元。 试求在完成合同的情况下，使该厂全年生产总费用试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。为最小的决策方案。生产能力生产能力单位成本（万元）单位成本（万元）一季度一季度2510.8二季度二季度3511.1三季度三季度3011.0四季度四季度1011.3 六、应用举例（六、应用举例（生产与储存问题生产与储存问题） 例例、某厂按合同规定须于当年每个、某厂按合同规定须于当年每个季度末分别提供季度末分别提供10、15、25、20

111、台同一台同一规格的柴油机。已知该厂各季度的生产能规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。万元。 试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。产地产地销地销地第一季度第一季度第二季度第二季度第三季度第三季度第四季度第四季度第一季度第一季度第二季度第二季度第三季度第三季度第四季度第四季度产量产量销量销量253530101015252010.9510.811.1011.2511.111.2511.4011.0011.1511.30MMMMMM分析：分析：本问题可转化为一运输问题本问题可转化为一运输问题最优方案为：最优方案为：例：固定费用问题（教材例：固定费用问题（教材P52例例2.20）固体废物处理规划：固体废物处理规划：