运筹学课件灵敏度分析.pptx

运筹学教程2、灵敏度分析的内容：、灵敏度分析的内容：目标函数的系数变化对最优解的影响；目标函数的系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程组系数阵变化对最优解的影响约束方程组系数阵变化对最优解的影响；回答两个问题回答两个问题：运筹学教程这这些些系系数数在在什什么么范范围围内内发发生生变变化化时时，最最优优基不变（即最优解或最优解结构不变）？基不变（即最优解或最优解结构不变）？系系数数变变化化超超出出上上述述范范围围时时，如如何何用用最最简简便便的方法求出新的最优解？的方法求出新的最优解？二、二、进行灵敏度分析的基本原则进行灵敏度分析的基本原则1 1、在最优单纯形表的基础上进行；、在最优单纯形表的基础上进行；2 2、尽量减少附加计算工作量；、尽量减少附加计算工作量；运筹学教程3 3、灵敏度分析的步骤：、灵敏度分析的步骤：（1 1）将参数的改变通过计算反映到单纯形表。）将参数的改变通过计算反映到单纯形表。参参数数a aijij,b,bi i,c,cj j的的变变化化引引起起的的单单纯纯形形表表上上的的有有关关数字的变化：数字的变化：运筹学教程（2 2）、检查原问题是否仍为可行解。）、检查原问题是否仍为可行解。（3 3）、检查对偶问题是否仍为可行解。）、检查对偶问题是否仍为可行解。原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题最优解或最优基不变问题最优解或最优基不变单纯形求解最优解单纯形求解最优解对偶单纯形求解最优解对偶单纯形求解最优解引进人工变量，新单纯形引进人工变量，新单纯形表重新计算表重新计算运筹学教程三、三、灵敏度分析举例：灵敏度分析举例：例例1-1引入非负的松弛变量引入非负的松弛变量x3,x4,x5,将该将该LP化为化为标准型标准型：运筹学教程用单纯形法求解如下：用单纯形法求解如下：运筹学教程Cj 2 1 0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21 x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2运筹学教程1、价值系数、价值系数Cj变化变化（1）当）当cj是非基变量的价值系数是非基变量的价值系数它的变它的变化只影响化只影响一个检验数一个检验数。例：例：c4发生变化时，发生变化时，最优解不变，最优解不变否否则则0,可可使使用用原原单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解。的最优解。运筹学教程（2）当当cj是是基基变变量量的的价价值值系系数数它它的的变变化化将影响所有非基变量的检验数将影响所有非基变量的检验数.当当cj变变化化时时，如如能能保保持持，则则当当前前解解仍仍为为最最优优解解，否否则则可可用用单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解的最优解。运筹学教程例例1-1:(1)1-1:(1)如果产品如果产品1 1的利润降至的利润降至1.51.5元元/件，产品件，产品2 2的利润增加的利润增加至至2 2元元/件，工厂的最优生产计划？件，工厂的最优生产计划？（2 2）如果产品）如果产品1 1的利润不变，则产品的利润在什么范围内变的利润不变，则产品的利润在什么范围内变化，工厂的最优生产计划不变？化，工厂的最优生产计划不变？Cj 1.5 2 0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/21.5 x1 7/2 2 x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 1/8 -9/4解（解（解（解（1 1 1 1）将产品）将产品）将产品）将产品1 1 1 1，2 2 2 2的利润变化直接反映到单纯形表的利润变化直接反映到单纯形表的利润变化直接反映到单纯形表的利润变化直接反映到单纯形表运筹学教程Cj 1.5 2 0 0 0CB 基基 b X1 x2 x3 x4 x50 x4 61.5 x1 22 x2 30 0 4/5 1 -61 0 -1/5 0 10 1 1/5 0 0 Cj-Zj0 0 -1/10 0 -3/2随利润的变化，调整如下：随利润的变化，调整如下：随利润的变化，调整如下：随利润的变化，调整如下：生产产品生产产品生产产品生产产品1 1 1 1为为为为2 2 2 2件，产品件，产品件，产品件，产品2 2 2 2为为为为3 3 3 3件。件。件。件。运筹学教程解（解（解（解（2 2 2 2）设产品）设产品）设产品）设产品2 2 2 2的利润的利润的利润的利润1+1+1+1+直接反映到单纯形表直接反映到单纯形表直接反映到单纯形表直接反映到单纯形表Cj 2 1+0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21+x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4+/4 -1/2-3 /2运筹学教程运筹学教程2、分析、分析bi（右端常数）变化：右端常数）变化：当当bi发生变化时，将影响所有基变量的取值。发生变化时，将影响所有基变量的取值。因为因为：若若bi的变化的变化保保持持B-1b0,当当前前的的基基仍仍为为最最优优基基，最最优优解解的的结结构构不变（取值改变）；不变（取值改变）；（B-1b）12(3/2)=27/212(3/2)=27/212(3/2)=27/212，不不不不满满满满足足足足该该该该约约约约束束束束，所所所所以以以以原原原原问问问问题题题题的的的的最最最最优优优优解解解解不不不不是是是是现现现现在在在在LPLPLPLP的的的的最最最最优优优优解解解解；将将将将约约约约束束束束条条条条件件件件标标标标准准准准化化化化后后后后加加加加入入入入原原原原最最最最优优优优表表表表格格格格，3 3 3 3x x x x1 1 1 1+x+x+x+x2 2 2 2+x+x+x+x6 6 6 6=12=12=12=12，进进进进行行行行初初初初等等等等行行行行变变变变换换换换，然然然然后用后用后用后用对偶单纯形法迭代对偶单纯形法迭代对偶单纯形法迭代对偶单纯形法迭代求出新的最优解。求出新的最优解。求出新的最优解。求出新的最优解。Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/21 x2 3/20 x6 120 0 1 5/4 -15/2 01 0 0 -1/2 00 1 0 -1/4 3/2 03 2 0 0 0 1Cj-Zj0 0 0 -1/4 -1/2 0X X X X1,x,x,x,x2列非单位向量列非单位向量列非单位向量列非单位向量r r2x(-3)+rx(-3)+r4r r3x(-1)+rx(-1)+r4运筹学教程Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/21 x2 3/20 x6 -3/20 0 1 5/4 15/2 01 0 0 -1/2 00 1 0 -1/4 3/2 00 0 0 -1/4 -3/2 1Cj-Zj0 0 0 -1/4 -1/2 0对对对对偶偶偶偶问问问问题题题题为为为为可可可可行行行行解解解解，原原原原问问问问题题题题为为为为非非非非可可可可行行行行解解解解，采采采采用用用用对对对对偶偶偶偶单单单单纯形法计算。纯形法计算。纯形法计算。纯形法计算。Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 152 x1 41 x2 00 x5 10 0 1 5/2 0 -51 0 0 1/3 0 -1/30 1 0 -1/2 0 10 0 0 1/6 1 -2/3Cj-Zj0 0 0 -1/6 0 -1/3添添加加试试验验工工序序后后，最最优优的的生生产产计计划划仅仅生生产产1 1产品产品4 4件。件。运筹学教程小结：小结：1 1、线线性性规规划划模模型型某某些些参参数数或或限限制制量量的的变变化化对对最最优优解解的的影影响响及及其其程程度度的的分分析过程称为灵敏度分析。析过程称为灵敏度分析。2 2、分分析析价价值值系系数数Cj的的变变化化、bi（右右端端常常数数）变变化化、增加一个变量xj、参参数数aij的的变变化化以以及及增增加加1 1个个约约束束条条件件对对线线性性规划的最优结构所造成的影响规划的最优结构所造成的影响。运筹学教程思考题：思考题：如如何何分分析析当当线线性性规规划划的的价价值值系系数数Cj、资资源源项项bi、工工艺艺系系数数aij变变化化时时，LPLP最最优优解解（或或最最优优基基或或最最优优结结构构）有何改变有何改变？运筹学教程作业：作业：2.112.11