第一章线性规划与单纯形法

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

2、的研究小组, 专门就改进防空系统进行研究u二战中, 除英国外, 美国、加拿大等国也相继成立了军事运筹研究小组,解决战争中提出的运筹学课题. 其中最著名的工作之一是改进深水炸弹的起爆深度.军事起源资料 当时德国的潜水艇严重威胁盟军的运输船, 1942年, 美国大西洋舰队主持反潜战的官员贝克(W.D.Baker)请求成立反潜战运筹组, 麻省理工学院的物理学家莫尔斯(P. W.Morse)被请来担任计划与监督. 莫尔斯领导的小组经过多方实地调查, 提出两条重要建议： 1. 将反潜攻击由反潜舰艇投掷水雷改为由飞机投掷深水炸弹; 仅当潜艇浮出水面或刚下潜时, 方投掷深水炸弹; 深水炸弹的定深(指起爆深度

3、)由100-200英尺, 修正为20-50英尺.2. 改进运送物资的船队及护航舰艇编队的方式, 由小规模多批次, 改进为加大规模、减少批次, 可使损失减少，军方采用了上述建议, 重创德国潜艇舰队, 最终成功地打破了德国的海上封锁. 军事起源战争结束时, 英美及加拿大军队中工作的运筹学工作者已超过了700人. 正是由于战争需要的促进, 以及大批著名科学家的参与, 运筹学得到迅速发展. 之后, 运筹学从单纯军事和战争中的应用研究, 扩展到经济和管理领域, 并形成了自己的理论与方法. 1948年, 美国麻省理工学院（MIT）率先开设了运筹学课程, 许多大学群起效法, 内容也日益丰富。军事起源1951

4、年, 莫尔斯和金博尔出版了(1946年内部出版, 1951年公开出版)第一本运筹学专著:运筹学的方法(The Methods of Operations Research). 书中总结了第二次世界大战中运筹学的军事应用, 并给出了运筹学的一个著名定义运筹学 是为执行部门对它们控制下的“业务”活 动采取决策提供定量依据的科学方法.管理起源第一次世界大战前就已经发展成熟的古典管理学派, 对运筹学的产生和发展影响很大。1911年, 泰勒出版了著名的科学管理原理一书. 书中, 泰勒的管理思想和理论, 概括起来主要有以下三个观点：科学管理的根本目的是谋求最高工作效率。 达到最高工作效率的重要手段是科学的

5、管理方法。 实施科学管理要求精神上的彻底变革。根据以上观点泰勒提出管理制度: 最佳动作原理; 合理的日工作量或恰当的工作定额原理; 刺激性付酬制度等.与泰勒同时代的, 对管理改革作出贡献的还有一些学者亨利甘特 甘特的贡献主要有以下几点：p提出了一种“工资任务加奖金”的工资制度p1903年, 发明了“甘特图”. 至今还在实践中使用, 并发展为统筹方法p强调管理民主和重视人的领导方式管理起源管理起源弗兰克杰尔布雷斯夫妇.有影响的著作有:动作研究(1911年)、科学管理入门(1912年)以及疲劳研究(1916年)等. 他们的研究比泰勒的研究更为细致和广泛, 其重要贡献在以下几方面：p 提出动作研究和

6、动作经济原理p疲劳研究. p注意到了工作、工人和环境之间的相互影响.爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。管理起源带有拥挤效应的服务行业如通讯业、交通运输业等都隐含排队论的问题。经济起源经济学理论对运筹学的影响是和数理经济学学派紧密联系的数理经济学对运筹学, 特别是对线性规划的影响可以从魁奈(Qusnay)1758年发表的经济表算起. 最著名的经济学家沃尔拉斯(Walras)研究了经济平衡问题, 后来的经济学家对其数学形

7、式继续研究并得到深入发展. 1928年 冯.诺伊曼以研究二人零和对策的一系列论文为“对策论”奠基. 1932年, 又提出了广义经济平衡模型. 1939年, 苏联的康托洛维奇发表生产组织和计划中的数学方法.这些工作都可以看作是运筹学的先驱工作发展二战结束后, 运筹学很快深入到工业、商业、政府部门等, 并得到了迅速发展；运筹学在中国研究及应用从20世纪50年代中期开始。1957年, 我国在建筑业和纺织业中首先应用运筹学. 1958年, 开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用20世纪60年代起, 在钢铁和石油部门得到了比较全面、深入的应用1965年起统筹法在建筑业、大型设备

