《运筹学》课件运筹一.ppt

1、目目 录录 绪绪 论论 第一章第一章 线性规划线性规划 第二章第二章 对偶理论与灵敏度分析对偶理论与灵敏度分析 第三章第三章 运输问题运输问题 第四章第四章 整数规划整数规划 第五章第五章 动态规划动态规划 第六章第六章 图与网路分析图与网路分析 第七章第七章 随机服务理论概述随机服务理论概述 第八章第八章 生灭服务系统生灭服务系统 第九第九章章 存储存储理论理论 第十章第十章 网络计划方法网络计划方法绪绪 论论 一、运筹学的起源与发展一、运筹学的起源与发展 二、运筹学的定义和主要研究分支二、运筹学的定义和主要研究分支 三、运筹学的特点及研究对象三、运筹学的特点及研究对象 四、运筹学解决问题的

2、方法步骤四、运筹学解决问题的方法步骤 五、五、运筹学与其他学科的关系运筹学与其他学科的关系一、运筹学的起源与发展一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科起源于二次大战的一门新兴交叉学科 与作战问题相关与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等的深度、飞行员的编组、军事物资的存储等 英国称为英国称为 Operational Research 美国称为美国称为 Operations Research 战后在经济、管理和机关学校及科研单战后在经济、管理和机关学校及科研单位继续研

3、究位继续研究 1952年，年，Morse 和和 Kimball出版出版运筹学方法运筹学方法 1948年英国首先成立运筹学会年英国首先成立运筹学会 1952年美国成立运筹学会年美国成立运筹学会 1959年成立国际运筹学联合会年成立国际运筹学联合会(IFORS)我国于我国于1982年加入年加入IFORS，并于，并于1999年年8月组织了第月组织了第15届大会届大会一、运筹学的起源与发展一、运筹学的起源与发展1、中国运筹学会简介、中国运筹学会简介50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。入国内。1980年年4月

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

5、、第六、七肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六、七届理事长陈光亚，第八、九届理事长汪寿阳，第十届届理事长陈光亚，第八、九届理事长汪寿阳，第十届杨晓光（现任）。（现任）。3、运筹学、系、运筹学、系 统工程统工程 主要研究人员构成主要研究人员构成1）数学：如华罗庚、越民义，徐光辉，）数学：如华罗庚、越民义，徐光辉，章祥荪章祥荪，袁亚湘袁亚湘，许国志，顾，许国志，顾基发，胡旭东，基发，胡旭东，戴彧虹等；等；2）控制论：张仲俊，刘豹，陈珽，郑维敏，）控制论：张仲俊，刘豹，陈珽，郑维敏，吴沧浦吴沧浦，赵纯均，陈剑等，赵纯均，陈剑等3）管理等专业相关教学、科研技术人员）管理等专业相关

6、教学、科研技术人员567一、运筹学的起源与发展一、运筹学的起源与发展4、相关研究机构和高校、相关研究机构和高校1）中国科学院数学与系统科学研究院系统科学研究所）中国科学院数学与系统科学研究院系统科学研究所2）中国科学院数学与系统科学研究院应用数学研究所）中国科学院数学与系统科学研究院应用数学研究所3）哈工大：胡运权，黄梯云，钱国明等）哈工大：胡运权，黄梯云，钱国明等4）天津大学：刘豹，顾培亮，张维，）天津大学：刘豹，顾培亮，张维，杜杜 纲纲等等5）西安交大：汪应洛，席酉民等）西安交大：汪应洛，席酉民等6）上海交大：张仲俊，王浣尘等）上海交大：张仲俊，王浣尘等7）清华大学：郑维敏，赵纯均，陈剑等

7、；）清华大学：郑维敏，赵纯均，陈剑等；8）大连理工：王众托，胡祥培等）大连理工：王众托，胡祥培等9）北航：顾昌耀，黄海军等）北航：顾昌耀，黄海军等10）北理工）北理工：吴沧浦吴沧浦，吴祈宗，张强等，吴祈宗，张强等9二、运筹学的定义和主要研究分支二、运筹学的定义和主要研究分支 运筹学的定义运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法为基础的科学方法Morse 和和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是

