第二章-对偶规划

1、 第 二 章 对偶规划本章主要内容 1. 对偶规划的定义 2. 对偶规划定理 3. 互补松弛关系 4. 对偶单纯形法对偶规划应掌握的主要内容对偶规划的意义对偶规划与原问题的关系对偶规划的定理对偶单纯形法影子价格灵敏度分析第一节 线性规划的对偶问题一、对偶问题的提出 例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500若以上问题的设备都用于外协加工，工厂收取加工费。试问

2、：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题 3x2 75 x1 ,x2 0 Min W = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题 （不少于乙产品的利润） y1, y2 , y3 0 例如，某企业生产甲乙两种产品，生产情况如表：问，如何安排生产使企业获利最大。 甲 乙资源限制原料15615原料22312

3、获利47Max z = 4x1+7x2s.t 5x1 + 6x2 15 2x1 + 3x2 12 x1 、x2 0 甲 乙资源限制原料15615原料22312获利47 甲 乙资源限制原料15615原料22312获利47 还是这个问题，我们从另一个方面考虑该问题。计算企业的成本，购买两种原料各需单位费用为Y1，Y2元如何安排生产使企业总费用最低。Min W = 15Y1+12Y2s.t 5Y1 + 2Y2 4 6Y1 + 3Y2 7 Y1 、Y2 0Max z = 4x1+7x2s.t 5x1 + 6x2 15 2x1 + 3x2 12 x1 、x2 0Min W = 15Y1+12Y2s.t

4、5Y1 + 2Y2 4 6Y1 + 3Y2 7 Y1 、Y2 0对偶问题原问题二、对偶问题的定义设以下线性规划问题Max Z = CXs.t. AX b X0 为原问题，则：Min W = bTY s.t. ATY CT Y0称为原问题的对偶问题。原问题的对偶问题也可表示为 Min W = Y b s.t. YA C Y0其中Y为行向量如果： Min Z =CTXs.t.AX b X0 为原问题，则： Max W =bTY s.t. ATY C Y0称为原问题的对偶问题。 对称形式： 互为对偶 (LP) Max z = cT x (LD) Min W = bT y s.t. Ax b s.t.

5、 AT y c x 0 y 0 “Max - ” “Min- ”三、对偶问题与原问题的关系原问题 Max Z=CX对偶问题 Min W = Yb 变量 n 个 0 0 无限制约束条件 n 个 =约束条件m个 =变量m个 无限制1、对称型对偶问题的关系Max z= 4x1+7x2s.t 5x1 + 6x2 15 2x1 + 3x2 12 x1 , x2 0Min W = 15y1+12y2s.t 5y1 + 2y2 4 6y1 + 3y2 7 y1 , y2 02、非对称型对偶问题的关系Max z= x1+x2+x3s.t x1+x2+x3 15 x1-x2+x3 = 12 2x1+x2+x3

6、1 x1 0 , x2 0 , x3 无限制Min W = 15y1 +12y2 + y3 y1 +y2 + 2y3 1 y1 -y2 +y3 1 y1 +y2 + y3 = 1 y1 0 , y2 无限制 , y3 0 Max z=x1+x2+x3 x1+x2+x3 15 x1-x2+x3 = 12 2x1+x2+x3 1 x1 0, x2 0, x3 无限制 3.写出下面线性规划的对偶规划模型 再根据非对称形式的对应关系，直接写出对偶规划解 先将约束条件变形为“”形式该线性规划的对偶规划模型W原问题 min Z=CX对偶问题Max W =Yb 变量 n 个 0 0 无限制约束条件 n 个

7、=约束条件m个 =变量m个 无限制 Xjyi X1 X2 Xn 原问题关系Min Wy1 y2 ym a11 a12 a1n a21 a22 a2n am1 am2 amn b1 b2bm对偶问题关系 Max Z= Min WMax Z C1 C2 Cn 线性规划原问题与对偶问题的关系(标准式)练习：写出下列线性规划问题的对偶问题. Max z= x1+x2+x3+x+xs.t x1+x2+x3 +x+x x1+x2+x3 +x+x= 2x1+x2+x3+x+x x1 0 , x 0 , x 无限制. Min z = x1-x2-x3 s.t x1 +x2 -x3 = x1 -x2 + x -

