运筹学全套课程教学课件.ppt

1、第第1 1节节 运筹学的简史运筹学的简史 第第2 2节节 运筹学的性质和特点运筹学的性质和特点 第第3 3节节 运筹学的工作步骤运筹学的工作步骤 第第4 4节节 运筹学主要分支简介运筹学主要分支简介 第第5 5节节 运筹学的应用运筹学的应用 第第6节节 运筹学的展望运筹学的展望 绪绪 论论 第第1 1节节 运筹学的简史运筹学的简史 “运筹学”名字的由来运筹学”名字的由来 最早出现在第二次世界大战期间最早出现在第二次世界大战期间 美、英等国家的美、英等国家的 作战研究小组为了解决作战中所遇到的许多错综复杂的作战研究小组为了解决作战中所遇到的许多错综复杂的 战略、战术问题而提出的。战略、战术问题而

2、提出的。 Operational Research (英国英国) Operations Research (缩写缩写O.R.) (美国美国) 运用研究，作业研究，管理数学，运用研究，作业研究，管理数学， 运用学运用学 “夫运筹帷幄之中，决胜于千里之外”“夫运筹帷幄之中，决胜于千里之外” 史记史记.高祖本纪高祖本纪 运筹学思想的出现可以追溯到很早运筹学思想的出现可以追溯到很早 如如“田忌“田忌 齐王赛马”、“丁渭主持皇宫修复齐王赛马”、“丁渭主持皇宫修复 ”。 “田忌齐王赛马”“田忌齐王赛马” 齐王齐王 田忌田忌 齐王齐王 田忌田忌 上上 上上 上上 上上 中中 中中 中中 中中 下下 下下 下

3、下 下下 实力实力 结果结果 优于优于 优于优于 优于优于 北宋时期，皇宫因火焚毁，由丁渭主持修复工作。北宋时期，皇宫因火焚毁，由丁渭主持修复工作。 他让人在宫前大街取土烧砖，挖成大沟后灌成水他让人在宫前大街取土烧砖，挖成大沟后灌成水 渠，利用水渠运来各种建筑材料，工程完毕后再渠，利用水渠运来各种建筑材料，工程完毕后再 以废砖乱瓦等填沟修复大街，做到减少和方便运以废砖乱瓦等填沟修复大街，做到减少和方便运 输，加快了工程进度。输，加快了工程进度。 “丁渭主持皇宫修复丁渭主持皇宫修复 ” 创建时期创建时期（194519455050年代初年代初) ) 美国麻省理工学院美国麻省理工学院( (19481

4、948) ) 英国伯明翰大学英国伯明翰大学（19501950) ) 美国卡斯工业大学美国卡斯工业大学( (19521952) ) 运筹学季刊运筹学季刊( (19501950) ) 英国运筹协会英国运筹协会( (19481948),),美国运筹协会美国运筹协会( (19521952) ) 丹捷格丹捷格( (19471947) )- -单纯形法单纯形法 莫尔斯和金博尔莫尔斯和金博尔( (19511951) )- - 运筹学方法运筹学方法 成长时期成长时期（5050年代初年代初5050年代末年代末) ) 计算机技术的迅速发展计算机技术的迅速发展，运筹学广泛应用运筹学广泛应用 法国运筹协会法国运筹协会

5、( (19561956) ) 日本日本、印度运筹协会印度运筹协会( (19571957) ) 国际运筹联合会国际运筹联合会( (19591959) ) 普及和迅速发展时间普及和迅速发展时间(60(60年代以后年代以后) ) 研究成果被应用到生产、经济领域，并得到迅速研究成果被应用到生产、经济领域，并得到迅速 发展发展有关理论和方法的研究、实践不断深入。有关理论和方法的研究、实践不断深入。 欧洲运筹协会欧洲运筹协会(1975),(1975),亚太运筹协会亚太运筹协会(1985)(1985) 我 国 的 运 筹 学 会 于我 国 的 运 筹 学 会 于 19801980 年 成 立年 成 立 ，