8、维修计划等方面的应用取得可喜的进展. 1970年在全国大部分省、市和部门推广优选法70年代中期, 最优化方法在工程设计界受到了广泛的重视, 并在许多方面取得成果; 排队论开始应用于矿山、港口、电信及计算机设计等方面; 图论用于线路布置、计算机设计、化学物品的存放等70年代后期, 存储论在应用汽车工业等方面获得成功近年来, 运筹学已趋向研究和解决规模更大、更复杂的问题, 并与系统工程紧密结合.来历及定义 二战期间, 英国为了研究“如何最好地运用空军及新发明的雷达保护国家”, 成立了一个由各方面专家组成的交叉学科小组.这就是最早的运筹学小组, 它的任务是进行“作战研究”(Operational R

9、esearch). 后来, 美国从事这方面研究的科学家又称之为“ Operations Research”, 简称为 O.R. O.R.的中文译名“运筹学”取自成语“运筹帷幄之中，决胜千里之外”，具有运用筹划，出谋献策，以策略取胜等内涵。目前国外的管理科学（Management Science）与运筹学的内容基本相同运筹学是一门应用科学, 它广泛地应用现有科学技术知识 和数学方法, 解决实际中提出的专门问题, 为决策者选择最优决策提供定量的依据.运筹学发展三阶段：运筹学发展三阶段：创建时期（创建时期（45年至年至50年代初）年代初）1948年年 英国成立英国成立“运筹学运筹学”俱乐部俱乐部19

10、48年年 麻省理工学院麻省理工学院 介绍运筹学介绍运筹学1950年年 伯明翰大学开设运筹学课程伯明翰大学开设运筹学课程1952年年 卡斯大学卡斯大学 设立运筹学硕士和博士学位设立运筹学硕士和博士学位1947年年 丹捷格丹捷格 提出单纯形法提出单纯形法50年代初年代初 计算机求解线性规划获得成功计算机求解线性规划获得成功成长时期（成长时期（50年代初至年代初至50年代末）年代末）多个国家成立运筹学会，多种运筹学刊物问世多个国家成立运筹学会，多种运筹学刊物问世1957年年 在牛津大学召开第一次国际运筹学会议在牛津大学召开第一次国际运筹学会议1959年年 成立国际运筹学联合会成立国际运筹学联合会迅速

11、发展时期（迅速发展时期（60年代以来）年代以来）运筹学进一步分为各个分支，更多运筹学出版物运筹学进一步分为各个分支，更多运筹学出版物运筹学课程纳入教学计划运筹学课程纳入教学计划我国运筹学发展历程：我国运筹学发展历程：1956年年 运筹学小组运筹学小组1958年年 运筹学研究室运筹学研究室1960年年 应用运筹学经验交流会议应用运筹学经验交流会议1962年年 全国运筹学专业学术会议全国运筹学专业学术会议1978年年 全国运筹学专业学术会议全国运筹学专业学术会议1980年年 成立中国运筹学学会成立中国运筹学学会运筹学分支运筹学是一门以决策支持为目标的学科，运筹学的内容丰富，应用范围非常之广，从军事

12、、政治到管理、经济及工程技术等许多领域都能应用到运筹学的思想和方法。经过半个世纪左右的发展，运筹学形成了下面主要几个分支在这过程中，科学家，学者和工程师 都起了很大的作用，在其它很多领域也是这样的！运筹学的分支:线性规划（线性规划（linear programminglinear programming）整数规划（整数规划（integer programming integer programming ）运输问题运输问题 （ transportation Problems transportation Problems ）多目标规划（多目标规划（multiobjective programmi

13、ng multiobjective programming ）图论与网络分析（图论与网络分析（graph theory and network analysisgraph theory and network analysis）非线性规划（非线性规划（nonlinear programmingnonlinear programming）动态规划（动态规划（dynamic programmingdynamic programming）对策论（对策论（game theorygame theory）决策论（决策论（decision theorydecision theory）排队论（排队论（queu

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

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

16、学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点的特点, ,理解理解 线性规划、整数规划、运输问题线性规划、整数规划、运输问题 、目标规划，图与网络等分支、目标规划，图与网络等分支的基本优化原理，掌握其中常用的模型和算法的基本优化原理，掌握其中常用的模型和算法, ,具有一定的建模能力。具有一定的建模能力。先修课程先修课程: : 线性代数，高等数学线性代数，高等数学 等等. .要要 求求：课前预习，课后要复习课前预习，课后要复习 课堂认真听讲（不能旷课）课堂认真听讲（不能旷课）( (每旷课一次平时成绩扣每旷课一次平时成绩扣1010分分) ) 认真完成作业认真完成作业成成 绩：绩： 平