8、 x1 - x2+ x3 x1 0 , x2 0 , x3 无限制作业Min第二节 对偶线性规划问题解的性质对偶问题的定理定理一：设 X0 、Y0 是原问题 和对偶问题的任一可行解 Max Z=CX , Min W=Yb AXb YAC X0 Y0 则有： CX0 Y0b原问题对偶问题证明：将式 AXb 同时左乘一个Y0 Y0AX0 Y0b = W 式 YAC同时右乘一个X0 Y0AX0 CX0 = Z CX0 Y0AX0 Y0b CX0 Y0b 最大化的目标函数值不超过最小化的目标函 数值。(弱对偶定理) 原问题的目标函数值是其对偶目标函数值的下限，对偶问题的目标函数值是原问题目标函数值的上

9、限。推论1 如果X0 、Y0 分别是原问题和对偶问题的可行解，并且它们对应的目标函数值相同CX0 = Y0b，则X0 、Y0 分别是原问题和对偶问题的最优解。 推论2： 如果原始问题和对偶问题中的任一个目标函数无界，则另一个必定无可行解。 请注意推论2之逆命题不存在即一个问题无可行解，不能推得另一个问题目标函数无界。 定理二 最优性准则定理(强对偶) 如果X0 、Y0 分别是原始问题和对偶问题的可行解，并且它们对应的，CX0 =Y0b则 X0 、Y0 分别是原始问题和对偶问题的最优解。 证明：由弱对偶性可以看出对原问题和对偶问题可行解的关系 CX0 Y0b，设原问题和对偶问题的最优解为X、Y

10、CX CX0 Yb Y0 b CX0 Y0b CX CX0 Y0 b Yb CX = Yb换句话说：当对偶问题和原问题目标函数值相同时 Z = W ，则 X和 Y一定是对偶问题和原问题的最优解。或者说如果对偶问题和原问题有最优解，那么它们的目标函数值一定相等。定理三、主对偶定理： 如果原问题有最优解，则其对偶问题也有最优解，则它们对应的两个目标函数最优值相等。 如果X0 、Y0 分别是原问题和对偶问题的可行解，并且有最优解，则 X0 、Y0 分别是原始问题和对偶问题的最优解,则它们的最优值相同，即对应的，CX0 =Y0b。原问题与对偶问题解之间的关系1.原问题有确定的最优解,对偶问题就有确定的

11、最优解,且最优值相等;2.原问题有可行解但无最优解,对偶问题无可行解,更无最优解;3.原问题无可行解,对偶问题有可行解但无最优解;4.原问题无可行解,对偶问题无可行解,更无最优解。原问题与对偶问题解的对应关系表问题与解的状态对偶问题有最优解无界解无可行解原问题有最优解一定不可能不可能无界解不可能不可能可能无可行解不可能可能可能定理四、互补松弛定理对偶问题Min W=Yb s.t. YAC Y0设X0 、Y0 分别为原问题和对偶问题的可行解,则X0 、Y0分别为原问题和对偶问题最优解的充要条件是： YSX0=0 和 Y0XS =0原问题Max Z =CX s.t. AX b X0原问题Max z

12、=CX AX +XS= b X ,XS 0 把AX +XS=b 左乘一个YYAX +YXS= YbYb = YAX + YXS 对偶问题Min W=Yb YA-YS= C Y, YS 0 把 YA-YS=C 右乘一个X YAX-YSX = CX CX = YAX - YSX Yb = AXY + XSY CX = AYX - YS X 两式相减W - Z = XSY + YS X如果有最优解 Z = W YSX + XSY = 0 由于非负性 YSX = XSY = 0结论：如果 YSX = XSY = 0 则 X、Y 分别是原问题和对偶问题的最优解。互补松弛定理应用练习Max z= x1+2

13、x2+3x3 +4x4s.t x1+ 2x2+2x3 +3x3 +xS1 = 20 2x1+ x2+3x3 +2x4 +xS2 = 20 xj 0 j=1,24 xs1,2 0 写出其对偶问题:对偶问题为：Min W = 20y1+20y2s.t y1 + 2y2 1 2y1 + y2 2 2y1 + 3y2 3 3y1 + 2y2 4 y1、y2 0用图解法求得最优解: y1 =12， y2 = 02 ,Min W = 28由于松弛互补 YSX = YXS = 0 对偶问题标准化为：Min z = 20y1+20y2s.t y1 + 2y2 - ys1 = 1 2y1 + y2 - ys2

