运筹学0 北邮

1、Operational Research ( OR ) |主讲人：赵秀娟 |单位：北京邮电大学经济管理 学院信息系统中心 |电子邮箱： |电话|研究方向：优化决策、经济评 价方法、金融分析与决策 201 1 年年 12 月月 出出 版版 目目 录录 绪绪 论论 第一章第一章 线性规划线性规划 第二章第二章 对偶理论与灵敏度分析对偶理论与灵敏度分析 第三章第三章 运输问题运输问题 第四章第四章 整数规划整数规划 第五章第五章 动态规划动态规划 第六章第六章 图与网路分析图与网路分析 第七章第七章 随机服务理论概述随机服务理论概述 第八章第八章 生灭服务系统生灭服务系统

2、第九章第九章 一般服务系统一般服务系统 第十章第十章 存储理论存储理论 第十一章第十一章 网络计划方法网络计划方法 绪绪 论论 一、运筹学的起源与发展一、运筹学的起源与发展 二、运筹学的定义和主要研究分支二、运筹学的定义和主要研究分支 三、运筹学的特点及研究对象三、运筹学的特点及研究对象 四、运筹学解决问题的方法步骤四、运筹学解决问题的方法步骤 五、运筹学与其他学科的关系五、运筹学与其他学科的关系 夫运筹帷幄之中， 决胜千里之外。 |中国古代的运筹学思想 z田忌赛马 z丁渭修皇宫 z候叔献治水 一、运筹学的起源与发展一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科起源于二次大战的一门新

3、兴交叉学科 与作战问题相关与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹如雷达的设置、运输船队的护航、反潜作战中深水炸弹 的深度、飞行员的编组、军事物资的存储等的深度、飞行员的编组、军事物资的存储等 英国称为英国称为 Operational Research 美国称为美国称为 Operations Research 战后在经济、管理和机关学校及科研单战后在经济、管理和机关学校及科研单 位继续研究位继续研究 1952年，年，Morse 和和 Kimball出版出版运筹学方法运筹学方法 1948年英国首先成立运筹学会年英国首先成立运筹学会 1952年美国成立运筹学会年美国成立运筹

4、学会 1959年成立国际运筹学联合会年成立国际运筹学联合会(IFORS) 我国于我国于1982年加入年加入IFORS，并于，并于1999年年8月组织了第月组织了第15 届大会届大会 一、运筹学的起源与发展一、运筹学的起源与发展 1、中国运筹学会简介、中国运筹学会简介 50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引 入国内。入国内。1980年年4月，中国数学会运筹学分会成立。月，中国数学会运筹学分会成立。1991年，中国运筹年，中国运筹 学会成立。历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁学会成立。历届学会理

5、事长有，华罗庚、越民义，徐光辉，章祥荪，袁 亚湘（现任）亚湘（现任） 2、中国系统工程学会简介、中国系统工程学会简介 1、1979年由钱学森、宋健、关肇直、许国志等年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡名专家、学者共同倡 议并筹备。议并筹备。1980年年11月月18日在北京正式成立。日在北京正式成立。 第一届理事会理事长关第一届理事会理事长关 肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理 事长陈光亚、第七届理事长汪寿阳（现任）。事长陈光亚、第七届理事长汪寿阳（现任）。 3、运筹学、系、运筹学、系

6、统工程统工程 主要研究人员构成主要研究人员构成 1）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾 基发等；基发等； 2）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等 3）管理等专业相关教学、科研技术人员）管理等专业相关教学、科研技术人员 一、运筹学的起源与发展一、运筹学的起源与发展 4、相关研究机构和高校、相关研究机构和高校 1）中国科学院数学与系统科学研究院应用数学研究所）中国科学院数学与系统科学研究院应用数学研究所 2）中国科学院数学与系统科学研究院应用数学研

7、究所）中国科学院数学与系统科学研究院应用数学研究所 3）哈工大：胡运权，黄梯云，钱国明等）哈工大：胡运权，黄梯云，钱国明等 4）天津大学：刘豹，顾培亮，张维，杜）天津大学：刘豹，顾培亮，张维，杜 纲等纲等 5）西安交大：汪应洛，席酉民等）西安交大：汪应洛，席酉民等 6）上海交大：张仲俊，王浣尘等）上海交大：张仲俊，王浣尘等 7）清华大学：郑维敏，赵纯均，陈剑等；）清华大学：郑维敏，赵纯均，陈剑等； 8）大连理工：王众托，胡祥培等）大连理工：王众托，胡祥培等 9）北航：顾昌耀，黄海军等）北航：顾昌耀，黄海军等 10）北理工）北理工 ：吴沧浦，吴祈宗，张强等：吴沧浦，吴祈宗，张强等 12 二、运筹

8、学的定义和主要研究分支二、运筹学的定义和主要研究分支 运筹学的定义运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为决策机构对所控制的业务活动作决策时，提供以数量 为基础的科学方法为基础的科学方法Morse 和和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府运筹学是把科学方法应用在指导人员、工商企业、政府 和国防等方面解决发生的各种问题，其方法是发展一个和国防等方面解决发生的各种问题，其方法是发展一个 科学的系统模式，并运用这种模式预测，比较各种决策科学的系统模式，并运用这种模式预测，比较各种决策 及其产生的后果，以帮助主管人员科学地决定工作方针及其产生的后果

