运筹学（OperationsResearch)(PPT 131)

1、运筹学（运筹学（Operations Research)宋光兴宋光兴E-mail：gxsong_ Tel:筹学简介运筹学简介运筹学及其研究内容：运筹学及其研究内容： 运筹学是一门应用学科，是管理科学和系统工程的基础，主要研究用最少费用取得最大效果的方法，具体为：（1）资源数量给定，完成尽可能多的任务；或（2）任务给定，用尽可能少的资源去完成该任务。 运筹学求解问题大致可归纳为五个步骤：第一步：收集资料，归纳问题。第二步：建立相应的模型第三步：求解模型第四步：检验和评价模型的解第五步：参考所获得的最优值，作出正确的决策。运筹学的发展历程：运筹学的发展历程：n运筹学的思想

2、和方法在古代就有不少记载，例如，我国战国时期的“齐王赛马齐王赛马”、瑞士数学家欧拉(1707-1783)解决“哥尼斯堡七桥问题哥尼斯堡七桥问题”(哥尼斯堡城就是今俄罗斯加里宁格勒)等。运筹学作为一门新兴学科是在第二次世界大战期间出现的。当时英美成立了名为“运用研究”（Operational Research）的小组，通过运用科学的方法成功地解决了许多非常复杂的战略与战术问题。n例如如何合理运用雷达有效地对付德国的空袭，对商船如何进行编队护航，在船队遭受德国的潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况下如何调整其爆炸深度，才能增加对德国潜艇的杀伤力等。n第二次世界大战后，从事这项工作的许多

3、专家转移到经济部门、民用企业、大学或研究所，继续从事决策的数量方法的研究，运筹学作为一门科学逐步形成并得以迅速发展，并形成了许多分支。n1947年丹捷格(George Dantzig)提出线性规划问题的单纯单纯形法形法，成为运筹学发展史上最重要的进展之一。计算机的应用极大地推动了运筹学的应用与普及，使得运筹学的方法成功地被用来解决经济管理中的大量决策问题。运筹学方法使用情况(美1983)运筹学方法在中国使用情况(随机抽样)n据美劳工局1992年统计预测：社会对运筹学应用分析人员的需求从1990年到2005年，其增长百分比预测为73%，增长速度排到各项职业的前三位。n数学对运筹学的作用是有关理论

4、和方法的研究基础，是建立运筹学模型的工具。n计算机的发展，促进运筹学的进一步发展高速、可靠的计算是运筹学解决问题的基本保障。运筹学的主要分支运筹学的主要分支 包括规划论、对策论、库存论、决策论、排队论、可靠性理论、网络理论等。(一一)规划论。规划论。规划论主要是研究对有限资源进行统一分配、全面安排、统筹规划，以取得最大效果的一种数学理论。包括线性规划、整数规划、动态规划、非线性规划、多目标规划等。近年来随机规划、模糊规划成为研究热点。 规划论的作用是，在满足既定的条件下，按照某一衡量指标，从各种可行方案中寻求最优的方案，为科学决策提供可靠的依据。(二二)对策论。对策论。对策论又称博弈论。它是运

5、用数学方法来研究有利害冲突的双方在竞争性活动中是否存在一方制胜他方的最优策略，以及如何找出这些策略的问题。(三三)库存论。库存论。它是研究物资最优储存量的理论和方法。(四四)决策论。决策论。它是研究决策问题的基本理论和方法。通过对系统状态信息的处理，并对这些信息可能选取的策略和采取这些策略对系统状态所产生的效果进行综合研究，以便按照某种衡量准则，选择出一个最优的策略。(五五)排队论。排队论。这是一种用来研究用于公用服务系统工作过程的数学理论和方法。在这个系统中，服务对象何时到达及其占用系统的时间的长短，均无法事前预知，即它是随机的。(六六)可靠性理论。可靠性理论。它是研究系统可靠性的基本理论和