6、网 址 为网 址 为 httphttp: :/orsc/orsc. .eduedu. .cn/cn/ 数学对运筹学的作用数学对运筹学的作用是有关理论和方法的研究是有关理论和方法的研究 基础，是建立运筹学模型的工具。基础，是建立运筹学模型的工具。 计算机的发展，促进运筹学的进一步发展计算机的发展，促进运筹学的进一步发展高速、高速、 可靠的计算是运筹学解决问题的基本保障。可靠的计算是运筹学解决问题的基本保障。 第第2 2节节 运筹学的性质和特点运筹学的性质和特点 英国大百科全书英国大百科全书: “运筹学是一门应用于管理有组织系统的科学运筹学是一门应用于管理有组织系统的科学”， “运筹学为掌管这类系

7、统的人提供决策目标和数量运筹学为掌管这类系统的人提供决策目标和数量 分析的工具分析的工具”。 中国大百科全书中国大百科全书: “用数学方法研究经济用数学方法研究经济、民政和国防等部门在内外民政和国防等部门在内外 环境的约束条件下合理分配人力环境的约束条件下合理分配人力、物力物力、财力等资财力等资 源源，使实际系统有效运行的技术科学使实际系统有效运行的技术科学，它可以用来它可以用来 预测发展趋势预测发展趋势,制定行动规划或优选可行方案制定行动规划或优选可行方案”。 莫斯和金博尔莫斯和金博尔: “为决策机构在对其控制下业务活为决策机构在对其控制下业务活 动进行决策时，提供以数量化为基础的科学方法。

8、”动进行决策时，提供以数量化为基础的科学方法。” “运筹学是一门应用科学，它广泛应用现有的科学“运筹学是一门应用科学，它广泛应用现有的科学 技术知识和数学方法，解决实际中提出的专门问题，技术知识和数学方法，解决实际中提出的专门问题， 为决策者选择最优决策提供定量依据。”为决策者选择最优决策提供定量依据。” “运筹学是一种给出问题坏的答案的艺术，否则的“运筹学是一种给出问题坏的答案的艺术，否则的 话问题的结果会更坏。”话问题的结果会更坏。” 前英国运筹学学会会长托姆林森：前英国运筹学学会会长托姆林森： ( (1 1) ) 合伙原则：合伙原则：是指运筹学工作者要和各方面人是指运筹学工作者要和各方面

9、人，尤尤 其是同实际部门工作者合作其是同实际部门工作者合作。 ( (2 2) ) 催化原则：催化原则：在多学科共同解决某问题时在多学科共同解决某问题时，要引导要引导 人们改变一些常规的看法人们改变一些常规的看法。 ( (3 3) ) 互相渗透原则：互相渗透原则：要求多部门彼此渗透地考虑问题要求多部门彼此渗透地考虑问题， 而不是只局限于本部门而不是只局限于本部门。 ( (4 4) ) 独立原则：独立原则：在研究问题时在研究问题时，不应受某人或某部门不应受某人或某部门 的特殊政策所左右的特殊政策所左右，应独立从事工作应独立从事工作。 ( (5 5) ) 宽容原则：宽容原则：解决问题的思路要宽解决问

10、题的思路要宽，方法要多方法要多，而而 不是局限于某种特定的方法不是局限于某种特定的方法。 ( (6 6) ) 平衡原则：平衡原则：要考虑各种矛盾的平衡要考虑各种矛盾的平衡，关系的平衡关系的平衡。 引入数学方法解决实际问题引入数学方法解决实际问题 -定性与定量方法结合定性与定量方法结合 系统与整体性系统与整体性 -从全局考察问题从全局考察问题 应用性应用性 -源于实践、为了实践、服务于实践源于实践、为了实践、服务于实践 交叉学科交叉学科 -涉及经济、管理、数学、工程和系统等涉及经济、管理、数学、工程和系统等 多学科多学科 开放性开放性 -不断产生新的问题和学科分支不断产生新的问题和学科分支 多分

