运筹学-1、线性规划

1、1,运筹学 Operations Research,2,运筹学是一门应用科学 ，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。,运筹学作为一门新兴的学科是在第二次世界大战期间出现的 。当时英美成立了名为“运作研究” ( Oprtational Research)小组，通过科学方法的运用成功地解决了许多非常复杂的战略和战术问题。,3,例如如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况下如何调整其爆炸深度，才能增加对德国潜艇的杀伤力等 ；军队营养物质供应问题。,运筹学

2、课程的一般内容有：线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、对策论、存贮论、决策论等。,4,线性规划,5,第一节数学规划的概念,6,例1:(生产计划问题)某工厂生产 I、II 两种产品。每件产品的单位利润，所消耗的两种材料数、设备工时及这两种材料、设备工时的限额如下表：,如何安排生产才能使利润最大？,7,解：设 x1、x2分别表示两种产品的产量，那么该问题的数学模型可以表示为：,目标函数,约束条件,决策变量,8,第i 种资源的拥有量为bi ;i=1,2,m , 生产一个单位第j种产品需要消耗第i 种资源的数量为aij; 第j种产品的利润（单价,产值）为cj 。j =1,2

3、,n。,上述问题推广到一般情况：,有m种不同资源（例如原材料，动力资源，资金，劳力等）可以用来生产n种不同产品。假设有关的数据为：,设x1、x2、xn 分别表示n种产品的产量，则其数学模型为：,如何安排生产才能使总的利润最大？,9,10,例2： (配料问题) 一饲养场饲养动物出售，每只动物每天至少需要700克蛋白质， 30克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示；,四种饲料各采购多少，才能使总费用最小？,11,解：设 x1、x2、 x3、 x4分别表示四种饲料的采购量，那么该问题的数学模型可以表示为：,12,上述模型推广到一般情况为：,每只动

4、物每天至少需要有m种不同营养成分bi； 有n种饲料可供选用，每公斤第j种饲料所含第i种营养成分量为aij; 第j种饲料的单价为cj 。i=1,2,m， j=1,2,n。,设x1、x2、xn 分别表示n种饲料的采购量，则其数学模型为：,如何采购才能使总费用最小？,13,14,例3：（运输问题）设有两个砖厂A1 、A2 ，产量分别为23万块、27万块，现将其产品联合供应三个施工现场B1 、 B2 、 B3 ，其需要量分别为17万块、18万块、15万块。各产地到各施工现场的单位运价如下表：,问如何调运才能使总运费最省？,15,解：设xij表示从砖厂Ai运往现场Bj的数量 (i=1，2;j=1,2，3

5、),则其数学模型如下：,16,一组决策变量x表示一个方案,一般x大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。求目标函数最大值或最小值,线性规划问题的共同特征,17,线性规划模型的一般形式,18,例4： （投资问题 ） 某投资公司在第一年初有100万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的两倍金额” 。投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。,解：设x1为第一年的投资; x2为 第一年的保留资金；,设x3为第二年新的投资； x4为第二年的保留资金；,19,设x5为

6、第三年新的投资；x6为第三年的保留资金；,设x7为第四年新的投资；第四年的保留资金为x8；,设x9为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。,约束条件保证每年满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额。,20,到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型：,21,例5：（下料问题） 某一机床需要用甲、乙、丙三种规格的钢轴各一根，这些轴的规格分别是2.9,2.1, 1.5(m),这些钢轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少根圆钢来生产这些钢轴？,解：第一步：设一根圆钢切割成甲、

7、乙、丙三种钢轴的根数分别为y1,y2,y3，则切割方式可用不等式2.9y1+2.1y2+1.5y37.4 表示，求这个不等式的有实际意义的非负整数解共有8组，也就是有8种不同的下料方式，如下表所示：,22,设x1、x2、x8 表示按8种方案下料的圆钢根数，则问题的数学模型为：,23,24,第二节 线性规划的数学模型,一、线性规划问题的标准形式,25,线性规划模型的一般形式,26,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions）,基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、