17、时成绩平时成绩 30% 30% （作业、出勤、课堂纪律、实验报告）（作业、出勤、课堂纪律、实验报告） + +考试成绩考试成绩 70%70%答疑时间：答疑时间：每次课后时间，周五下午（行政楼每次课后时间，周五下午（行政楼619 619 ）参考书目：参考书目：运筹学教程（第二版胡运权 清华大学出版社 运筹学运筹学赵可培赵可培, ,上海财经大学出版社上海财经大学出版社 管理运筹学管理运筹学谢家平谢家平, , 中国人民大学出版社中国人民大学出版社 复习线性代数内容复习线性代数内容: :列向量列向量 x=(x1，x2，xn）T为n维列向量。xRn行向量行向量 x=(x1，x2，xn）为n维列向量。xRn

18、矩阵矩阵( (向量向量) )运算规则运算规则 加减乘、求逆运算 结合律 分配律 交换律 乘法无交换律乘法无交换律线性相关线性相关 一组向量v1,vn,如果有一组不全为零的 系数1, ,n,使得: 1 v1+nvn=0 则称v1,vn 是线性相关的.线性无关线性无关 一组向量v1,vn,如果对于任何数1,n, 若要满足: 1 v1+nvn=0 ,则必有系数 1=n=0,(全为零)则称v1,vn线性无关. 矩阵矩阵A A的秩的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.Chapter 1线性规划与单纯形法 Linear pro

19、gramming and the simplex method上海工程技术大学上海工程技术大学管理学院管理学院Chapter 1 线性规划与单纯形法 线性规划线性规划是用线性数学模型表示不同的生产活动、营销活动、是用线性数学模型表示不同的生产活动、营销活动、金融活动或其他活动的计划。金融活动或其他活动的计划。 本章重点1、根据实际问题写出线性规划模型2、掌握线性规划化标准型的方法3、理解并掌握线性规划解的概念4、能够用图解法求解线性规划问题5、熟练掌握线性规划单纯形法的基本思想和 步骤难点难点线性规划（Linear Programming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广

20、泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。 线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。Chapter 1 线性规划与单纯形法 1 1 线性规划数学模型线性规划数学模型1.11.1问题的提出问题的提出 线性规划应用的问题种类繁多，形式各线性规划应用的问题种类繁多，形式各异，主要分为四类线性规划问题。前三类问题分异，主要分为四类线性规划问题。前

21、三类问题分别是资源分配问题，成本效益问题以及网络配送别是资源分配问题，成本效益问题以及网络配送问题。第四类具有两种以上的约束的线性规划问问题。第四类具有两种以上的约束的线性规划问题。题。 Chapter 1 线性规划与单纯形法 某工厂近期要安排生产甲、乙两种产品，某工厂近期要安排生产甲、乙两种产品，产品甲需要用原料产品甲需要用原料A A，产品乙需要用原料，产品乙需要用原料B B，由于两种产品都在一个设备上生产，由于两种产品都在一个设备上生产， 且设且设备使用时间有限，管理者必须合理安排两备使用时间有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下种产品的产量，使得在资源有限的条件下

22、获得最大的利润。获得最大的利润。举例因此这个问题的决策目标是收益的最大化，因此这个问题的决策目标是收益的最大化， 研究者根据这个目标需要收集以下相关数研究者根据这个目标需要收集以下相关数据：据： 1)1)工厂两种原料存量以及可用设备工时工厂两种原料存量以及可用设备工时数；数； 2)2)甲、乙两种产品的单位产品需要的原甲、乙两种产品的单位产品需要的原料和设备工时数；料和设备工时数； 3) 3)甲、乙两种产品的单位产品利润。甲、乙两种产品的单位产品利润。Chapter 1 线性规划与单纯形法 甲甲 乙乙资源限资源限制制原料原料A106原料原料B028设备设备2318单位利润单位利润(百万百万)43

23、举例这些数据可以通过调研或估算得出，这些数据可以通过调研或估算得出，如表如表1.1所示：所示：建立数学模型为建立模型，引入变量如下：为建立模型，引入变量如下：x x1 1-产品甲的数量产品甲的数量x x2 2-产品乙的数量产品乙的数量Z -Z -利润利润由表由表1.11.1最后一行知最后一行知Z Z4x4x1 1+3x+3x2 2建立数学模型目标是如何确定目标是如何确定x x1 1和和x x2 2，使得利润，使得利润Z Z最大最大, ,同同时需要满足资源约束。对于原料时需要满足资源约束。对于原料A A和原料和原料B B，有：有：x x1 166，2x2x2 288对于设备工时，有：对于设备工时

24、，有：2x2x1 1+3x+3x2 21818此外，甲、乙两种产品数量不可能是负值，此外，甲、乙两种产品数量不可能是负值，因此，有如下对变量的非负约束：因此，有如下对变量的非负约束：x x1 1 0 , x 0 , x2 200于是，问题的数学模型现在可以用代数式表述如下：于是，问题的数学模型现在可以用代数式表述如下：满足：满足：12121212maxZ43x6 (1.1)28(1.2)2318(1.3),0(1.4)xxxxxx x原材料限制原材料限制设备限制实际上这是求一个线性函数在一组线性约实际上这是求一个线性函数在一组线性约束条件下的最大值问题，称之为线性规划束条件下的最大值问题，称之

