运筹学课件(全)全书教学教程完整版电子教案最全幻灯片

1、运筹学Operational Research目 录绪 论第一章 线性规划第二章 对偶理论与灵敏度分析第三章 运输问题第四章 整数规划第五章 动态规划第六章 图与网路分析第七章 随机服务理论概述第八章 生灭服务系统第九章 存储理论第十章 网络计划方法绪 论一、运筹学的起源与发展二、运筹学的定义和主要研究分支三、运筹学的特点及研究对象四、运筹学解决问题的方法步骤五、运筹学与其他学科的关系一、运筹学的起源与发展起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为 Operational Research美国称为

2、 Operations Research战后在经济、管理和机关学校及科研单位继续研究1952年，Morse 和 Kimball出版运筹学方法1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会一、运筹学的起源与发展1、中国运筹学会简介50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。1980年4月，中国数学会运筹学分会成立。1991年，中国运筹学会成立。历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁亚湘，胡旭东，戴彧虹（现任）2、中国系统工程学会简介

3、1、1979年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡议并筹备。1980年11月18日在北京正式成立。 第一届理事会理事长关肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六、七届理事长陈光亚，第八、九届理事长汪寿阳，第十届杨晓光（现任）。3、运筹学、系 统工程 主要研究人员构成1）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾基发，胡旭东，戴彧虹等；2）控制论：张仲俊，刘豹，陈珽，郑维敏，吴沧浦，赵纯均，陈剑等3）管理等专业相关教学、科研技术人员一、运筹学的起源与发展4、相关研究机构和高校1）中国科学院数学与系统科学研究院系统科学研究所2）中国科学院数学与系

4、统科学研究院应用数学研究所3）哈工大：胡运权，黄梯云，钱国明等4）天津大学：刘豹，顾培亮，张维，杜 纲等5）西安交大：汪应洛，席酉民等6）上海交大：张仲俊，王浣尘等7）清华大学：郑维敏，赵纯均，陈剑等；8）大连理工：王众托，胡祥培等9）北航：顾昌耀，黄海军等10）北理工 ：吴沧浦，吴祈宗，张强等7二、运筹学的定义和主要研究分支运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse 和 Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助

5、主管人员科学地决定工作方针和政策英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science8二、运筹学的定义和主要研究分支运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论网络计划方法决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程9三、运筹学的特点及研究对象运筹学的特点：1)优化以整体最优为目标，从系统的观点出发，力图以整个系统

6、最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法2定量为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。运筹学的研究对象：来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。10四、运筹学解决问题的方法步骤1、理清问题、明确目标2、建立模型讨论：什么叫模型 3、求解模型。建立模型之后，需要设计相应算法进行求解，实际问题运算量一般都很大，通常需要用计算机求解。 4、结果分析讨论：模型计算结果与已有的经验或知识进行比较 1）模型计算结果和已有的经验或知识比

7、较一致 2）模型计算结果和已有的经验或知识差异较大 你喜欢那一种情况？11五、运筹学与其他学科的关系 运筹学目标分析、建模、求解和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切。1、数学：学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学；2、管理学：运筹学研究对象是生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论；3、计算机：运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成。12第一章 线性规划1.1 线性规划模型1.1.1问

8、题的提出一、例1、多产品生产问题（Max, ）甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64需求无限制7另 问该工厂应如何安排生产才能使工厂的总收入最大？一、例1、多产品生产问题（Max, ）设x1, x2 分别代表甲、乙两种电缆的生产量，f(x)为工厂的总收入，则上述问题可用如下数学模型来表示其中，OBJ（Objective）表示目标，S.t.（Subject to）表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大。最优解为二、例2、配料问题（min, )某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对VA、VB1

9、、VB2和VD的最低含量有一定的要求。已知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价格如下表所示。问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足VA、VB1、VB2和VD的最低含量要求条件下，总成本最小？二、例2、配料问题（MIN, )设 x1, x2分别代表混合单位饲料对甲、乙两种原料的用量，f(x)表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：该数学模型的最优解为该问题的最优解为x1=3.69，x2=0.77，minf(x)=1.49三、线性规划数学模型的特征和定义1、线性

10、规划数学模型的特征：1）有一组决策变量（x1，x2，xn）表示某一方案。这一组决策变量的具体值就代表一个具体方案；2）有一个目标函数，该目标函数根据其的具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。3）有一组约束方程，包括决策变量的非负约束；4）目标函数和约束方程都是线性的。2、线性规划数学模型的定义定义1.1 有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。四、线性规划数学模型的背景模型和思考1、线性规划数学模型的背景模型：例1.1的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下