9、，以帮助主管人员科学地决定工作方针 和政策和政策英国运筹学会英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统运筹学是应用分析、试验、量化的方法对经济管理系统 中人力、物力、财力等资源进行统筹安排，为决策者提中人力、物力、财力等资源进行统筹安排，为决策者提 供有根据的最优方案，以实现最有效的管理供有根据的最优方案，以实现最有效的管理中国百中国百 科全书科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science 13 二、运筹学的定义和主要研究分支二、运筹学的定义和主要研究分支 运筹学的分支运筹学的分支

10、数学规划：线性规划、非线性规划、整数规划、动态规数学规划：线性规划、非线性规划、整数规划、动态规 划、目标规划等划、目标规划等 图论与网路理论图论与网路理论 随机服务理论：排队论随机服务理论：排队论 存储理论存储理论 网络计划方法网络计划方法 决策理论决策理论 对策论对策论 系统仿真：随机模拟技术、系统动力学系统仿真：随机模拟技术、系统动力学 可靠性理论可靠性理论 金融工程金融工程 例1： 某工厂在生产过程中需要使用 浓度为80%的硫酸100吨，而市面上 只有浓度为30%，45%，73%，85% ，92%的硫酸出售，每吨的价格分 别为400、700、1400、1900和2500 元。问：采用怎

11、样的购买方案，才 能使所需费用最小？ 王经理花费12000元购买了一台微型车，年 度维护费用取决于年初时汽车的役龄，如表示。 为避免使用旧车会带来较高的维护费用，王经理 可选择卖掉旧车而购买新车使用的策略，旧车的 售价如表示。为简化计算，假定任何时刻购买新 车都需花费12000元，王经理的目标是使净费用 最小。（净费用=购置费+维护费-卖旧车收入） 役龄(年) 0 1 2 3 4 5 年维护费2000 4000 5000 9000 12000 - 交易价格 - 7000 6000 2000 1000 0 费用单位：元 若你在俱乐部玩掷骰子的游戏，两枚骰子 同时掷，胜负取决于出现的点数之和。两枚

12、骰 子之和可能212。若点数为2，你就损失10元 ，若点数为7或11，你就赢W元；若出现其它点 数，你就损失1元。问：W为多大时，这个游戏 才能对你有吸引力？ 17 三、运筹学的特点及研究对象三、运筹学的特点及研究对象 运筹学的特点：运筹学的特点： 1)优化优化 以整体最优为目标，从系统的观点出发，力图以整个系以整体最优为目标，从系统的观点出发，力图以整个系 统最佳的方式来协调各部门之间的利害冲突，从而求出统最佳的方式来协调各部门之间的利害冲突，从而求出 问题的最优解。所以运筹学可看成是一门优化技术，为问题的最优解。所以运筹学可看成是一门优化技术，为 解决各类问题提供优化方法解决各类问题提供优

13、化方法 2定量定量 为所研究的问题提供定量的解决方案。如采用运筹学研为所研究的问题提供定量的解决方案。如采用运筹学研 究资源分配问题时，其求解结果是一个定量的最优资源究资源分配问题时，其求解结果是一个定量的最优资源 分配方案。分配方案。 运筹学的研究对象：运筹学的研究对象： 来自生产管理过程中的具体问题，如资源分配、物资调来自生产管理过程中的具体问题，如资源分配、物资调 度，生产计划与控制等。度，生产计划与控制等。 |特点： z系统的整体观念 z多学科的综合 z以及模型方法的应用。 |优点： 1 事前分析、减少失误 2 符号语言、便于交流 3 抽象反映实际、突出共性 2a x 用一块边长为2a

14、的正方形铁皮，四角剪 去相等小正方形后将四边折起做一个铁盒， 问：如何剪能使做成的盒子体积最大？ 底 模型的概念：按一定规则完成的对现 实的抽象。 模型的形式： （1）实物模型：以实体描述对象。 （2）图像模型：以图示描述对象。 （3）数学模型：以数学符号和表达式完 成的对现实的抽象。 模型的建立：实际问题抽象为数学表 达式的过程称为建模。 设 剪掉的小正方形的边长为x， 则该问题等同于 求max V=(2a-2x)2 x 在满足2x2a x0 V所做成的盒子的体积。 （1）按表达事物的数学特点：线性规 划、整数规划、非线性规划等； （2）按特定专题用途：运输模型、 分配模型、存储模型、投入产

15、出模型 、排队模型等； （3）按研究对象：能源模型、教育模 型、人口模型、投资模型、宏观经济 模型。 管理内容核心问题：正确决策 管理方法核心问题：科学性；艺术性 定性决策：方向性、战略性 定量决策：数量上、战术上 24 四、运筹学解决问题的方法步骤四、运筹学解决问题的方法步骤 1、理清问题、明确目标、理清问题、明确目标 2、建立模型、建立模型 讨论：什么叫模型讨论：什么叫模型 3、求解模型。建立模型之后，需要设计相应算法进、求解模型。建立模型之后，需要设计相应算法进 行求解，实际问题运算量一般都很大，通常需要用计行求解，实际问题运算量一般都很大，通常需要用计 算机求解。算机求解。 4、结果分