25、为线性规划问题模型。问题模型。以上模型中，将以上模型中，将x x1 1、x x2 2称为称为决策变量决策变量； Z Z4x4x1 1+3x+3x2 2为为目标函数目标函数；约束；约束(1.1)(1.1)(1.3)(1.3) 为为函数约束函数约束；(1.4)(1.4)为为非负约束非负约束。 Chapter 1 线性规划与单纯形法 从以上过程我们可以归纳出根据实际从以上过程我们可以归纳出根据实际 问题建立线性规划模型的步骤：问题建立线性规划模型的步骤：1) 1) 根据管理层的要求确定决策目标和收集根据管理层的要求确定决策目标和收集相关数据。相关数据。2) 2) 确定要做出的决策，引入决策变量。确定

26、要做出的决策，引入决策变量。3) 3) 确定对这些决策的约束条件和目标函数。确定对这些决策的约束条件和目标函数。Chapter 1 线性规划与单纯形法 例例1.21.2 成本效益平衡问题成本效益平衡问题某饲料公司希望用玉米、红薯作原料配制某饲料公司希望用玉米、红薯作原料配制一种混合饲料，各种原料包含的营养成分一种混合饲料，各种原料包含的营养成分和采购成本都不同，公司管理层希望能够和采购成本都不同，公司管理层希望能够确定混合饲料中的各种原料数量，使得饲确定混合饲料中的各种原料数量，使得饲料能够以最低成本达到一定的营养要求。料能够以最低成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如研

27、究者根据这一目标收集到的有关数据如下（见表下（见表1.21.2）举例表1.2 营养成分营养成分每公斤玉每公斤玉米米每公斤每公斤红薯红薯每公斤最每公斤最低要求低要求碳水化合物碳水化合物8420蛋白质蛋白质3618维他命维他命1516采购成本采购成本（元（元/公斤）公斤）0.80.5举例为建立线性规划模型，我们引入变量如下：为建立线性规划模型，我们引入变量如下：x x1 1= =混合饲料中的玉米数量；混合饲料中的玉米数量；x x2 2= =混合饲料中红薯的数量；混合饲料中红薯的数量；目标函数目标函数 Z=0.8xZ=0.8x1 1+0.5x+0.5x2 2，表示产量的成本，表示产量的成本函数函数.

28、 . 即如何确定即如何确定x x1 1， x x2 2 使得成本使得成本Z=0.8xZ=0.8x1 1+0.5x+0.5x2 2 最低且满足最低营养要求最低且满足最低营养要求的约束，的约束，Chapter 1 线性规划与单纯形法 因此这个问题的线性规划模型为：因此这个问题的线性规划模型为：其中其中“s.t.”是是“subject to”的缩写，意思的缩写，意思是是“受约束于受约束于”。12121212min0.80.58x4203x618s.tx51601,2iZxxxxxxi碳水化合物要求蛋白质物要求维他命物要求Chapter 1 线性规划与单纯形法 某物流公司需要将甲、乙、丙三个工厂某物流

29、公司需要将甲、乙、丙三个工厂生产的一种新产品送到生产的一种新产品送到 A A、B B 两个仓库，甲、两个仓库，甲、乙两个工厂的产品可以通过铁路运送到仓库乙两个工厂的产品可以通过铁路运送到仓库A A，数量不限；丙工厂的产品可以通过铁路运送到数量不限；丙工厂的产品可以通过铁路运送到仓库仓库B B，同样，产品数量不限。，同样，产品数量不限。 由于铁路运输由于铁路运输成本较高，公司也可以考虑由独立的卡车来运成本较高，公司也可以考虑由独立的卡车来运输，可将多达输，可将多达8080个单位的产品由甲、乙、丙三个单位的产品由甲、乙、丙三个工厂运到一个配送中心，再从配送中心以最个工厂运到一个配送中心，再从配送中

30、心以最多多9090单位的载货量运到各个仓库。公司管理层单位的载货量运到各个仓库。公司管理层希望以最小的成本运送所需的货物。希望以最小的成本运送所需的货物。 举例Chapter 1 线性规划与单纯形法 配送配送中心中心仓库仓库A仓库仓库B运输量运输量工厂甲工厂甲$3.0$7.5- 100工厂乙工厂乙$3.5$8.2- 80工厂丙工厂丙$3.4-$9.2 70配送中配送中心心-$2.3$2.3 需求量需求量-120130 250举例首先，需要收集每条线路上的单位运输成本和各工厂首先，需要收集每条线路上的单位运输成本和各工厂产品的产量以及各仓库分配量等数据，如表产品的产量以及各仓库分配量等数据，如表