6、数学方法。在给定的时间、区间和规定的运用条件下，一个实体系统有效地执行其任务的概率，称为系统装置的可靠性。(七七)网络理论。网络理论。它是利用网络图把庞大复杂的工程项目的各个环节合理地街接起来，使之相互协调，以实现工程项目在时间和费用上达到最优目标的一种理论和方法。网络理论的研究着眼于整体系统，即将整体工程中各个环节的相互联系与时间关系组成统一的网络形式，清晰地反映整个工程的主要矛盾、关键环节和各种工作顺序。通过网络图的绘制和网络时间计算，可以预计影响进度和资源利用的各种因素，做到统筹规划、合理安排和使用资源，从而保证顺利地完成工程项目的预定目标。运筹学在工商管理中的应用运筹学在工商管理中的应

7、用n生产计划生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化n库存管理库存管理：多种物资库存量的管理、库存方式和库存量的确定等n运输问题运输问题：确定成本最小的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等n人事管理人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等n市场营销市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等n财务和会计财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等 此外还有设备维修、更新，项目选择、评价，工程优化设计与管理等。n由国际运筹与管理科学协会（INFO

8、RMS）和它的管理科学实践学会（College for the Practice of the Management Sciences）主持评奖的负有盛名的弗兰茨厄德曼（F. Edlman）奖，旨在奖励优秀的运筹学在管理中的应用成就，该奖每年举行一次，在对大量富有竞争力的入闱者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都于第二年发表在著名刊物Interface的第一期上，下面是发表在Interface期刊上的一些获奖项目。组织组织应用应用Interface期刊号期刊号 每年节支每年节支（美元）（美元）联合航空公司满足乘客需求前提下,以最低成本进行订票及安排机场工作班次1-2

9、/1986600万Citgo石油优化炼油程序及产品供应、配送及营销1-2/19877000万荷马特发展公司（Homart Development Co.）优化商业区和办公楼销售程序1-2/19874000万AT&T 优化商业用户的电话销售中心选址1-2/19904.06亿 ，更多销售标准品牌公司控制成品库存（制定最优再订购点和订购量，确保安全库存）12/1981380万施乐公司通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率11/1975第二部分生产率提高50%以上宝洁公司重新设计北美生产和分销系统以降低成本并加快了市场进入速度1-2/19972亿法国国家铁路制定最优铁路时刻

10、表并调整铁路日运营量1-2/19981500万更多年收入Delta航空公司进行上千个国内航线的飞机优化配置来最大化利润1-2/19941亿IBM重组全球供应链，保持最小库存的同时满足客户需求1-2/2000第一年7.5亿Merit青铜制品公司安装统计销售预测和成品库存管理系统，改进客户服务1-2/1993更优的服务CH1 线性规划与单纯形法线性规划与单纯形法1 线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题的特点及线性规划问题举例一、线性规划问题的特点及线性规划问题举例线性规划：线性规划：求一组变量的值，在满足一组约束条件的情况下，使某个目标函数达到最优。 线性规划问题的三个

11、要素：（1）决策变量：决策变量：是指实际系统中有待确定的未知因素，这些因素对系统目标的实现和各项经济指标的完成具有决定性影响。（2）约束条件：约束条件：约束条件是指实现系统目标的限制因素，它涉及到系统的内外部条件的各个方面，如内部条件的原材料的储备量，生产设备能力，产品质量要求，外部坏境的市场需求和上级的计划指标等等。（3）目标函数。目标函数。是对系统目标的数学描述。线性规划目标函数的重要特征之一是线性函数，即目标值与变量之间的关系是线性关系，目标函数的特性之二是单目标，实现单目标的最优值。一是求效益性指标，如产值、利润等的极大值，或者是损耗性指标，如原材料消耗、成本、费用的极小值。 经济管理