11、：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。2、背景模型的思考1）讨论：什么叫背景模型能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。2）背景模型的思考利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些基础概念和原理是本课程力求在教学中体现的第一个特点，希望大家用心体会。 1.1.2 线性规划数学模型的一般表示方式19 1、和式20 2、向量式21 3、矩阵式22 1.1.3 线性规划的图解法f(x)=36线性规划问题的几个特点：1、线性规划的可行域为凸集；讨论：什么叫凸集？集合中任意两点连线上的一切点仍然在该集合中，在平面上

12、为凸多边形，在空间上为凸几何体；讨论：最优解在那里取得？2、线性规划的最优解一定可在其凸集的某一顶点上达到；讨论：什么情况有最优解？最优解的存在性条件？3、线性规划若有可行域且其可行域有界，则一定有最优解。上述3个结论是线性规划的3个基础定理，可以用严格的数学方法进行证明。我们以简单、直观的图解法方式给出，相信大家是可以接受的。1.3 线性规划求解的基础原理和单纯形法1.3.1 线性规划问题的标准形一、线性规划模型一般形式二、求解思路1、规定一标准型线性的规划问题数学模型；2、如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？3、如何求解标准形线性规划问题数学模型。三、线性

13、规划问题的标准形在上述线性规划标准形中，决策变量的个数取n+m个是习惯表示法。我们知道，对于线性规划背景模型，有m个约束方程，且每个约束方程的不等式均为“”号。如果我们在每个约束方程的左边加上一个大于等于0的变量，则可将各个约束方程的“”号转变为“=”。此时，决策变量就有n+m个。26 四、变换的方法1、目标函数为min型，价值系数一律反号。令 g(x) = -f(x) = -CX, 有 min f(x) = - max - f(x) = - max g(x)2、第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向3、第i 个约束为 型，在不等式左边增加一个非负的变量xn

14、+i ，称为松弛变量；同时令 cn+i = 04、第i 个约束为 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 05、若xj 0，令 xj= -xj ，代入非标准型，则有xj 06、若xj 不限，令 xj= xj - xj， xj 0，xj 0，代入非标准型27 五、 变换举例：1.3.2 线性规划问题的解和基础定理本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些基础概念和定理，与前面讨论的内容相比，线性规划问题解的一些基础概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为

15、了帮助大家比较容易理解这些概念，我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手，然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念。著名数学家笛卡尔曾说过，他最擅长做的两件事是：1)第一做简单事；2)第二是将复杂事变为简单事。本课程将从大家熟悉的一些简单问题入手，然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理。这是本课程教学力求的另一特点。一、线性方程组的解考虑如下线性方程组的解：再考虑如下线性方程组的解：一、线性方程组的解类似地，如果将方程组（3）中的变量x2或x1当成常数，分别移到其方程的右边后采用消元法进行求解，则也可得到如下两组通解及其特解：一、线性方程组的

16、解仔细观察和思考方程组（3）的三组通解（4）、（6）和（8）或三组特解（5）、（7）和（9）是如何得到的，以及能够得到这些通解或特解的条件是什么？根据求解线性方程组克莱姆条件可知，能够得到方程组（3）的通解（4）或特解（5）的条件是方程组（3）中的变量x1和x2的系数矩阵行列式不等于0，即或变量x1和x2的系数矩阵B1是非奇异矩阵或变量x1和x2的系数列向量是线性无关。显然，这三个条件是等价的。一、线性方程组的解同样，由于方程组组（3）中的变量x1和x3的系数矩阵行列式|B2|不等于0与变量x2和x3的系数矩阵行列式|B3|不等于0，即才能得到方程组（3）的通解或特解（6）或（7）与通解或特解

17、（8）或（9）。将上面讨论的方程组（3）加上一目标函数和变量非负约束条件后就变成一标准型线性规划。如：一、线性方程组的解对于上述标准型线性规划（10）,称 B1 、B2和B3为线性规划（10）的基。因利用其中任何一个基B1 或B2或B3，都能得到线性规划（10）的一组通解和特解（见式（4）-（9）。变量x1和x2为基变量，变量x3为非基变量，令x3=0，得解（5）为线性规划（10）的基础解，但因该基础解中x1= -10，不满足线性规划（10）的变量非负约束条件，因此，该基础解（5）是线性规划（10）的基础非可行解。变量x1和x3为基变量，变量x2为非基变量，令x2=0，得解（7）为线性规划（1