11、支多分支 -问题的复杂和多样性问题的复杂和多样性 运筹学的性质与特点运筹学的性质与特点 第第3 3节节 运筹学的工作步骤运筹学的工作步骤 ( (1 1) ) 提出和形成问题提出和形成问题。即要弄清问题的目标即要弄清问题的目标，可能可能 的约束的约束，问题的可控变量以及有关参数问题的可控变量以及有关参数，搜集有搜集有 关资料；关资料； ( (2 2) ) 建立模型建立模型。即把问题中可控变量即把问题中可控变量、参数和目标参数和目标 与约束之间的关系用一定的模型表示出来；与约束之间的关系用一定的模型表示出来； ( (3 3) ) 求解求解。用各种手段用各种手段( (主要是数学方法主要是数学方法，也

12、可用其也可用其 他方法他方法) )将模型求解将模型求解。解可以是最优解解可以是最优解、次优解次优解、 满意解满意解。复杂模型的求解需用计算机复杂模型的求解需用计算机，解的精度解的精度 要求可由决策者提出；要求可由决策者提出； ( (4 4) ) 解的检验解的检验。首先检查求解步骤和程序有无错误首先检查求解步骤和程序有无错误， 然后检查解是否反映现实问题；然后检查解是否反映现实问题； ( (5 5) ) 解的控制解的控制。通过控制解的变化过程决定对解是通过控制解的变化过程决定对解是 否要作一定的改变；否要作一定的改变； ( (6 6) ) 解的实施解的实施。是指将解用到实际中必须考虑到实是指将解

13、用到实际中必须考虑到实 施的问题施的问题，如向实际部门讲清解的用法如向实际部门讲清解的用法，在实施在实施 中可能产生的问题和修改中可能产生的问题和修改。 以上步骤应反复进行以上步骤应反复进行。 运筹学的分支运筹学的分支 一、线性规划一、线性规划 变量连续取值，目标函数和约束条件均为变量连续取值，目标函数和约束条件均为 线性。线性。 运输问题、生产计划问题、下料问题、混运输问题、生产计划问题、下料问题、混 合配料问题等。合配料问题等。 二、非线性规划二、非线性规划 目标函数或约束条件不全是线性的。目标函数或约束条件不全是线性的。 在各类工程的优化设计中得到较多应用。在各类工程的优化设计中得到较多

14、应用。 运筹学的分支运筹学的分支 三、动态规划三、动态规划 研究多阶段决策过程的最优化。研究多阶段决策过程的最优化。 资源分配问题，生产与存储问题，设备资源分配问题，生产与存储问题，设备 更新问题等。更新问题等。 四、图论与网络分析四、图论与网络分析 图论是研究由节点和边所组成的图形的图论是研究由节点和边所组成的图形的 数学理论和方法。数学理论和方法。 运筹学的分支运筹学的分支 五、存储论五、存储论 研究最优存储策略的理论和方法。研究最优存储策略的理论和方法。 六、排队论六、排队论 研究顾客不同输入，各类服务时间的分研究顾客不同输入，各类服务时间的分 布，不同服务员数及不同排队规则的情布，不同

15、服务员数及不同排队规则的情 况下，排队系统的工作性能和状态。况下，排队系统的工作性能和状态。 运筹学的分支运筹学的分支 七、对策论七、对策论 研究具有对抗局势的模型，提供一套完整研究具有对抗局势的模型，提供一套完整 的、定量化和程序化的选择策略的理论和的、定量化和程序化的选择策略的理论和 方法。方法。 八、决策论八、决策论 是对整个决策过程中涉及方案目标的选取、是对整个决策过程中涉及方案目标的选取、 度量、概率值确定、效用值计算，一直到度量、概率值确定、效用值计算，一直到 最优方案和策略选取的有关科学理论。最优方案和策略选取的有关科学理论。 第第5 5节节 运筹学的应用运筹学的应用 市场销售市

16、场销售：在广告预算和媒体的选择：在广告预算和媒体的选择、竞争性定价竞争性定价、 新产品开发新产品开发、销售计划的制定等方面销售计划的制定等方面。 生产计划生产计划：生产作业的计划：生产作业的计划、日程表的编排日程表的编排、合理合理 下料下料、配料问题配料问题、物料管理等物料管理等。 库存管理库存管理：多种物资库存量的管理：多种物资库存量的管理，库存方式库存方式、库库 存量等存量等。 运输问题运输问题：确定最小成本的运输线路：确定最小成本的运输线路、物资的调拨物资的调拨、 运输工具的调度以及建厂地址的选择等运输工具的调度以及建厂地址的选择等。 财务和会计财务和会计：包括预测：包括预测、贷款贷款、