8、发展一个和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针及其产生的后果，以帮助主管人员科学地决定工作方针和政策和政策英国运筹学会英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理供有根据的最优方案，以实现最有效的管理中国百中国百科全书科全书 现代运筹学涵盖了一切

9、领域的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science10二、运筹学的定义和主要研究分支二、运筹学的定义和主要研究分支 运筹学的分支运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等划、目标规划等 图论与网路理论图论与网路理论 随机服务理论：排队论随机服务理论：排队论 存储理论存储理论 网络计划方法网络计划方法 决策理论决策理论 对策论对策论 系统仿真：随机模拟技术、系统动力学系统仿真：随机模拟技术、系统动力学 可靠性理论可靠性理论 金融工程金融工程11三、运筹学的

10、特点及研究对象三、运筹学的特点及研究对象运筹学的特点：运筹学的特点：1)优化优化以整体最优为目标，从系统的观点出发，力图以整个系以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法解决各类问题提供优化方法2定量定量为所研究的问题提供定量的解决方案。如采用运筹学研为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源究资源分配问题时，其求解结果是

11、一个定量的最优资源分配方案。分配方案。运筹学的研究对象：运筹学的研究对象：来自生产管理过程中的具体问题，如资源分配、物资调来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。度，生产计划与控制等。12四、运筹学解决问题的方法步骤四、运筹学解决问题的方法步骤 1、理清问题、明确目标、理清问题、明确目标 2、建立模型、建立模型 讨论：什么叫模型讨论：什么叫模型 3、求解模型。建立模型之后，、求解模型。建立模型之后，需要设计相应算法进需要设计相应算法进行求解，实际问题行求解，实际问题运算量一般都很大，通常需要用计运算量一般都很大，通常需要用计算机算机求解求解。4、结果分析、结果分析

12、 讨论：模型计算结果与已有的经验或知识进行比较讨论：模型计算结果与已有的经验或知识进行比较 1）模型计算结果和已有的经验或知识比较一致）模型计算结果和已有的经验或知识比较一致 2）模型计算结果和已有的经验或知识差异较大）模型计算结果和已有的经验或知识差异较大 你喜欢那一种情况？你喜欢那一种情况？13五、五、运筹学与其他学科的关系运筹学与其他学科的关系 运筹学运筹学目标分析、目标分析、建模建模、求解求解和结果分析需要用到和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较很多相关学科的知识，它与如下学科的知识关系比较密切。密切。1、数学：、数学：学习、应用运筹学应该具备较广的数学知识

13、，学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学认为运筹学是一门应用数学；2、管理学：运筹学研究对象是、管理学：运筹学研究对象是生产管理过程的具体问生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论的涉及管理科学的有关理论；3、计算机：、计算机：运筹学所研究的实际问题通常都是比较复运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助杂，而且规模比较大，在求解这些问题时，必

14、须借助计算机来完成计算机来完成。14第一章第一章 线性规划线性规划1.1 线性规划模型线性规划模型1.1.11.1.1问题的提出问题的提出一、一、例例1 1、多产品生产问题、多产品生产问题（Max,）甲电缆甲电缆乙电缆乙电缆资源量资源量铜（吨）铜（吨）2110铅（吨）铅（吨）118价格（万元）价格（万元）64需求需求无限制无限制7另 问该工厂应如何安排生产才能使工厂的总收入最大？问该工厂应如何安排生产才能使工厂的总收入最大？一、一、例例1 1、多产品生产问题、多产品生产问题（Max,）设设x1,x2 分别代表甲、乙两种电缆的生产量，分别代表甲、乙两种电缆的生产量，f(x)为工厂为工厂的总收入，

15、则上述问题可用如下数学模型来表示的总收入，则上述问题可用如下数学模型来表示其中，其中，OBJ（Objective）表示目标，）表示目标，S.t.（Subject to）表示满足）表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大入这一目标达到最大。最优解为。最优解为产量不允许为负值产量约束铅资源约束铜资源约束0,78102.46)(max:212212121xxxxxxxtsxxxfOBJ.36)(max,6,221xfxx二、例二、例2、配料问题（、配料问题（min,)某混合饲料加工厂计划从市场上购买甲、

