《运筹学08-对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学08-对偶理论与灵敏度分析.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第8讲 对偶理论与灵敏度分析IIISchoolofBusinessECUST灵敏度分析灵敏度分析o在以前在以前讲的的线性性规划划问题中，中，aij,bi,cj均均为已知常数，但已知常数，但实际上上这些数往往是一些估些数往往是一些估计和和预测的数字，如随市的数字，如随市场条件条件变化，化，cj的的值就会就会变化；化；aij也会随工也会随工艺条件的改条件的改变而改而改变，bi是各是各项资源的投入数量，随着企源的投入数量，随着企业资金水平的金水平的变化也会化也会变化。化。o因此，就会提出以下因此，就会提出以下问题：当：当这些参数中的一个或几个些参数中的一个或几个发生生变化化时，问题的最的最优解会有什
2、么解会有什么变化，或者化，或者这些参些参数在多大范数在多大范围内内变化化时，问题的最的最优解不解不变。这就是灵就是灵敏度分析所要研究和解决的敏度分析所要研究和解决的问题。一、目标函数中价值系数一、目标函数中价值系数cj 的变化分析的变化分析非基变量在目标函数非基变量在目标函数中系数的灵敏度分析中系数的灵敏度分析 基变量在目标函数中基变量在目标函数中系数的灵敏度分析系数的灵敏度分析 目标函数中价值系数目标函数中价值系数 c cj j 的变化会引起非基变量检的变化会引起非基变量检验数的变化，从而影响最优性条件能否成立。验数的变化，从而影响最优性条件能否成立。1.若若cj 是非基是非基变量的系数量的
3、系数n若若cj 是非基变量的系数，则是非基变量的系数，则cj 的变化仅影响非基变量的变化仅影响非基变量xj的检验数的检验数 ，设，设 ，则变化后，非基变量，则变化后，非基变量xj的检验数为：的检验数为：n若若 成立，成立，则最优性条件保持不变，则最优性条件保持不变，cj的改变不会对最优解产生影响。的改变不会对最优解产生影响。SchoolofBusinessECUST2.若若cr 是基是基变量的系数量的系数n若若cr 是基变量是基变量xr的系数，即的系数，即cr是是CB的一个分量，因此的一个分量，因此cr 的变化即引起的变化即引起CB的变化，而在计算所有非基变量的检验数时，均要使的变化，而在计算
4、所有非基变量的检验数时，均要使用用CB，所以，所以cr 的变化可能影响多个非基变量的检验数。设的变化可能影响多个非基变量的检验数。设 ，则变化后，任一非基变量，则变化后，任一非基变量xj的检验数为：的检验数为：B-1要求原最优性不变，则必须满足要求原最优性不变，则必须满足于是得到：于是得到：当当 时，有时，有 当当 时，有时，有j为非基变量的下标为非基变量的下标因此，因此，的允许变化范围是：的允许变化范围是：最优单纯形表系数矩阵中最优单纯形表系数矩阵中第第r行第行第j列的元素列的元素例例1 1：佳美公司计划制造佳美公司计划制造、两种产品，已知各制造一个单两种产品，已知各制造一个单位时分别占用的
5、设备位时分别占用的设备A A、B B的台时、调试时间、每天设备的台时、调试时间、每天设备A A、B B 的的台时、调试工序每天可用于这两种产品的能力及各售出一单位台时、调试工序每天可用于这两种产品的能力及各售出一单位时的获利情况，如表，问应怎样组织生产才能使总利润最多。时的获利情况，如表，问应怎样组织生产才能使总利润最多。设备设备A(h)设备设备B(h)调试工序调试工序(h)利润利润(百元)每天可每天可用能力用能力资源资源产品产品0562112115245(1)(1)如果产品如果产品的利润降至的利润降至1.51.5百元百元/单位，单位，而产品而产品的利润增至的利润增至2 2百元百元/单位时，最
6、优生单位时，最优生产计划有何变化；产计划有何变化；(2)如果产品如果产品的利润不变，则产品的利润不变，则产品的利的利润在什么范围内变化时，则该公司的最优润在什么范围内变化时，则该公司的最优生产计划将不发生变化。生产计划将不发生变化。SchoolofBusinessECUST解：解：设设 x1,x2 分别表示分别表示、两种产品的生产数量，两种产品的生产数量，max z=2x1+x2 s.t.5 x215 6x1+2x224x1+x25 x1,x20max z=2x1+x2+0 x3+0 x4+0 x5 s.t.5 x2+x3=15 6x1+2x2+x4=24x1+x2+x5=5 x1,x2,x3
7、,x4,x50用单纯形法求解得最终单纯形表用单纯形法求解得最终单纯形表ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2得最优解为：得最优解为：x*=(7/2,3/2,15/2,0,0)T zmax=8.5(百元百元)(1)(1)若两产品利润均改变若两产品利润均改变3/223/2 21/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x*=(2,3,0,6,0)Tx40 zmax=9(百元百元)ccBxB x1x2x3x
8、4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2(2)(2)由由 直接计算直接计算,得得:解得解得即产品即产品的利润的利润 c2 的变化满足的变化满足:2/3 2/3 c2 2 2 时时,该公司的最优生产计划将不发生变化该公司的最优生产计划将不发生变化二、二、约束条件中资源数量约束条件中资源数量bi 的变化分析的变化分析 检验数B-1b-cB B-1b I B-1N0cN-cB B-1N由最终单纯形表可知，资源数量由最终单纯形表可知，资源数量 bi 的变化，会影响到的变化，会影响到原
9、最优解的可行性与目标函数值。原最优解的可行性与目标函数值。设某个资源数量设某个资源数量 br 变化为变化为并假设原问题的其他系数不变，则使最终单纯形表中并假设原问题的其他系数不变，则使最终单纯形表中原问题的解相应地变化为原问题的解相应地变化为其中其中这时这时其中其中为为B-1 的第的第 r 列，要保持原最优基列，要保持原最优基B不变，不变，则必须则必须当当 时，有时，有当当 时，有时，有 因此因此 的允许变化范围是：的允许变化范围是：例例2 2：在上述佳美公司的例子中：（：在上述佳美公司的例子中：（1 1）若设备）若设备 A A 和调试工序的每天能力不变，而设备和调试工序的每天能力不变，而设备
10、 B B 每天的能力增加到每天的能力增加到3232小时，分析公司最优计划的变化；（小时，分析公司最优计划的变化；（2 2）若设）若设备备A A和和 B B 每天可用能力不变，则调试工序能力在什么范围内变化时，问题每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。的最优基不变。解：解：(1)(1)因设备因设备 B B 原每天的能力为原每天的能力为2424，所以，所以 有有进一步有进一步有根据最终单纯形表，得根据最终单纯形表，得：SchoolofBusinessECUSTccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2
11、010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2设备设备 B 每天的能力增加到每天的能力增加到32小时后，小时后，不再是可行解。不再是可行解。此时，检验数不变，应用对偶单纯形法继续求解。此时，检验数不变，应用对偶单纯形法继续求解。厂商的最优生产计划厂商的最优生产计划改变为：仅生产改变为：仅生产5个个单位单位产品。此时，产品。此时，利润利润 z*=10ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/235/211/2-1/2-21/
12、2-1/4500 x40151015-10-2-10-41-62ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2(2)由此由此,调试工序的能力应在调试工序的能力应在4小时小时6小时之间小时之间.ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2三、增加一个变量增加一个变量 xj 的分析的分析 增加一个变量在该实际问题中反映为
13、增加一种新的产品。增加一个变量在该实际问题中反映为增加一种新的产品。设新变量为设新变量为在原最优单纯形表增加一列在原最优单纯形表增加一列及检验数及检验数若若则原问题最优解不变；则原问题最优解不变；若若则按单纯形法继续计算。则按单纯形法继续计算。o例例3 3：在佳美公司例子中，设该公司又计划推出新产品：在佳美公司例子中，设该公司又计划推出新产品，生产一单位产品生产一单位产品，所需设备，所需设备A A、B B、调试工序的时间分别为、调试工序的时间分别为3 3小时、小时、4 4小时、小时、2 2小时，该产品的预期盈利为小时，该产品的预期盈利为3 3百元百元/单位，单位，试分析该新产品是否值得投产；如
14、投产对该公司的最优生产试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化。计划有何变化。解：解：设新产品设新产品的生产数量为的生产数量为 x6,c6=3,P6=(3,4,2)TccBxB x1x2x3x4x5x6210003021x3x1x2检验数0015/4-15/2-71001/4-1/20010-1/43/2215/2 7/2 3/2-17/2b000-1/4-1/21x6321/2-1/8 3/413/4-1/2-1/8-5/40-37/47/23/8-9/4051/4最优生产计划为最优生产计划为:每天生产产品每天生产产品 7/2单位单位;新产品新产品 3/4单位单位获利
15、获利 37/4(37/4(百元百元)SchoolofBusinessECUST四、约束条件中技术系数四、约束条件中技术系数 aij 的变化分析的变化分析1.1.非基变量非基变量 xj 的系数列向量的系数列向量 Pj 的变化分析的变化分析 检验数B-1b-cB B-1b I B-1Pj0cj-cB B-1Pj设设非基变量非基变量 xj 的系数列向量的系数列向量 Pj 改变为改变为则变化后的检验数为则变化后的检验数为要使原最优基要使原最优基 B 保持不变，保持不变，则必须则必须在计算中，若非基变量在计算中，若非基变量 xj 的系数列向量的系数列向量 Pj 有改变量有改变量 ，可先，可先由初始表和最
16、优表找到由初始表和最优表找到B-1，然后判断，然后判断 是否成立，是否成立，若成立，则最优基若成立，则最优基B保持不变，否则重新求解。保持不变，否则重新求解。2.基变量基变量 xj 的系数列向量的系数列向量Pj 的变化分析的变化分析 对于最优基对于最优基 B 而言，当而言，当基变量基变量 xj 的系数列向量的系数列向量 Pj 发生变化发生变化时，将使相应的时，将使相应的B，B-1-1都发生变化，因此，它不仅影响现行最优都发生变化，因此，它不仅影响现行最优解的可行性，也影响它的最优性。这种情况，一般需要重新迭代解的可行性，也影响它的最优性。这种情况，一般需要重新迭代求解。求解。检验数B-1b-c
17、B B-1b I B-1Pj0cj-cB B-1Pj五、增加新约束条件的分析五、增加新约束条件的分析 增加一个约束条件在实际问题中相当增添一道工增加一个约束条件在实际问题中相当增添一道工序。设在原规划线性问题中，增加一个新的约束条件序。设在原规划线性问题中，增加一个新的约束条件(*)则则首先把已求得的原问题的最优解首先把已求得的原问题的最优解 代入新增加的约束条件代入新增加的约束条件(*)(*)，如果条件满足，则原，如果条件满足，则原问题的最优解问题的最优解 x*仍为新问题的最优解，结束。如果仍为新问题的最优解，结束。如果条件不满足，则将新增加的约束条件直接反映到最终条件不满足，则将新增加的约
18、束条件直接反映到最终单纯形表中再进一步分析。单纯形表中再进一步分析。o例例4 4：仍以佳美公司为例，设产品仍以佳美公司为例，设产品、经调试后，还需经调试后，还需经过一道环境试验工序，产品经过一道环境试验工序，产品每单位须环境试验每单位须环境试验3 3小时小时，产品，产品每单位须每单位须2 2小时，又环境试验工序每天生产能力小时，又环境试验工序每天生产能力为为1212小时，试分析增加该工序后的佳美公司最优生产计划。小时，试分析增加该工序后的佳美公司最优生产计划。解：解：ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/2
19、15/2 7/2 3/2-17/2b000-1/4-1/2增加约束条件增加约束条件 3x1+2x212 原问题的最优原问题的最优解解 x1=7/2x2=3/2 不满足不满足环环境试验工序约束，境试验工序约束，故将约束条件故将约束条件 3x1+2x2+x6=12加入单纯形表中加入单纯形表中ccBxB x1x2x3x4x5x62100000210 x3x1x2x6 检验数0015/4-15/201001/4-1/20010-1/43/2032000115/27/23/212-17/2b000-1/4-1/200-3/43/23/20-1/4-3/2-3/2x5-3/21/61-2/315/20-5151/30-1/34-1/2010-1/60-1/3-8 添加环境试验工序后添加环境试验工序后,佳美公司的最优生产计划佳美公司的最优生产计划为只生产为只生产 4 4 单位单位I I产品产品,获利获利8(8(百元百元)