运筹学第一章-线性规划与单纯形法.ppt

《运筹学第一章-线性规划与单纯形法.ppt》由会员分享，可在线阅读，更多相关《运筹学第一章-线性规划与单纯形法.ppt（209页珍藏版）》请在三一办公上搜索。

1、 运筹学,陈克东,上海工程技术大学管理学院,“一门科学只有成功的应用数学时，才算达到了完善的地步”-马克思,运筹学的发展：三个来源,军 事 管 理 经 济,运筹学思想方法的起源可追溯到古代,我国先秦时期诸子著作中就存在许多朴素的运筹思想.孙子兵法中有丰富的运筹思想.,军事起源,在国外,运筹学思想也可追溯到很早以前.如阿基米德、达芬奇、伽利略等都研究过作战问题,军事起源 二战期间1939年,由英国曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获得诺贝尔奖的布莱凯特()为首,组建了一个代号为“Blackett马戏团”的研究小组,专门就改进防空系统进行研究二战中,除英国外,美国、加拿大等国也相

2、继成立了军事运筹研究小组,解决战争中提出的运筹学课题.其中最著名的工作之一是改进深水炸弹的起爆深度.,军事起源资料 当时德国的潜水艇严重威胁盟军的运输船,1942年,美国大西洋舰队主持反潜战的官员贝克()请求成立反潜战运筹组,麻省理工学院的物理学家莫尔斯(P.W.Morse)被请来担任计划与监督.莫尔斯领导的小组经过多方实地调查,提出两条重要建议：将反潜攻击由反潜舰艇投掷水雷改为由飞机投掷深水炸弹;仅当潜艇浮出水面或刚下潜时,方投掷深水炸弹;深水炸弹的定深(指起爆深度)由100-200英尺,修正为20-50英尺.改进运送物资的船队及护航舰艇编队的方式,由小规模多批次,改进为加大规模、减少批次,

3、可使损失减少，军方采用了上述建议,重创德国潜艇舰队,最终成功地打破了德国的海上封锁.,军事起源,战争结束时,英美及加拿大军队中工作的运筹学工作者已超过了700人.正是由于战争需要的促进,以及大批著名科学家的参与,运筹学得到迅速发展.之后,运筹学从单纯军事和战争中的应用研究,扩展到经济和管理领域,并形成了自己的理论与方法.1948年,美国麻省理工学院（MIT）率先开设了运筹学课程,许多大学群起效法,内容也日益丰富。,军事起源,1951年,莫尔斯和金博尔出版了(1946年内部出版,1951年公开出版)第一本运筹学专著:运筹学的方法(The Methods of Operations Researc

4、h).书中总结了第二次世界大战中运筹学的军事应用,并给出了运筹学的一个著名定义运筹学 是为执行部门对它们控制下的“业务”活 动采取决策提供定量依据的科学方法.,管理起源,第一次世界大战前就已经发展成熟的古典管理学派,对运筹学的产生和发展影响很大。1911年,泰勒出版了著名的科学管理原理一书.书中,泰勒的管理思想和理论,概括起来主要有以下三个观点：科学管理的根本目的是谋求最高工作效率。达到最高工作效率的重要手段是科学的管理方法。实施科学管理要求精神上的彻底变革。根据以上观点泰勒提出管理制度:最佳动作原理;合理的日工作量或恰当的工作定额原理;刺激性付酬制度等.,与泰勒同时代的,对管理改革作出贡献的

5、还有一些学者,亨利甘特 甘特的贡献主要有以下几点：提出了一种“工资任务加奖金”的工资制度1903年,发明了“甘特图”.至今还在实践中使用,并发展为统筹方法强调管理民主和重视人的领导方式,管理起源,管理起源,弗兰克杰尔布雷斯夫妇.有影响的著作有:动作研究(1911年)、科学管理入门(1912年)以及疲劳研究(1916年)等.他们的研究比泰勒的研究更为细致和广泛,其重要贡献在以下几方面：提出动作研究和动作经济原理疲劳研究.注意到了工作、工人和环境之间的相互影响.,爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式