16、析、结果分析 讨论：模型计算结果与已有的经验或知识进行比较讨论：模型计算结果与已有的经验或知识进行比较 1）模型计算结果和已有的经验或知识比较一致）模型计算结果和已有的经验或知识比较一致 2）模型计算结果和已有的经验或知识差异较大）模型计算结果和已有的经验或知识差异较大 你喜欢那一种情况？你喜欢那一种情况？ 确定目标，明确约束 抓主要矛盾、舍次要矛盾 选择模型、设定变量 描述约束和目标、确定参数 选择求解方法、求解问题 灵敏度分析、评价 汇总、解释结果、报告 提出问题 建立模型 优化求解 评价分析 决策支持 26 五、运筹学与其他学科的关系五、运筹学与其他学科的关系 运筹学目标分析、建模、求解

17、和结果分析需要用到运筹学目标分析、建模、求解和结果分析需要用到 很多相关学科的知识，它与如下学科的知识关系比较很多相关学科的知识，它与如下学科的知识关系比较 密切。密切。 1、数学：学习、应用运筹学应该具备较广的数学知识，、数学：学习、应用运筹学应该具备较广的数学知识， 许多运筹学者来自数学专业就是这个原因，有人甚至许多运筹学者来自数学专业就是这个原因，有人甚至 认为运筹学是一门应用数学；认为运筹学是一门应用数学； 2、管理学：运筹学研究对象是生产管理过程的具体问、管理学：运筹学研究对象是生产管理过程的具体问 题，在利用运筹学理论和方法解决具体问题时，需要题，在利用运筹学理论和方法解决具体问题

18、时，需要 的涉及管理科学的有关理论；的涉及管理科学的有关理论； 3、计算机：运筹学所研究的实际问题通常都是比较复、计算机：运筹学所研究的实际问题通常都是比较复 杂，而且规模比较大，在求解这些问题时，必须借助杂，而且规模比较大，在求解这些问题时，必须借助 计算机来完成。计算机来完成。 认真听课，出勤，预习与复习； 及时完成作业：课堂作业； (3)考核办法： 平时成绩 分 期中考试 分 期末考试 分 28 第一章第一章 线性规划线性规划 1.1 线性规划模型线性规划模型 1.1.11.1.1问题的提出问题的提出 一、例一、例1 1、多产品生产问题、多产品生产问题（Max, ） 甲电缆甲电缆乙电缆乙

19、电缆资源量资源量 铜（吨）铜（吨）2110 铅（吨）铅（吨）118 价格（万元）价格（万元）64 需求需求无限制无限制7 另 问该工厂应如何安排生产才能使工厂的总收入最大？问该工厂应如何安排生产才能使工厂的总收入最大？ 一、例一、例1 1、多产品生产问题、多产品生产问题（Max, ） 设设x1, x2 分别代表甲、乙两种电缆的生产量，分别代表甲、乙两种电缆的生产量，f(x)为工厂为工厂 的总收入，则上述问题可用如下数学模型来表示的总收入，则上述问题可用如下数学模型来表示 其中，其中，OBJ（Objective）表示目标，）表示目标，S.t.（Subject to）表示满足）表示满足 于。表示在

20、满足铜、铅资源和需求等约束条件下，使工厂的总收于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收 入这一目标达到最大。最优解为入这一目标达到最大。最优解为 产量不允许为负值 产量约束 铅资源约束 铜资源约束 0, 7 8 102 . . 46)(max: 21 2 21 21 21 xx x xx xx ts xxxfOBJ .36)(max, 6, 2 21 xfxx 二、例二、例2、配料问题（、配料问题（min, ) ) 某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种 混合饲料。混合饲料对混合饲料。混合饲料对VA、VB1、

21、VB2和和VD的最低含量有一定的最低含量有一定 的要求。已知单位甲、乙两种原料的要求。已知单位甲、乙两种原料VA、VB1、VB2和和VD的含量，的含量， 单位混合饲料对单位混合饲料对VA、VB1、VB2和和VD的最低含量以及甲、乙两的最低含量以及甲、乙两 种原料的单位价格如下表所示。种原料的单位价格如下表所示。 问该该加工厂应如何搭配使用甲乙两种原料，才能使混合问该该加工厂应如何搭配使用甲乙两种原料，才能使混合 饲料在满足饲料在满足VA、VB1、VB2和和VD的最低含量要求条件下，的最低含量要求条件下， 总成本最小？总成本最小？ 二、例二、例2、配料问题（、配料问题（MIN, ) ) 设设 x