14、= 2 2y1 + 3y2 - ys3 = 3 3y1 + 2y2 - ys4 = 4 y1,y2 ,ys1-s4 0 1、y1 = 12 0， y1 xs1 =0 xs1 = 02、y2 = 02 0， y2 xs2 =0 xs2 = 03、y1+2y2 =16 隐含ys0 x1=04、2y1+y2 = 26 隐含ys20 x2=05、2y1+3y2=3 隐含ys3 = 0 考虑 ys3x3= 0 x3 = 0 或为任意6、3y1+2y2=4 隐含ys4 = 0 考虑 ys4x4= 0 x4 = 0 或为任意据上所述： x1=0， x2=0， x3、x4任意计算x3、x4的值 2x3 +3x

15、3 = 20 3x3 +2x4 = 20得出： x3 = 4， x4 = 4，Max z = 28 定理五：原问题的检验数与对偶问题解的关系定理原问题Max Z = CX AX +XS= b X ,XS 0对偶问题Min W = Yb YA -YS = C Y, YS 0 则原问题单纯形表中的检验数行对应其对偶问题的一个基本解,其对应关系如下表：原问题 Max z = CBXB + CNXN BXB + NXN + XS = b XB、XN、XS0对偶问题 Min W = Y b st: YA-YS= C , YS =(YS1，YS2 )把它分解为： YB-YS1 = CB YN-YS2 =

16、CN Y, YS1，YS2 0注：YS1 原问题中基变量XB的剩余变量， YS2 原问题中非基变量XN的剩余变量。j=CN- CBB-1N= Cj Zj 原问题的检验数令：Y= CBB-1 并把它们代入对偶问题中： YB-YS1 = CBB-1B-YS1 = CB CB-YS1 = CB计算结果： YS1 = 0 （基变量的剩余变量=0） YN-YS2 = CBB-1N-YS2 = CN YS2 = -（CN CBB-1N） 因为是求最小值 YS2 = - j Y, YS1，YS2 0结论：基变量的剩余变量YS1=0，对偶问题非基变量的检验数与原问题非基变量的检验数值相同符号相反， YS2 =

17、 -j 说明对偶问题的检验数只有小于0时才可以继续迭代。 对偶问题最优解是原问题剩余非基变量检验数的相反数 Y= CBB-1具体如下表:原问题变量 XB XN XS原问题检验数0 CN - CB B-1 N =N - CB B-1 =S对偶问题变量YS1=0YS2= - （CN - CB B-1 N ）= - NY= CB B-1 = - S结论：基变量的剩余变量为0，非基变量的剩余变量与原问题的检验数符号相反。对偶问题的基本性质1.弱对偶性两个问题的可行解对应的目标函数值互为上下界。(最大化的目标函数值不超过最小化的目标函数值)2.最优性两个问题最优解的目标函数值必相等。3.强对偶性两个问题

18、都有可行解时则两个问题必都有最优解。4.互补松弛性两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，该定理又称为松紧定理。5.原问题的检验数与对偶问题解的关系6.对称性原始问题与对偶问题是两个互为对偶的问题。已知线性规划问题Max z = 2x1+4x2+ x3 + x4s.t x1 + 3x2 + x4 8 2x1 + x2 6 x1 + x2 + x3 9 x2 + x3+ x4 6 x1401.试写出该问题的对偶问题。2.已知原问题的最优解为X=2 2 4 0T 。试根据对偶理

19、论，直接求出对偶问题的最优解。第三节 对偶单纯形法一、对偶单纯形法的基本思想二、对偶单纯形法及特点三、对偶单纯形法的求解步骤和计算举例四、对偶单纯形法和单纯形法区别五、对偶单纯形法的适用范围六、对偶单纯形法的优点一、对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原问题的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形

20、法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基本解由不可行逐步变为可行，当同时得到对偶问题与原问题的可行解时，便得到原问题的最优解。对偶单纯形法在什么情况下使用 ：应用前提：有一个基，其对应的基满足:1.单纯形表的检验数行全部非正（对偶可行）；2.变量取值可有负数（非可行解）。注： 通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。 二、对偶单纯形法及特点1.对偶单纯形法 利用对偶原理求解原问题的一种方 法。而不是用单纯形法求解对偶问 题。(不是对偶问题的单纯形法)2.对偶单纯形法的特点： 1、始终保持原问题的可行性 2、始终保持检验数的非正 3、在迭代过