12、中常见的线性规划问题有生产计划与组织问题、工农业布局问题、合理下料问题、配料问题、运输问题、分派问题等。例例1（合理下料问题）（合理下料问题）：某企业根据生产需要，要将一批圆型钢管截成长2.9米、2.1米、1.5米三种不同长度的管料，根据生产经验有5种不同的下料方式，现三种管料各需100根，如何下料可以使消耗的钢管总数最少？解：解：设X1、X2、X3、X4、X5分别为5种下料方式所用钢管根数。目标函数：约束条件：例例2（指派问题指派问题） 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n

13、项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。例例有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。 工 作工 人ABCD甲15182124乙19232218丙26171619丁19212317解解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Minz =15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+1

14、6x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工

15、作只能一人干) xij 为0-1变量，i,j = 1, 2, 3, 4二、线性规划问题数学模型的一般形式及二、线性规划问题数学模型的一般形式及标准形式标准形式线性规划问题数学模型的一般形式一般形式为：Max （Min） z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 目标函数Max z = c1x1 + c2x2 + + cnxn约束

16、条件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0线性规划问题的标准形式：线性规划问题的标准形式：n可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。n 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式: 设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问题与下面的极大化问题有相同的最优解，即 Max z

17、= -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z1. 极小化目标函数的问题：极小化目标函数的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi 2、约束条件不是等式的问题：、约束条件不是等式的问题： 当约束条件为 ai1 x1

18、+ai2 x2+ +ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi 为了使约束由不等式成为等式而引进的变量s称为“松弛变量松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的

19、大小。3. 变量无符号限制的问题：变量无符号限制的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bim，秩(A) = m，b Rm 。 在约束等式中，令n维空间的解向量为： x = (x1，x2，xn)T 对于线性规划的约束条件 Ax=b， x0 设B是A矩阵中的一个非奇异（可逆）的mm子矩阵，则称B为线性规划的一个基基。 记 A=( p1 ，p2 ，pn ) ，其中 pj=( a1j ，a2j ，amj )T Rm ，任取A中的m个线性无关列向量 pj Rm 构成矩阵 B=( pj1 ，pj2 ，pjm )，那么B为线性规划的一个基基。 我们称对应于基B的

20、变量xj1 ，xj2，xjm为基变量基变量；而其它变量称为非基变量非基变量。记XB=(xj1 ，xj2，xjm)T。（5）线性规划的基基：（6）线性规划问题的基本解基本解、基本可行解基本可行解和可行基可行基： 对于线性规划问题，设矩阵B = ( pj1，pj2，pjm ) 为一个基，在 Ax=b中，令所有非基变量为零，可以得到关于m个基变量xj1 ，xj2 ，xjm的线性方程组BXB = b，该方程组有唯一解，解这个线性方程组得到基变量的值XB = B-1b 。 基变量的值及非基变量的值（为0）组成的向量称为线性规划问题的对应于基B的基本解基本解；若得到的基变量的值均非负，则称其为基本可行解基

21、本可行解，同时称这个基B为可行基可行基。考虑如下线性规划模型： Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意注意：线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。 A = P1 ,P2 ,P3 ,P4 ,P5 A矩阵包含以下10个33的子矩阵： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5

22、B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 其中B4= 0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。 对于基B3= p1 ，p2 ，p5 ，令非基变量x3 = 0， x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的基本可行解：X3= (x1 ，x2 ，

23、x3 ，x4 ，x5 )T = (15，10，0，0，45)T。于是对应的基B3是一个可行基。类似可得到 X2 = (5,25,0,5,0)T （对应B2） X5 = (20,0,5,0,75)T （对应B5） X7 = (0,25,15,15,0)T （对应B7） X10 = (0,0,65,40,75)T （对应B10） 是基本可行解.而 X9=(0,32.5,0,7.5,-22.5)T （对应B9） X6 =(65/3,0,0,-10/3,75)T （对应B6） X1= (7.5,25,-7.5,0,0)T （对应B1） X8= (0,40,-15,0,-45)T （对应B8） 是基本解