6、。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。,管理起源,带有拥挤效应的服务行业如通讯业、交通运输业等都隐含排队论的问题。,经济起源,经济学理论对运筹学的影响是和数理经济学学派紧密联系的数理经济学对运筹学,特别是对线性规划的影响可以从魁奈(Qusnay)1758年发表的经济表算起.最著名的经济学家沃尔拉斯(Walras)研究了经济平衡问题,后来的经济学家对其数学形式继续研究并得到深入发展.1928年 冯.诺伊曼以研究二人零和对策的一系列论文为“对策论”奠基.1932年,又提出了广义经济平衡模型.1939年,苏联的康托洛维奇发表生产组织和计划中的数学方法.这些工作

7、都可以看作是运筹学的先驱工作,发展二战结束后,运筹学很快深入到工业、商业、政府部门等,并得到了迅速发展；运筹学在中国研究及应用从20世纪50年代中期开始。1957年,我国在建筑业和纺织业中首先应用运筹学.1958年,开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用20世纪60年代起,在钢铁和石油部门得到了比较全面、深入的应用1965年起统筹法在建筑业、大型设备维修计划等方面的应用取得可喜的进展.1970年在全国大部分省、市和部门推广优选法70年代中期,最优化方法在工程设计界受到了广泛的重视,并在许多方面取得成果;排队论开始应用于矿山、港口、电信及计算机设计等方面;图论用于线路布

8、置、计算机设计、化学物品的存放等70年代后期,存储论在应用汽车工业等方面获得成功近年来,运筹学已趋向研究和解决规模更大、更复杂的问题,并与系统工程紧密结合.,来历及定义,二战期间,英国为了研究“如何最好地运用空军及新发明的雷达保护国家”,成立了一个由各方面专家组成的交叉学科小组.这就是最早的运筹学小组,它的任务是进行“作战研究”(Operational Research).后来,美国从事这方面研究的科学家又称之为“Operations Research”,简称为 O.R.O.R.的中文译名“运筹学”取自成语“运筹帷幄之中，决胜千里之外”，具有运用筹划，出谋献策，以策略取胜等内涵。目前国外的管理

9、科学（Management Science）与运筹学的内容基本相同,运筹学是一门应用科学,它广泛地应用现有科学技术知识 和数学方法,解决实际中提出的专门问题,为决策者选择最优决策提供定量的依据.,运筹学发展三阶段：,创建时期（45年至50年代初）,1948年 英国成立“运筹学”俱乐部1948年 麻省理工学院 介绍运筹学1950年 伯明翰大学开设运筹学课程1952年 卡斯大学 设立运筹学硕士和博士学位1947年 丹捷格 提出单纯形法50年代初 计算机求解线性规划获得成功,成长时期（50年代初至50年代末）,多个国家成立运筹学会，多种运筹学刊物问世1957年 在牛津大学召开第一次国际运筹学会议19

10、59年 成立国际运筹学联合会,迅速发展时期（60年代以来）,运筹学进一步分为各个分支，更多运筹学出版物运筹学课程纳入教学计划,我国运筹学发展历程：,1956年 运筹学小组1958年 运筹学研究室1960年 应用运筹学经验交流会议1962年 全国运筹学专业学术会议1978年 全国运筹学专业学术会议1980年 成立中国运筹学学会,运筹学分支,运筹学是一门以决策支持为目标的学科，运筹学的内容丰富，应用范围非常之广，从军事、政治到管理、经济及工程技术等许多领域都能应用到运筹学的思想和方法。经过半个世纪左右的发展，运筹学形成了下面主要几个分支,在这过程中，科学家，学者和工程师 都起了很大的作用，在其它很

11、多领域也是这样的！,运筹学的分支:,线性规划（linear programming）整数规划（integer programming）运输问题（transportation Problems）多目标规划（multiobjective programming）图论与网络分析（graph theory and network analysis）非线性规划（nonlinear programming）动态规划（dynamic programming）对策论（game theory）决策论（decision theory）排队论（queueing theory）存贮论（inventory theory

12、）,运筹学的作用,运营管理：生产计划，项目进度和物资供应计划物流管理：仓贮控制，配送中心选址，配送运输调度财务和投资管理：资金流分析，债务链清偿，证券组合选择，商品套利和套期，资产定价人力资源管理：调薪方案，人力资源分配质量管理：服务系统分析市场分析：市场占有率转移分析和模拟社会系统分析：交通管理，社会保障系统分析，人口发展分析.,随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对