17、成本分析成本分析、定价定价、 证券管理证券管理、现金管理等现金管理等。 人事管理人事管理：对人员的需求和使用的预测：对人员的需求和使用的预测，确定人员确定人员 编制编制、人员合理分配人员合理分配，建立人才评价体系等建立人才评价体系等。 工程的优化设计工程的优化设计：设备维修：设备维修、更新更新，项目选择项目选择、评评 价价，工程优化设计与管理等工程优化设计与管理等。 计算机和信息系统计算机和信息系统：运筹学用于计算机的内存分配：运筹学用于计算机的内存分配， 利用图论利用图论、数学规划等方法研究计算机信息系统数学规划等方法研究计算机信息系统 的自动设计的自动设计。 城市管理城市管理：各种紧急服务

18、系统的设计和运用：各种紧急服务系统的设计和运用。 第第6节节 运筹学的展望运筹学的展望 美国前运筹学会主席邦特美国前运筹学会主席邦特(S.Bonder) ： 运筹学应用运筹学应用 运筹科学运筹科学 运筹数学运筹数学 近几年来出现一种新的批评近几年来出现一种新的批评 指出有些人只迷恋于数学模型的精巧、复杂指出有些人只迷恋于数学模型的精巧、复杂 化，使用高深的数学工具，而不善于处理面化，使用高深的数学工具，而不善于处理面 临大量新的不易解决的实际问题。现代运筹临大量新的不易解决的实际问题。现代运筹 学工作者面临的大量新问题是经济、技术、学工作者面临的大量新问题是经济、技术、 社会、生态和政治等因素

19、交叉在一起的复杂社会、生态和政治等因素交叉在一起的复杂 系统。系统。 非数学的方法和理论引入运筹学非数学的方法和理论引入运筹学 美国运筹学家沙旦美国运筹学家沙旦(T.L.Saaty)，他在，他在20世纪世纪 70年代末提出了层次分析法年代末提出了层次分析法(AHP)， 切克兰特切克兰特(P.B.Checkland)把传统的运筹学方把传统的运筹学方 法称为硬系统思考，它适用于解决那种结构法称为硬系统思考，它适用于解决那种结构 明确的系统以及战术和技术性问题，而对于明确的系统以及战术和技术性问题，而对于 结构不明确的，有人参与活动的系统就不太结构不明确的，有人参与活动的系统就不太 胜任了，这就应采

20、用软系统思考方法胜任了，这就应采用软系统思考方法 。 解的概念变化解的概念变化 相应的一些概念和方法都应有所变化，如将相应的一些概念和方法都应有所变化，如将 过分理想化的“最优解”换成“满意解”。过分理想化的“最优解”换成“满意解”。 过去把求得的“解”看作精确的、不能变的过去把求得的“解”看作精确的、不能变的 凝固的东西，而现在要以“易变性”的理念凝固的东西，而现在要以“易变性”的理念 看待所得的“解”以适应系统的不断变化看待所得的“解”以适应系统的不断变化 。 两个很重要的趋势两个很重要的趋势 一个趋势是软运筹学崛起一个趋势是软运筹学崛起 一个趋势是与优化有关的，即软计算。这种一个趋势是与

21、优化有关的，即软计算。这种 方法不追求严格最优，具有启发式思路。方法不追求严格最优，具有启发式思路。 第一章第一章 线性规划与单纯形法线性规划与单纯形法 第第1节节 线性规划问题及其数学模型线性规划问题及其数学模型 第第2节节 线性规划问题的几何意义线性规划问题的几何意义 第第3节节 单纯形法单纯形法 第第4节节 单纯形法的计算步骤单纯形法的计算步骤 第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论 第第6节节 应用举例应用举例 1 线性规划及其数学模型 1.1 问题的提出 1.2 图解法 1.3 线性规划问题的标准形式 1.4 线性规划问题的解的概念 1.1 问题的提出 在生产管理和经营

