运筹学基础课件 1

1、主讲教师：,联系电话： 短 号：,E-mail:,清华大学出版社,运筹学教程（第三版）,运筹学基础,胡运权 主编,教材,运 筹 学 课 件 第二章,Linear progranming,对偶理论 与 灵敏度分析,例一,美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少件,使获取的利润为最大。,第一节 线性规划的对偶问题,一、对偶问题的提出,1）标准化,）写出初始单纯形表（假设存在有单位矩阵）,2 1 0 0 0,）最优解检验（唯一解、无限多解、无界

2、解和无解）,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,一个问题？,市场上设备A、设备B和调试工序每小时值多少钱？在什么价位时，可以出租或去租借适当数量的资源来扩大生产规模？,6y2 + y3,分 析,设： y1 设备A值的价值 y2 设备B值的价值 y3 调试工序值的价值,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,总价值,min,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2

3、y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,问题求解,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,Y=(0, , , 0, 0),z=-17/2,z = 17/2,问题求解,Y*=(0, , , 0, 0 ),问题分析,问题 的解,问题：,？,原问题：,问题 的解,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,

4、Z*= 17/2,5*3/2 = 15/2,15,结 论,两个问题的最优解的值一致 最大值问题的最优解是最小值问题的可行解 一个问题的剩余变量（松弛变量） 不为0（即有资源剩余），则对应问题的解为0 一个决策变量不为0，则对应的问题的约束条件的剩余变量(松弛变量) 为0(即无资源剩余),估价影子价格 （即增加单位资源所得到的贡献）,Z= =CX=Yb Z/ b=(Yb) =Y,二、对称形式下对偶问题的一般形式,对称形式的定义,对称形式,X 0,st.,AX b,max z =,CX,其中： C=（c1，c2, ,cn) b=（b1，b2, ,bm)T X=（x1，x2, ,xn)T Y=（y1

5、，y2, ,ym)T,A=,a11 a12 a1n a21 a22 a2n am1 am2 anm,Y 0,st.,ATY CT,min w =,YTb,三、非对称形式的原对偶问题关系,非对称形式？,x1 0, x2 0, x3无约束,st.,a11x1+a12x2+a13x3 b1 a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 b3,max z = c1x1 + c2x2 +c3x3,x1 , x2, x3，x3 0,st.,a11x1 - a12x2 + a13x3- a13x3 b1 a21x1 - a22x2 + a23x3- a23x3 b2 -a

6、21x1 + a22x2 _ a23x3+ a23x3 -b2 -a31x1 + a32x2 - a33x3+ a33x3 -b3,max z = c1x1 - c2x2 + c3x3 - c3x3,y1 , y2, y2 ，y30,st.,a11y1 + a21y2 a21y2 - a31y3 c1 -a12y1 - a22y2+ a22y2 - a32y3-c2 a13y1 + a23y2 a23y2- a33y3 c3 -a13y1 - a23y2+ a23y2+ a33y3-c3,min w = b1y1 + b2y2- b2y2 - b3y3,min w = b1y1 + b2y2

7、+ b3y3,a11y1 + a21y2 + a31y3 c1 a12y1 + a22y2 + a32y3 c2 a13y1 + a23y2 + a33y3 = c3,st.,y10, y2无约束，y3 0,对偶规则 变量、约束与系数,原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反,对偶规则 变量与约束对应关系,第二节 对偶问题的基本性质,X 0,st.,AX b,max

8、z = CX,X, Xs 0,st.,AX + IXs = b,max z = CX + 0Xs,一、单纯形法计算的矩阵描述,B与B-1,Y=(0, , , 0, 0 ),X*=(7/2,3/2, 15/2,0,0),二、原问题和对偶问题解的关系,第二节 对偶问题的基本性质,对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值。P56推论 无界性：原问题有可行解且z无界，对偶问题无可行解。 对偶定理：若原问题与其对偶问题均具有可行解，则两者均具有最优解且最优解对应的目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=

9、CBB-1 互补松弛性：,需要说明的是：这些性质同样适用于非对称形问题,T,T,对偶定理的证明,X 0,st.,AX b,max z = CX,对称形式,Y 0,st.,ATY CT,min w = YTb,原问题为优解0，即：,CB-CBB-1B 0 CN-CBB-1N 0 -CBB-1 0,C - CBB-1A0,令YT= CBB-1,则有：,CBB-1 0,ATY CT Y 0,w = YTb = CBB-1b = z 即此时原问题与对偶问题的解的值是相等的。,则可以得到：,Y*=(0, , , 0, 0 ),互补松弛性：,问题 的解,对偶问题：,？,原问题：,问题 的解,X*=(7/2

10、,3/2,15/2,0,0),Z*= 17/2,Z*= 17/2,5*3/2 = 15/2,15,互补松弛性,当原问题约束0,则yi=0 未充分利用。 yi0,原问题约束为等式。资源得到充分利用，即xsi=0。,第三节 影子价格,一、原问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,二、对偶问题是资源定价问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始