21、程中直到基变量取值(常数项)逐渐变为非负为止。例： Min w = X1+4X2 +3X4s.t X1+2X2-X3 + X4 3 -2X1-X2+4x3 + X4 2 X1 X4 0该问题可以用两阶段法或大M法(人工变量法)求解，但很麻烦，下面用对偶单纯形法求解。三、对偶单纯形法的求解步骤和计算举例1.把原问题化标准型2.给定一个初始对偶可行的基本解,建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转3；3.进行最优性检验:若b0,则得到最优解,停止;若所有akj0( j = 1,2,n )，则原问题无可行解,更无最优解,停止;否则若有akj0,则转4 ；4.换基迭代(1)首先确定出

22、基变量: 出基用限定性常数进行判断，若有b0,取min(b)所对应的k行的基变量为出基变量XK ,转5 ；(2)确定入基变量： 入基若所有akj0( j = 1,2,n )，则原问题无可行解,更无最优解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么所对应的变量xr为进基变量,转5；5.换基迭代运算以akr为主元素,作矩阵行变换使其变为1,该列其他元素变为0,转3。6.进行最优性检验:最优解： 基变量的检验数为0 非基变量的检验数小于等于0 限定性常数大于0得出原问题与对偶问题的最优解和最优值7.否则转4,重复进行。8.对于非对称型对偶问题的解与原问题检验数的关

23、系需要换算。 Min w = X1+4X2 +3X4s.t -X1-2X2+ X3-X4 -3 2X1+ X2-4x3-X4 -2 X1 X4 0 Max - w = -X1-4X2 -3X4 -X1-2X2+ X3-X4 +X5 = -3 2X1+ X2-4x3-X4 + X6 = -2 X1 X6 0 Cj -1 -4 0 -3 0 0bCBXB X1 X2 X3 X4 X5 X6 0 0X5X6 -1 -2 1 -1 1 0 2 1 -4 -1 0 1 -3 -2j -1 -4 0 -3 0 0Z= 0 Cj -1 -4 0 -3 0 0bCBXB X1 X2 X3 X4 X5 X6-1

24、 0X1X6 1 2 1 -1 -1 0 0 -3 -2 -3 2 1 3 -8j 0 -2 -1 -2 -1 0Z= -3 Cj X1 X2 X3 X4 X5 X6b CB XB -1 -4 0 -3 0 0-10X1X6 1 2 1 -1 -1 0 0 -3 -2 -3 2 1 3-8j 0 -2 -1 -2 -1 0Z= -3 Cj X1 X2 X3 X4 X5 X6b CB XB -1 -4 0 -3 0 0-1 0X1X3 1 7/2 0 2/5 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 4j 0 -2 -1 -2 -1 0Z= -7练习:Min W = 2x1 +

25、 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + 3x3 4 x1 , x2 , x3 0 标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0四、对偶单纯形法和单纯形法区别单纯形法:1.求解原问题2.建立初始单纯形表3.可行基4.基本可行解5.凸集顶点开始6.初始单纯形表最终表7.可行基 最优基8.基本可行解 迭代基本可行解(最优解)9.凸集顶点 迭代凸集顶点对偶单纯形法:1.求解原问题2.建立初始对偶单纯形表3.对偶可行基4.对偶

26、可行的基本解5.非凸集顶点开始6.初始对偶单纯形表最终表7.对偶可行基 最优基8.非可行解 迭代基本可行解(最优解)9.非凸集顶点 迭代凸集顶点10. b0 j0 b 0 j 010. b 0, j 0 b 0 j 0单纯形法:对偶单纯形法:是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法五、对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题W 在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的问题

27、基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。六、对偶单纯形法的优点1.可尽量避免人工变量法2.减少计算工作量第 四 节 对偶问题的经济解释 影子价格一、对偶问题的经济解释（影子价格）1.影子价格的概念： 在最优决策中，增加某种资源的投入时，目标函数的提高量，称为这种资源的影子价格。也就是说影子价格反映的是