18、0）的基础解。该基础解中x1和x3均大于0，满足线性规划（10）的变量非负约束条件，因此，该基础解（7）是线性规划（10）的基础可行解。变量x2和x3为基变量，变量x1为非基变量，令x1=0，得解（9）为线性规划（10）的基础解.该基础解中x2和x3均大于0，满足线性规划（10）的变量非负约束条件，因此，该基础解（9）是线性规划（10）的基础可行解。二、标准型线性规划解的若干基础概念标准型有 n+m 个变量， m 个约束行“基”的概念在标准型中，技术系数矩阵有 n+m 列，即 A = ( P1, P2 , , Pn+m )A中线性独立的 m 列，构成该标准型的一个基，即 B = ( P1 ,

19、P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为基向量与基向量对应的变量称为基变量，记为 XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = （XB ， XN ) 最多有 个基二、标准型线性规划解的若干基础概念可行解与非可行解满足约束条件和非负条件的解 X 称为可行解，不满足约束条件或非负条件的解 X 称为非可行解基础解对应某一基B且令其非基变量 XN = 0，求得基变量 XB的值。称X = (XB , XN)T为基础解。 其中，XB = B1 b， XN

20、= 0XB 是基础解必须满足如下条件： 1）非0分量的个数 m； 2、m个基变量所对应的系数矩阵为非奇异的； 3、满足m个约束条件。二、标准型线性规划解的若干基础概念 基础可行解与基础非可行解基础解 XB 的非零分量都 0 时，称为基础可行解，否则为基础非可行解。退化解 基础可行解的非零分量个数 f (X(0) )=0（五）最优检验将（5）式代入(1)的目标函数后可得 f (X)=30+x2-3x3 （6）从目标函数（6）可知，非基变量x2的系数是正数，所以X(1)不是最优解。（六）求另一个更好的基础可行解481、确定换入变量及其值从从目标函数（6）可知，只有非基变量x2的系数为正，所以，可确