16、乙两种原料生产一种某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对混合饲料。混合饲料对VA、VB1、VB2和和VD的最低含量有一定的最低含量有一定的要求。已知单位甲、乙两种原料的要求。已知单位甲、乙两种原料VA、VB1、VB2和和VD的含量，的含量，单位混合饲料对单位混合饲料对VA、VB1、VB2和和VD的最低含量以及甲、乙两的最低含量以及甲、乙两种原料的单位价格如种原料的单位价格如下下表所示。表所示。问该该加工厂应如何搭配使用甲乙两种原料，才能使混合问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足饲料在满足VA、VB1、VB2和和VD的最低含量要求条件下

17、，的最低含量要求条件下，总成本最小？总成本最小？二、例二、例2、配料问题（、配料问题（MIN,)设设 x1,x2分别代表混合单位饲料对甲、乙两种原料的用量，分别代表混合单位饲料对甲、乙两种原料的用量，f(x)表示单位混合饲料所需要的成本，则上述问题的线性规划数学表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：模型如下：该数学模型的最优解为该问题的最优解为该数学模型的最优解为该问题的最优解为x1=3.69，x2=0.77，minf(x)=1.490,22.05.02.16.02.033.00.125.05.0.5.03.0)(min212121212121xxxxxxxxxxts

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

19、）目标函数和约束方程都是线性的。目标函数和约束方程都是线性的。2、线性规划数学模型的定义线性规划数学模型的定义定义定义1.1 有一个目标函数和一组约束方程，且目标函数和约束有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。方程都是线性的数学模型称为线性规划数学模型。四、线性规划数学模型的背景模型和思考四、线性规划数学模型的背景模型和思考1、线性规划数学模型线性规划数学模型的背景模型的背景模型：例例1.1的多产品生产计划问题的数学模型称为线性规划的背景模的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下：用有限量的几

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

21、课程力求在力求在教学教学中体现的第中体现的第一个特点，一个特点，希望大家希望大家用心体会用心体会。1.1.2 1.1.2 线性规划数学模型的一般表示方式线性规划数学模型的一般表示方式技术系数右端项价值系数线性规划问题的规模约束行数变量个数:;:;:;:;:0,),(),(),(.)(max(min)21221122222121112121112211ijijnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf21 1、和式和式njxmibxatsxcxfjinjjijnjjj,2,1 ,0,2,1 ,.)(max1122 2、向量式向量式

22、0000 ),();,(.)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj23 3、矩阵式矩阵式 00,00),(),();,(.)(max212121212222111211矩阵表示，TTmTnnmnmmnnbbbxxxcccaaaaaaaaatsxf0bXCA0XbAXCX24 1.1.3 线性规划的图解法线性规划的图解法1187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12.36)(max,6,2:0,78102.46)(max21212212121xfxxxxxxxxxtsxx

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

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

25、1 1、规定一标准型线性的规划问题数学模型；规定一标准型线性的规划问题数学模型；2 2、如何把非标准形的线性规划问题数学模型转化为标准形如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？线性规划问题数学模型？3 3、如何求解标准形线性规划问题数学模型。如何求解标准形线性规划问题数学模型。njxmibxatsxcxfjinjjijnjjj,2,1 ),0(0,2,1 ,),(.)(max(min)11不限不限三、三、线性规划问题的标准形线性规划问题的标准形在上述线性规划标准形中，决策变量的个数取在上述线性规划标准形中，决策变量的个数取n+mn+m个是习惯表个是习惯表示法。我们

26、知道，对于线性规划背景模型，有示法。我们知道，对于线性规划背景模型，有m m个约束方程，个约束方程，且每个约束方程的不等式均为且每个约束方程的不等式均为“”号。如果我们在每个约束号。如果我们在每个约束方程的左边加上一个大于等于方程的左边加上一个大于等于0 0的变量，则可将各个约束方程的变量，则可将各个约束方程的的“”号转变为号转变为“=”。此时，决策变量就有。此时，决策变量就有n+mn+m个。个。njmixbmibxatsxcxfjiimnjjijmnjjj,2,1 ,2,1 ,0,2,1 ,.)(max1128 四、变换的方法变换的方法 1 1、目标函数为、目标函数为minmin型，价值系数

27、一律反号。令型，价值系数一律反号。令 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 个约束为个约束为 型，在不等式左边增加一个非负的型，在不等式左边增加一个非负的变量变量x xn+in+i ，称为松弛变量；同时令称为松弛变量；同时令 c cn+in+i =0=0 4 4、第、第i i

28、 个约束为个约束为 型，在不等式左边减去一个非负的型，在不等式左边减去一个非负的变量变量x xn+in+i ，称为剩余变量；同时令称为剩余变量；同时令 c cn+in+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 j -x xj j，x xj j 0 0，x xj j 0 0，代入非标准型代入非标准型29 五、五、变换举例：变换举例：0,20040065300432.423)(min:213321321321321xx

29、xxxxxxxxxxtsxxxxf不限原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型1.3.2 线性规划问题的解和线性规划问题的解和基础基础定理定理本章开始到现在已讨论的内容，相信大部分读者都会感到本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些问题解的一些基础基础概念和定理，与前面讨论的内容相比，概念和定理，与前面讨

30、论的内容相比，线性规划问题解的一些线性规划问题解的一些基础基础概念略显难一些，其中比较难概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为了帮的概念有线性规划问题的基和基础解等相关概念。为了帮助大家比较容易理解这些概念，我们先从大家熟悉的两个助大家比较容易理解这些概念，我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手，然后逐步过渡到变量两个线性方程组这一简单问题入手，然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念。我们所要讨论的线性规划问题的基和基础解等相关概念。著名数学家笛卡尔曾说过，他最擅长做的两件事是：著名数学家笛卡尔曾说过，他最擅长做的两件

31、事是：1)第一做简单事；第一做简单事；2)第二是将复杂事变为简单事。第二是将复杂事变为简单事。本本课程课程将从大家熟悉的一些简单问题入手，然后逐步过渡将从大家熟悉的一些简单问题入手，然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理。这是本到运筹学一些相对比较抽象和难的概念和原理。这是本课课程教学程教学力求的另一特点。力求的另一特点。一、线性方程组的解一、线性方程组的解考虑如下线性方程组的解：考虑如下线性方程组的解：(1)852532121xxxx(2)2121xx再考虑如下线性方程组的解：再考虑如下线性方程组的解：(3)85253321321xxxxxx(4)221333231xxxxxx