28、增加单位的投入与带来的产出量之间的关系。影子价格也称机会价格 Max Z = CX= YbY 表示资源在生产中的价格，而不是市场价，b 表示资源的数量，当价格发生变化是对目标函数值的影响，Y 的这种变化对目标函数的影响称为影子价格。对偶问题是资源定价问题，对偶问题的最优解Y称为m种资源的影子价格（Shadow Price）增加单位资源可以增加利润减少一件产品可以节省资源减少一件产品可以节省的资源可以增加利润 如果线性规划问题的最优基为B，则最优解： XB = B-1b Z=CB B-1b 对偶问题： Y= CB B-1 W=Yb=CB B-1b 如果资源增加b则目标函数的增量为：Z= CB B

29、-1b = Yb当b=1时 Z = Y Z = Y Z/b=(yb)=y说明对偶问题的最优解，既为原问题目标函数的增加量。 Y即影子价格Y值是原问题剩余松弛变量检验数的相反数影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价。 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。（2） 影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（LP）和对偶

30、规划（LD）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2， ,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过

31、了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。.资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 。.产品的机会成本产品的机会成本 C C =YA Y0其中Y为行向量 产品的机会成本表示减少一件产品可以节省的资源可以增加利润。.产品的差额成本（Reduced Cost）产品的差额成本=产品的机会成本利润= C C =YA Cj产品的差额成本（就是对偶问题的剩余变量的值）.资源的边际利润第i种资源的边际利润最大利润的增量/第

32、i种资源的增量 /biyi (就是资源影子价格)二、互补松弛关系的经济解释最优解之间的关系互补松弛关系在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产 A A A 资源限量资源B 1资源B资源B资源B 2 1 3 1 2 2 3 4 1 2 3 2 200 350 220 400利润 4 3 5三、练习：某企业生产情况如表，试求企业获得最大利润的生产计划安排。 Cj X1 X2 X3 X4 X5 X6 X7 b CBXB 4 3 5 0 0 0 00000X4 X5 X6 X7

33、2 1 3 1 0 0 0 1 2 2 0 1 0 0 3 4 1 0 0 1 0 2 3 2 0 0 0 1200350220400 Cj X1 X2 X3 X4 X5 X6 X7 bCBXB4 3 5 0 0 0 05000X3 X5 X6 X72/3 1/3 1 1/3 0 0 0-1/3 4/3 0 -2/3 1 0 07/3 11/3 0 -1/3 0 1 02/3 7/3 0 -2/3 0 0 1200/3650/3460/3800/3j4 3 5 0 0 0 0Z=j/Z= 1000/3 Cj X1 X2 X3 X4 X5 X6 X7 bCBXB4 3 5 0 0 0 05030

34、X3 X5 X2 X75/11 0 1 4/11 0 1/11 0-13/11 0 0 -6/11 1 4/11 07/11 1 0 -1/11 0 3/11 09/11 0 0 -5/11 0 -7/11 1580/111770/11460/111860/11经过运算的最终结果为下表：X1 = 0， X2 = 460/11= 418， X3 = 580/11= 52 7， X4 = 0，X5 = 177/11=16.， X6 = 0 X7 = 1860/11=169. ， Z = 389j-2/11 0 0 -17/11 0 -4/11 0Z= /试问：1、影子价格是多少？2、哪种资源有剩余

35、？资源的剩余量是多少？3、机会成本是多少？4 、差额成本是多少？5、资源的边际利润是多少？1、影子价格： y1=17/11， y2=0 y3=4/11 y4=02、资源的剩余量： X = b1=200- (2x1 +x2 +3x3 ) = 0 X= b2=350- (x1 +2x2 +2x3 ) = 160 9 X= b3=220- (3x1 +4x2 +x3 ) = 0 X= b4=400- (2x1 +3x2 +2x3 )=169 3、对偶问题的最优解：y1=17/11 y2=0 y3=4/11 y4=0y=/y=0y= 4、通过对偶关系计算机会成本：C1=2y1 + y2 +3y3 +2

36、y4 = 418C2= y1 +2y2 +4y3 +3y4 = 30C3=3y1 +2y2 + y3 +2y4 = 50 产品资源A1 A2 A3 资源限量 (吨)资源剩 余 (吨)影子价格(万元/吨)B1B2B3B42 0 1 0 3 01 0 2 0 1 03 0 4 0 1 02 0 3 0 2 0200350220400 016090 016909 17/11 0 4/11 0利润C4 0 30 50 Max Z= Min W=389机会成本418 30 50差额成本0 18 0 0产品数量0 41 8 52 7 休息一会 对偶问题的经济解释包括两个方面的内容： 1、最小成本问题 2、