22、活动中，经常会碰到 一类问题，即如何合理的利用有限的人 力、物力、财力等资源以便得到最好的 经营效果。 例1：某工厂在计划期内要安排生产、两种 产品。已知生产单位产品所需的设备台时及A 、B 两种原材料的消耗，如下表所示。该工厂每生产 一件产品可获利2元,每生产一件产品可获利 3元,问应如何安排计划使该工厂获利最多？ 产品 产品 设 备 1 2 8台时 原材料A 4 0 16kg 原材料B 0 4 12kg 利润（元/件） 2 3 可用资源 解： 设变量x1为计划期内产品的产量； 变量x2为计划期内产品的产量。 x1 + 2x2 8；设备的有效台时数限制 4x1 16；原材料A的限量 4x 2

23、 12；原材料B的限量 另外，产品数不可能为负，即 x1, x2 0。 目标：获得最大利润，利润可以用函数 表示为： z = 2x1+3x2 目标函数 max z = 2x1 + 3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 把目标函数和约束条件放在一起，可以 建立如下的数学模型： 其中： “max” 含义为“最大化”； 因此，模型的含义是：在给定条件限制下， 求使目标函数 z 达到最大的x1, x2 的取值。 这是一个典型的利润最大化的生产计划问 题。 线性规划问题的共同特征 （模型的三要素） 每一个问题都用 一组决策变量 ( x 1 ， x 2 ， ，

24、x n ) 表示某一方案；这组决策变量的值就代表一个具体方案。 一般这些变量取值都是 非负 的。 存在一定的 约束条件 ，这些约束条件可以用 一组 线性等式或线性不等式 来表示。 都有一个要求达到的目标，它可用决策变量的 线 性 函数 （称为目标函数）来表示。按问题的不同，要求 目标函数 实现最大化或最小化。 线性规划数学模型的一般形式： max (min) z = c1x1 + c2x2 + + cnxn st. a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b2 . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ，

25、，xn 0 它们的对应关系可用表格表示： 对于模型中只含有两个变量的线性 规划问题，可以通过在平面上作图 的方法来求解。 1.2 图解法 图解法的目的 判别线性规划问题的求解结局； 存在最优解的情况下，求出问题 的最优解。 有关概念 可行解：满足约束条件的解。 可行域：全部可行解的集合。 最优解：可行域中使目标函数值达到最 优的可行解。 问题无解：不存在可行解的线性规划问 题。 图解法的步骤： 1. 在平面上建立直角坐标系； 2. 图示约束条件，找出可行域； 3. 图示目标函数和寻找最优解。 解 法: 1. 建立平面直角坐标系； 2.找出表示每个约束的半平面，所有半平面 的交集是可行域（全体可

26、行解的集合）； 3. 画出目标函数的等值线; 4. 向着目标函数的优化方向平移等值线， 直至得到等值线与可行域的最后交点， 这种点就对应最优解。 x1 x2 0 4 4x1=16 x1+2x2=8 4x2=12 3 Q1 Q3 Q4 Q2 2x1+3x2=0 Q2(4,2) 线性规划问题求解的几种可能结果 1. 唯一最优解； 2. 无穷多最优解； 3. 无界解； 4. 无可行解 。 (1)存在唯一最优解 x1 x2 0 4 4x1=16 x1+2x2=8 4x2=12 3 Q1 Q3 Q4 Q2 2x1+3x2=0 Q2(4,2) （2）有无穷多最优解 若目标函数变为 max z = 2x1+

27、 4x2 则存在无穷多最优解 max z = 2 x 1 + 4 x 2 s.t . x 1 + 2 x 2 8 4 x 1 16 4 x 2 12 x 1 ， x 2 0 x1 x2 0 4 4x1=16 4x2=12 3 Q1 Q3 Q4 Q2 2x1+4x2=0 Q2(4,2) x1+2x2=8 （3）无界解 （4）无可行解（可行域为空集） 注意： (3)缺乏必要的约束条件;(4)有矛盾的约束条 件 可行域有界时必有最优解，无界时不一定无 最优解 z 由图解法得到的启示 1. 求解线性规划问题时，解的情况有：唯一最 优解，无穷多最优解，无界解，无可行解。 2. 若线性规划问题的可行域存在