22、1, x2分别代表混合单位饲料对甲、乙两种原料的用量，分别代表混合单位饲料对甲、乙两种原料的用量，f(x) 表示单位混合饲料所需要的成本，则上述问题的线性规划数学表示单位混合饲料所需要的成本，则上述问题的线性规划数学 模型如下：模型如下： 该数学模型的最优解为该问题的最优解为该数学模型的最优解为该问题的最优解为 x1=3.69，x2=0.77，minf(x)=1.49 0, 22 . 05 . 0 2 . 16 . 02 . 0 33 . 00 . 1 25 . 05 . 0 . . 5 . 03 . 0)(min 21 21 21 21 21 21 xx xx xx xx xx ts xxx

23、f 三、线性规划数学模型的特征和定义三、线性规划数学模型的特征和定义 1、线性规划数学模型的特征：、线性规划数学模型的特征： 1）有一组决策变量（）有一组决策变量（x1，x2，xn）表示某一方案。这一组）表示某一方案。这一组 决策变量的具体值就代表一个具体方案；决策变量的具体值就代表一个具体方案； 2）有一个目标函数，该目标函数根据其的具体性质取最大值）有一个目标函数，该目标函数根据其的具体性质取最大值 或最小值。当目标为成本型时取最小，而当目标为效益型时取或最小值。当目标为成本型时取最小，而当目标为效益型时取 最大。最大。 3）有一组约束方程，包括决策变量的非负约束；）有一组约束方程，包括决

24、策变量的非负约束； 4）目标函数和约束方程都是线性的。）目标函数和约束方程都是线性的。 2、线性规划数学模型的定义、线性规划数学模型的定义 定义定义1.1 有一个目标函数和一组约束方程，且目标函数和约束有一个目标函数和一组约束方程，且目标函数和约束 方程都是线性的数学模型称为线性规划数学模型。方程都是线性的数学模型称为线性规划数学模型。 四、线性规划数学模型的背景模型和思考四、线性规划数学模型的背景模型和思考 1、线性规划数学模型的背景模型：、线性规划数学模型的背景模型： 例例1.1的多产品生产计划问题的数学模型称为线性规划的背景模的多产品生产计划问题的数学模型称为线性规划的背景模 型。把该背

25、景模型的条件一般化后可叙述如下：用有限量的几型。把该背景模型的条件一般化后可叙述如下：用有限量的几 种资源生产若干种产品，如何安排生产，才能使工厂的总收入种资源生产若干种产品，如何安排生产，才能使工厂的总收入 或利润达到最大。或利润达到最大。 2、背景模型的思考、背景模型的思考 1）讨论：什么叫背景模型）讨论：什么叫背景模型 能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题 模型。模型。 2）背景模型的思考）背景模型的思考 利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运 筹

26、学中的一些基础概念和原理是本课程力求在教学中体现的第筹学中的一些基础概念和原理是本课程力求在教学中体现的第 一个特点，希望大家用心体会。一个特点，希望大家用心体会。 1.1.2 1.1.2 线性规划数学模型的一般表示方式线性规划数学模型的一般表示方式 技术系数右端项价值系数 线性规划问题的规模 约束行数变量个数 : ;: ;: : ;: ;: 0, ),( ),( ),( . )(max(min) 21 2211 22222121 11212111 2211 ijij n mnmnmm nn nn nn abc mn mn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxc

27、xcxf 35 1、和式和式 njx mibxa ts xcxf j i n j jij n j jj , 2 , 1 , 0 , 2 , 1 , . )(max 1 1 36 2、向量式向量式 0 0 0 0 ),( );,( . )(max 2 1 0 2 1 2121 0 1 0 b b b b a a a P xxxXcccC 0X bxP ts CXxf mmj j j j T nn n j jj 37 3、矩阵式矩阵式 00 ,00 ),( ),( );,( . . )(max 21 21 21 21 22221 11211 矩阵表示， T T m T n n mnmm n n b

28、bb xxx ccc aaa aaa aaa ts xf 0 b X C A 0X bAX CX 38 1.1.3 线性规划的图解法线性规划的图解法 1 1 8 7 6 5 4 3 2 2x1876543 O 10 9 x2 A B C E D F G H 1 2 3 f(x)=0 f(x)=1 2 .36)(max , 6, 2: 0, 7 8 102 . 46)(max 21 21 2 21 21 21 xf xx xx x xx xx ts xxxf 最优解最优解 1 1 8 7 6 5 4 3 2 2x1876543 O 10 9 x2 A B C E D F G H 1 2 3 f(

29、x)=36 线性规划问题的几个特点：线性规划问题的几个特点： 1、线性规划的可行域为凸集；、线性规划的可行域为凸集； 讨论：什么叫凸集？讨论：什么叫凸集？ 集合中任意两点连线上的一切点仍然在该集合中，在平面上集合中任意两点连线上的一切点仍然在该集合中，在平面上 为凸多边形，在空间上为凸几何体；为凸多边形，在空间上为凸几何体； 讨论：最优解在那里取得？讨论：最优解在那里取得？ 2、线性规划的最优解一定可在其凸集的某一顶点上达到；、线性规划的最优解一定可在其凸集的某一顶点上达到； 讨论：什么情况有最优解？最优解的存在性条件？讨论：什么情况有最优解？最优解的存在性条件？ 3、线性规划若有可行域且其可

30、行域有界，则一定有最优解。、线性规划若有可行域且其可行域有界，则一定有最优解。 上述上述3个结论是线性规划的个结论是线性规划的3个基础定理，可以用严格的数学个基础定理，可以用严格的数学 方法进行证明。我们以简单、直观的图解法方式给出，相信方法进行证明。我们以简单、直观的图解法方式给出，相信 大家是可以接受的。大家是可以接受的。 1.3 线性规划求解的基础原理和单纯形法线性规划求解的基础原理和单纯形法 1.3.1 1.3.1 线性规划问题的标准形线性规划问题的标准形 一、线性规划模型一般形式一、线性规划模型一般形式 二、求解思路二、求解思路 1 1、规定一标准型线性的规划问题数学模型；、规定一标

31、准型线性的规划问题数学模型； 2 2、如何把非标准形的线性规划问题数学模型转化为标准形、如何把非标准形的线性规划问题数学模型转化为标准形 线性规划问题数学模型？线性规划问题数学模型？ 3 3、如何求解标准形线性规划问题数学模型。、如何求解标准形线性规划问题数学模型。 njx mibxa ts xcxf j i n j jij n j jj ,2 , 1 ),0(0 ,2 , 1 ,),( . )(max(min) 1 1 不不限限 三、线性规划问题的标准形三、线性规划问题的标准形 在上述线性规划标准形中，决策变量的个数取在上述线性规划标准形中，决策变量的个数取n+mn+m个是习惯表个是习惯表

32、示法。我们知道，对于线性规划背景模型，有示法。我们知道，对于线性规划背景模型，有m m个约束方程，个约束方程， 且每个约束方程的不等式均为且每个约束方程的不等式均为“ ”号。如果我们在每个约束号。如果我们在每个约束 方程的左边加上一个大于等于方程的左边加上一个大于等于0 0的变量，则可将各个约束方程的变量，则可将各个约束方程 的的“ ”号转变为号转变为“= =”。此时，决策变量就有。此时，决策变量就有n+mn+m个。个。 njmixb mibxa ts xcxf ji i mn j jij mn j jj , 2 , 1 , 2 , 1 , 0, , 2 , 1 , . )(max 1 1 4

33、2 四、变换的方法变换的方法 1 1、目标函数为、目标函数为minmin型，价值系数一律反号。令型，价值系数一律反号。令 g(g(x x) = ) = - -f f( (x x) = -) = -CXCX, , 有有 min min f f( (x x) = - max - ) = - max - f f( (x) = - x) = - max gmax g( (x)x) 2 2、第、第i i 个约束的个约束的b bi i 为负值，则该行左右两端系数同时为负值，则该行左右两端系数同时 反号，同时不等号也要反向反号，同时不等号也要反向 3 3、第、第i i 个约束为个约束为 型，在不等式左边增加

34、一个非负的型，在不等式左边增加一个非负的 变量变量x xn+i n+i ， ，称为松弛变量；同时令称为松弛变量；同时令 c cn+i n+i = 0 = 0 4 4、第、第i i 个约束为个约束为 型，在不等式左边减去一个非负的型，在不等式左边减去一个非负的 变量变量x xn+i n+i ， ，称为剩余变量；同时令称为剩余变量；同时令 c cn+i n+i = 0 = 0 5 5、若、若x xj j 0 0，令 ，令 x xj j= -= -x xj j ，代入非标准型，则有，代入非标准型，则有x xj j 0 0 6 6、若、若x xj j 不限，令 不限，令 x xj j= = x xj

35、j - - x xj j ， x xj j 0 0，x xj j 0 0， 代入非标准型代入非标准型 43 五、五、 变换举例：变换举例： 0, , 200 40065 300432 . . 423)(min: 213 321 321 321 321 xxx xxx xxx xxx ts xxxxf 不限 原非标准型 0, 200 400665 3004432 . 0004423)(max: 6543321 63321 53321 43321 6543321 xxxxxxx xxxxx xxxxx xxxxx ts xxxxxxxxf标准型标准型 1.3.2 线性规划问题的解和基础定理线性规划

36、问题的解和基础定理 本章开始到现在已讨论的内容，相信大部分读者都会感到本章开始到现在已讨论的内容，相信大部分读者都会感到 比较容易理解和掌握。这一节我们将要讨论关于线性规划比较容易理解和掌握。这一节我们将要讨论关于线性规划 问题解的一些基础概念和定理，与前面讨论的内容相比，问题解的一些基础概念和定理，与前面讨论的内容相比， 线性规划问题解的一些基础概念略显难一些，其中比较难线性规划问题解的一些基础概念略显难一些，其中比较难 的概念有线性规划问题的基和基础解等相关概念。为了帮的概念有线性规划问题的基和基础解等相关概念。为了帮 助大家比较容易理解这些概念，我们先从大家熟悉的两个助大家比较容易理解这

37、些概念，我们先从大家熟悉的两个 变量两个线性方程组这一简单问题入手，然后逐步过渡到变量两个线性方程组这一简单问题入手，然后逐步过渡到 我们所要讨论的线性规划问题的基和基础解等相关概念。我们所要讨论的线性规划问题的基和基础解等相关概念。 著名数学家笛卡尔曾说过，他最擅长做的两件事是：著名数学家笛卡尔曾说过，他最擅长做的两件事是： 1)第一做简单事；第一做简单事； 2)第二是将复杂事变为简单事。第二是将复杂事变为简单事。 本课程将从大家熟悉的一些简单问题入手，然后逐步过渡本课程将从大家熟悉的一些简单问题入手，然后逐步过渡 到运筹学一些相对比较抽象和难的概念和原理。这是本课到运筹学一些相对比较抽象和