37、最大利润问题第五节 灵敏度分析 以前我们所讨论的问题是都假设A、b、C是常数时的情况，但是，实际这些值都具有一定的波动性，当它们某些系数发生变化时，线性规划最优解是否会受到影响，影响的范围有多大。这就是这节要解决的灵敏度分析问题。目标函数系数灵敏度分析 限定性常数的灵敏度分析 技术系数变化灵敏度分析增加新的变量灵敏度分析增加约束条件灵敏度分析一、目标函数的系数的灵敏度分析Max Z=CX , AXb X0求解Z = CBB-1bXB = B-1b,从求得的结果看： 1、价值系数的变化并不影 响基变量的取值 2、 对于目标函数的最优值来说： 非基变量的价值系数的变化对目标函数无影响， 基变量的目

38、标函数的系数的变化就要引起注意。它主要影响检验数的变化，它涉及的是基变量和非基变量的检验数。j= CN - CBB-1N 0 CB = CB+Crj*= CN - (CB+Cr )B-1Nj*= CN CBB-1N - Cr B-1 NNj*= j - Cr B-1N讨论：如果j* 0，则对目标函数无影响，若j* 0，就必须要求使得j* 0 时， 看Cr的变化范围，这时对目标函数将无影响。所以，保证： j-Cr B-1 N 0 Cr B-1N j 令： B-1N = aij Cr aij j讨论：如果 aij 0， Cr j / aij aij 0， Cr j / aij j aij aij

39、0 Cr j aij aij 0例： Max z = 2X1-X2 +X3 s.t X1 + X2 + X3 6 -X1 + 2X2 4 X1 X3 0Min Max Cj X1 X2 X3 X4 X5 b CB XB 2 -1 1 0 000X4 X5 1 1 1 1 0-1 2 0 0 1 6 4j 2 -1 1 0 0Z=0 Cj X1 X2 X3 X4 X5 bCB XB 2 -1 1 0 0 20X1 X5 1 1 1 1 0 0 3 1 1 1 6 10j 0 -3 -1 -2 0Z=12 Cj X1 X2 X3 X4 X5 b CB XB 2 -1+C2 1 0 020X1 X5

40、 1 1 1 1 0 0 3 1 1 1 610j 0 -3 -1 -2 0Z=12令： X2的价值系数增加C2 X2（非基变量）的系数增加C2 ，我们主要判断检验数是否发生变化： 如果 j 0 , 即-3+C2 0, C2 3C2 2,则最优解不发生变化，如果 j 0 则最优解发生变化，此时利用单纯形法求新的最优解，以X为换入变量，并按最小比原则找到换出变量进行迭代，直至所有的检验数j非正为止。-3+C2 0, 即+C2 3时,即C2 2时最优解发生变化.若C2 = -8C2 = -5C2 = -3C2 = -2C2 = 0C2 = 1C2 = 2C2 = 3C2 = 8C2 = C2 =

41、12C2 = 20最优基有何变化最优解有何变化最优值有何变化价值系数C发生变化： 考虑检验数 j = C- CBB-1 A j =1,2,n 1. 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。练习: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0最优单纯形表从表中看

42、到3= C3+C3-(C2a13+C1a23 ) -5/9+C3 0可得到C3 9/5 时，原最优解不变。Cj Cj 2.基变量的价值系数发生变化时例： Max z = -X1-X2 +4X3 s.t X1+ X2+2X3 9 X1+ X2 -X3 2 -X1+ X2 +X3 4 X1 X3 0 Cj-1 1 4 0 0 0 b CB XBX1 X2 X3 X4 X5 X6-10X1X5 X31 - 1/3 0 1/3 0 2/3 0 2 0 0 1 10 2/3 1 1/3 0 1/31/3 613/3j0 -4 0 -1 0 -2Z= 17经运算得如下最优表：现基变量X1的系数增加了C1