24、。2 单纯形法的基本原理单纯形法的基本原理n单纯形法于1947年由G. B. Dantzig提出。其解题思路与图解法思路相同，是通过求出初始基础可行解后，从这个可行解出发，通过换基迭代，不断改进，最终求得最优解。n用单纯形法求解线性规划问题，需要将原线性规划问题化为标准形式。一、概念一、概念n凸集凸集的概念：设S是n维向量组成的集合，若对任意的X1 S， X2 S，有X1+（1- ）X2 S，( 0,1)则称S为凸集。凸集的例子：凸多边形，实心球等。非凸集的例子：圆环、空心球等。n凸集的顶点顶点（极点）：设S为凸集，X S，若对任意的X1 S， X2 S，不存在 (0,1)，使X X1+（1-

25、 ）X2成立，则称X为凸集的顶点或极点。二、单纯形法的基本原理二、单纯形法的基本原理n单纯形法的基本理论基本理论：1、若线性规划问题有可行解，则可行域必为凸集。2、线性规划问题的基可行解与可行域的顶点一一对应。3、若线性规划问题有最优解，则最优值一定可在可行域的某个顶点处达到，即一定存在某个基可行解是最优解。单纯形法的基本思路是： 从可行域中某一个顶点(基可行解)开始，判断此顶点是否是最优解，如不是,则再找另一个使得目标函数值更优的顶点，称之为迭代迭代，再判断此点是否是最优解。重复这一过程,直到找到一个顶点使目标函数值达到最优，或者判断出线性规划问题无最优解为止。3 单纯形法的计算步骤单纯形法

26、的计算步骤一、单纯形表的概念一、单纯形表的概念 设LP问题的标准形式为：0XbAXCXZ max 假设B为该LP问题的一个基，对应于B的单纯形表为（其中CB为C中对应于基变量的分量构成的m维向量） ：ABCCbBCABbBBTBB1111)(二、单纯形法的计算步骤二、单纯形法的计算步骤（1）求初始基，写出其对应的初始单纯形表（初始基可行解含在其中）。（2）最优性检验。利用检验数判断当前基可行解是否为最优解，如果所有检验数0，则这个基可行解就是最优解，停止计算；否则转下一步。（3）换基迭代。利用矩阵的初等行变换，从当前基可行解转到另一个更好的新的基可行解。（4）重复第（2）、（3）两步。例：求解

27、线性规划问题（L）： 213020maxxxZ 0,25402402 . .21212121xxxxxxxxts 解：化为标准型： 543210003020maxxxxxxZ 0,25 40 240 2 . .54321521421321xxxxxxxxxxxxxxts 取初始基B1=(P3, P4, P5)，初始单纯形表T（B1）为：jc 20 30 0 0 0 1BC 1BX bB11 1x 2x 3x 4x 5x 0 3x 40 2 1 1 0 0 0 4x 40 1 2 0 1 0 0 5x 25 1 1 0 0 1 j 20 30 0 0 0 新基B2=(P3, P2, P5)，T（

28、B2）为：jc 20 30 0 0 0 2BC 2BX bB12 1x 2x 3x 4x 5x 0 3x 20 3/2 0 1 -1/2 0 30 2x 20 1/2 1 0 1/2 0 0 5x 5 1/2 0 0 -1/2 1 j 5 0 0 -15 0 新基B3=(P3, P2, P1)，T（B3）为：1 每一个线性规划问题，都存在一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。 例例1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C的台时如下表所示：该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产

29、品，才能使工厂获利最多？解：设x1 为产品 的计划产量， x2为产品的计划产量，则有 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？ 设y1， y2， y3 分别为设备A、B、C的每台时的租金。作为出租者来说，生产单位产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产产品以获利50元；50221yy 同样，生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即 ，否则这些设备台时就不出租，还是用于生产产品以获利100元。但对于租用者来说，他要求在满足上述条件的前提下，也就

30、是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们就得到该问题的数学模型：100321yyy321250400300yyyn这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中一个叫做原问题原问题，而另外一个叫对偶问题对偶问题。具有对称形式的互为对偶的线性规划问题： (LP) Max = (DP) Min = b s.t. AX b s.t. YA C X 0 Y 0 其中Y= (y1 ，y2 ，ym )2 线性规划的对偶理论线性规划的对偶理论一、原问题与对偶问题的关系一、原问题与对偶问题的关系

31、一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。非对称形式的对偶规划： 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统

32、一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 下面对关系（2）作一说明。对于关系（3） 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么，这个等式与下面两个不等式等价 a11x1 + + a1nxn b1 及 a11x1 + + a1nxn b1 (即-a11x1 - - a1nxn -b1)基本规律：基本规律：n原问

33、题的变量对应对偶问题的约束条件，原问题的目标函数中第i个变量的系数就等于对偶问题中第i个约束条件的右端常数项。n原问题的约束条件对应对偶问题的变量，原问题第i个约束条件的右端常数项就等于对偶问题的目标函数中第i个变量的系数。n对偶问题的约束条件的系数矩阵是原问题约束矩阵的转置。 例例2 写出下面线性规划问题的对偶问题：写出下面线性规划问题的对偶问题：无非负限制321432143143214321 , 0, ,10530 226027 2252375maxxxxxxxxxxxxxxxxxxxZ将约束条件改为：没有非负限制4321443214314321,0,001 -5 03 2260-27 2

34、25 23xxxxxxxxxxxxxxxx54321105306025minyyyyyw00007 2 5 721 2 31 2254321542132131321yyyyyyyyyyyyyyyyy，无非负限制，二、对偶问题的基本性质二、对偶问题的基本性质1、对称性对称性。即对偶问题的对偶是原问题。2、弱对偶定理。弱对偶定理。 若 X, Y 分别为（LP) 和（DP）的可行解，那么CX Yb。 由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无