38、难的概念和原理。这是本课 程教学力求的另一特点。程教学力求的另一特点。 一、线性方程组的解一、线性方程组的解 考虑如下线性方程组的解：考虑如下线性方程组的解： (1) 852 53 21 21 xx xx (2) 2 1 2 1 x x 再考虑如下线性方程组的解：再考虑如下线性方程组的解： (3) 852 53 321 321 xxx xxx (4)2 21 33 32 31 xx xx xx (5) 0 2 1 3 2 1 x x x 一、线性方程组的解一、线性方程组的解 类似地，如果将方程组（类似地，如果将方程组（3 3）中的变量）中的变量x x2 2或或x x1 1当成常数，分别当成常数

39、，分别 移到其方程的右边后采用消元法进行求解，则也可得到如下移到其方程的右边后采用消元法进行求解，则也可得到如下 两组通解及其特解：两组通解及其特解： (6) 2 23 22 23 21 xx xx xx (8) 2 1 2 1 2 1 2 3 11 13 12 xx xx xx (7) 0 2 3 2 3 1 x x x (9) 0 2 1 2 3 1 3 2 x x x 一、线性方程组的解一、线性方程组的解 仔细观察和思考方程组（仔细观察和思考方程组（3 3）的三组通解（）的三组通解（4 4）、（）、（6 6）和）和 （8 8）或三组特解（）或三组特解（5 5）、（）、（7 7）和（）和（

