运筹学第11讲灵敏度分析.ppt
对偶问题的经济解释影子价格,Duality Theory,线性规划的对偶问题,对偶单纯形法,灵敏度分析,对偶问题的基本性质,第二章 线性规划的对偶理论,1、什么是灵敏度分析？是指研究线性规划模型的某些参数(bi,cj,aij）或限制量（xj,约束条件）的变化对最优解的影响及其程度的分析过程。,一、含义和研究对象,s.t.,回答两个问题：,这些系数在什么范围内发生变化时，最优解不变？系数变化超出上述范围，如何用最简便的方法求出新的最优解？,2、灵敏度分析的研究对象：目标函数的系数 cj 变化对最优解的影响；约束方程右端系数 bi 变化对最优解的影响；约束方程组系数矩阵 A 变化对最优解的影响；,一、含义和研究对象,1、在最终单纯形表的基础上进行；2、尽量减少附加的计算工作量；,二、进行灵敏度分析的基本原则,将参数的改变通过计算反映到最终单纯形表上来.检查是否仍为原问题的可行解.检查是否仍为对偶问题的可行解.4.依据不同情况决定继续计算或得到结论.,三、灵敏度分析的步骤,4.分析增加一个约束条件的变化,四、灵敏度分析的主要内容,1.分析 cj 的变化,2.分析 bi 的变化,3.分析增加一个变量 xj 的变化,5.分析系数 aij 的变化,s.t.,对偶问题决策变量的最优解：,初始单纯形表,最优单纯形表,X*=B-1b,CNCBB-1N 0,CBB-1 0,原问题基变量的最优解：,Z*=CBB-1b,最优值：,Y*T=CBB-1,Y*T=CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 cj 的变化,最优值可能已变,分析1和2分别在什么范围变化时，最优解不变？,例1-1,当2=0时，将1 反映在最终单纯形表中，可得,从而，表中解仍为最优解的条件是,即当时问题的最优解不变。,例1-1,分析1和2分别在什么范围变化时，最优解不变？,当1=0时，将2 反映在最终单纯形表中，可得,从而，表中解仍为最优解的条件是,即当时问题的最优解不变。,例1-1,分析1和2分别在什么范围变化时，最优解不变？,美佳公司计划生产I、II两种产品，每天生产条件如表，问(1)该公司应如何安排生产计划才能使总利润最多?(2)若产品的利润降至1.5百元/单位，而产品的利润增 至2百元/单位，最优生产计划有何变化？(3)若产品的利润不变，则产品的利润在什么范围内变 化时，该公司的最优生产计划将不发生变化？,例2-1,例2-1,如何安排生产计划才能使总利润最多？,解：,(1)设x1,x2分别表示、两种产品的生产数量，得LP模型,用单纯形法求解得最终单纯形表,例2-1,如何安排生产计划才能使总利润最多？,解：,(1)设x1,x2分别表示、两种产品的生产数量，得LP模型,用单纯形法求解得最终单纯形表,得最优解为：,X*=(7/2,3/2,15/2,0,0)T,zmax=8.5(百元)。,即每天生产3.5单位产品，1.5单位产品时总利润最多，且,例2-1,产品利润降至1.5百元/单位，产品的利润增至2百元/单位，生产计划如何变化？,解：,(2)将产品、的利润变化反映在最终单纯形表中，可得,因有非基变量的检验数大于零,需继续用单纯形法迭代计算，,例2-1,产品利润降至1.5百元/单位，产品的利润增至2百元/单位，生产计划如何变化？,解：,(2)将产品、的利润变化反映在最终单纯形表中，可得,因有非基变量的检验数大于零,需继续用单纯形法迭代计算，,得最优解为：,X*=(2,3,0,6,0)T,说明随产品利润的改变，为获得最高利润，应将生产计划调整为每天生产2单位产品，3单位产品，且,zmax=9(百元)。,例2-1,解：,(3)将产品的利润变化反映在最终单纯形表中，可得,表中解仍为最优解的条件是,产品的利润在什么范围内变化时，最优生产计划不会发生变化？,即故当产品的利润在 范围变化时，最优生产计划不变。,11+c2,Y*T=CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 cj 的变化,B-1N B-1,Y*T=CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 bi 的变化,最优解或最优值可能已变,分析i分别在什么范围变化时，最优基不变？,例1-2,例1-2,解：,先分析1的变化范围:,为使最优基不变，则需,即,从而得到,同理可得2与3的取值范围,分析i分别在什么范围变化时，最优基不变？,美佳公司计划生产I、II两种产品，每天生产条件如表，问(4)设备A和调试工序每天能力不变，而设备B能力增加到32，问最优生产计划如何变化？(5)若设备A和B的能力不变，调试工序能力在什么范围内变化时，问题的最优基不变？,例2-2,得最优解为：,X*=(7/2,3/2,15/2,0,0)T,例2-2,解：,(4)由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,例2-2,解：,(4)由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,反映到最终单纯形表可得,例2-2,解：,(4)由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,反映到最终单纯形表可得,例2-2,解：,(4)由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,表中原问题为非可行解，用,对偶单纯形法继续计算得,出基,入基,表中原问题为非可行解，用,例2-2,解：,(4)由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,对偶单纯形法继续计算得,最优解为：,X*=(5,0,15,2,0)T,说明随设备B能力的增加，为获得最高利润，应将生产计划调整为每天仅生产5单位产品，且,zmax=10(百元)。,例2-2,解：,调试工序能力在什么范围变化，最优基不变？,(5)由 最终单纯形表，可得,例2-2,解：,(5)由 最终单纯形表，可得,由，计算得,调试工序能力在什么范围变化，最优基不变？,例2-2,因此当调试工序能力在 范围变化时，问题的最优基不变。,调试工序能力在什么范围变化，最优基不变？,为使最优基不变，则需,即,从而得到,55+b3,B-1N B-1,Y*T=CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 bi 的变化,4.分析增加一个约束条件的变化,灵敏度分析的主要内容,1.分析 cj 的变化,2.分析 bi 的变化,3.分析增加一个变量 xj 的变化,5.分析系数 aij 的变化,s.t.,出基变量判断参数,0,单纯形法:保持可行性，调整最优性,基变量的系数,目标函数中变量的系数,决策变量,约束方程组的系数矩阵,方程右端常数项,各变量的检验数,基变量,出发,在迭代运算中设法保持约束常数非负（原问题可行），同时逐个调整检验数，使之全部0（对偶问题可行），得最优解。,终止,有若干个0,0,出基变量判断参数,0,对偶单纯形法:保持最优性，调整可行性,基变量的系数,目标函数中变量的系数,决策变量,约束方程组的系数矩阵,方程右端常数项,各变量的检验数,基变量,迭代运算中设法保持所有检验数（对偶问题可行），把约束常数逐个调整成非负数（原问题可行），得到最优解。,出发,有若干个0,