31、1.3所示。所示。为了更清楚地说明问题，我们用网络图来为了更清楚地说明问题，我们用网络图来直观表示该配送问题。见图直观表示该配送问题。见图1.11.1 其中其中 ，v v1 1、v v2 2、v v3 3 表示甲、乙、丙三个表示甲、乙、丙三个工厂，节点工厂，节点v v4 4表示配送中心，节点表示配送中心，节点v v5 5、v v6 6表表示两个仓库；每一条箭线表示一条可能的示两个仓库；每一条箭线表示一条可能的运输线路，并给出了相应的单位运输成本，运输线路，并给出了相应的单位运输成本，对运输量有限制的路线的最大运输能力也对运输量有限制的路线的最大运输能力也同时给出。同时给出。$8.2$2.390

32、$2.390$9.280$3.480$3.5生产10080$3$7.5v1v5v2v3 v4 v6生产80生产70130仓库B120仓库A图图1.1配送中心 我们要解决的是各条线路最大运输量，引我们要解决的是各条线路最大运输量，引入变量入变量 x xij ij 表示由表示由 v vi i 经过路线经过路线 (v(vi i， v vj j ) ) 运输到运输到 v vj j 的产品数。的产品数。 问题的目标是总运问题的目标是总运输成本最小化，总运输成本可以表示为：输成本最小化，总运输成本可以表示为： 总运输成本总运输成本 = 7.5x= 7.5x1515+3 x+3 x1414+8.2x+8.2

33、x2525+3.5 +3.5 x x2424+2.3 x+2.3 x4545+3.4 x+3.4 x3434+2.3x+2.3x4646+9.2 x+9.2 x3636 数学模型1514252445244636151425243436142434454615254546361424344546min7.538.23.52.33.42.39.21008070s.t.12013080,80,80,90,900ijZxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx从以上的几个例子可以看出，线性规划问题有从以上的几个例子可以看出，线性规划问题有如下共同如下共同特征特征： （模型的三要素）（

34、模型的三要素） 每一个问题都用一组决策变量每一个问题都用一组决策变量( (x x1 1，x x2 2，x xn n) ) 表示某一表示某一方案；这组决策变量的值就代表一个具体方案。一般这些方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。变量取值都是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。或线性不等式来表示。 都有一个要求达到的目标，它可用决策变量的线性函数（都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实称为目标函数）来表示。按问题

35、的不同，要求目标函数实现最大化或最小化。现最大化或最小化。例2 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表404524332231 A B C单位产品利润单位产品橡胶量单位产品钢消耗量产品已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？练习解解：设x1，x2， x3分别为A、B、C日产量，则有 约束条件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30因此，线性规划模型为 目标函数： max z=40 x1+45x2 +24x3123123123max40452423100s.t. 332

36、1200, 1,2,3iZxxxxxxxxxxiChapter 1 线性规划与单纯形法 根据上节分析，线性规划的一般形式为：根据上节分析，线性规划的一般形式为：1 12211 11221121 1222221 12212max(min) Z= + +,s.t. ,0nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xx 决策变量向量：决策变量向量：X X=(=(x x1 1，x x2 2，x xn n) )T T价值向量：价值向量：C C=(=(c c1 1，c c2 2，c cn n) )T T资源向量：资源向量：b b=(=(b b1

37、1，b b2 2，b bm m) )T T系数矩阵系数矩阵A=（aij）mn =mnmmnnaaaaaaaaa 212222111211为了讨论和制定统一的算法，引入线性规划的标准形式本教材规定的标准形式为本教材规定的标准形式为：(1) 目标函数要求是目标函数要求是max; (有的要求有的要求min) (2) 约束条件的要求是等式约束条件的要求是等式; (3) 决策变量的要求是非负约束决策变量的要求是非负约束; (4) 在标准型式中规定各约束条件的右端项在标准型式中规定各约束条件的右端项bi0，否则等式两端乘以否则等式两端乘以“-1”。 即标准形式为：1 12211 11221121 1222