28、，则可行域是 一个有界或无界的凸多边形。 3. 若线性规划问题的最优解存在，则最优解一 定在可行域的某个顶点上得到；若在两个顶 点同时得到最优解，则它们连线上的任意一 点都是最优解，即无穷多最优解。 1.3 线性规划问题的标准型形式 用求和符号表示为: 用向量和矩阵符号表示为： 用矩阵符号表示为： x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 max z = 2x1+ 3x2 + 0 x3 + 0 x4+ 0 x5 标准型： 例3将例1的数学模型化为标准型。 max z = 2x1+ 3x2 所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有 利润，在目标函

29、数中其系数应为零；即c3 ，c4 ，c5 = 0。 x1+ 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 + x5 =12 x1，x2，x3，x4，x5 0 x1 + x2 + x3 7 x1 x2 + x3 2 3 x1+ x2 +2 x3 = 5 x1，x2 0，x3为无符号约 束 例4将下述线性规划问题化为标准型 min z = x1 +2x2 3x3 解：令z = -z，用x4 - x5 替换x3 x1 + x2 + (x4 - x5) + x6 = 7 x1 x2 + (x4 - x5) - x7 = 2 3x1 + x2 +2(x4 - x5) = 5 x1，x

30、2，x4，x5，x6，x7 0 max z= x1 2x2 + 3(x4 - x5)+0 x6+0 x7 用标准型求最优解后，再回到原变量。 1.4 线性规划问题的解的概念 可行解、可行域 最优解、最优值 基、基向量、基变量、非基变量 基解、基可行解 可行基、最优基 1. 可行解 满足约束条件(1-5)，(1-6)式的解X=(x1,x2， xn)T， 称为线性规划问题的可行解，线性规划全部可 行解的 集合称为可行域。其中使目标函数(1-4)达到最 大值的 可行解称为最优解，最优解对应的目标函数(1-4) 的值 称为最优值。 设A为约束方程组的 维系数矩阵，其 秩为m。B是矩阵A中 阶非奇异子矩

31、阵 （ ），则称B是线性规划问题的一个基。 2. 基，基向量，基变量 称Pj ( j = 1, 2, , m)为基向量。与基向量Pj对 应的变量xj ( j = 1, 2, , m)为基变量。线性规 划中除基变量以外的变量称为非基变量。 设 3. 基解，基可行解基解，基可行解 在约束方程组（1-5）中，令所有非基变量 xm+1= xm+2 = = xn = 0，又因为有 ，根 据克莱姆法则，由m个约束方程可解出m个基 变量的唯一解 ，将这 个解加上非基变量取的值有 称为线性规划问题的基解。满足变量非负 约束条件(1-6)的基解称为基可行解。 显然在基解中变量取非零值的个数不大于方程数 m，故基

32、解的总数不超过 个。 4 可行基 、最优基 对应于基可行解的基称为可行基。 对应于最优解的基称为最优基。 注意：线性规划的基解、基可行解和 可行基只与线性规划问题标准形式的 约束条件有关。 图1-6 它们之间的关系 max z = 2x1+ 3x2 st. x1+2x2 8 4x1 16 4x2 12 x1, x2 0 例：找出例1所建线性规划问题的全部基解， 指出其中的基可行解。 解：例1所建的线性规划模型为： 化为标准形式为： max z =2x1+3x2 + 0 x3 + 0 x4 + 0 x5 st. x1+2x2 + x3 = 8 4x1 + x4 = 16 4x2 +x5 = 12