21、定x2为换入变量。由于所以，当另一个非基变量x3仍然为0时，由（7）式可得到换入变量x1的值为 x2=Min5/0.5，3/0.5，7/1=62、确定换出变量从（7）式可知，当x2=6时，x4=0，所以x4为换出变量。由此得到线性规划（1）的一个新的基B2和一组新的基变量与非基变量。B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T493、求另一个更好的基础可行解将（1)约束方程中对应于基B2的非基变量x3和x4移到方程的右边后可得令非基变量x3=x4=0，可得另一基础可行解 X(2) = (2，6，0，0，1)T此时，对应于X(2)的目标函数f (X

22、(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, )50设线性规划问题为另设bi0 (i=1,2,m)。标准化后，若对xj和aij重新编号，则约束方程可化为变量x1，x2，xm作为初始基变量，其余变量作为初始非基变量，并令xm+1=xm+1=xn+m=0，则得初始本可行解四、最优检验51对于标准化线性规划问题

23、(2)，经过若干次迭代后，如果对xj及aij重新编号，则约束方程可化为其中，bi和aij表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数bi和技术系数aij。将上式代入（2）的目标函数后可得机会成本52在一般情况下，目标函数值OBJ计算公式和机会成本计算公式可写成四、最优检验其中，I为基变量的下标集。最优检验条件为其中，J表示非基变量的下标集。对于基变量的检验数为因为基变量的技术系数满足： aij=1, 当i=j aij=0, 当ij五、 求另一个更好的基础可行解53若某一基础可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的基础可行解。求另一个更好的基础可行

24、解的主要步骤如下：1、确定换入变量；2、确定换出变量；3、通过基变换或初等变换求得另一个更好的基础可行解。我们已在前面例子中说明了这种初等变换方法的基础思路。下一小节我们将用单纯形表进一步说明这种初等变换方法。54 1.3.4 单纯形法表及单纯形法55 例 试列出下面线性规划问题的初始单纯型表单纯形法步骤561、求初始基础可行解 将线性规划模型标准化，建立初始单纯形表，求初始基础可行解。2、最优检验：对任一基础可行解X，若其所有检验数 j =cj zj0，jJ 则X为最优解，即X*=X，计算最优解所对应的最优目标函数值f(X*)，算法停止。否则转3。3、求另一个更好的基础可行解1）确定入变量x

25、k 若则xk为换入变量；2）确定换出变量xl* 计算若l为空集，则为无界解，算法停止。否则与右端系数bl 同一行的基变量xl*为换出变量。转3）3）初等变换，得到另一个更好的基础可行解将入变量xk所在列k，出变量xl*所在行l的主元技术系数al k变换为1，主元al k 所在列的其余元变换为0。更换基变量（用入变量xk替换出变量xl*）及其价值系数，得到另一个更好的基础可行解。转2。57 表1.2.4 例1.2.2 单纯型表的迭代过程答：最优解为 x1=20, x2=20, x3=0, OBJ=170058 单纯型表中元素的几点说明任何时候，各基变量对应的列都构成一个单位矩阵当前表中的 b 列

26、表示当前基变量的解值，通过变换 B 1 b 得到 (资源已变成产品)当前非基变量对应的向量可通过变换 B 1 AN 得到， 表示第 j 个变量对第 i 行对应的基变量的消耗率非基变量的机会成本为591.4 单纯形法的进一步讨论1.4.1 人工变量法 上一节我们涉及的线性规划模型都是线性规划的背景模型，即目标函数为最大，每个约束方程都是“”型，右端系数都是大于等于0。对于这样一类的线性规划，每个约束方程引入一个松弛变量将其标准化后，约束方程的系数矩阵含有单位矩阵，以此单位矩阵作为初始可行基，很容易得到一个初试基础可行解。但是，对于下面的线性规划，将其标准化后，其约束方程的系数矩阵不存在单位矩阵。

27、因此无法直观和方便地得到一个初始基础可行解 例1.4.1解 令g(x)= -f(x)，第1和2个约束方程分别减去一个剩余变量x4和x5，则可将上述线性规划转化为如下标准形线性规划。1.4.1 人工变量法60变量x6称为人工变量。这样，变量x3和x6系数矩阵可构成一个单位矩阵，即可构成一个初始可行基，以变量x3和x6为初始基变量，其它变量为非基变量0，则可得一初始基础可行解X(0) = (0，0，4，0，0，6)T这种在约束方程中加人工变量来得到初始基础可行解的方法称为人工变量法。61我们知道，对于任何一个基础可行解，非基变量都是等于0，所以，人工变量在初始基础可行解中虽然不等于0，但如果在后面

28、迭代过程中，能把所有人工变量转变为非基变量，则所有人工变量都将等于0，这样，原有的约束方程就不会被破坏。但如果在迭代过程中，已得到最优解（即满足最优解检验条件），而基变量中还有人工变量，或最优解时所有人工变量不全部等于0，则原线性规划无解，即不存在满足所有约束方程的可行解。将人工变量从初始基础可行解中转变为非基变量的方法主要有：（1）大M法；（2）两阶段法。下面我们分别讨论。1.4.1 人工变量法621.4.2 大M法 例1.4.163 表1.4.1 例1.4.1的单纯型表迭代过程答：最优解为 x1=2, x2=2, x3=0, OBJ=3664 大M法的一些说明大M法实质上与原单纯型法一样，

29、M 可看成一个很大的常数人工变量被迭代出去后一般就不会再成为基变量当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法手算很不方便因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易651.4.3 两阶段法第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解若第一阶段结束时，人工变量仍在基变量中，则原问题无解为了简化计算，在第一阶段重新定义价值系数如下：66 用二阶段法求解例1.4.1的第一阶段67 用二阶段法求解例1.4.1的第二阶段最优解对应的B1在哪？681.4.4 单纯

30、型法的一些具体问题一、无界解可行区域不闭合(约束条件有问题)单纯型表中入变量 xj* 对应的列中所有69 例1.4.2 的单纯型表及其迭代过程70 二、退化解退化问题的原因很复杂，当原问题存在平衡约束时当单纯型表中同时有多个基变量可选作出变量时退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法71 三、多重解多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行最优单纯型表中有非基变量的检验数为0最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=172 例1.4.4 的单纯型表及其迭代过程73 四、无可行解约束条件互相矛盾，无可行域单纯型表达到最优

31、解检验条件时，人工变量仍在基变量中74 例1.4.5 第一阶段的单纯型表1.5 修正单纯形法1.5.1 单纯形法的矩阵描述75其中，XS=(xs 1，xs 2，xs m)为松弛变量，I为mm阶单位矩阵。目标函数中松弛变量XS的系数0是一列0矩阵。以XS对应的系数矩阵单位阵I做为初始可行基B，对应的松弛变量XS为初始基变量，记为XB，其余变量为初始非基变量，记为XN。令XN =0，则可得到对应于初始可行基B（为单位阵）的初始基础可行解X = (XB, XN) = (b, 0)，对应目标函数值为f(X)= 0。并以该初始基础可行解X = (XB, XN) = (b, 0)为切入点开始进行迭代运算。

32、1.5.1 单纯形法的矩阵描述76一般地，对于任一标准型线性规划，在某一步迭代运算中，设B是其可行基，则该标准型线性规划可用矩阵形式表示如下：其中，X = (XB ,XN)T， C=(CB，CN） ，A=(B，AN）。由于B是可行基，B-1存在，所以，上述线性规划的约束方程可写成 XB = B-1(b - ANXN) 将上式XB代入上述线性规划的目标函数，并整理后可得， f(X) = CB B-1b+(CN - CBB-1AN)XN 令XN =0，X = (XB, XN) = (B-1b, 0)，f(X)= CBB-1b对应某一可行基B的最优检验条件用矩阵形式可表示如下： N = (CN -

33、CBB-1AN) 0 （2）771.5.1 单纯形法的矩阵描述若非基变量XN的系数向量(CN - CBB-1AN)有一些分量大于0，则取其中数值最大的一个分量k所对应的非基变量分量xk做为换入变量分量。对于某一非最优可行基B，确定换出变量时，可用如下矩阵形式表示：其中，Pk为标准型线性规划（1）技术系数矩阵A中换入变量xk的系数列向量。根据公式（3）的计算结果，基变量向量XB中的第i*分量xl为换出变量。当然，如果公式（3）的计算结果为空集，则为无界解。确定了换入变量xk和换出变量xl，就可以得到新的可行基和对应的基变量和非基变量等，并按公式(2)进行最优检验。781.5.2 改进单纯形法原单

34、纯型法迭代所需存储量大，原单纯型法有不必要的计算量由于改进单纯形算法通过矩阵运算求解线性规划，其关键是计算某一可行基B的逆矩阵B-1。可按如下初等变换进行： (B I) (I B-1)例1.5.1 用改进单纯形算法求解如下线性规划79解 （一）列出技术系数矩阵A，选择初始基、初始基变量等 （二）最优检验 由于B0是单位阵，其逆矩阵B0-1也是单位阵。XB0=（x3，x4，x5)T，XN0=（x1，x2)TC B0 =（0，0，0），C N0 =（2，3），AN0=(P1，P2)所以，初始基B0不是最优基。由于检验数向量第2个分量值最大，所以对应初始非基变量 XN0=（x1，x2)T的第2个分量