13、策论、搜索论、模拟等等。运筹学有广阔的应用领域，它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。,本课程的要求和说明,目 的：通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点,理解 线性规划、整数规划、运输问题、目标规划，图与网络等分支的基本优化原理，掌握其中常用的模型和算法,具有一定的建模能力。先修课程:

14、线性代数，高等数学 等.要 求：课前预习，课后要复习 课堂认真听讲（不能旷课）认真完成作业成 绩：平时成绩 30%（作业、出勤、课堂纪律、实验报告）+考试成绩 70%答疑时间：每次课后时间，周二、周五下午（行政楼619，电话或短信联系）参考书目：运筹学教程（第二版胡运权 清华大学出版社 运筹学赵可培,上海财经大学出版社 管理运筹学谢家平,中国人民大学出版社,复习线性代数内容:列向量 x=(x1，x2，xn）T为n维列向量。xRn行向量 x=(x1，x2，xn）为n维列向量。xRn矩阵(向量)运算规则 加减乘、求逆运算 结合律 分配律 交换律 乘法无交换律线性相关 一组向量v1,vn,如果有一组

15、不全为零的 系数1,n,使得:1 v1+nvn=0 则称v1,vn 是线性相关的.线性无关 一组向量v1,vn,如果对于任何数1,n,若要满足:1 v1+nvn=0,则必有系数 1=n=0,(全为零)则称v1,vn线性无关.矩阵A的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.,Chapter 1线性规划与单纯形法 Linear programming and the simplex method,上海工程技术大学管理学院,Chapter 1 线性规划与单纯形法,线性规划是用线性数学模型表示不同的生产活动、营销活动、金融活动

16、或其他活动的计划。,引言,本章重点,1、根据实际问题写出线性规划模型2、掌握线性规划化标准型的方法3、理解并掌握线性规划解的概念4、能够用图解法求解线性规划问题5、熟练掌握线性规划单纯形法的基本思想和 步骤,难点,难点,线性规划（Linear Programming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。,线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，

17、如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。,Chapter 1 线性规划与单纯形法,1 线性规划数学模型1.1问题的提出 线性规划应用的问题种类繁多，形式各异，主要分为四类线性规划问题。前三类问题分别是资源分配问题，成本效益问题以及网络配送问题。第四类具有两种以上的约束的线性规划问题。,Chapter 1 线性规划与单纯形法,例1.1资源分配问题 某工厂近期要安排生产甲、乙两种产品，产品甲需要用原料A，产品乙需要用原料B，由于两种产品都在一个设备上生产，且设备使用时间有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大的利润。,举例,因此这个问题的决策目标

18、是收益的最大化，研究者根据这个目标需要收集以下相关数据：1)工厂两种原料存量以及可用设备工时数；2)甲、乙两种产品的单位产品需要的原料和设备工时数；3)甲、乙两种产品的单位产品利润。,Chapter 1 线性规划与单纯形法,举例,这些数据可以通过调研或估算得出，如表1.1所示：,建立数学模型,为建立模型，引入变量如下：x1-产品甲的数量x2-产品乙的数量Z-利润由表1.1最后一行知Z4x1+3x2,建立数学模型,目标是如何确定x1和x2，使得利润Z最大,同时需要满足资源约束。对于原料A和原料B，有：x16，2x28对于设备工时，有：2x1+3x218此外，甲、乙两种产品数量不可能是负值，因此，

19、有如下对变量的非负约束：x1 0,x20,于是，问题的数学模型现在可以用代数式表述如下：满足：,原材料限制,原材料限制,设备限制,实际上这是求一个线性函数在一组线性约束条件下的最大值问题，称之为线性规划问题模型。以上模型中，将x1、x2称为决策变量；Z4x1+3x2为目标函数；约束(1.1)(1.3)为函数约束；(1.4)为非负约束。,Chapter 1 线性规划与单纯形法,从以上过程我们可以归纳出根据实际 问题建立线性规划模型的步骤：1)根据管理层的要求确定决策目标和收集相关数据。2)确定要做出的决策，引入决策变量。3)确定对这些决策的约束条件和目标函数。,Chapter 1 线性规划与单纯

