《对偶问题的分析》PPT课件.ppt

第三章第三章 线性规划问题的对偶与线性规划问题的对偶与灵敏度分析灵敏度分析线性规划的对偶问题概念、线性规划的对偶问题概念、理论及经济意义理论及经济意义线性规划的对偶单纯形法线性规划的对偶单纯形法线性规划的灵敏度分析线性规划的灵敏度分析本章内容重点1线性规划原问题线性规划原问题 例例2.1:2.1:某某工工厂厂拥拥有有A A、B B、C C三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用用的的时时数数如如下下表表所所示示。求求获获最大利润的方案。最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025002一、对偶问题：一、对偶问题：它的对偶问题就是一个价格系统，使在平衡了它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力最具有竞争力 若另外一个工厂要求租用该厂的设备若另外一个工厂要求租用该厂的设备A A、B B、C C，那么该厂应如何确定合理的租金。，那么该厂应如何确定合理的租金。设设 y y1 1，y y2 2，y y3 3 分别为每工时设备分别为每工时设备 A A、B B、C C 的租金。的租金。线性规划对偶问题线性规划对偶问题3设备的租金收入不能低于自己组织生产设备的租金收入不能低于自己组织生产时的获利收入：时的获利收入：3 3y y1 1+2+2y y2 2 15001500（不少于甲产品的利润）（不少于甲产品的利润）2 2y y1 1+y y2 2+3+3y y3 3 25002500（不少于乙产品的利润）（不少于乙产品的利润）用于生产第用于生产第i种产品的资源转让收益不小种产品的资源转让收益不小于生产该种产品时获得的利润于生产该种产品时获得的利润租方希望在满足上述条件下尽量要求全租方希望在满足上述条件下尽量要求全部设备的总租金越少越好，即部设备的总租金越少越好，即Min W=65yMin W=65y1 1+40y+40y2 2+75y+75y3 34对偶变量的经济意义可以解释为对工时及原材料对偶变量的经济意义可以解释为对工时及原材料对偶变量的经济意义可以解释为对工时及原材料对偶变量的经济意义可以解释为对工时及原材料的单位定价的单位定价的单位定价的单位定价若工厂自己不生产产品若工厂自己不生产产品A、B和和C，将现有的工时，将现有的工时及原材料转而接受外来加工时，那么及原材料转而接受外来加工时，那么上述的价格上述的价格上述的价格上述的价格系统能保证不亏本又最富有竞争力系统能保证不亏本又最富有竞争力系统能保证不亏本又最富有竞争力系统能保证不亏本又最富有竞争力（包工及原材（包工及原材料的总价格最低）料的总价格最低）当原问题和对偶问题都取得最优解时，这一对线当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：性规划对应的目标函数值是相等的：Zmax=Wmin=85原问题的对偶问题原问题的对偶问题DPDP：Min Min W W=65=65y y1 1+40+40y y2 2+75+75y y3 3 .3 .3y y1 1+2+2y y2 2 15001500 2 2y y1 1+y y2 2+3+3y y3 3 25002500 y y1 1,y y2 2,y y3 3 0 06 Max Max z z=1500=1500 x x1 1+2500+2500 x x2 2 s.t.3 s.t.3x x1 1+2+2x x2 2 65 65 2 2x x1 1+x x2 2 40 40 原问题原问题 3 3x x2 2 75 75 x x1 1,x x2 2 0 0 Min Min W W=65=65y y1 1+40+40y y2 2+75+75y y3 3 .3 .3y y1 1+2+2y y2 2 15001500 2 2y y1 1+y y2 2+3+3y y3 3 2500 2500 对偶问题对偶问题 y y1 1,y y2 2,y y3 3 0 0 7原问题求极大化，对偶问题求极小化原问题求极大化，对偶问题求极小化从约束系数矩阵看：一个模型中为，从约束系数矩阵看：一个模型中为，则另一个模型中为则另一个模型中为AT。一个模型是。一个模型是m个个约束，约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个个约束，约束，m个变量。个变量。从数据从数据b、C的位置看：在两个规划模型的位置看：在两个规划模型中，中，b和和C的位置对换。的位置对换。8对偶问题与原问题的对比对偶问题与原问题的对比原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数max目标函数目标函数min不同不同0约束约束0变量变量不同不同条件条件=无约束无约束0变量变量0约束约束相同相同无约束无约束条件条件=9 原原问题（或（或对偶偶问题）对偶偶问题（或原（或原问题）目目标函数函数 MaxZ目目标函数函数 MinF约束条件数：束条件数：m个个 第第 i个个 约 束束 条条 件件 类 型型 为“”第第 i个个 约 束束 条条 件件 类 型型 为“”第第i个个约束条件束条件类型型为“=”对偶偶变量数：量数：m个个 第第i个个变量量0 第第i个个变量量0 第第i个个变量是自由量是自由变量量 决策决策变量数：量数：n个个 第第j个个变量量0 第第j个个变量量0 第第j个个变量是自由量是自由变量量 约束条件数：束条件数：n 第第 i个个 约 束束 条条 件件 类 型型 为“”第第 i个个 约 束束 条条 件件 类 型型 为“”第第i个个约束条件束条件类型型为“=”10 例3.1 写出下面线性规划的对偶规划模型11Maxz=x1-x2+5x3-7x4.x1+3x2-2x3+x4=252x1+7x3+2x4-602x1+2x2-4x330 x4-5 x4 10 x1,x2,0 x3 ,x4取值无约束12Minf=25y160y2+30y3-5y4+10y5.y1+2y2+2y313y1+2y3-60-2y1+7y2-4y3=5 y1+2y2+y4+y5 =-7 y1 取值无约束y3,y50 y2,y4 013对称性定理对称性定理 对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题。主对偶定理主对偶定理若若若若(LP)(LP)和和和和(DP)(DP)均可行，那么均可行，那么均可行，那么均可行，那么(LP)(LP)和和和和(DP)(DP)均有最优解均有最优解均有最优解均有最优解,且且且且最优值相等。最优值相等。最优值相等。最优值相等。如果原问题有最优解，则其对偶问题也一样具有最优如果原问题有最优解，则其对偶问题也一样具有最优如果原问题有最优解，则其对偶问题也一样具有最优如果原问题有最优解，则其对偶问题也一样具有最优解，且有解，且有解，且有解，且有maxz=minwmaxz=minw。二、对偶问题的基本性质二、对偶问题的基本性质14弱对偶定理弱对偶定理若若x,y分别为（分别为（LP)和（和（DP）的可行解，那么）的可行解，那么cTxbTy。推论推论若若LP（或（或DP）可行，那么）可行，那么LP（或（或DP）无有限最优）无有限最优解解(有无界解有无界解)的充分必要条件是的充分必要条件是DP（或（或LP）无可行解。）无可行解。？当？当LP（或（或DP）无可行解时，则）无可行解时，则DP（或（或LP）具有）具有无界解。无界解。极大化问题的任意一个可行解所对应的目标函数值极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。是其对偶问题最优目标函数值的一个下界。极小化问题的任意一个可行解所对应的目标函数值极小化问题的任意一个可行解所对应的目标函数值极小化问题的任意一个可行解所对应的目标函数值极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。是其对偶问题最优目标函数值的一个上界。是其对偶问题最优目标函数值的一个上界。是其对偶问题最优目标函数值的一个上界。15最优性准则定理最优性准则定理若若若若x,yx,y分别分别分别分别(LP)(LP)，(DP)(DP)的可行解的可行解的可行解的可行解,且且且且c cT Tx=bx=bT Tyy，那么，那么，那么，那么x,yx,y分别为分别为分别为分别为(LP)(LP)和和和和(DP)(DP)的最优解。的最优解。的最优解。的最优解。16三、影子价格三、影子价格市场价格市场价格市场价格市场价格影子价格影子价格影子价格影子价格，确切的定义是：，确切的定义是：一个线性规划对偶问一个线性规划对偶问一个线性规划对偶问一个线性规划对偶问题的最优解题的最优解题的最优解题的最优解（简称为（简称为“对偶最优解对偶最优解”）。）。对偶变量对偶变量yi：代表对一个单位第：代表对一个单位第i种资源的估价。种资源的估价。这种估价不是资源的市场价格，而是根据资源在这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价。生产中做出的贡献而作的估价。bi是线性规划原问题约束条件右端项，它代表第是线性规划原问题约束条件右端项，它代表第i种资源的拥有量。种资源的拥有量。17 影子价格是一个向量，它的分量表示最优目影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。标值随相应资源数量变化的变化率。若若x x*,y y*分别为（分别为（LPLP）和（和（DPDP）的最优解，的最优解，那么，那么，c cT T x x*=b bT T y y*。根据根据 w w=b bT Ty y*=b b1 1y y1 1*+b b2 2y y2 2*+b bm my ym m*可知可知 w w/b bi i =y yi i*y yi i*表示表示 b bi i 变化变化1 1个单位对目标个单位对目标W W 产生的影产生的影响，称响，称 y yi i*为为 b bi i的影子价格。的影子价格。18 企企业业可可以以根根据据现现有有资资源源的的影影子子价价格格，对对资资源源的的使使用用有有两两种种考考虑：虑：第第一一，是是否否将将设设备备用用于于外外加加工工或或出出租租，若若租租费费高高于于某某设设备备的的影影子子价价格格，可可考考虑虑出出租租该该设设备备，否否则则不不宜出租。宜出租。第第二二，是是否否将将投投资资用用于于购购买买设设备备，以以扩扩大大生生产产能能力力，若若市市价价低低于于某某设设备备的的影影子子价价格格，可可考考虑虑买买进进该该设备，否则不宜买进。设备，否则不宜买进。19 需需要要指指出出，影影子子价价格格不不是是固固定定不不变变的的，当当约约束束条条件件、产产品品利利润润等等发发生生变变化化时时，有有可可能能使使影影子子价价格格发发生生变变化化。另另外外，影影子子价价格格是是指指资资源源在在一一定定范范围围内内增增加加时时的的情情况况，当当某某种种资资源源的的增增加加超超过过了了这这个个“一一定定的的范范围围”时时，总总利利润润的的增增加加量量则则不不是是按按照照影影子子价价格格给给出出的的数数值值线线性性地地增增加加。这这个个问问题题还还将将在在灵灵敏敏度度分分析析一一节节中中讨论。讨论。20利用最优单纯形表求对偶问题最优解利用最优单纯形表求对偶问题最优解 标准形式：标准形式：Max Max z z=50 =50 x x1 1+100+100 x x2 2 s.t.s.t.x x1 1+x x2 2+x x3 3 =300=300 2 2x x1 1+x x2 2+x+x4 4=400=400 x x2 2+x+x5 5=250 =250 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 0四、对偶问题的解四、对偶问题的解21-c-cB BB B-1-1I IB B=(p p1 1,p,p4 4,p,p2 2)B B-1-1最优解 x1=50 x2=250 x4 =50影子价格影子价格 y y1 1=50 =50 y y2 2=0 =0 y y3 3 =50,=50,y yi i=c cB BB B-1-1 。22线性规划的对偶问题概念、理论线性规划的对偶问题概念、理论及经济意义及经济意义线性规划的对偶单纯线性规划的对偶单纯形法形法线性规划的灵敏度分析线性规划的灵敏度分析23 对偶单纯形法的基本思想对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从一个对对偶偶可可行行解解（检验数非正）出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。24 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。251.1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检所有检验数均非正验数均非正,转转2 2；2.2.若若b b0,0,则得到最优解则得到最优解,停止停止;否则否则,若有若有b bk k00则则选选b b最小最小的基变量为出基变量的基变量为出基变量,转转3 3 3.3.若所有若所有a akjkj0(0(j j=1,2,=1,2,n n)，则原问题无，则原问题无可行解可行解,停止停止;否则否则,若有若有a akjkj0 0 则选则选 =min=min j j/a akjkja akjkj00=r r/a akrkr那么那么 x xr r为入基变量为入基变量,转转4 4；4.4.作矩阵行变换使入基变量变为单位向量，转作矩阵行变换使入基变量变为单位向量，转2 2。26对偶单纯形法的适用范围对偶单纯形法的适用范围 适合于解如下形式的线性规划问题适合于解如下形式的线性规划问题在引入松弛变量化为标准型之后，约束等式两在引入松弛变量化为标准型之后，约束等式两侧同乘侧同乘-1-1，能够立即得到检验数全部非正的原，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。进行求解，非常方便。27例：求解线性规划问题：求解线性规划问题：标准化：标准化：Max z=-2x1-3x2 -4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0 28表格对偶单纯形法29线性规划的对偶问题概念、理论及线性规划的对偶问题概念、理论及经济意义经济意义线性规划的对偶单纯形法线性规划的对偶单纯形法线性规划的灵敏度分析线性规划的灵敏度分析30 进一步理解最优单纯性表中各元素进一步理解最优单纯性表中各元素的含义考虑问题的含义考虑问题 Max Max z=c1 x1+c2 x2+cn xn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 031aij 是随工艺技术条件的改变而改变是随工艺技术条件的改变而改变bi 值是根据资源投入后能产生多大经济值是根据资源投入后能产生多大经济效果来决定的一种决策选择效果来决定的一种决策选择Cj 则是容易受到市场条件的影响则是容易受到市场条件的影响32I IB B-1-1B B=(p p1 1,p,p4 4,p,p2 2)33b=b+bb=B-1bPj=B-1Pjj=cj-CBPj=cj-CBB-1Pj=cj-YTPj34 1.1.价值系数价值系数c c发生变化：发生变化：m 考虑检验数 j=cj-cri arij j=1,2,n i=1例:Max Max z z=2=2x x1 1+3+3x x2 2+0+0 x x3 3+0+0 x x4 4+0+0 x x5 5.x1 1+2x2 2+x3 3=84x1 1+x4 4=164x2 2+x5 5=12x1 1,x2 2,x3 3,x4 4,x5 5035问：问：c c2 2在什么范围内变化，问题的最优解不变在什么范围内变化，问题的最优解不变 30，40可得到 0c24时，原最优解不变。36 2.2.右端项右端项 b b 发生变化发生变化 先求 b，b=B-1b，b=b+b若 b1增加4，最优解有何变化？37 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 b=B B-1*bb=(4,0,0)Tb=(0,-8,2)T b=(4,-4,4)T38用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=1739 3.3.增加一个变量增加一个变量 增加变量增加变量 x xn n+1+1 则有相应的则有相应的p pn n+1+1,c cn n+1+1 。那么那么 计算出计算出p pn n+1+1=B B-1-1p pn n+1+1,n n+1+1=c cn n+1+1-c cri ri a ariri n n+1+1 填入最优单纯形表填入最优单纯形表,若若 n n+1+1 0 0 则则 最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。40例3.6:增加x6,p6=(2,6,3)T,c6=5 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 B B-1p6=(2/3,2,)T41用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f42 4.4.增加一个约束增加一个约束 增加约束一个之后，把最优解带入新的约束，若满足约束条件则最优解不变，否则作为新的一行，填入最优单纯形表，并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。43例3.7:增加3x1+2x215，问最优解有何变化？X=（4，2）T不满足这个约束。首先将约束条件标准化：3x1+2x2+x6=1544 经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为 13.7545 5.5.系数矩阵系数矩阵A A中元素发生变化中元素发生变化 第一种情况第一种情况：若相应的变量xj在最终单纯形表中为非基变量，那么aij的变化分析如下：假设 pj 变化，那么，重新计算出B B-1pj 与 j j=cj-cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。46475.5.5.5.系数矩阵系数矩阵系数矩阵系数矩阵A A A A中元素发生变化中元素发生变化中元素发生变化中元素发生变化第二种情况：第二种情况：若相应的变量在最终单纯形表中为基变量，aij的变化将引起B和B-1发生变化。例：美佳公司计划制造，两种家电，已知各制造一件时，分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各出售一件时的获利情况如下表所示。产品产品 设备能力（h）设备A0 05 51515设备B6 62 22424调试工序1 11 15 5利润（元/件）2 21 148最终单纯型表如下，若家电若家电 每件需设备每件需设备A,BA,B和调试工时变为和调试工时变为8h,4h,1h,8h,4h,1h,该该产品的利润为产品的利润为3 3元元/件，试重新确定该公司的最优生件，试重新确定该公司的最优生产计划。产计划。首先假设增加了变量首先假设增加了变量X X2 2，那么计算其在最终单纯，那么计算其在最终单纯形表中相应的系数列向量与检验数形表中相应的系数列向量与检验数即企业利润最大时生产 7/2件件，3/2件件4911.25-7.5这里B-1=00.25-0.50-0.251.5B-1p2=(11/2,1/2,1/2)T50此时原问题与对偶问题均为非可行解51所以，先将原问题变为可行解x3+4x4-24x5=-9-x3-4x4+24x5+x6=9用此约束等式替代上一个约束等式52可得最优解为（11/4,15/8,0,0,3/8)T53