35、x2为换入变量。即xk = x2。80（三）确定换出变量，得到新的可行基及对应的基变量等i*=3，对应基变量XB0=（x3，x4，x5)T的第3个分量x5为换出变量，根据换出变量x5、换入变量x2和初始基B0=( P3，P4，P5)，得到新的可行基及其基变量等B1=( P3，P4，P2)，XB1=（x3，x4，x2)T，C B1=（0，0，3），XN1=（x1，x5)T，C N1=（2，0），AN1=(P1，P5)。（四）最优检验 由于可行基B1的非基变量检验数向量所以，可行基B1不是最优基。由于检验数向量第1个分量值最大，所以对应非基变量 XN1=（x1，x5)T的第1个分量x1为换入变量。

36、81（五）确定换出变量，得到新的可行基及对应的基变量等i*=1，对应基变量XB1=（x3，x4，x2)T的第1个分量x3为换出变量根据换出变量x3、换入变量x1和可行基B1=( P3，P4，P2)，得到新的可行基及其基变量等B2=( P1，P4，P2)，XB2=（x1，x4，x2)T，C B2=（2，0，3），XN2=（x3，x5)T，C N2=（0，0），AN2=(P3，P5)。（六）最优检验 由于可行基B2的非基变量检验数向量所以，可行基B2不是最优基。检验数向量第2个分量值最大，所以对应非基变量 XN2=（x2，x5)T的第2个分量x5为换入变量。82（七）确定换出变量，得到新的可行基及

37、对应的基变量等i*=2，对应基变量XB2=（x1，x4，x2)T的第2个分量x4为换出变量，根据换出变量x4、换入变量x5和可行基B2=( P1，P4，P2)，得到新的可行基及其基变量等B3=( P1，P5，P2)，XB3=（x1，x5，x2)T，C B3=（2，0，3），XN3=（x3，x4)T，C N3=（0，0），AN3=(P3，P4)。（八）最优检验 由于可行基B3的非基变量检验数向量所以，可行基B3是最优基。对应的最优解为1.6 线性规划建模案例分析1.6.1 线性规划建模基础步骤83一、建模前需要考虑的问题1）所讨论问题的目标是否可用一线性函数来描述；2）所讨论问题是否存在多种解决