33、 x1, x2 , x3 , x4 , x5 0 约束条件的系数矩阵为： A矩阵包含以下10个33的子矩阵： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 分析： 其中B4= 0，B= 0 ，因而B4 ，B 不是该线性规划问题的基。其余均为非 奇异方阵，因此该问题共有个基。 下面分别求出各个基所对应的基解。 于是对应的基B1不是可行基。 X = ( x1, x2

34、, x3, x4, x5 )T = (4，3，-2，0，0)T 对应的基解是： 得到x1 = 4，x2 = 3，x3 = -2 解线性方程组： x1 +2x2 + x3 = 8 4x1 +0 x2 + 0 x3 = 16 0 x1+ 4x2 +0 x3 = 12 首先令非基变量 x4 = x5 = 0。 以基B1=p1 ，p2 ，p3为例： 类似可得到其它基对应的基解： B1: X = (4, 3, -2, 0, 0)T B2: X = (2, 3, 0, 8, 0)T B3: X = (4, 2, 0, 0, 4)T B5: X = (4, 0, 4, 0, 12)T B6: X = (8,

35、 0, 0, -16, 12)T B7: X = (0, 3, 2, 16, 0)T B9: X = (0, 4, 0, 16, -4)T B10: X = (0, 0, 8, 16, 12)T 其中绿色所示为基可行解，对应的基 为可行基。 o 1 1 3 x 1 x 2 2 2 3 4 Q4 5 6 7 8 4 5 Q3 Q2 Q1 思考1：线性规划问题的基可行解与可行 域的顶点之间的关系？ 思考2：求线性规划问题的最优解的方法？ 基(最多 个）基可行解(可行域顶 点)最优解? 凸集凸集 设 n E K ，若任意两点 K X , K X 2 1 连线上的所有点，即 ) ( K X ) ( X

36、 X 1 0 1 2 1 - + = a a a 则称 K 为凸集。 上图中 (a) 、 (b) 是凸集， (c) 、 (d) 不是凸集，任何两 个凸集的交集是凸集，如图 (e) 。从直观上说，凸集没 有凹入部分，其内部没有空洞。 (a) (b) (c) (d) (e) 2 线性规划问题的几何意义 2.1 基本概念 凸组合 设 ，若存在 ，0 1 ，且 ，使 则称X 为 的凸组合。 两点连线上的任何一点都是这两点的凸组合 X1 X2 X 2 1 (a) (b) (c) (d) (e) 图中红粗线和红点是顶点。 2.2 基本定理 定理1: 若线性规划问题存在可行解，则所有可行解的集 合可行域 D

37、= X| AX= b ， X0 是凸集。 证明： 设X1D，X2 D，则A X1=b， AX2 =b， X1 0， X2 0 ,故AX=Aa X1+（1-a)X2 = a AX1+A(1-a)X2 = b X= a X1+（1-a)X2 0， ( 0 a 1 ) 所以X D， D为凸集。 引理1 线性规划问题的可行解X=（x1， x2， xn)T为基可行 解的充分必要条件是X的正分量所对应的系数列向量是线 性无关的。 证明： 必要性：由基可行解的定义可知， X为基可行解其正分量 的系数列向量线性无关。 充分性： 设可行解X=（x1， x2， xs，0，0)T的系数列向量 P1，Ps 线性无关，