40、9 9）是如何得到的，以）是如何得到的，以 及能够得到这些通解或特解的条件是什么？根据求解线性及能够得到这些通解或特解的条件是什么？根据求解线性 方程组克莱姆条件可知，能够得到方程组（方程组克莱姆条件可知，能够得到方程组（3 3）的通解（）的通解（4 4） 或特解（或特解（5 5）的条件是方程组（）的条件是方程组（3 3）中的变量）中的变量x x1 1和和x x2 2的系数的系数 矩阵行列式不等于矩阵行列式不等于0 0，即，即 0-1 52 31 B 1 或变量或变量x x1 1和和x x2 2的系数矩阵的系数矩阵B B1 1是非奇异矩阵或变量是非奇异矩阵或变量x x1 1和和x x2 2的的

41、 系数列向量是线性无关。显然，这三个条件是等价的。系数列向量是线性无关。显然，这三个条件是等价的。 一、线性方程组的解一、线性方程组的解 同样，由于方程组组（同样，由于方程组组（3 3）中的变量）中的变量x x1 1和和x x3 3的系数矩阵行列式的系数矩阵行列式 |B|B2 2| |不等于不等于0 0与变量与变量x x2 2和和x x3 3的系数矩阵行列式的系数矩阵行列式|B|B3 3| |不等于不等于0 0，即，即 0-1 12 11 B2 0-1 15 13 B3 才能得到方程组（才能得到方程组（3 3）的通解或特解（）的通解或特解（6 6）或（）或（7 7）与通解或）与通解或 特解（特

42、解（8 8）或（）或（9 9）。）。 将上面讨论的方程组（将上面讨论的方程组（3 3）加上一目标函数和变量非负约）加上一目标函数和变量非负约 束条件后就变成一标准型线性规划。如：束条件后就变成一标准型线性规划。如： (10) 0,0,0 852 53 . 32)( 321 321 321 321 xxx xxx xxx ts xxxxMaxf 一、线性方程组的解一、线性方程组的解 对于上述标准型线性规划（对于上述标准型线性规划（1010）, ,称称 B B1 1 、B B2 2和和B B3 3为线性规划为线性规划 （1010）的基。因利用其中任何一个基）的基。因利用其中任何一个基B B1 1

43、或或B B2 2或或B B3 3，都能得到，都能得到 线性规划（线性规划（1010）的一组通解和特解（见式（）的一组通解和特解（见式（4 4）-（9 9）。）。 52 31 21 1 xx B 变量变量x x1 1和和x x2 2为基变量，变量为基变量，变量x x3 3为非基变量，令为非基变量，令x x3 3=0=0，得解（，得解（5 5） 为线性规划（为线性规划（1010）的基础解，但因该基础解中）的基础解，但因该基础解中x x1 1= -10= -10，不，不 满足线性规划（满足线性规划（1010）的变量非负约束条件，因此，该基础）的变量非负约束条件，因此，该基础 解（解（5 5）是线性规

44、划（）是线性规划（1010）的基础非可行解。）的基础非可行解。 12 11 31 2 xx B 变量变量x x1 1和和x x3 3为基变量，变量为基变量，变量x x2 2为非基变量，令为非基变量，令x x2 2=0=0，得解（，得解（7 7） 为线性规划（为线性规划（1010）的基础解。该基础解中）的基础解。该基础解中x x1 1和和x x3 3均大于均大于0 0，满，满 足线性规划（足线性规划（1010）的变量非负约束条件，因此，该基础解（）的变量非负约束条件，因此，该基础解（7 7） 是线性规划（是线性规划（1010）的基础可行解。）的基础可行解。 15 13 32 3 xx B 变量变

45、量x x2 2和和x x3 3为基变量，变量为基变量，变量x x1 1为非基变量，令为非基变量，令x x1 1=0=0，得解（，得解（9 9） 为线性规划（为线性规划（1010）的基础解）的基础解. .该基础解中该基础解中x x2 2和和x x3 3均大于均大于0 0，满足，满足 线性规划（线性规划（1010）的变量非负约束条件，因此，该基础解（）的变量非负约束条件，因此，该基础解（9 9） 是线性规划（是线性规划（1010）的基础可行解。）的基础可行解。 二、标准型线性规划解的若干基础概念标准型线性规划解的若干基础概念 标准型有标准型有 n+m 个变量，个变量， m 个约束行个约束行 “基基

46、”的概念的概念 在标准型中，技术系数矩阵有在标准型中，技术系数矩阵有 n+m 列，即列，即 A = ( P1, P2 , , Pn+m ) A中线性独立的中线性独立的 m 列，构成该标准型的一个列，构成该标准型的一个基基，即，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为称为基向量基向量 与与基向量基向量对应的变量称为对应的变量称为基变量基变量，记为，记为 XB = ( x1 , x2 , , xm )T，其余的变量称为，其余的变量称为非基变量非基变量， 记为记为 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有故

47、有 X = （XB ， ， XN ) 最多有最多有 个基个基 m nm C 二、标准型线性规划解的若干基础概念二、标准型线性规划解的若干基础概念 可行解可行解与与非可行解非可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X 称为称为可行解可行解，不满足约束，不满足约束 条件或非负条件的解条件或非负条件的解 X 称为称为非可行解非可行解 基础解基础解 对应某一基对应某一基B且令其且令其非基变量非基变量 XN = 0，求得，求得基变量基变量 XB的值。的值。 称称X = (XB , XN)T为为基础解。基础解。 其中其中，XB = B 1 b， XN = 0 XB 是是基础解基础解必