38、方案及其相关数据；3）所要达到的目标是在一定约束条件下可以实现，且这些约束条件可以线性方程来表示。二、建立线性规划模型的基础步骤1、确定一目标；2、选择一组决策变量；3、列出目标函数和所有的约束方程。上面三个步骤中，步骤一和步骤二尤其重要。其中步骤一要确定一适当的目标并能够用恰当的方式进行表示，有时直接表示问题的目标有困难时，可用等价方式表示；步骤二要求选择一组合理的决策变量，用这些变量能够方便地列出步骤三的目标函数和所有约束方程。84案例1某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。试建

39、立使产品数最大的线性规划模型。消耗工时车间1车间2车间3A2115B1215可用工时100120100解：上述问题看似比较简单，目标是使产品数最大，决策变量分别是车间1、车间2和车间3生产产品零件A和B的数量。但是，一个产品是由2个A零件和1个B零件组成，所以直接表示产品数最大有一定困难，为此，我们考虑如下等价表示方式：1）产品数最大等价于：零件B数最大，且零件A的总数满足是零件B的总数两倍；2) 产品数最大等价于：零件A数最大，且零件B的总数满足是零件A的总数1/2倍85案例1解：设车间 1 生产x1A单位A、生产x1B单位B；设车间 2 生产x2A单位A、生产x2B单位B；设车间 3 生产

40、x3A单位A、生产x3B单位B；则有生产安排最优化的模型如下：讨论：第4个约束方程取“”好，还是取“=”好呢？86案例2某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表，饮料品种规格每升售价（元）需求量甲（1）A60%, C20%6.801500乙（2）A15%, C60%5.703000丙（3）C50%4.50无限制A、B、C三种原料每月的供应量和每升的价格如下表。供应量（升/月）价格（元/升）A2000700B2500500C1200400饮料甲、乙和丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益

41、的生产方案的线性规划模型。87案例2解：问题是要确定原料A，B和C的购买量和饮料甲、乙和丙的生产量，使得在满足规定约束条件下，饮料厂的总收益最大。建立该问题的线性规划模型的主要问题是如何选择决策变量，如果直接选择A，B和C的购买量和饮料甲、乙和丙的生产量六个变量做为决策变量，那将无法表示饮料甲、乙和丙中的A和（或）C的规格要求。为此，我们设：x1A 为饮料甲中A的总含量 (升)；x2A 为饮料乙中A的总含量 (升)；x3A 为饮料丙中A的总含量 (升)；x1B 为饮料甲中B的总含量 (升)；x2B 为饮料乙中B的总含量 (升)；x3B 为饮料丙中B的总含量 (升)；x1C 为饮料甲中C的总含量

42、 (升)；x2C 为饮料乙中C的总含量 (升)；x3C 为饮料丙中C的总含量 (升)；f(x)为饮料厂的总利润，则该问题的线性规划模型如下：889192939495第二章对偶理论与灵敏度分析窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象2.1 线性规划问题的对偶问题及其变换2.1.1 线性规划对偶问题的提出及其经济意义任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义96 假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？例 2.1.1 例2.1.1设A、B资源的出售价格分别为 y1 和 y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少97

43、 2.1.2 原问题与对偶问题的表达形式98 2.1.2原问题与对偶问题的表达形式99 一、标准(max,)型的对偶变换目标函数由 max 型变为 min 型对应原问题每个约束行有一个对偶变量 yi，i=1,2,m对偶问题约束为 型，有 n 行原问题的价值系数 C 变换为对偶问题的右端项原问题的右端项 b 变换为对偶问题的价值系数原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义100 二、非标准型的对偶变换三、原问题和其线性规划对偶问题的相互关系表约束条件的类型与非负条件对偶非标准的约束条件类型对

44、应非正常的非负条件对偶变换是一一对应的102103在使用上表规则写出某一线性规划的对偶规划时，要注意如下一些问题：1）要看清原问题目标函数是max问题还是min问题。如果原问题目标函数是max，在写其对偶问题时，应该利用上表左侧规则向右侧规则变换；而如果原问题目标函数是min，在写其对偶问题时，则应该利用上表右侧规则向左侧规则变换；2）如果原问题的约束条件不符合上表的规范要求，应该利用等价变换规则，将约束条件变换成符合上表的规范要求。例 2.1.4 写出如下线性规划的对偶规划1）第一、二约束方程可用两个约束方程等价表示；2) 没有给出x1 变量的约束条件，但根据第二约束方程可推得，x1 变量的

