运筹学灵敏度分析1.pptx

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