38、则必有sm。当s = m 时， P1， Ps构成的行列式不为零， X 为基可行解；当s X是可行域的顶点 X 是基可行解，有 = = s j j j b x P 1 ( S m ) , P 1 ， ， P s 线性无关 设 X 不是顶点，则 有 X 1 ， X 2 为可行解， X 1 X 2 ， ( X ) ( X X 0 a 1) 0 1 2 1 - + = a a 由 0 1 2 1 = - + j j x ) ( ax a ( j s ) 得 0 2 1 = = j j x x ( j s ) 故 = = s j j j b x P 1 1 ， = = s j j j b x P 1 2

39、 二式相减得 = = - s j j j j ) x x ( P 1 2 1 0 由 X 1 X 2 知 $ j s 使 2 1 j j x x ，这 与 P 1 ， ， P s 线性无关矛盾 。 结论： 线性规划问题的可行域是凸集（凸多 面体），有有限多个顶点, 顶点对应基可 行解。当可行域有界时，必有顶点达到 目标函数最优值。 3 单纯形法 3.1 单纯形法的基本思想 3.2 单纯形法的迭代原理 对于一个标准线性规划问题，从一个初始 基可行解出发，判断其是否为最优解，若是则 结束；否则求一个与其“相邻”的、改进的基 可行解。再判断这个解是否最优，若是则结束， 否则再求一个“相邻”的、改进的

40、基可行 解直至得到一个基最优解。 如例1，O Q1 Q2 或 O Q4 Q3 Q2 x1 x2 0 4 4x1=16 x1+2x2=8 4x2=12 3 Q1 Q3 Q4 Q2 2x1+3x2=0 Q2(4,2) 3.1 单纯形法基本思想 例6：用单纯形法的基本思路解例1的 线性规划问题 max z = 2x1+ 3x2 st. x1+2x2 8 4x1 16 4x2 12 x1, x2 0 解：例1所建的线性规划模型为： 化为标准形式为： max z =2x1+3x2 + 0 x3 + 0 x4 + 0 x5 st. x1+2x2 + x3 = 8 4x1 + x4 = 16 4x2 +x5

41、 = 12 x1, x2 , x3 , x4 , x5 0 约束系数矩阵为： 由约束矩阵可以看出： x3 ，x4 ，x5的 系数列向量是线性独立的，这些向量 构成一个基。x3 ，x4 ，x5为基变量，x1 ， x2为非基变量。 将基变量用非基变量表示： x3 = 8 - x1 - 2 x2 x4 = 16 - 4x1 x5 = 12 - 4x2 代入目标函数得到： z = 2x1+ 3x2 + 0 当非基变量x1，x2 = 0时，可以知道： x3 =8，x4 =16，x5 = 12 z = 0， 得到初始基可行解： X(0) = (0, 0, 8, 16, 12)T，z (0) = 0 确定初

42、始基解及对应目标函数的值 分析： 目标函数 z = 2x1+ 3x2 + 0 中非基变量x1，x2 的系数都是正数。因此将非基变量变换成 基变量，目标函数的值就可能增大。 找出相邻的基可行解，提高目标函数的值。 确定一个非基变量为换入变量，将它换到 基变量中去，同时要从当前基变量中换出 来一个变量，使之成为非基变量。 第一次迭代： 确定换入变量 在目标函数 z = 2x1+ 3x2 中，x2 的系数 为 3，比 x1 的系数 2 大，因此猜想把 x2作为换入变量可以使目标函数 z 增加 更快。选择 x2 为换入变量，使 x2 的值 从0开始增加，另一个非基变量 x1 保持 零值不变。 确定换出

43、变量 由于x1=0，必须从基变量x3 、x4 、x5中找出 一个换出变量，并保证其余为非负，即 x3 = 8 - 2 x2 0 x4 = 16 0 x5 = 12 - 4x2 0 可以看出，只有选择 x2 = min（8/2，-，12/4）= 3 时，才能满足此要求。 因当x2 = 3时， x5 =0。因此，新的基变量 为x3、x4、x2，非基变量为x1、x5 。 确定基可行解及对应目标函数的值 将基变量用非基变量表示： x3 = 2 - x1 + 0.5x x4 = 16 - 4x1 x = 3 - 0.25x 代入目标函数得到： z = 9 + 2x1 - 0.75x5 当非基变量x1，x

44、5 = 0时，可以知道： x3 = 2，x4 =16，x2 = 3 z = 9， 得到基可行解： X(1) = (0, 3, 2, 16, 0)T，z (1) = 9 分析： 目标函数z = 9 + 2x1 - 0.75x5中非基变量 x1的系数是正数。说明目标函数的值还 有可能增大。 X(1) 不是最优解。 再找相邻的基可行解，提高目标函数的 值。 第二次迭代： 确定换入变量 考虑目标函数 z = 9 + 2x1 - 0.75x5 中的 非基变量，只有 x1 的系数 2 是正数， 因此把 x1 作为换入变量可以使目标函 数 z 增加。选择 x1 为换入变量，另一 个非基变量 x5 保持零值不变。 确定换出变量 从基变量x3 、x4 、x2中找出一个换出变量， 并保证其余为非负，由x5= 0知 x3 = 2 - x1 0