20、形法,例1.2 成本效益平衡问题某饲料公司希望用玉米、红薯作原料配制一种混合饲料，各种原料包含的营养成分和采购成本都不同，公司管理层希望能够确定混合饲料中的各种原料数量，使得饲料能够以最低成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如下（见表1.2）,举例,表1.2,举例,为建立线性规划模型，我们引入变量如下：x1=混合饲料中的玉米数量；x2=混合饲料中红薯的数量；目标函数 Z=0.8x1+0.5x2，表示产量的成本函数.即如何确定x1，x2 使得成本Z=0.8x1+0.5x2 最低且满足最低营养要求的约束，,Chapter 1 线性规划与单纯形法,因此这个问题的线性规划模型为：

21、,其中“s.t.”是“subject to”的缩写，意思是“受约束于”。,碳水化合物要求,蛋白质物要求,维他命物要求,Chapter 1 线性规划与单纯形法,例1.3 物流网络配送问题 某物流公司需要将甲、乙、丙三个工厂生产的一种新产品送到 A、B 两个仓库，甲、乙两个工厂的产品可以通过铁路运送到仓库A，数量不限；丙工厂的产品可以通过铁路运送到仓库B，同样，产品数量不限。由于铁路运输成本较高，公司也可以考虑由独立的卡车来运输，可将多达80个单位的产品由甲、乙、丙三个工厂运到一个配送中心，再从配送中心以最多90单位的载货量运到各个仓库。公司管理层希望以最小的成本运送所需的货物。,举例,Chapt

22、er 1 线性规划与单纯形法,举例,首先，需要收集每条线路上的单位运输成本和各工厂产品的产量以及各仓库分配量等数据，如表1.3所示。,为了更清楚地说明问题，我们用网络图来直观表示该配送问题。见图1.1 其中，v1、v2、v3 表示甲、乙、丙三个工厂，节点v4表示配送中心，节点v5、v6表示两个仓库；每一条箭线表示一条可能的运输线路，并给出了相应的单位运输成本，对运输量有限制的路线的最大运输能力也同时给出。,配送中心,我们要解决的是各条线路最大运输量，引入变量 xij 表示由 vi 经过路线(vi，vj)运输到 vj 的产品数。问题的目标是总运输成本最小化，总运输成本可以表示为：总运输成本=7.