38、221 12212max Z= + +,0nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xxChapter 1 线性规划与单纯形法 用向量和矩阵符号表述时为：用向量和矩阵符号表述时为：1max z=CXs.t.0,1,2,njjjjP xbxjn),(21ncccC12nxxXx12jjjmjaaPa12mbbbb用矩阵描述时为：用矩阵描述时为：其中：其中：11121121200,;00nnmmmnaaaAP PPaaa maxb 0ZCXAXXChapter 1 线性规划与单纯形法称称A A为约束条件的为约束条件的m mn n维系数矩

39、阵，维系数矩阵，一般一般m0;m0;b b为资源向量；为资源向量；C C为价值向量；为价值向量；X X为决策变量向量。为决策变量向量。下面讨论化标准型的方法：下面讨论化标准型的方法：如何把一般的线如何把一般的线性规划转化为标准型性规划转化为标准型（1 1）若要求目标函数实现最小化，即）若要求目标函数实现最小化，即min min z=CXz=CX。这时只需将目标函数最小化变换求目。这时只需将目标函数最小化变换求目标函数最大化，即令标函数最大化，即令 z=-zz=-z，于是得到，于是得到max max z= z= CXCX。这就同标准型的目标函数的形。这就同标准型的目标函数的形式一致了。式一致了。

40、MinZ=CXZ=-Z（2 2）约束方程为不等式。这里有两种情况：）约束方程为不等式。这里有两种情况：一种是约束方程为一种是约束方程为不等式，则可在不等式，则可在不等式的左端加入不等式的左端加入非负非负松弛变量松弛变量 x xj j，把原把原不等式变为等式；不等式变为等式； 另一种是约束方程为另一种是约束方程为不等式，则可不等式，则可在在不等式的左端减去一个非负剩余不等式的左端减去一个非负剩余变量变量x xk k（也可称松弛变量），把不等式约束（也可称松弛变量），把不等式约束条件变为等式约束条件。条件变为等式约束条件。（3 3）若变量约束中：）若变量约束中： x xi i 0,0,则令则令x

41、xi i= = x xi i 得到得到 x xi i00； 若若x xj j取值无约束取值无约束, ,则令则令 x xj j = x= xj j x xj j, ,得得 x xj j, x, xj j0, 0, 用用 x xj j，x xj j代替代替 x xj j后得到线性规划的变量约束为非负约束。后得到线性规划的变量约束为非负约束。（4 4）目标函数中加上）目标函数中加上 0 x0 xi i ( (松弛变量松弛变量) )Chapter 1 线性规划与单纯形法 加入松弛变量12121212max2328416s.t.412,0Zxxxxxxxx：12345123142512345max230

42、0028416s.t.412,0Zxxxxxxxxxxxxx x x x xChapter 1 线性规划与单纯形法 123123123123123min2372s.t.325,0, zxxxxxxxxxxxxx xx取值无约束用笔算算看Chapter 1 线性规划与单纯形法 ：(1) (1) 用用x x4 4 - x- x5 5 替换替换 x x3 3, , 其中其中 ，(2) (2) 在第一个约束不等式在第一个约束不等式 号的左端加入松弛变号的左端加入松弛变量量 x x6 6(3) (3) 在第二个约束不等式在第二个约束不等式 号的左端减去松弛变号的左端减去松弛变量量 x x7 7(4) (

43、4) 令令 ，把，把 改改为为 , , 即可得到该问题的标准型即可得到该问题的标准型举例45, 0 xx ZZ min ZmaxZ12456712456124571245124567max 23()00()7()2s.t.32()5,0zxxxxxxxxxxxxxxxxxxxxx x x x x x把例1.5 第三个约束为下面的形式，化标准型。：123123123123123min2372s.t.325,0, zxxxxxxxxxxxxx xx 取值无约束12456781245612457124581245678max 23()000()7()2s.t.32()5,0zxxxxxxxxxxxx

44、xxxxxxxxxxx x x x x x xChapter 1 线性规划与单纯形法 一般线性规划问题的标准型为：一般线性规划问题的标准型为：maxZ=CX|AX=b,X0 u 可行解：可行解： 满足上式约束满足上式约束 条件条件 的解的解x=(x1,x2,x3,xn)T ，称为线性，称为线性规划问题的可行解。全部可行解的规划问题的可行解。全部可行解的集合称为可行域。集合称为可行域。Chapter 1 线性规划与单纯形法 u 最优解：最优解： 使目标函数达到最大值的可行解称使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。为最优解，对应的目标函数值称为最优值。u 基：基： 设

45、设 A Am mn n(mn) (mn) 为约束方程组的系数矩阵，为约束方程组的系数矩阵，其秩为其秩为m m。 B Bm mm m 是矩阵是矩阵 A A 中的子矩阵且是满秩中的子矩阵且是满秩阵，阵， 则称则称 B B 是线性规划问题的一个基（基矩是线性规划问题的一个基（基矩阵）。不妨设阵）。不妨设 B=B=（a aijij）m mm m 中的每一个列向量中的每一个列向量 p pj j (j=1,2,m)(j=1,2,m)为基向量。与基向量为基向量。与基向量 p pj j 对对应的变量应的变量 x xj j 称为基变量，其它的变量称为非基称为基变量，其它的变量称为非基变量。变量。 注注：当：当

46、m=n m=n 时，基矩阵唯一，当时，基矩阵唯一，当mn, m12, 12, 我们有我们有边界方程边界方程 L4: xL4: x1 1+x+x2 2=12, =12, 约束条件为约束条件为 L4 L4 的上方，则该问题的可行域为空集，即没的上方，则该问题的可行域为空集，即没有一个点满足所有的约束条件，问题无可有一个点满足所有的约束条件，问题无可行解，也不存在最优解。行解，也不存在最优解。 （可行域为空集可行域为空集）图解法适用于求解只有两个决策变量的线性图解法适用于求解只有两个决策变量的线性规划问题，具体步骤如下：规划问题，具体步骤如下： 1.1.画出每个函数约束的约束边界，用原点画出每个函数

47、约束的约束边界，用原点（或其它不在边界上的点）判断直线的哪（或其它不在边界上的点）判断直线的哪一边是约束条件所允许的。一边是约束条件所允许的。2.2.找出所有约束条件都同时满足的区域，找出所有约束条件都同时满足的区域，即可行域。即可行域。图解法的步骤3.3.给目标函数一个特定的值给目标函数一个特定的值 k, k, 画出目标画出目标函数等值线，当函数等值线，当 k k 变化时，目标函数等值变化时，目标函数等值线平行移动；线平行移动； 对于目标函数最小化的问题，对于目标函数最小化的问题，找出目标函数减少的方向，目标函数最后找出目标函数减少的方向，目标函数最后离开可行域的点是最优解。离开可行域的点是

48、最优解。 4. 4. 从图解法可以看出，线性规划问题的可从图解法可以看出，线性规划问题的可行域非空时它是一个凸多边形，若线性规划行域非空时它是一个凸多边形，若线性规划问题存在最优解，它一定在可行域的边界得问题存在最优解，它一定在可行域的边界得到；到； 若有唯一最优解，则一定在可行域的顶点若有唯一最优解，则一定在可行域的顶点处得到；若两个顶点同时达到最优解，则两处得到；若两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解。个顶点之间线段上的任意一点都是最优解。9621基本概念基本概念)(X)(XX10121 凸组合凸组合 设设 ，若存在若存在 ，0 0 10 0 1，且，且 ，使使

49、则称则称X 为为 的凸组合。的凸组合。 k, 1kkXXX 11i nKEX,X 1KX,X 111 Kii 两点连线上的任何一点都是这两点的凸组合两点连线上的任何一点都是这两点的凸组合 基本概念基本概念97设设 nEK ，若任意两点，若任意两点KX,KX 21的凸组合属的凸组合属于于 K，即，即 )(KX)(XX10121 则称则称 K 为凸集。为凸集。 aab(c)ccdd凸集凸集98图中粗线和圆点是顶点。图中粗线和圆点是顶点。aabb(c)cdLP问题解的性质（1 1）若）若(LP)(LP)问题有可行解，则可行解集问题有可行解，则可行解集( (可可行域行域) )是凸集是凸集( (可能有界

50、，也可能无界可能有界，也可能无界) )，有，有有限个顶点。有限个顶点。99（2 2）(LP)(LP)问题的基本可行解问题的基本可行解 可行可行域的顶点。域的顶点。 （3）若若(LP)(LP)问题有最优解，必可以在问题有最优解，必可以在基本可行解基本可行解( (顶点顶点) )达到。达到。定理定理1 1 若线性规划问题存在可行解，则所若线性规划问题存在可行解，则所有可行解的集合有可行解的集合可行域可行域 D D = = X| AX= X| AX= b b，X X 0 0 是凸集。是凸集。定理定理2 2 线性规划问题的基可行解线性规划问题的基可行解X X对应于对应于可行域可行域 D D 的顶点的顶点

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

52、有效地寻找最优解的方法。 若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。Chapter 1 线性规划与单纯形法 2 2 单纯形法单纯形法从上一节中我们看到，若线性规划有最优解，从上一节中我们看到，若线性规划有最优解，必在可行域的某个顶点达到。最可能想到的必在可行域的某个顶点达到。最可能想到的是把所有顶点都找出来，然后逐个比较，求是把所有顶点都找出来，然后逐个比较，求出最优解，这种方法事实上是行不通的，因出最优解，这种方法事实上是行不通的，因为顶点的个数非常大。例如为顶点的个数非常大。例如m=20m=20，n=40n=40，顶，顶点的个

53、数有点的个数有 个，个，要计算这么多顶点对象目标函数值，显然是要计算这么多顶点对象目标函数值，显然是不可能的。不可能的。112040103 . 1C换一种思考方法，从某一个基可行解出发，每换一种思考方法，从某一个基可行解出发，每次总是寻找比上一个更好的基可行解，如果不次总是寻找比上一个更好的基可行解，如果不比上一个好就不去计算，这样做就大大减少计比上一个好就不去计算，这样做就大大减少计算量。其基本想法是判别当前解是否最优，提算量。其基本想法是判别当前解是否最优，提出问题的标准，从可行域中某个基可行解（一出问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶个顶点）开始，

54、转换到另一个基可行解（顶点），并且使目标函数逐步增大，最后就得到点），并且使目标函数逐步增大，最后就得到了最优解。美国数学家丹捷格（了最优解。美国数学家丹捷格（G.B.DantzigG.B.Dantzig）提出的单纯形方法解决了此问题，单纯形方法提出的单纯形方法解决了此问题，单纯形方法到目前为止是求解线性规划的最普遍最有效的到目前为止是求解线性规划的最普遍最有效的方法。方法。单纯性方法基本思想单纯性方法基本思想 对于一个对于一个标准型标准型LPLP问题，从一个初始问题，从一个初始基可行解基可行解出出发，判断其是否为最优解，若是则结束；否则求一发，判断其是否为最优解，若是则结束；否则求一个与其个

55、与其“相邻相邻”的、改进的的、改进的基可行解基可行解。再判断这个。再判断这个解是否最优，若是则结束，否则再求一个解是否最优，若是则结束，否则再求一个“相邻相邻”的、改进的的、改进的基可行解基可行解直至得到一个基直至得到一个基最优解最优解。利用下面的例子说明几何意义121231425max2328416s.t.41201,5jzxxxxxxxxxxjx1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2 O Q1 Q2或或 O Q4 Q3 Q2Chapter 1 线性规划与单纯形法 2.12.1初始基可行解的确定初始基可行解的确定为了确定初始基可行

56、解，要首先找出初始可行基，为了确定初始基可行解，要首先找出初始可行基，其方法如下：其方法如下：若线性规划问题：若线性规划问题： 11max. .(6.1)0;1,2,njjjnjjjjzc xP xbs txjn从从 P Pj j (j=1,2,n) (j=1,2,n) 中一般能直接观察到一个中一般能直接观察到一个初始可行基初始可行基：100010001BChapter 1 线性规划与单纯形法 2 2）对约束条件是）对约束条件是“”形式的不等式，在形式的不等式，在每个约束条件的左端加上一个松弛变量。每个约束条件的左端加上一个松弛变量。经整理，重新对经整理，重新对 x xj j 及进行编号，可得

57、到下及进行编号，可得到下列方程组：列方程组：11,111122,1122,11(6.2).mmnnmmnnmm mmmnnmxaxa xbxaxa xbxaxaxb显然可以得到一个单位矩阵：显然可以得到一个单位矩阵：以以B B 作为可行基，将每个等式移项：作为可行基，将每个等式移项：100010001Bq令令x xm+1m+1= =x xm+2m+2= = =x xn n=0,=0,由上式可得由上式可得: : x xi i= =b bi i （i=1i=1，2 2，m m）X=(xX=(x1 1,x,x2 2,x,xm m,0,0),0,0)T T=(b=(b1 1,b,b2 2,b,bm m

58、,0,0,0)0)T T111,111222,112,11.(6.3)mmnnmmnnmmm mmmnnxbaxa xxbaxa xxbaxaxChapter 1 线性规划与单纯形法 q3 3）对所有约束条件是）对所有约束条件是“”形式的不等式形式的不等式及等式约束情况，及等式约束情况，化为标准型后若不存在单化为标准型后若不存在单位矩阵式，就采用人造基方法位矩阵式，就采用人造基方法。 即对不等即对不等式约束减去一个非负剩余变量，再加上一个式约束减去一个非负剩余变量，再加上一个非负人工变量；对于等式约束再加上一个非非负人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。负的人工

59、变量，总能得到一个单位矩阵。（有关加上人工变量的线性规划问题，以后（有关加上人工变量的线性规划问题，以后再讨论。）再讨论。）Chapter 1 线性规划与单纯形法 由两个变量的线性规划图解方法我们得到启示，线由两个变量的线性规划图解方法我们得到启示，线性规划问题的求解结果可能出现性规划问题的求解结果可能出现 n唯一最优解、唯一最优解、n无穷多最优解、无穷多最优解、n无界解无界解n和无可行解四种情况，和无可行解四种情况， 为此需要建立对解的判别准则。为此需要建立对解的判别准则。我们以下面的线性我们以下面的线性规划模型为例说明解的判别准则规划模型为例说明解的判别准则1 12 211,111122,

60、1122,11max Z= + +(6.2).n nmmn nmmn nmm mmmn nmcx c xc xxaxa xbxaxa xbxaxa xb化标准型后，对于约束矩阵中含有单位基矩阵的情况，化标准型后，对于约束矩阵中含有单位基矩阵的情况，我们重新对我们重新对 xj 进行编号，总可以得到下面的形式：进行编号，总可以得到下面的形式：111,111222,112,11.(6.3)mmnnmmnnmmm mmmnnxbaxa xxbaxa xxbaxax1(1,2,)niiijjj mxba x im即：根据上节得到的基解计算公式可归纳如下：根据上节得到的基解计算公式可归纳如下：注注 ： 初