11、和对偶问题都取得最优解时，最大利润 max z=min y,三、资源影子价格的性质,影子价格代表在资源最优利用条件下对单位第i种资源的估价。,市场价格是已知数，相对稳定。影子价格依赖于资源的利用情况，是未知数。因企业生产任务、产品结构等的变化而变化。,资源影子价格是一种边际价格,影子价格越大，说明增加这种资源越带来的z增加越多， 该资源是相对紧缺的。 影子价格越小，说明增加这种资源越带来的z增加越少， 该资源是相对不紧缺的。 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1 w2 wm,影子价格是一种机会成本,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本

12、 表示减少一件产品所节省的资源可以增加的利润,在纯市场经济下，当市场价格y*时，卖出该资源，否则当市场价格y*时，买进该资源。,隐含成本,利润,差额成本,产品的差额成本（Reduced Cost）,差额成本=机会成本 - 利润,第四节 对偶单纯形法,对于单纯形法叠代过程本质：1）确保z变大； 2）B-1b 0,由对偶理论知道，当原问题为最优解时，-0且为对偶问题的最优解，因此人们提出对 偶单纯形法。叠代过程本质：1） 0； 2）逐步使B-1b 0,与,设原问题为 max z=CX AX=b X0 又设B是一个基。不失一般性，令B=（P1,P2,Pm）,它对应的变量为XB=(x1,x2,xm)

13、当非基变量都为0时，可以得到XB=B-1b.若B-1b中至少有一个负分量，设（B-1b）I0,并且在单纯形表的检验数行中得检验数都为非正，即对偶问题保持可行解。 每次迭代是将基变量中的负分量xl取出，取替换非基变量中的xk,经基变换，所有检验数仍保持非正，从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。,对偶单纯形法的计算步骤：,（1）根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则得到了最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行下一步计算。 （2） 确定换出变量按 对应的

14、基变量xl为换出变量。,（3） 确定换出变量 在单纯形表中检查xl所在行的各系数alj0,则无可行解。停止计算。 若存在alj0(j=1,2,n),计算 按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍然为可行解。,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,例一,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y

15、1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,-15 0 -1 -4 0,y2 y5,-24 0,-24 -5,y2 y3,-15 0 0 -7/2 3/2,对偶单纯形法优点,初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 当变量个数多于约束条件个数，对这样的线性规划问题，用对偶单纯形法可以减少计算的工作量。因此对变量较少而约束条件很多的线性规划问题，可以先将它变为对偶问

16、题，然后用对偶单纯形法求解。 在灵敏度分析中,有时需要用对偶单纯形法，可使问题的处理简化。对偶单纯形法的局限性主要是对大多数线性规划问题，很难找到一个初始可行基，因而这方法很少单独使用。,第五节 灵敏度分析,灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,当线性规划问题的系数发生变化时，最优解一般要发生变化，主要有以下几种情况：,当线性规划问题的系数发生变化时，最优解一般要发生变化，主要有以下几种情况：,第五节 灵敏度分析,灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,一、目标函数中价值系数cj的变化分析,可以分别就cj时对应的非基变量和基变量两种情况

17、来讨论。,（1） 若cj是非基变量xj的系数，这时他在计算表中所对应的检验数是 当cj变化cj时，要保证最终表中这个检验数仍然小于或等于零，即 j=cj+cj- CBB-1Pj0 那么cj+cjYPj,即cj的值必需小于或等于YPj-cj,才可以满足原最优解条件，这可以确定cj的变化范围了。,下面就各种情况分别进行讨论。,(2)若cr是基变量xr的系数。因crCB,当cr变化cr时，就引起CB的变化，这时 (CB+CB)B-1A=CB B-1A+(0, cr,0) B-1A = CB B-1A+cr(ar1,ar2,arn) 可见当cr变化cr时，最终表中的检验数是 j=cj - CBB-1A-cjarj,j=1,2,n,若要求原最优解不变，即必需满足j0。于是得到 当arj0，crj/a rj j=1,2,n cr可变化的范围是 例题见书P64,二、资源数量bj变化的分析,资源数量变化是