23、5x15+3 x14+8.2x25+3.5 x24+2.3 x45+3.4 x34+2.3x46+9.2 x36,数学模型,从以上的几个例子可以看出，线性规划问题有如下共同特征：,（模型的三要素）每一个问题都用一组决策变量(x1，x2，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。,练习,Chapter 1 线性规划与单纯形法,1.1.2 线性规划的标准型 根据上节分析，

24、线性规划的一般形式为：,决策变量向量：X=(x1，x2，xn)T价值向量：C=(c1，c2，cn)T资源向量：b=(b1，b2，bm)T,系数矩阵A=（aij）mn=,为了讨论和制定统一的算法，引入线性规划的标准形式,这里规定的标准形式为：(1)目标函数要求是max;(有的要求min)(2)约束条件的要求是等式;(3)决策变量的要求是非负约束;(4)在标准型式中规定各约束条件的右端项bi0，否则等式两端乘以“-1”。,即标准形式为：,Chapter 1 线性规划与单纯形法,用向量和矩阵符号表述时为：,用矩阵描述时为：其中：,Chapter 1 线性规划与单纯形法,称A为约束条件的mn维系数矩阵

25、，一般m0;b为资源向量；C为价值向量；X为决策变量向量。,下面讨论化标准型的方法：如何把一般的线性规划转化为标准型（1）若要求目标函数实现最小化，即min z=CX。这时只需将目标函数最小化变换求目标函数最大化，即令 z=-z，于是得到max z=CX。这就同标准型的目标函数的形式一致了。,（2）约束方程为不等式。这里有两种情况：一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量 xj，把原不等式变为等式；另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量xk（也可称松弛变量），把不等式约束条件变为等式约束条件。,（3）若变量约束中：xi 0,则令xi=xi 得到 xi

26、0；若xj取值无约束,则令 xj=xj xj,得 xj,xj0,用 xj，xj代替 xj后得到线性规划的变量约束为非负约束。（4）目标函数中加上 0 xi(松弛变量),Chapter 1 线性规划与单纯形法,下面举例说明。例1.4 将下述线性规划化标准型,加入松弛变量,解：加入松弛变量后，即可得该问题的标准型,Chapter 1 线性规划与单纯形法,例1.5 将下述线性规划化标准型,用笔算算看,Chapter 1 线性规划与单纯形法,解：按上述规则化标准型如下：(1)用x4-x5 替换 x3,其中，(2)在第一个约束不等式 号的左端加入松弛变量 x6(3)在第二个约束不等式 号的左端减去松弛变

27、量 x7(4)令，把 改为,即可得到该问题的标准型,举例,把例1.5 第三个约束为下面的形式，化标准型。,解：按上述规则化标准型如下：,Chapter 1 线性规划与单纯形法,1.1.3 线性规划问题的解的概念,一般线性规划问题的标准型为：maxZ=CX|AX=b,X0 可行解：满足上式约束 条件 的解x=(x1,x2,x3,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。,Chapter 1 线性规划与单纯形法,最优解：使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。基：设 Amn(mn)为约束方程组的系数矩阵，其秩为m。Bmm 是矩阵 A 中的子矩阵且是

28、满秩阵，则称 B 是线性规划问题的一个基（基矩阵）。不妨设 B=（aij）mm 中的每一个列向量 pj(j=1,2,m)为基向量。与基向量 pj 对应的变量 xj 称为基变量，其它的变量称为非基变量。注：当 m=n 时，基矩阵唯一，当mn,基矩阵可能有多个，但数目不超过 个 看下面的练习,（补充例题）线性规划,求所有基矩阵。,解：约束方程的系数矩阵为25矩阵,容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即,基与基向量、基变量之间的对应关系,以本例说明,Chapter 1 线性规划与单纯形法,基解：令所有非基变量xm+1,，xn为

29、，得 到约束方程 BXB=b,由克莱姆法则可得到 唯一解 XB=(x1,x2,xm)T，则称由约束方 程确定的唯一解X=(x1,x2,x3,xm,0,0)T 为 线性规划问题的基解。,基可行解：满足约束条件的基解称为基可行解。可行基：对应于基可行解的基称为可行基。若基可行解 XB中至少有一个分量为零，则称为退化的基可行解。,Chapter 1 线性规划与单纯形法,由此可知，退化基可行解中的非零分量一定小于m,非退化解中非零分量一定等于m，若有关线性规划问题的所有基可行解都是非退化解，则该问题为非退化线性规划问题；否则，称为退化线性规划问题。,各解的关系如图1.2,75,上述解的概念中基解和基可

30、行解最为重要，各种解的关系粗略地可用下图表示：,Chapter 1 线性规划与单纯形法,例1.6 写出例1.1的标准形式，指出基、基变量、基解、基可行解和可行基。解：显然，标准形式为,Chapter 1 线性规划与单纯形法,由此，约束方程的系数矩阵为矩阵秩不大于，而 是一个的满秩阵，,故 是一个基,是基变量，是非基变量。令 则 是一个基解。因该基解中所有变量取值为非负，故又是基可行解，对应的基 是一个可行基。,基不是唯一的，也是一个基。是基可行解。也是一个基。看看还有那些基？,80,补充例子,以(P3、P4、P5)作为基，令x1=x2=0，得到 X=(0，0，8，16，12)T为一个基可行解，

31、对应图中O点；,以(P2、P4、P5)作为基，令x1=x3=0，由,2 x2=8 x4=164 x2+x5=12,得X=(0，4，0，16，-4)T是个基解，不是基可行解，对应图中A点；,以(P1、P2、P5)为基，令x3=x4=0，可得X=(4，2，0，0，4)T是基最优解，对应图中Q2点。,Chapter 1 线性规划与单纯形法,1.1.4 线性规划问题的图解法,图解法简单直观，有助于了解线性规划问题求解的基本原理。现用例1.1来说明图解法。例1.1的线性规划问题是：,Chapter 1 线性规划与单纯形法,k(4,3),梯度方向,4X1+3X2=30,最优解在顶点上达到,几种特殊情况,1

32、）无穷多最优解。若将上例中的目标函数变为求 maxZ=4x1+6x2，则目标函数与等值区域边界线2x1+3x2=18平行，线段BC上的任意一点都使Z取得相同的最大值，此 时线性规划问题有无穷多最优解，如图1.5所示.,无穷多最优解,图1.5,Chapter 1 线性规划与单纯形法,2）无界解。考虑下列线性规划问题,无界解,图1.6,注：可行域无界时，线性规划有时也有有限最优解，例如上例中目标函数改为,线性规划问题有有限最优解,3）无可行解。如果在例1.1的线性规划问题中增加一个约束条件 x1+x212,我们有边界方程 L4:x1+x2=12,约束条件为 L4 的上方，则该问题的可行域为空集，即

33、没有一个点满足所有的约束条件，问题无可行解，也不存在最优解。（可行域为空集）,图解法适用于求解只有两个决策变量的线性规划问题，具体步骤如下：1.画出每个函数约束的约束边界，用原点（或其它不在边界上的点）判断直线的哪一边是约束条件所允许的。2.找出所有约束条件都同时满足的区域，即可行域。,图解法的步骤,3.给目标函数一个特定的值 k,画出目标函数等值线，当 k 变化时，目标函数等值线平行移动；对于目标函数最小化的问题，找出目标函数减少的方向，目标函数最后离开可行域的点是最优解。,4.从图解法可以看出，线性规划问题的可行域非空时它是一个凸多边形，若线性规划问题存在最优解，它一定在可行域的边界得到；

34、若有唯一最优解，则一定在可行域的顶点处得到；若两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解。,94,21基本概念,凸组合 设，若存在，0 10 1，且，使则称X 为 的凸组合。,两点连线上的任何一点都是这两点的凸组合,基本概念,95,凸集,96,图中粗线和圆点是顶点。,LP问题解的性质,（1）若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。,97,定理1 若线性规划问题存在可行解，则所有可行解的集合可行域 D=X|AX=b，X 0 是凸集。定理2 线性规划问题的基可行解X对应于可行域 D 的顶点（极点）。定理3 若可行域有界，线性规

35、划问题的目标函数一定可以在顶点上达到最优。,线性规划的基本定理,99,基本可行解个数有限，当约束条件为m个，n个变量时，基本可行解个数不超过:,定理2 刻画了可行解集的极点与基本可行解的对应关系：极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一 对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。,定理 2及 3 给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行解中去寻求。下一节将介绍一种有效地寻找最优解的方法。,若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。,Chapter 1

36、线性规划与单纯形法,2 单纯形法从上一节中我们看到，若线性规划有最优解，必在可行域的某个顶点达到。最可能想到的是把所有顶点都找出来，然后逐个比较，求出最优解，这种方法事实上是行不通的，因为顶点的个数非常大。例如m=20，n=40，顶点的个数有 个，要计算这么多顶点对象目标函数值，显然是不可能的。,换一种思考方法，从某一个基可行解出发，每次总是寻找比上一个更好的基可行解，如果不比上一个好就不去计算，这样做就大大减少计算量。其基本想法是判别当前解是否最优，提出问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数逐步增大，最后就得到了最优解。美国数学家丹捷

37、格（）提出的单纯形方法解决了此问题，单纯形方法到目前为止是求解线性规划的最普遍最有效的方法。,单纯性方法基本思想 对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解直至得到一个基最优解。,利用下面的例子说明几何意义,Chapter 1 线性规划与单纯形法,2.1初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下：若线性规划问题：,从 Pj(j=1,2,n)中一般能直接观察到一个初始可行基：,Chapter 1 线性规划与单纯形法,

38、2）对约束条件是“”形式的不等式，在每个约束条件的左端加上一个松弛变量。经整理，重新对 xj 及进行编号，可得到下列方程组：,显然可以得到一个单位矩阵：以B 作为可行基，将每个等式移项：,令xm+1=xm+2=xn=0,由上式可得:xi=bi（i=1，2，m）X=(x1,x2,xm,0,0)T=(b1,b2,bm,0,0)T,Chapter 1 线性规划与单纯形法,3）对所有约束条件是“”形式的不等式及等式约束情况，化为标准型后若不存在单位矩阵式，就采用人造基方法。即对不等式约束减去一个非负剩余变量，再加上一个非负人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。（有关加上

39、人工变量的线性规划问题，以后再讨论。）,Chapter 1 线性规划与单纯形法,1.2.2 最优解的检验和解的判别,由两个变量的线性规划图解方法我们得到启示，线性规划问题的求解结果可能出现 唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。我们以下面的线性规划模型为例说明解的判别准则,化标准型后，对于约束矩阵中含有单位基矩阵的情况，我们重新对 xj 进行编号，总可以得到下面的形式：,即：,根据上节得到的基解计算公式可归纳如下：,将上式代入目标函数式，整理后得到：,令：,于是 再令：则,注意：xj 的检验数 是当 z 表示为非基变量的函数时目标函数中 xj 的系数。

40、基变量的检验数为零。,最优性判别定理：若基可行解对应的检验数 0(j=1，2，,n)，则此解是最优解，否则不是最优解。,验证可行性：因为,每一个aij和bi均带“撇”,最优解的判断：若基可行解对应的检验数(j=m+1，,n)，则此解是最优解，否则不是最优解。若(j=m+1，,n)，则最优解唯一。无穷多最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解无界解的判断:某个 且（i=1，2,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。,线性规划解的情况：,注：若是求最小化问题-检验数的取值？,Chapter 1 线性规划与单纯形法,1.2.3

41、 基变换 若初始基可行解 X(0)不是最优解及不能判断无界时，需要找一个新的基可行解。具体做法是从原可行解基中换出一个列向量（当然要保持线性独立），从原非可行基中换入一个列向量，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行交换，得到一个新的基可行解。,Chapter 1 线性规划与单纯形法,1)换入变量的确定 当某些 时，xj 增加则目标函数值还可以增大，这时要将某个非基变量 xj 换入到基变量中去（称为换入变量）。若有两个以上的，那么选 中大的那个，即：则对应的 xk 为换入变量。但也可以任选或按最小足码选.,2)换出变量的确定 在