35、界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。3、最优性定理、最优性定理 若X、Y分别(LP)、(DP)的可行解，且CX=Yb ，那么X、Y分别为(LP)和(DP)的最优解。4、对偶定理、对偶定理 若(LP)和(DP)均有可行解，那么(LP)和(DP)均有最优解,且最优值相等。注意：注意：除性质2外，以上定理及推论对任意形式的线

36、性规划问题及其对偶问题均成立。5、互补松弛性、互补松弛性。 在线性规划问题的最优解中在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。换句话说： 设 为(LP)的最优解， 为(DP)的最优解，则有TnxxxX),(*2*1*),(*2*1*myyyY（1）（2）（3）（4）njijijibxay1* 00 *1*injijijybxamijiijjcyax1* 00 *1*jmijiijxcya 注意：注意：使用以上结论求线性规划问题的最优解时，（1）和（4）配合使用，（2）和（3）配合使用。

37、例例3：课本P60例53 影子价格影子价格对偶问题的经济解释对偶问题的经济解释 影子价格影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。或者说 对偶问题的最优解称为原问题约束条件的影子价格。（如何求影子价格如何求影子价格：对偶问题的最优解是原问题最终单纯形表中松弛变量对应的检验数的相反数。） 某一约束条件的影子价格表示当它的右端常数项增加一个单位时（设原问题的最优基不变），原问题目标函数最优值的增量。 若X*,Y* 分别为（LP）和（DP）的最优解， 那么CX* = Y*b 。 根据 w = Y*b = b1y1* + b2y2* + + bmym* 可知 w / bi

38、= yi* yi* 表示 bi 变化1个单位对目标 w产生的影响，称 yi* 为 bi的影子价格。影子价格的经济含义影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价 企业根据现有资源的影子价格，对某资源的使用有两种考虑： 第一，是否将该资源用于外加工或出租，若租费高于该资源的影子价格，可考虑出租该资源，否则不宜出租。第二，是否将投资用于购买该资源，以扩大生产能力，若该资源的市价低于其影子价格，可考虑买进该资源，否则不宜买进。（2） 影子价格表明资源增加对总效益产生的影响。 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加资源，就

39、应该从影子价格高的资源入手，这样可以用较少的局部努力，获得较大的整体效益。4 对偶单纯形法对偶单纯形法对偶单纯形法的基本思想对偶单纯形法的基本思想: : 从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应着一个对偶可行解对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。 如果得到的基本解的分量皆非负,则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，

40、当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 对偶单纯形法的对偶单纯形法的应用前提：应用前提： 能找到一个基，使得: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。 具有如下形式的线性规划问题常用对偶单纯形法求解（也可用人工变量法求解，但很麻烦）:(1) 目标函数形如：min Z = CX；(2) 至少有一个约束条件形如： ai1 x1+ai2 x2+ +ain xn bi (bi0)(3) X0 在引入松弛变量化为标准型之后，约束等式两侧同乘 -1，能够立即得到检验数全部非

41、正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，以便简化计算。对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：1. 建立初始对偶单纯形表，对应一个基本解，所有检验数均非正，转2；2. 若B-1b0，则得到最优解，停止；否则，令min (B-1b )i (B-1b )i0=(B-1b )l，选第l行对应的基变量（注

42、意，该基变量不一定是xl)为换出变量，转3； 3. 若所有(B-1A )l0，则原问题无可行解（因为其对偶问题有无界解），停止；否则令 = minj /( (B-1A )l )j /( (B-1A )l )j0 = k /( (B-1A )l )k， 那么 xk为换入变量，转4；4. 以( (B-1A )l )k为主元素，利用矩阵初等行变换使其变为1，该列其它元变为0，转2。例：求解线性规划问题例：求解线性规划问题Min Z = 2x1 + 3x2 + 4x3 s.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0化为标准型：Max w = -