43、Cj -1+C1 -1 4 0 0 0 b CBXB X1 X2 X3 X4 X5 X6-1 0 4X1 X5 X31 -1/3 0 1/3 0 2/3 0 2 0 0 1 10 2/3 1 1/3 0 1/31/3 613/3j0 -4 0 -1 0 -2 Z=17 现基变量X1的系数增加了C1 Cr j aij aij 0 j aij aij 0 MaxMin j aij = -4 -1 -2 -1/3 1/3 -2/3= 12 -3 3 C1的原系数为- 1，把它加到两边即得到：-4 C1 2-3 C1 3 C1的原系数为- 1，把它加到两边即得到：-4 C1 2-3 C1 3则最优解不

44、发生变化则最优解发生变化 若C1 2或 C1 -4 则用单纯形法继续迭代运算求出新的最优解试问:基变量X1的系数增加了C1基变量X5的系数增加了C5基变量X3的系数增加了C3非基变量X2的系数增加了C2非基变量X4的系数增加了C4非基变量X6的系数增加了C6 Cr j aij aij 0 j aij aij 0 MaxMin j aij = -4 -1 -2 2 0(不比) 1 = - 2 -2 C5的原系数为0，把它加到两边即得到： -2 C5 -2 C5 则最优解不发生变化 Cr j aij aij 0 j aij aij 0 MaxMin j aij = -4 -1 -2 2/3 1/3

45、 1/3= - 6 -3 - 6 C3的原系数为4，把它加上即得到： 1 C3 -3 C3 则最优解不发生变化X2（非基变量）的系数增加C2 ，我们主要判断检验数是否发生变化： 如果 j 0 , 即2 = -4+C2 0 , C2 4C2 3则最优解不发生变化如果 j 0 则最优解发生变化，此时利用单纯形法求新的最优解，以X为换入变量，并按最小比原则找到换出变量进行迭代，直至所有的检验数j非正为止。2 0即C2 4时,即C2 3时最优解发生变化.X4（非基变量）的系数增加C4 ，我们主要判断检验数是否发生变化： 如果 j 0 , 即4 = 0+C4 (-1) 1/3 +00 +41/3 0,

46、-1 +C4 0,C4 1C4 1则最优解不发生变化如果 j 0 则最优解发生变化，此时利用单纯形法求新的最优解，以X4为换入变量，并按最小比原则找到换出变量进行迭代，直至所有的检验数j非正为止。4 0即C4 1时,即C4 1时最优解发生变化.X6（非基变量）的系数增加C6 ，我们主要判断检验数是否发生变化： 如果 j 0 , 即6 = 0 +C6 (-1) (-2/3) +01 +41/3 0, -2 +C6 0, C6 2C6 2则最优解不发生变化如果 j 0 则最优解发生变化，此时利用单纯形法求新的最优解，以X6为换入变量，并按最小比原则找到换出变量进行迭代，直至所有的检验数j非正为止。

47、6 0即C6 4时,即C6 2时最优解发生变化.练习:Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0 下表为最优单纯形表,考虑基变量系数c2发生变化从表中看到(3/a23 = -1.5/1/2= -3, 4/a24 = -1/8/-1/8=1)j=cj-(c1a1j+c5 a5j+(c2+c2) a2j),j=3,4可得到 -3c21时，原最优解不变。二、右边常数的灵敏度分析 当右边常数向量b发生变化，成为b= br

48、+br时，对变量检验数与目标函数中的系数没有影响 (j=Cj-Zj = CN CBB-1N) 。当XB = B-1（b+br） 0 时，最优表中变量检验数不变，则原来的最优基仍为最优基，即最优基不变。只是最优解发生变化,最优值也发生变化。 当XB = B-1（b+br） 0，即基变量中存在负数，则最优基发生变化。最优解发生变化,最优值也发生变化。由于右边常数向量b发生变化不影响检验数，故仍保持所有检验数都 0，只会影响最优基的原始可行性而不会影响其对偶可行性。原来的基成为对偶可行基但不是原始可行基，即满足对偶可行性。现行的基本解为对偶可行的基本解，这时要用对偶单纯形法求得新的最优基。最优解，最

49、优值。 小结当XB = B-1（b+br） 0 ，最优基不变。最优解发生变化,最优值发生变化。当XB = B-1（b+br） 0 ，最优基发生变化,最优解发生变化,最优值发生变化。当：XB = B-1（b+br） 0 限定性常数的变化范围XB = B-1 b+ B-1 br 0 XB = b+ B-1 br0 air br - b air br - b 讨论：如果 air 0br- bair air 0讨论：如果 air 0 br - bair air 0 结论：br - biairair 0- biairair 0 上例，如果右边的的第一种资源增加了一个b1时，目标函数在什么情况下获利更多？