42、确定 xk为换入变量后，由于其他的非基变量仍然为非基变量，即 xj=0(j=m+1,2,n,且 jk),则由约束方程组有,Chapter 1 线性规划与单纯形法,由于所有的,所以若令则 的增加不能超过，此方程相应的变量 即为换出变量。这时 的值是按最小比值来确定的，称为最小比值原则；与此相应的 称为主元素。,Chapter 1 线性规划与单纯形法,1.2.4 单纯形表首先介绍一下单纯形表：为了计算上的方便和规格化，对单纯形法计算设计了一种专门表格，称为单纯形表。表格如下1.4,表1.4,Chapter 1 线性规划与单纯形法,在单纯形表的第2-3列列出某个基可行解中的基变量及它们的取值，接下来

43、列出问题中的所有变量。在基变量下面各列数字分别是对应的基向量数字。表中变量 x1,x2,xm下面各列组成的单位矩阵就是初始基可行解对应的基。,其中：每个基变量xj下面的数字，是该变量在约束方程的系数向量Pj表达为基向量线性组合时的系数。Cj 为表最上端的一行数，是各变量的目标函数中的系数值CB 为表中最左端一列数是与各基变量对应的目标函数中的系数值；b 列中填入约束方程右端的常数；,Chapter 1 线性规划与单纯形法,检验数 称为变量 xj 的检验数，将 xj下面的这列数字 Pj与 CB 这列数中同行的数字分别相乘，再用xj上端 Cj值减去上述乘积之和即：i列的数字是在确定换入变量后，按