8、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,27,目标函 数最大 约束条 件等式 决策变 量非负,线性规划问题的标准形式,28,用求和号表示为：,线性规划问题的标准形,29,用向量表示为：,线性规划问题的标准形,其中：,30,用矩阵表示为：,C价值向量 b资源向量 X决策变量向量 A资源消耗系数矩阵,31,一般线性规划问题的标准形化,1) 若目标函数为：minZ=CX，则令Z= -Z ,于是得到max Z= -CX,2) 若约束条件为：,引进松弛变量xn+1 , 使：,显然：,32,若约束条件为：,引进松弛变

9、量xn+1 , 使：,显然：,若xk无非负约束 ，则令：,33,例1：将下列线性规划化为标准形,解：标准形为：,34,二、线性规划问题的解的概念,可行解：满足AX=b, X0的解X称为线性规划问题的可行解。 可行域：可行解的全体称为可行域。 最优解：使Z=CX达到最大值的可行解称为最优解。,标准型,35,标准形的假定,36,基：若B是矩阵A中mm阶非奇异子矩阵，则称B是线性规划问题的一个基。不妨设：,线性规划问题解的概念, 基向量, 基变量, 非基变量,37,38,两边同时左乘B-1得到：,约束方程化为：,于是得解：,39,基本解：上面求出的X称为对应基B下的基本解 基本可行解：非负的基解X称

10、为基本可行解 可行基：对应基可行解的基称为可行基 基本最优解：最优的基可行解称为基本最优解 最优基：对应基本最优解的基称为最优基,40,例7:,解：系数矩阵为：,41,易知：,都是基。,相应基本解及目标函数值为：,不是基。,42,可以看到B2、B3、B4、B6、B7、B8是可行基， B3是最优基, B1、B5不是可行基。,43,线性规划解的关系图,非可行解,可行解,基可行解,基本解,线性规划问题解的概念,基本最优解,？,最 优 解,44,三、线性规划问题的图解法,例2:,45,x1 + 2x2 8,4x1 16,4 x2 12,2x1 + 3x2 =5 等值线,可行域,(4,2),C,A,B,

11、D,最优解X=(4,2)T 最优值Z=14,Z= 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,(1,1),46,(2,3),最优解X(1)=(4,2)T X(2)=(2,3)T 最优值Z=16,(4,2),当=0.5时 X =0.5(4,2)T+ 0.5(2,3)T=(3, 2.5)T,有无穷多个最优解 即具有多重解,通解为X=X(1)+(1-) X(2) 01,例3:,47,2,4,6,x1,x2,2,4,6,最优解X=(3,1)T 最优值Z=5,(3,1),例4:,48,2,4,6,x1,x2,2,4,6,无界解 (无最优解),例5:,49,x1

12、,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解 即无最优解,例6:,50,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸多边形的顶点，计算其目标函数值，比较即得。,51,由以上例题可知， 线性规划的解有4种形式：,2.有无穷多最优解,3.有无界解,4.无可行解,1、2情形为有最优解 3、4情形为无最优解,1.有唯一最优解,52,凸集：设K是n维欧氏空间En的一个点集。若任意两点X(1)、X(2)K的连线

13、上的一切点X(1)+(1-)X(2)K，01 ，则称K为凸集。,四、线性规划问题的基本定理,53,凸组合： 设X(1)、 X(2)、 、X(k)是n维欧氏空间En的k个点，若存在1、 2、 、k ,且0 i 1, 1+ 2+ +k =1，使得： X=1X(1) + 2X(2) + +k X(k) 则称X是X(1)、 X(2)、 、X(k)的凸组合。,顶点： 设K是凸集，XK；若X不能用K中不同的两点X(1)、 X(2)的线性组合表示为：,则X 称为K的一个顶点(或极点)。,X=X(1)+(1-)X(2)， 0 1 。,X,54,定理1：若LP问题存在可行解，则其可行域,证: 设,是D内的任意两