43、2x1 - 3x2 - 4x3 s.t. x1+2x2+x3 -x4 = 3 2x1-x2+3x3 -x5 = 4 x1, x2, x3, x4, x5 0再转化为： Max w = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4 = -3 -2x1+x2-3x3 +x5 = -4 x1, x2, x3, x4, x5 0因此原问题的最优解为：X*=(11/5, 2/5,0)T，最优值为Z*=28/5。5 灵敏度分析灵敏度分析考虑线性规划问题考虑线性规划问题: Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + +

44、 a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0 bi _ 资源数量; ci _ 价值系数; aij _ 技术系数; 所谓灵敏度分析，灵敏度分析，就是考虑当上述数据部分发生变化时，已求得的线性规划问题的最优解如何变化，并要求间接给出新问题的最优解（不是用单纯形法直接求解新问题）。一、资源数量（约束条件右端常数项）发一、资源数量（约束条件右端常数项）发生变化的情况生变化的情况 设向量b变为b*，原问题的最优基为B，只要将最终单纯形表中基变量的取值换为B-1 b*，则

45、出现课本表2-9中的第一或第三种情况，对于第三种情况，用对偶单纯形法继续迭代即可求出新问题的最优解。 其中B-1由最终单纯形表中初始基变量（初始单纯形表中的基变量）对应的列构成。例：课本例例：课本例7 用对偶单纯形法进一步求解，可得：X* = ( 4, 3, 2, 0, 0 )T Z* = 17二、价值系数（目标函数中变量的系数）二、价值系数（目标函数中变量的系数）发生变化的情况发生变化的情况 设向量C变为C*，原问题的最优基为B，则重新计算检验数* = C*- CB*B-1A填入最终单纯形表中，这时出现课本表2-9中的第一或第二种情况，对于第二种情况，用单纯形法继续迭代即可求出新问题的最优解。三、增加一种产品（增加一个新变量）三、增加一种产品（增加一个新变量） 设增加变量xj，它在目标函数中的系数为Cj，在约束条