48、须满足如下条件：必须满足如下条件： 1）非）非0分量的个数分量的个数 m； 2、m个基变量所对应的系数矩阵为非奇异的；个基变量所对应的系数矩阵为非奇异的； 3、满足、满足m个约束条件。个约束条件。 二、标准型线性规划解的若干基础概念二、标准型线性规划解的若干基础概念 基础可行解基础可行解与与基础非可行解基础非可行解 基础解基础解 X XB B 的非零分量都 的非零分量都 0 0 时，称为时，称为基础可行解基础可行解，否，否 则为则为基础非可行解。基础非可行解。 退化退化解解 基础可行解的非零分量个数基础可行解的非零分量个数 f (X(0) )=0 （五）最优检验（五）最优检验 将（将（5）式代

49、入）式代入(1)的目标函数后可得的目标函数后可得 f (X)=30+x2-3x3 （6） 从目标函数（从目标函数（6）可知，非基变量）可知，非基变量x2的系数是正数，所以的系数是正数，所以X(1) 不是最优解。不是最优解。 （六）求另一个更好的基础可行解（六）求另一个更好的基础可行解 64 1、确定换入变量及其值、确定换入变量及其值 从从目标函数（从从目标函数（6）可知，只有非基变量）可知，只有非基变量x2的系数为正，所以，的系数为正，所以， 可确定可确定x2为换入变量。为换入变量。 由 于 (7) 07 0 2 1 2 1 3 0 2 1 2 1 5 25 324 321 xx xxx xx

50、x 所以，当另一个非基变量所以，当另一个非基变量x3仍仍 然为然为0时，由（时，由（7）式可得到换）式可得到换 入变量入变量x1的值为的值为 x2=Min5/0.5，3/0.5，7/1=6 2、确定换出变量、确定换出变量 从（从（7）式可知，当）式可知，当x2=6时，时，x4=0，所以，所以x4为换出变量。由此得为换出变量。由此得 到线性规划（到线性规划（1）的一个新的基）的一个新的基B2和一组新的基变量与非基变和一组新的基变量与非基变 量。量。 B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T 65 3、求另一个更好的基础可行解、求另一个更好的基础

51、可行解 将（将（1)约束方程中对应于基约束方程中对应于基B2的非基变量的非基变量x3和和x4移到方程的右移到方程的右 边后可得边后可得 7 8 102 52 421 321 xx xxx xxx (8) 21 26 2 435 432 431 xxx xxx xxx 令非基变量令非基变量x3=x4=0，可得另一基础可行解，可得另一基础可行解 X(2) = (2，6，0，0，1)T 此时，对应于此时，对应于X(2)的目标函数的目标函数f (X(2) )=6x1+4x2=36 f (X(1) )=30 （七）最优检验（七）最优检验 将（将（8）式代入）式代入(1)的目标函数后可得的目标函数后可得