50、MaxMin右端项 b 发生变化 设分量 br 变化为 br + br ，根据第1章的讨论，最优解的基变量 xB = B-1b，那么只要保持 B-1(b + b) 0 ，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。 例： Max z = -X1-X2 +4X3 s.t X1+ X2+2X3 9 X1+ X2 -X3 2 -X1+ X2 +X3 4 X1 X3 0试问:1.b1在什么条件下,原来的最优基仍为最优基。.b1在什么条件下,原来的最优基发生变化。CjX1 X2 X3 X4 X5 X6 b CB XBX1X5 X31 1/3 0 1/3 0 - 2/30

51、 2 0 0 1 10 2/3 1 1/3 0 1/31/3+b1 613/3 -1/3 -6 -13/3 1/3 0(不比)1/3 b1= - 1 ， -13j0 4 0 1 0 2 Z= 17这里 B-1 = XB = B-1 b+ B-1 b = B-1 b = + = =/ 0 - 2/3 1 / 0 1/3/ 0 -2/3 1/ 0 1/3b1/ b1/ b1/ /b1 / /b1 XB = B-1 b+ B-1 b = B-1 b 所以，取 b1 -1 , b1 9-1=8 当第一种资源b1 8 时，原最优基不变；当第一种资源b1 8时，原最优基发生变化；如果b1 0 ， 且b1

52、8则用单纯形法求之；如果b1 0 ，则用对偶单纯形法求之。试问:3.b2在什么条件下,原来的最优基仍为最优基。4.b2在什么条件下,原来的最优基发生变化。这里 B-1 = XB = B-1 b+ B-1 b = B-1 b = + = =/ 0 - 2/3 1 / 0 1/3/ 0 -2/3 1/ 0 1/3 b2 / 1 b2 0/ 0 1 b2 / 0 -1/3 -6 -13/3 b2 = = - 6 0(不比) 1 0(不比) XB = B-1 b+ B-1 b = B-1 b 所以，取 b2 -6 , b2 2-6= - 4 当第2种资源b2 -4时，原最优基不变；当第2种资源b2 -

53、4时，原最优基发生变化 ，则用对偶单纯形法求之。试问:5.b3在什么条件下,原来的最优基仍为最优基。6.b3在什么条件下,原来的最优基发生变化。这里 B-1 = XB = B-1 b+ B-1 b = B-1 b = + = =/ 0- 2/3 1 / 0 1/3/ 0 -2/3 1 / 0 1/3 0b3/-2/3 b30 1/3 b3/ - 2/3 b3 0/ 1/3 b3 -1/3 -6 -13/3 b3 = = 2 - 13 - 2/3 0(不比) 1/3XB = B-1 b+ B-1 b = B-1 b 所以，取 - 13 b3 2 , - 9 b3 6 当第3种资源- 9 b3 6

54、时，原最优基不变；当第3种资源b3 -9或b3 6时，原最优基发生变化；当第3种资源b3 -9时，则用对偶单纯形法求之。当第3种资源b3 6时，则用单纯形法求之。例:Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0 最优单纯形表如下各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4b 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 XB = B-1 b+ B-1 b =

55、B-1 b = + = =4420 0.25 0-2 0.5 10.5 -0.125 0- x1 x5 x2 则 x1 ,x5 ,x2分别变为：x1 = 4+04=4,x5 = 4+(-2)4=-40 x2 = 2+0.54=4因为XB = B-1 b+ B-1 b = B-1 b 中存在负数,则最优基发生变化用对偶单纯形法进一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T ， W* = 17三、 增加一个新的变量 当前最优基是B。设新增加的变量xj在目标函数中的系数为cj，在约束中的系数向量是pj，计算 aj=B-1 pj Cj-Zj = Cj CBB-1pj， 在最优表中增加一个新的变量以Xn+1及新的一列Pn+1，Cn+1 ，将以上系数计算B-1 Pn+1，然后置于最优表中，构成新的单纯形表。判断其检验数，若新变量的j=cj - zj 0 则原来的基仍为最优基，原来的基变量以及基变量的值保持不变，Xn+1=0 。cj-zj 0 则xj进基，用单纯形法继续运行，直至获得新的最优基和最优解。 增加一个变量增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B-1pn