32、(5)021321xxx一、线性方程组的解一、线性方程组的解类似地，如果将方程组（类似地，如果将方程组（3 3）中的变量）中的变量x x2 2或或x x1 1当成常数，分别当成常数，分别移到其方程的右边后采用消元法进行求解，则也可得到如下移到其方程的右边后采用消元法进行求解，则也可得到如下两组两组通通解解及其特解及其特解：(6)223222321xxxxxx(8)21212123111312xxxxxx(7)023231xxx(9)02123132xxx一、线性方程组的解一、线性方程组的解仔细观察和思考方程组（仔细观察和思考方程组（3 3）的三组通解（）的三组通解（4 4）、（）、（6 6）和

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

34、阵或变量是非奇异矩阵或变量x x1 1和和x x2 2的的系数列向量是线性无关。显然，这三个条件是等价的。系数列向量是线性无关。显然，这三个条件是等价的。一、线性方程组的解一、线性方程组的解同样，由于方程组组（同样，由于方程组组（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-11211B2 0-11513B3才能得到方程组（才能得到方程组（3 3）的通解或特解（）的通解或特解（6 6）或（）或（7 7）与

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

36、3 3，都能得到，都能得到线性规划（线性规划（1010）的一组通解和特解（见式（）的一组通解和特解（见式（4 4）-（9 9）。）。5231 211xxB变量变量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）是线性规划（是线性规划（1010）的基础非可行解。）的基础非