44、规则计算后填入；其中。（其中 xj为换入变量）。,单纯形法的计算步骤 求解线性规划问题的单纯形法的计算步骤归纳如下：第一步：求出线性规划的初始基可行解，列出初始单纯形表。,单纯形法,第二步：进行最优性检验。各非基变量检验数为 则表中的基可行解是问题的最优解，计算到此结束，否则进入下一步。,单纯形法,第三步：在 中，若有某个 对应 xk 的系数列向量 Pk，则此问题无界，停止计算。否则，转入下一步。,单纯形法,第四步：从一个基可行解换到另一个目标函数值更大的基可行解，列出新的单纯形表。确定换入变量，有，对应的变量 xj就可作为换入变量，当有两个以上检验数大于零，一般取最大的，即，取 xk 作为换

45、入变量。,单纯形法,确定换出变量。根据最小 规则，对 Pk列由公式计算得:确定是 换出变量。,单纯形法,元素 决定了从一个基本可行解到另一个可行解的转移去向，取名为主元素。以 为主元素进行旋转变换，得到新的单纯形表，转到步骤二。,Chapter 1 线性规划与单纯形法,下面，我们用例1.1说明单纯形表进行迭代运,例1的标准型,表1.5,1)根据问题的标准型，取松弛变量x3,x4,x5 为基变量，对应得单位矩阵的基得到初始基可行解,得到初始单纯形表，如表 1.5 所示算：,Chapter 1 线性规划与单纯形法,其中，非基变量的检验数2)由检验数大于零，P1,P2有正分量，转入下一步,Chapt