14、点，且X(1) X(2)。,是凸集。,55,则有 ：,令X=(x1, x2, ，xn)T为X(1)、 X(2)连线上的任意一点，即： X=X(1)+(1-)X(2)， 0 1 。,X的分量是xj=xj(1)+(1-) xj(2) ， 将它代入约束条件，得到,56,又因 xj(1)、xj(2) 0，0，1-0， 所以xj 0 ，j=1、2 、 、n 。,于是X为可行解，即D是凸集。,57,定理：如果LP问题存在可行解，则一定存在基可行解。,若1, 2, ，k线性相关，即存在一组不全为零的数i ,i=1、2 、 、k （其中至少有一个正数）, 使得:,证:设X=(x1 , x2 , , xk ,

15、0 , , 0)T为可行解，若向量1, 2, ，k线性无关，则X就是一个基可行解。否则，可通过下列步骤一个构造出一个基可行解。,由下式定义一个新的点，令,58,其中,于是有,特别地：,将代入约束条件,59,由此可见是一个可行解，但的正分量比的正分量少一个。若的正分量所对应的系数列向量是线性无关的，则就是一个基可行解，如若不然，继续以上步骤直到得到一个基可行解。,60,定理3：LP问题的可行解X=(x1 , x2 , , xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。,证: 1)必要性：由基可行解的定义可知。,2）充分性：设可行解X的正分量x1,x2,xk所对应的列向量

16、p1, p2, ,pk线性无关，则必有km；当k=m时，它们恰好构成一个基，从而X=(x1,x2, ,xk , 0, ,0)T为相应的基可行解。,当km时，则一定可以从其余的列向量中取出m-k个列向量与p1, p2, ,pk构成最大的线性无关向量组,其对应的基解恰为X，由定义可知它是基可行解。,61,定理4：线性规划问题的基可行解对应于可行域的顶点。,证： 不失一般性，假设可行解X的前k个分量为正。,现在分两步来证明，分别用反证法。,1)若X不是基可行解，则它一定不是可行域的顶点。 根据定理2，若X不是基可行解，则其正分量所对应的列向量p1, p2, ，pk线性相关，即存在一组不全为零的数i

17、,i=1、2 、 、k , 使得:,故,62,用一个0的数乘式(2)式再分别与(1)式相加和相减，这就得到,现取,由X(1)、 X(2)可以得到：,即表示X是X(1)、 X(2)连线的中点。,63,另一方面，当 充分小时，可保证,即X(1)、 X(2)是可行解。 这就证明了X不是可行域D的顶点。,2) 若X不是可行域D的顶点，则它一定不是基可行解：,因为X不是可行域D的顶点，则在可行域D中可找到不同的两个点X(1) X(2) ：,使得 X=X(1)+(1-)X(2)， 0 1 。,64,由于X(1)、 X(2)是可行域D的顶点，应满足,两式相减，即得:,因X(1)X(2),所以上式系数 不全为

18、0，,故向量组P1、Pk 线性相关，即X 不是基可行解。,设X是可行解，则当jk时，有,65,引理: 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。,用下述例子来说明这个引理。,X,例：设X是三角形中任意一点，又X(1)、X(2)和X(3)是三角形的三个顶点，试用这三个顶点表示点X。,66,因X(0)不是顶点，所以它可以用D的顶点凸组合表示为：,定理4：若可行域有界，则LP问题的目标函数值一定可以在其可行域的极点上达到最优。,证：设X(1)，X(2)， X(k)是可行域D的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最大值ZC X(0)。,因此,67,在所有的顶点中必然能找到

19、某一个顶点X(r),使CX(r)是所有CX(i)中的最大者。并且将X(r)代替(1)式中的所有X(i),这就得到:,由此得到 CX(0) CX(r),根据假设CX(0)是最大值。 所以只有CX(0)= CX(r) 。 即目标函数在顶点X(r)处也达到了最大值。,68,求解LP的基本思路,1、构造初始可行基； 2、求出一个基可行解（顶点）； 3、最优性检验：判断是否最优解； 4、基变换，转2。要保证目标函数值比 原来更优。,69,第三节 单纯形方法,70,一、 举例,本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。,71,例1:

20、,引例（上一节例）,72,解：标准化为,73,第1步 确定初始可行基,根据,显然 ， 可构成初始可行基B0 。,为基变量,74,第2步 求出基可行解,基变量用非基变量表示，并令非基变量为 0时对应的解,初始基可行解,目标函数 Z02x13x2,是否是最优解？,75,第3步 最优性检验,分析目标函数,检验数,无解 换基，继续,换入？基变量 换出？基变量,考虑将 或 换入为基变量,0时，最优解 0 时，,Z02x13x2,只要取x10或x20 , Z 的值可能增大。,76,第4步 基变换,换入变量,（即选最大检验数对应的变量）,一般选取 对应的变量,均可换入。,77,换出变量,使换入的变量越大越好

21、 同时，新的解要可行。,选非负的最小者对应的变量换出,为换入变量，应换出 ？ 变量。,思考： 当a/k20 时会怎样？,78,转第2步：基变量用非基变量表示。 第3步：最优性判断 检验数 存在正，按第4步换基继续迭代 均非正，停止 （这时的解即是最优解）,为换入变量，应换出 变量。,因此，基由,变为,79,转 第2步,进基,Z02x13x2,80,因此，基由,确定换出变量,变为,81,进基,基变量用非基变量表示为：,82,确定换出变量,因此，基由,变为,83,0,最优解,基变量用非基变量表示为：,84,下面我们用矩阵的初等变换来表示上述求解过程。,85,结合图形法分析(单纯形法的几何意义),A

22、(0,3),B(2,3),C(4,2),O(0,0),86,二、 单纯形法的基本原理,为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。下面介绍用单纯形表计算线性规划问题的原理。,87,从计算过程可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。,设 是一个可行基，,88,初等行变换,89,用矩阵表示为：,由此得基可行解：,是否为最优，如何由表得到判断？,90,检验数的计算：,91,非基变量的检验数为：,基变量的检验数为：,故所有变量的检验数统一表示为：,92,单纯形表：,

23、E 单位阵,B-1N 非基阵,基变量XB,非基变量XN,0,93,2 1 0 0 0,检验数,单纯形表结构,单纯形表, 24/6 5/1,C,94,2 1 0 0 0, 24/6 5/1,C,检验数,单纯形表结构,单纯形表,基可行解：,95,单纯形表结构,单纯形表,2 1 0 0 0, 24/6 5/1,C,检验数,96,单纯形表结构,2 1 0 0 0, 24/6 5/1,C,检验数,求,单纯形表,97,单纯形表结构,单纯形表,2 1 0 0 0, 24/6 5/1,C,检验数,求,0设此为主列,主行,98,单纯形表结构,单纯形表,2 1 0 0 0, 24/6 5/1,C,检验数,主元,9

24、9,三、初始单纯形表的确定,对资源约束模型,100,化标准型后,易知 B =I 是可行基。,对应单纯形表为：,101,用单纯形表求解LP问题,例2: 用单纯形表求解LP问题,102,解: 化标准形,则B=(P3 P4P5)是一个可行基。,初始单纯形表为：,103,主元化为1 主列单位向量 x4换出,x1换入,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,检验数中最大者对应的列为主列,比值最小的对应的行为主行,104,表2：换基 （初等行变换，主列化为单位向量，主元为1）,105,最优解为X=(7/2,3/2,15/2,0,0)T 最优目标函数值maxZ=17/2,106,四、人工变量法