37、可行解。1211 312xxB变量变量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）的基础可行解。）的基础可行解。1513 323xxB变量变量x x2 2和和x x3 3为基变量，变量为基变量，变量x x1 1为非基变量，令为非

38、基变量，令x x1 1=0=0，得得解（解（9 9）为线性规划（为线性规划（1010）的基础解）的基础解.该基础解中该基础解中x x2 2和和x x3 3均大于均大于0 0，满足，满足线性规划（线性规划（1010）的变量非负约束条件，因此，该基础解（）的变量非负约束条件，因此，该基础解（9 9）是线性规划（是线性规划（1010）的基础可行解。）的基础可行解。二、标准型线性规划解的若干基础概念标准型线性规划解的若干基础概念 标准型有标准型有 n+m 个变量，个变量，m 个约束行个约束行“基基”的概念的概念 在标准型中，技术系数矩阵有在标准型中，技术系数矩阵有 n+m 列，即列，即 A=(P1,P

39、2 ,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，故有故有 X=（XB，XN)最多有最多有 个基个基mnmC二、标准型线性规划解的若干基础概念二、标准型线性规划解的若干基础概念 可行解可行解与与非可行解非可行解 满足约束条件和非负条件的解满足约

40、束条件和非负条件的解 X 称为称为可行解可行解，不满足约束，不满足约束条件或非负条件的解条件或非负条件的解 X 称为称为非可行解非可行解 基础解基础解 对应某一基对应某一基B且令其且令其非基变量非基变量 XN=0，求得，求得基变量基变量 XB的值。的值。称称X=(XB,XN)T为为基础解。基础解。其中其中，XB=B 1 b，XN=0 XB 是是基础解基础解必须满足如下条件：必须满足如下条件：1）非非0分量的个数分量的个数 m；2、m个基变量所对应的系数矩阵为非奇异的；个基变量所对应的系数矩阵为非奇异的；3、满足、满足m个约束条件。个约束条件。二、标准型线性规划解的若干基础概念二、标准型线性规划

41、解的若干基础概念 基础可行解基础可行解与与基础非可行解基础非可行解基础解基础解 X XB B 的非零分量都的非零分量都 0 0 时，称为时，称为基础可行解基础可行解，否，否则为则为基础非可行解。基础非可行解。退化退化解解 基础可行解基础可行解的非零分量个数的非零分量个数 f(X(0)=0（五五）最优检验）最优检验将（将（5）式代入）式代入(1)的目标函数后可得的目标函数后可得 f(X)=30+x2-3x3 （6）从目标函数（从目标函数（6）可知，非基变量）可知，非基变量x2的系数是正数，的系数是正数，所以所以X(1)不是最优解。不是最优解。（六六）求另一个更好的）求另一个更好的基础基础可行解可

42、行解501、确定换入变量及其值、确定换入变量及其值从从目标函数（从从目标函数（6）可知，）可知，只有只有非基变量非基变量x2的系数的系数为正为正，所以，所以，可确定可确定x2为换入变量为换入变量。由于(7)0702121302121525324321xxxxxxxx所以，所以，当另一个非基变量当另一个非基变量x3仍仍然为然为0时，由时，由（7）式可得到换式可得到换入变量入变量x1的值为的值为 x2=Min5/0.5，3/0.5，7/1=62、确定换出变量、确定换出变量从（从（7）式可知，当）式可知，当x2=6时，时，x4=0，所以，所以x4为换出变量。由此得为换出变量。由此得到线性规划（到线性

43、规划（1）的一个新的基）的一个新的基B2和和一组新的基变量与非基变一组新的基变量与非基变量。量。B2=(P1,P2,P5),XB2=（x1，x2，x5)T，XN2=（x3，x4)T513、求另一个更好的、求另一个更好的基础基础可行解可行解将将（1)约束方程中对应于基约束方程中对应于基B2的非基变量的非基变量x3和和x4移到方程的右移到方程的右边后可得边后可得7810252421321xxxxxxxx(8)21262435432431xxxxxxxxx令非基变量令非基变量x3=x4=0，可得，可得另另一一基础基础可行解可行解 X(2)=(2，6，0，0，1)T此时，对应于此时，对应于X(2)的目