45、约束条件为x10。因此，上述线性规划等价于如下线性规划：1042.2 线性规划的对偶定理1、弱对偶定理定理1 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值105 为了便于讨论，下面不妨总是假设将(1)式左乘Y0，将(2)式右乘X0，立刻可得Y0b Y0AX0 CX0，证毕。 弱对偶定理推论max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解如果原max(min)问题有可行解，其对偶

46、 min (max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况106107例 2.2.1 设有如下线性规划原问题令 X0=(x01，x02，x03，x04)T= (1，1，1，1)T，Y0=（y01，y02，y03）=（1，1，1），则显然X0和Y0分别为原问题和对偶问题的可行解。它们对应的目标函数值分别为f(X0)=C X0=10，即其对偶问题目标函数值的下限不会小于10；g(Y0)= Y0 b=140，即其原问题目标函数值的上限不会大于140；这一结果验证了弱对偶定理C X0 Y0 b。108例 2.2.2 设有如下线性规划原问题令 X0=(x01，x02)T

47、= (1，1)T，则显然X0为原问题的可行解，即线性规划原问题有可行解；但将对偶问题的两个约束方程相加后可得 - y1 2，这显然与非负约束矛盾，所以对偶问题无可行解。根据弱对偶定理推论3可以判断原问题为无界解。事实上，利用单纯形法求解原问题（见第一章例1.10）可得，原问题的确为无界解，根据弱对偶定理推论2可以判断对偶问题无可行解2、最优解判别定理定理2 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解证：由弱对偶定理推论1，有 CX0 = Y0b CX, 即X0是原问题的最优解；另有Y0b = CX0 Yb，即Y0是对偶问题

48、的最优解；证毕。1093、主对偶定理定理3 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。 现证明定理的后一句话。 主对偶定理的证明 证：现证明定理的后一句话，采用反证法。 设 X0 ， Y0分别为原问题和对偶问题的最优解，且 Y0b CX0 根据最优性检验条件，非基变量的检验数满足CN CBB1N 0，而基变量的检验数为0，可写成CB CBB1B = 0，所以，包括基变量在内的所有变量的检验数满足 C CBB1A 0。令 Y= CBB1，则有 Y A C。 另外，对应于松驰变量，

49、有 CBB1I 0，即 Y= CBB1 0，故 Y为对偶问题的可行解。对偶问题可行解Y的目标函数值为 g(Y)=Yb = CBB1bY0b 原问题最优解X0的目标函数值为 f(X0)=CX0= CBB1b=Yb 所以有CX0Y0b, 与假设矛盾。故得证，该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格1103、互补松弛定理定理4 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 =

50、0证：由定理所设，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b C X0若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。111112根据互补松弛定理和决策变量满足非负条件可知，在最优解时，Y0 U0 和 V0 X0同时等于0，所以有3、互补松弛定理上面公式称为互补松弛条件。该条件表明，在最解条件下，如果知道v0j与x0j（或u0j与y0j）中的任意一个值为非

51、0时，则可推得另一个必然为0。利用这个条件，有时可大大地简化计算过程。例 2.2.4 利用互补松弛定理求解如下线性规划问题113其对偶问题引入剩余变量v1，v2，v3和v4后，可得到如下线性规划利用图解法可求得其最优解为：y01=1.2，y02=0.2，Min g (Y0)=28。利用得到的对偶规划最优解和互补松弛定理，可求得原线性规划的最优解。具体步骤如下：1、因为y01=1.20，根据互补松弛定理可得u01=0；2、因为y02=0.20，根据互补松弛定理可得u02=0；3、因为y01+ 2y02=1.61，根据对偶规划(2.13)的第1个约束方程 可得v010，然后根据互补松弛定理可得x0

52、1=0；4、因为2y01+ y02=2.62，根据对偶规划(2.13)的第2个约束方程 可得v020，然后根据互补松弛定理可得x02=0；5、根据上述4个步骤的结论及原线性规划的约束方程可得如下线性方程组解得，x03=x04=4。X0 = (x01，x02，x03，x04)T=(0，0，4，4)T 2.3原问题检验数与对偶问题的解在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值 可以证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似

53、上述关系。更一般地讲，可以证明，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛、剩余或人工变量) 的机会成本的绝对值等于其对偶问题实变量 (对偶变量)的最优解的绝对值，原问题实变量(决策变量)的检验数的绝对值等于其对偶问题虚变量 (松弛或剩余变量)的最优解的绝对值。因此，原问题或对偶问题只需求解其中之一就可以了。114 例2.2.3 原问题检验数与对偶问题的解1151161172.4对偶单纯型法2.4.1 基本思路1、原单纯型迭代要求每步都是基础可行解2、达到最优解时，检验数 cjzj 0 (max)3、对于(min, )型所加的剩余变量无法构成初始基础可行解4、因此通过加人