25、,问题：线性规划 问题化为标准形时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？,107,加入 人工变量,设线性规划问题的标准形为：,108,系数矩阵为 单位矩阵， 可构成初始 可行基。,加入人工变量,构造初始可行基.,109,约束条件已改变， 目标函数如何调整？,110,1、大 M 法,目标函数中添加“罚因子” -M（M是任意大的正数） 为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。,人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数。,111,系数矩阵为 单位矩阵， 可构成初始 可行基。,构造新的线性规划：,112,目标函数中添加“罚因子”

26、 -M为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。,求解结果出现检验数非正 .,用单纯形法求解,1) 若基变量中含非零的人工变量， 则原问题无可行解；,2) 若基变量中不含非零的人工变量，则原问题有最优解。,113,例3: 求解线性规划问题,114,解:加入松弛变量标准化为：,115,加入人工变量构造初始可行基.,则B=(P4 P6 P7)是一个可行基（人造基）,借用为基变量,初始单纯形表为：,116,表1（初始单纯形表）,117,118,检验数均非正，此为最终单纯形表,最优解为X=(4,1,9,0,0)T ， 原规划最优目标函数值minZ=-2,119,2、两阶段法,M在计

27、算机上处理困难。 分阶段处理先求 初始可行基，再求解。,120,人工变量的 系数矩阵为 单位矩阵， 可构成初始 可行基。,目标函数仅含人工变量，并要求实现最小化。 若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。,第一阶段: 构造如下的线性规划问题 （称为辅助规划）,121,1) 若0，则原问题无可行解。,2) 若=0，进入第二阶段。,a. 若基变量中不含人工变量，则此最优基就是原问题的一个可行基；,b. 若基变量中含有人工变量，则还原为方程:,用单纯形法求解,122,若这时所有的 全为0.即,则表明原问题中第r个方程是多余的，可以去掉多余方程。

28、,求和式中的变量皆为非基变量.,若至少有某个 不为0.则以其为主元做换基迭代,可将yr从基变量中去掉.,123,例4：,124,解:加入松弛变量标准化为：,125,构造第一阶段辅助规划并求解,则B=(P4 P6 P7)是一个可行基（人造基）,初始单纯形表为：,126,第一阶段、求min ,127,得到辅助规划的最终表，由此进入第二阶段。,128,辅助规划的最终表,不含人工变量且=0,第 二 阶 段,129,第二阶段,去掉人工变量还原目标函数系数，做出初始单纯形表。,130,最优解为X=(4,1,9,0,0)T ， 原规划最优目标函数值minZ=-2,检验数均非正，此为最终单纯形表,131,例：

29、某工厂利用三种资源生产两种产品， 有关数据如下表：,第四节 、对偶理论,一、对偶问题的提出,132,如何安排生产， 使获利最多？,厂 家,设 产量 产量,厂家考虑将资源转让出去？,133,设：原料A 百元公斤 原料B 百元公斤 设备C 百元台时,收 购 方,付出的代价最小， 且让对方能接受。,出让收益应不低于 用同等数量的资源 自己生产的利润。,134,厂家能接受的条件：,出让收益应不低于 用同等数量的资源 自己生产的利润。,收购方的意愿：,135,对 偶 问 题,原 问 题,收 购 方,厂 家,一对对偶问题,136,3个约束 2个变量,2个约束 3个变量,一般规律,137,其它形式 的对偶

30、?,特点：,138,当原问题与对偶问题只含有不等式约束时，称为对称形式的对偶。,称为标准的对偶问题:,二、原问题与对偶问题的关系,139,证明：原问题（LP）,定理:(对称性) 对偶问题的对偶是原问题。,对偶问题（LD）,将（LD）化为：,140,根据对称形式的变换关系，求上式的对偶问题是：,即：,141,标准形式的对偶：,142,推导:,原问题化为：,即：,143,根据对称形式的对偶模型,可直接写出上述问题的对偶问题:,144,令 ，得对偶问题为：,145,一般形式的对偶关系用表格表示为：,146,1: 标准对标准 ； 2: 非标准对非标准 ； 3: 等式对无约束 。,求LP的对偶问题的原则