44、标函数的目标函数f(X(2)=6x1+4x2=36 f(X(1)=30（七七）最优检验）最优检验将（将（8）式代入）式代入(1)的目标函数后可得的目标函数后可得 f(X)=36-2x3-2x4 （9）从目标函数（从目标函数（9）可）可知知，非基变量，非基变量x3和和x4的系数都是的系数都是负负数，数，所以所以X(2)是最优解。即是最优解。即X*=X(2)=(2，6，0，0，1)T,f(X*)=36三、求初始基础可行解（背景模型，三、求初始基础可行解（背景模型，MAX,)52设线性规划问题为设线性规划问题为 ,2,1 ,0,2,1 ,.)(max11njxmibxatsxcxfjinjjijnj

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

46、对xj及及aij重新编号，则约束方程可化为重新编号，则约束方程可化为 ,2,1 1mixabxmnmjjijii其中，其中，bi和和aij表示经过若干次迭代后，当前的右端系数和技表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数术系数，以便区别于原始的右端系数bi和技术系数和技术系数aij。将。将上上式式代入代入（2）的）的目标函数后可得目标函数后可得mnmjjjjjmiijimimnmjjiimnmjjjmimnmjjijiixzczxaccbcxcxabcxf10111111)()()()(,.,10Iimkkibcz 1miijijacz机会成本机会成本54在一般情

47、况下，目标函数值在一般情况下，目标函数值OBJ计算公式和机会成本计算计算公式和机会成本计算公式可写成公式可写成四、最优检验四、最优检验 ,10IimkkibczOBJ ,10IimkkibczOBJ,1Iimkkjijacz Jj 0,1Iimkkjijjjjacczc其中，其中，I为基变量的下标集。为基变量的下标集。最优检验条件为最优检验条件为其中，其中，J表示非基变量的下标集。表示非基变量的下标集。对于对于基变量基变量的的检验数为检验数为0,1iiIjmkkijiiiiccacczc因为因为基变量的技术系数基变量的技术系数满足：满足：aij=1,当当i=j aij=0,当当i j五、五、求

48、另一个更好的求另一个更好的基础基础可行解可行解55若某一若某一基础基础可行解经过最优检验表明不是最优解，可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的则需要设法求得另一个更好的基础基础可行解。求另一可行解。求另一个更好的个更好的基础基础可行解的主要步骤如下：可行解的主要步骤如下：1、确定换入变量；、确定换入变量；2、确定换出变量；、确定换出变量；3、通过基变换或初等变换求得另一个更好的、通过基变换或初等变换求得另一个更好的基础基础可行解。可行解。我们已在前面例子中说明了这种初等变换方法的我们已在前面例子中说明了这种初等变换方法的基基础础思路。下一小节我们将用单纯形表进一步说明这思

49、路。下一小节我们将用单纯形表进一步说明这种初等变换方法。种初等变换方法。56 1.3.4 单纯形法表及单纯形法单纯形法表及单纯形法 IV III IIIx1x2xnxn+1xn+2xn+mCBXBbc1c2cncn+1cn+2cn+mc1=cn+1xn+1b1a11a12a1n100c2=cn+2xn+2b2a21a22a2n010 cm=cn+mxn+mbmam1am2 amn001OBJz1z2znzn+1zn+2zn+mc1-z1c2-z2 cn-zncn+1-zn+1cn+2-zn+2 cn+m-zn+m57 例例 试列出下面线性规划问题的初始单纯型表试列出下面线性规划问题的初始单纯型

50、表0,12023310032.244540)(max321321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb404524000 x4100231100 x512033201 OBJ=0 zj00000 cj-zj40452400单纯形法单纯形法步骤步骤581、求初始、求初始基础基础可行解可行解 将线性规划模型标准化，建立初始单纯将线性规划模型标准化，建立初始单纯形表，求初始形表，求初始基础基础可行解。可行解。2、最优检验：对任一基础可行解、最优检验：对任一基础可行解X，若其所有检验数，若其所有检验数 j=cj zj 0，j J 则则X为最优解，即为最优解，即X*=