54、工变量来解决,但大M法和二阶段法较繁5、对偶单纯形法基本思路： 从原问题的某一个满足最优检验条件的基本解出发，判断该基本解是否满足可行性条件，若是，则已得最优解，若否，则通过迭代得到另一个满足最优检验条件且更接近可行解的基本解。如此循环，直到找到满足最优检验条件且可行解的基本解（即最优解）为止。118 2.4.2对偶单纯形法的步骤1、求一个满足最优检验条件的初始基础解，列出初始单纯形表；2、可行性检验 若所有的右端系数均大于等于0，即 bi 0，i=1,2,.,m则已得最优解，停止运算。否则，转步骤3；3、求另一个满足最优检验条件且更接近可行解的基础解1）确定出变量 找非可行解中分量最小者，即

55、 min bi | bi 0，不会破坏最优解若 aij 0 中找最大者，对应 xij 就是入变量2、以 xij 为起点，寻找由原基变量构成的闭合回路该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量(包括 xij )，且回路中每行每列只有两个变量3、求入变量 xij 的最大值及新基变量的解从 xij出发，沿任一个方向对回路拐角上的基变量依此标“”和“+”，表示“”和“+” xij ，从而迭代后仍满足分配的平衡标有“”的变量中最小者就是出变量xij* ，对应 xij*的值就是所求入变量 xij 的最大值标有“”的变量减去 xij*，标有“+”的变量加上 xi

56、j* 4、用位势法求新基变量的检验数若所有 zij wij 0，则达到最优，算法停止；否则返回 1159 例3.2.1 踏石法，以最低费用法所得初始解开始160答：最优解如上分配表，OBJ=98OBJ=121OBJ=1013.3 运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法闭合回路不一定是矩形 3.3.2 产销不平衡供过于求，即 ai bj ，增加一个虚收点Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m供小于求，即 ai 0 中找最大

57、者，对应 xij 就是入变量2、以 xij 为起点，寻找由原基变量构成的闭合回路该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量(包括 xij )，且回路中每行每列只有两个变量3、求入变量 xij 的最大值及新基变量的解从 xij出发，沿任一个方向对回路拐角上的基变量依此标“”和“+”，表示“”和“+” xij ，从而迭代后仍满足分配的平衡标有“”的变量中最小者就是出变量xij* ，对应 xij*的值就是所求入变量 xij 的最大值标有“”的变量减去 xij*，标有“+”的变量加上 xij* 4、用位势法求新基变量的检验数若所有 zij wij 0，则达

58、到最优，算法停止；否则返回 1164 例3.2.1 踏石法，以最低费用法所得初始解开始165答：最优解如上分配表，OBJ=98OBJ=121OBJ=1013.3 运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法闭合回路不一定是矩形 3.3.2 产销不平衡供过于求，即 ai bj ，增加一个虚收点Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m供小于求，即 ai bj ，增加一个虚发点Wm+1，am+1= bj - ai , 令 wm+1,j

59、=0, j=1,2,n 3.3.3 关于退化问题1、初始解退化。即所求初始基变量的个数少于 m+n1。必须补足基变量的个数，否则不能正常解出 m+n个 ui 和 vj所补基变量的值为 0 ，补充的原则：(1)尽量先选运费小的实变量；(2)补充后不能有某个基变量独占一行一列166 3.3.3 关于退化问题2、迭代过程中出现退化闭合回路中标有“”的基变量同时有多个达到最小变换后，有多个原基变量变为 0，选运费最大者为出变量，其余保留在新的基础解中退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。此时，一要耐心，二要正确选择出变量167踏石法迭代中需注意的问题：1、错误地将分配表中基变量

60、的解代入到运费表中2、不能正确画闭合回路3、初始解退化，未能补足基变量的个数。因此在位势法中多次令某个 ui 或 vj 为 0；4、在位势法中只能令一个 ui 或 vj 为 0；若不能求出全部 ui和 vj ，说明基变量未选够数或未选对168169170171第四章 整数规划 整数规划的难度远大于一般线性规划4.1 整数规划简介要求所有 xj 的解为整数，称为纯整数规划要求部分 xj 的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解1734.2 整数规划的解法 4.2.1 思路与解题步