52、f (X)=36-2x3-2x4 （9） 从目标函数（从目标函数（9）可知，非基变量）可知，非基变量x3和和x4的系数都是负数，所以的系数都是负数，所以 X(2)是最优解。即是最优解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36 三、求初始基础可行解（背景模型，三、求初始基础可行解（背景模型，MAX, ) 66 设线性规划问题为设线性规划问题为 , 2 , 1 , 0 , 2 , 1 , . . )(max 1 1 njx mibxa ts xcxf j i n j jij n j jj ,2, 1 ,0 ,2, 1 , )(max 1 1 mnjx mibxax x

53、cxf j i mn mj jiji mn j jj 另设另设bi 0 (i=1,2,m)。标。标 准化后，若对准化后，若对xj和和aij重新编重新编 号，则约束方程可化为号，则约束方程可化为 变量变量x1，x2，xm作为初始基变量，其余变量作为初始非作为初始基变量，其余变量作为初始非 基变量，并令基变量，并令xm+1=xm+1=xn+m=0，则得初始本可行解，则得初始本可行解 ),0,0,.,0b., ,b ,(b T m21 (0) X 四、最优检验四、最优检验 67 对于标准化线性规划问题对于标准化线性规划问题(2)，经过若干次迭代后，如果对，经过若干次迭代后，如果对xj及及 aij重新

54、编号，则约束方程可化为重新编号，则约束方程可化为 , 2 , 1 1 mixabx mn mj j iji i 其中，其中，bi和和aij表示经过若干次迭代后，当前的右端系数和技表示经过若干次迭代后，当前的右端系数和技 术系数，以便区别于原始的右端系数术系数，以便区别于原始的右端系数bi和技术系数和技术系数aij。将上式。将上式 代入（代入（2）的目标函数后可得）的目标函数后可得 mn mj jjj j m i ij i m i mn mj j i i mn mj jj m i mn mj j iji i xzcz xaccbc xcxabcxf 1 0 1 11 111 )( )( ) ()

55、( 1 0 m i iib cz 1 m i ijij acz 机会成本机会成本 68 在一般情况下，目标函数值在一般情况下，目标函数值OBJ计算公式和机会成本计算计算公式和机会成本计算 公式可写成公式可写成 四、最优检验四、最优检验 , 1 0 Ii mk kib czOBJ , 1 0 Ii mk kib czOBJ , 1 Ii mk kjij acz Jj 0 , 1 Ii mk kjijjjj acczc 其中，其中，I为基变量的下标集。最优检验条件为为基变量的下标集。最优检验条件为 其中，其中，J表示非基变量的下标集。对于基变量的检验数为表示非基变量的下标集。对于基变量的检验数为

56、0 , 1 ii Ij mk kijiiii ccacczc 因为基变量的技术系数因为基变量的技术系数 满足：满足： aij=1, 当当i=j aij=0, 当当i j 五、五、 求另一个更好的基础可行解求另一个更好的基础可行解 69 若某一基础可行解经过最优检验表明不是最优解，若某一基础可行解经过最优检验表明不是最优解， 则需要设法求得另一个更好的基础可行解。求另一则需要设法求得另一个更好的基础可行解。求另一 个更好的基础可行解的主要步骤如下：个更好的基础可行解的主要步骤如下： 1、确定换入变量；、确定换入变量； 2、确定换出变量；、确定换出变量； 3、通过基变换或初等变换求得另一个更好的基

57、础、通过基变换或初等变换求得另一个更好的基础 可行解。可行解。 我们已在前面例子中说明了这种初等变换方法的基我们已在前面例子中说明了这种初等变换方法的基 础思路。下一小节我们将用单纯形表进一步说明这础思路。下一小节我们将用单纯形表进一步说明这 种初等变换方法。种初等变换方法。 70 1.3.4 单纯形法表及单纯形法单纯形法表及单纯形法 IV III III x1x2 xnxn+1xn+2xn+m C B X B bc1c2 cncn+1cn+2cn+m c1 = cn+1xn+1b1a11a12 a1n100 c2 = cn+2xn+2b2a21a22 a2n010 cm = cn+mxn+m

58、bmam1am2 amn001 OBJ z1z2 znzn+1zn+2zn+m c1-z1c2-z2 cn-zncn+1-zn+1cn+2-zn+2 cn+m-zn+m 71 例例 试列出下面线性规划问题的初始单纯型表试列出下面线性规划问题的初始单纯型表 0, 120233 10032 . 244540)(max 321 321 321 321 xxx xxx xxx ts xxxxf x1x2x3x4x5 CBXBb 40452400 0 x4 10023110 0 x5 12033201 OBJ = 0 zj00000 cj- -zj40452400 单纯形法步骤单纯形法步骤 72 1、求

59、初始基础可行解、求初始基础可行解 将线性规划模型标准化，建立初始单纯将线性规划模型标准化，建立初始单纯 形表，求初始基础可行解。形表，求初始基础可行解。 2、最优检验：对任一基础可行解、最优检验：对任一基础可行解X，若其所有检验数，若其所有检验数 j =cj zj 0，j J 则则X为最优解，即为最优解，即X*=X，计算最优解所对应的最优目标函数值，计算最优解所对应的最优目标函数值 f(X*)，算法停止。否则转，算法停止。否则转3。 3、求另一个更好的基础可行解、求另一个更好的基础可行解 1）确定入变量）确定入变量xk 若若 0 j Jj k Max则则xk为换入变量；为换入变量； 2）确定换

60、出变量）确定换出变量xl* 计算计算 ,1 0| lk l ik ik i mi l a b a a b Min 若若 l为空集，则为无界解，算法停止。否则与右端系数为空集，则为无界解，算法停止。否则与右端系数bl 同一行的同一行的 基变量基变量xl*为换出变量。转为换出变量。转3） 3）初等变换，得到另一个更好的基础可行解）初等变换，得到另一个更好的基础可行解 将入变量将入变量xk所在列所在列k，出变量，出变量xl*所在行所在行l的主元技术系数的主元技术系数al k变换为变换为1， 主元主元al k 所在列的其余元变换为所在列的其余元变换为0。更换基变量（用入变量。更换基变量（用入变量xk替