31、是：,例1: 求线性规划问题的对偶问题,147,解：对偶问题为,148,三 、对偶理论的基本定理,设原问题（LP） 对偶问题（LD）,标准化后分别为：,149,1、弱对偶性：若 和 分别是原问题（LP）及对偶问题（LD）的可行解，则有 。,证明：,即,因 和 分别是LP及LD的可行解,所以 和,则 和,150,2、无界性：若原问题(对偶问题）为无界解，则对偶问题(原问题）无可行解。,注意：原问题和对偶问题皆无可行解。,例,151,3、最优性定理： 若 和 分别是（LP）和（LD）的可行解，且有 ，则 和 分别是（LP）和（LD）的最优解 。,证明：若,由弱对偶性（LP）和（LD）的任何可行解

32、X、Y 均满足：,即 和 分别是LP和LD的最优解 。,152,4、对偶定理（强对偶性）：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,证明：LP标准化为,设X为（LP）的最优解， 则其相应最优基B下检验数为：,153,则,就是对偶问题(LD)的可行解,同时，,于是 CX=Y*b,由最优性定理知X，Y*是最优解。,154,5、互补松弛性：若 分别是原问题(LP)与对偶问题(LD)的可行解， 分别为(LP)、(LD)的松弛变量，则 为最优解的充分必要条件是：,证明：（LP）和（LD）标准化为：,155,则有:,必要性：,则,于是,所以,充分性：若,若 为最

33、优解,所以 为最优解,则,156,例2:,157,解：对偶问题为,将y1，y2代入，知(2), (3), (4)为严格不等式, x2 = x3 = x4 = 0,由y1，y20知原约束为等式:, x = (1, 0, 0, 0, 1)T , min W=5,158,6、原问题的检验数行对应对偶问题的一个基解。,证明： （LP）和（LD）标准化为：,设B是原问题的一个可行基，于是A(B,N)，所以原问题可以改写为：,159,当求得原问题的一个解,其相应检验数为：,相应地对偶问题可表示为：,令 ，并将它代入上式得：,160,四 、对偶单纯形法,原问题基可行解 最优解判断,对偶问题的可行解,对偶问题

34、 最优解判断,对偶单纯形法 基本思路,单纯形法的基本思路：,161,对偶单纯形法的计算步骤,线性规划问题,不妨设 为初始对偶可行基，则 。,若 ，即表示原问题和对偶问题均为最优解，否则换基。,162,换基方法：,确定换出基变量 对应变量 为换出变量,确定换入变量,为主元素， 为换入变量,163,初始可行基？,例1：用对偶单纯形法求解线性规划,为初始对偶 可行基,解：标准化为,进一步化为,164,则B=(P4P5)是对偶可行基，用对偶单纯形法求解如下：,要使基变换后还是对偶基可行：,换入,165,因为0，所以为最优解,166,最优解为：y1*=0, y2*=1/4, y3*=1/2, Maxw/

35、=-17/2,minW=17/2.,对偶单纯形法的优点： 不需要人工变量； 在灵敏度分析中，有时需要用对偶单纯形法处理简化。,y1*, y2*, y3*为影子价格。,167,单纯形乘子,称 为资源的影子价格。,代入各自的目标函数后有：,当线性规划原问题求得最优解 时，,其对偶问题也得到最优解 ，,五 、影子价格,168,说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数Z的增量。,影子价格是一种边际价格：,169,这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,在对偶问题的互补松弛性质中有,170,从影子价格的含义上考察检验数的经济意义。,171,几何解释：引例图解法分析,(3,3) ,z=9,(7/2,3/2), z=8.5,(15/4,5/4), z=8.75,172,第五节 灵敏度分析,标准型,利用单纯形法求得最优解。,问题：参数A，b，C中一个或者几个参数发生变化时，对当前方案有无影响？如果有影响，如何用简便方法求新的最优方案？,173, Z0=CBB-1b ， XB=B-1b, A =C-CBB-1A ， N =CN-CBB-1 N j =Cj-CB