46、er 1 线性规划与单纯形法,3）max()=max(4,3)=4，对应 x1为进入变量它对应的基变量 x3是换出基变量，x3 所对应的行与 x1 所对应的列包括检验数变为，在XB 列将 x3 换成 x1得到新单纯形表（表1.6）。,表1.6,Chapter 1 线性规划与单纯形法,此时，新基变量XB=(x1,x4,x5)T,对应于基可 行解 X(1)=(6,0,0,8,6)T,相应的目标值 Z=24.检验表1.6中的检验数行得知 x2 的检验数 为，说明 x2 应为换入基变量，计算 值：,所以对应的 x5为换出基变量，基变量x5 的行与进入基变量 x2 的列交叉处元素 3 为主元素，再对主元

47、素进行旋转变换，使 x2 列变为单位向量(0,0,1,0)T 得到表1.7,表1.7,此时，基变量为 XB=(x1,x,x)T,对应的基可行解为 X(3)=(6,2,0,4,0)T,对应目标函数值Z=30。由于所有检验数均小于或等于0，所以此解是最优解，对应基为最优基。从表上可以看出线性规划有唯一解,作业：1.1（1），1.2（2），1.4（1）1.7（1）、（2）1.81.9,Chapter 1 线性规划与单纯形法,3 单纯形法的进一步讨论,3.1 人工变量法在前文中提到用人工变量法可以得到初始基可行解。但加入人工变量的数学模型与未加人工变量的数学模型一般是不等价的，一般情况下关于这一点有以

48、下结论：,(1)加入人工变量的线性规划用单纯形方法得到最优解中，人工变量处在非基变量位置。(2)最优解中，人工变量可能在基变量中，但取值为零，则可以求出原问题的最优解。若最优解中包含有非零的人工变量，则原问题无可行解。,Chapter 1 线性规划与单纯形法,分别给每一个约束方程加入人工变量xn+1,xn+m,得到,Chapter 1 线性规划与单纯形法,以xn+1,，xn+m为基变量，并可得到一个mm单位矩阵。令非基变量x1,xn为零，便可得到一个初始基可行解,Chapter 1 线性规划与单纯形法,大M法 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为

49、此假定人工变量在目标函数(max z)中的系数为(-M)（M为任意大的正数），若目标函数为min Z，则人工变量在目标函数中系数为M，这样目标函数要实现最大化（最小化）时，应把人工变量从基变量换出，或者人工变量在基变量中，但取值为0。否则目标函数不可能实现最大化。,Chapter 1 线性规划与单纯形法,例1.7 现有线性规划问题,试用大M法求解。,Chapter 1 线性规划与单纯形法,解:在上述问题的约束条件中加入松弛变量，剩余变量，人工变量，得到,这里M是一个任意大的正数。,Chapter 1 线性规划与单纯形法,转化为最大化,同样的做法，注意检验数的变化,Chapter 1 线性规划与

50、单纯形法,用单纯形法进行计算时，见表（1.8）。因本例是求Min，所以用所有 cj-zj0 来判别目标函数是否实现了最小化。表中的最终表表明得到最优解是 x1=4,x2=1,x3=9,x4=x5=x6=x7=0 目标函数 z=-2,Chapter 1 线性规划与单纯形法,(2)两阶段法用电子计算机求解含人工变量的线性规划问题时，只能用很大的数代替M,这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如,Chapter 1 线性规划与单纯形法,然后用单纯形法求解上述模型，若得