1、管理运筹学管理运筹学第六章第六章 单纯形法的灵敏度分析与对偶单纯形法的灵敏度分析与对偶北京理工大学 韩伯棠 教授单纯形表的灵敏度分析单纯形表的灵敏度分析线性规划的对偶问题线性规划的对偶问题对偶规划的基本性质对偶规划的基本性质对偶单纯形法种特殊情况对偶单纯形法种特殊情况本章内容本章内容1234单纯形表的灵敏度分析单纯形表的灵敏度分析本章内容本章内容1线性规划的对偶问题线性规划的对偶问题对偶规划的基本性质对偶规划的基本性质对偶单纯形法种特殊情况对偶单纯形法种特殊情况234 1单纯形表的灵敏度分析单纯形表的灵敏度分析一、目标函数中变量系数一、目标函数中变量系数 ck 灵敏度分析灵敏度分析1、在最终的
2、单纯形表里，xk是非基变量非基变量由于进行行初等变换，约束方程增广矩阵不变基变量系数cB不变zj都不变，包括zkjBjzcpkkkccckkc 0kkc kkkkkkkkczcczc kkkccc 若要原来的最优解不变 1单纯形表的灵敏度分析单纯形表的灵敏度分析2在最终的单纯形表中，xk 是基变量基变量由于进行行初等变换，约束方程增广矩阵不变基变量系数cB变化变化对所有的对所有的zj都都变化变化，包括zkjBjzcp假设cB=(cB1,cB2,ck,cBm)(cB1,cB2,ck+ck,cBm)6 1 原最优单纯形表可表示如下。单纯形表的灵敏度分析单纯形表的灵敏度分析迭代迭代次数次数 基变基变
3、量量cBxkxjb比值bi/aijckcjxB1cB1ak1aj1xB2cB2ak2aj2xkckakkajkxBmcBmakmajmzsckzjs=cs-zs0j+kc+jkkac-jkkac 1单纯形表的灵敏度分析单纯形表的灵敏度分析 cB=(cB1,cB2,ck,cBm)(cB1,cB2,ck+ck,cBm)1122()=jBjBjkkkjBmmjjkkjzcacaccacazc a ()=jjjjjkkjjkkjczczc ac a由于j=cj zj 1单纯形表的灵敏度分析单纯形表的灵敏度分析 0 0 0 jkjkkjjjkjkkjacaaca 当jk时，当j=k时，0,1 =0 =k
4、kkkxkkkkkakkkkkkcczcczc a 为基变量max0 min0jjkjkkjkjkjacaaa=jjkkjc a若要最优解不变 1单纯形表的灵敏度分析单纯形表的灵敏度分析 例 用单纯形表求解下列线性规划问题（第二章例1）目标函数：max z=50 x1 +100 x2 约束条件：x1 +x2 300,2x1 +x2 400,x2 250,x1,x2 0.最优单纯表如下表：迭代迭代次数次数基变基变量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-
5、zj00-500-50 1单纯形表的灵敏度分析单纯形表的灵敏度分析迭代迭代次数次数基变基变量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-zj00-500-50 先对非基变量 s1的目标函数的系数 c3 进行灵敏度分析。这里3=50，所以当 c3 的增量 c3 50 时，c3 50时，最优解不变。3c3c 1单纯形表的灵敏度分析单纯形表的灵敏度分析当当50 c150 ，即在，即在 0 c1100 时最优解不变。时最优解不变。迭代迭代次数次数基变基变量量cBx
6、1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-zj00-500-50再对基变量x1的目标函数系数 c1进行灵敏度分析1c1c0j0150c0150c1c1c1c 1单纯形表的灵敏度分析单纯形表的灵敏度分析2、从30，得 c1 0，即 c101、用c1代替原来的c1=50迭代迭代次数次数基变量基变量cBx1x2s1s2s3b比值比值100000bi/aij2x11010-150s2000-21150 x210001001250zj100027500j=cj-zj000
7、-c1c1c1c1c1-c1+100c1-10050505050-5050-503、从50，得 c1 1000c1100,若c1超出取值范围，必存在检验数0，可通过迭代来得到新的最优解。1单纯形表的灵敏度分析单纯形表的灵敏度分析 当ckk，即ckzk时，xk 变为入基变量。由 c3 50，最优解不变。kkkxkccc 为非基变量 剩余单位台时数设备：从不获利到获利50元时从而设备台时数的对偶价格为z3=50元。同样可知原料A的对偶价格为z4=0元，原料B的对偶价格为 z5=50 元。c3 ：0 50 若有人出50元买1个设备台时，厂家则不必为生产、产品而使用完所有的设备台时。1单纯形表的灵敏度
8、分析单纯形表的灵敏度分析由最终单纯形表对于不同约束类型的对偶价格的取值如下表：从对偶价格的定义可知，当对偶价格为正，将改进目标函数值，从对偶价格的定义可知，当对偶价格为正，将改进目标函数值，当对偶价格为负，将当对偶价格为负，将“恶化恶化”目标函数值。目标函数值。约束类型约束类型对偶价格的取值对偶价格的取值等于该约束条件对应的松弛变量的zj值等于该约束条件对应的剩余变量zj的相反数-zj=等于该约束条件对应的人工变量的zj值 1单纯形表的灵敏度分析单纯形表的灵敏度分析 在求目标函数最大值最大值的线性规划中，对偶价格等于等于影子价格；求目标函数最小值时最小值时，影子价格为对偶价格的相反数相反数。约
9、束类型约束类型影子价格的取值影子价格的取值求目标函数最大值求目标函数最大值求目标函数最小值求目标函数最小值等于该约束条件对应的松弛变量的zj值等于该约束条件对应的松弛变量zj的相反数-zj等于该约束条件对应的剩余变量zj的相反数-zj等于该约束条件对应的剩余变量的zj值=等于该约束条件对应的人工变量的zj值等于该约束条件对应的人工变量zj的相反数-zj 1单纯形表的灵敏度分析单纯形表的灵敏度分析 求使所得新的解仍可行（0）的bj的变化范围，即使其新的最优解的基变量（最优基）都不变，且其对偶价格不变的。二、约束方程中常数项的灵敏度分析二、约束方程中常数项的灵敏度分析kkkbbb由于进行行初等变换
10、，最终单纯形表系数矩阵不变基变量系数cB不变zj 都不变jBjzcpj都不变，基变量都不变 1单纯形表的灵敏度分析单纯形表的灵敏度分析原始的约束方程组：Axb迭代，对原系数矩阵进行初等行变换，变成以B为基的最终单纯形表，即对原来约束方程组左乘B-1:11B AxB b原始的最终单纯形表中系数矩阵：1B A原始的最终单纯形表中基变量xB的解为：1B b 1单纯形表的灵敏度分析单纯形表的灵敏度分析 kkkbbb 1200 00kkmbbbbbbbbb 原始的最终单纯形表中基变量xB变为xB：11()=BkBkBkkxBbbxBbxDb 其中Dk为B-1的第k列，12 =kkkmkddDd 1单纯形
11、表的灵敏度分析单纯形表的灵敏度分析11112222=0BkBkBkBkkBBmmkBmmkxdxb dxdxb dbxxdxb d 使得对应约束条件 的对偶价格不变为使新的基本解xB的各分量均非负即：max0min0BiBiikkikikikxxdbddd 1单纯形表的灵敏度分析单纯形表的灵敏度分析以第二章例1在最终单纯形表上对进行b1灵敏度分析：迭代迭代次数次数基变基变量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-zj00-500-50在第一个约束方程中
12、含有松弛变量s1,其对应的列为(1,-2,0)T,xB为(50,50,250)T,由 ，得到 时第1个约束条件的对偶价格不变。max0min0BiBiikkikikikxxdbddd 15025,b 11250325bb 实际意义：当设备台时数在250与325之间变化时，该约束条件即设备台时数的对偶价格不变，都为每设备台时50元。1单纯形表的灵敏度分析单纯形表的灵敏度分析三、三、约束方程系数矩阵约束方程系数矩阵 A 灵敏度分析灵敏度分析1最终单纯形表上xk是非基变量非基变量 xk的初始单纯形表的系数列 kkpp 迭代 xk的系数列、zk以及k变化，其他均不变最终单纯形表中新的系数列:zk :k
13、:-1kpB-1BkcpB-1kBkccpB若k0，则原最优解仍然为最优解。若k0，则继续进行迭代以求出最优。1单纯形表的灵敏度分析单纯形表的灵敏度分析 例 1以第二章例1为基础，该厂除生产，种产品外，现试制新产品，已知生产产品，每件需要设备2台时，A原料0.5公斤,B原料1.5公斤，获利 150元，问该厂是否该生产该产品、生产多少？分析：这是一个增加新变量的问题，可以认为是改变x3 在初始表上的系数列的问题。1单纯形表的灵敏度分析单纯形表的灵敏度分析迭代迭代次数次数基变基变量量cBx1x2s1s2s3501000002x1501010-1s2000-211x210001001zj501005
14、0050j=cj-zj00-500-50b比值比值bi/aij505025027500 x315020.51.5175-251、首先，在最终单纯形表中直接插入新的列2、在最终单纯形表中找到B-1，求出B-1p6,替换该列系数1500.5-21.53、求出该列zj,j新变量的6 0不为0 且由互补松弛定理有x1=x3=0从而原问题的两个约束不等式应该取“=”1234123412341234 max 22.23420 4 3220 ,0zxxxxstxxxxxxxxx x x x1234123412341234 max 22.23420 4 3220 ,0zxxxxstxxxxxxxxx x x
15、x将 x1=x3=0 带入此时原问题的约束条件 3对偶规划的基本性质x1=x3=01234123412341234 max 22.23420 4 3220 ,0zxxxxstxxxxxxxxx x x x242424203 20 xxxx解得，2,642xx可知可知 满足原问题约束条件，从而满足原问题约束条件，从而其为原问题的最优解，对应的目标函数最大值为其为原问题的最优解，对应的目标函数最大值为14142,0,6,04321xxxx对偶规划的基本性质对偶单纯形法本章内容本章内容1234单纯形表的灵敏度分析线性规划的对偶问题 4对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯
16、形法是在保持保持原问题所有所有i 0的情况下，通过迭代，使所有约束条件常数所有约束条件常数bj 0，最后求得最优解。简化计算简化计算是对偶单纯形法的优点，但其使用上有局限性，主要是大多线性规划问题很难找到初始解使其所有检验数均i 0。4对偶单纯形法 在灵敏度分析中，有时需要对偶单纯形法，可简化计算。解：求出在第2次迭代表上的常数列，带入第2次迭代表，以第二节例1为例。已知当250b1325时第1个约束条件的对偶价格不变，现在b1=300变成b1=350，问此时第1个约束方程的对偶价格为多少？11115050100502 502502500=bbbbXXBbb 4对偶单纯形法迭代迭代次数次数基变
17、基变量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-1100s2000-211-50 x210001001250zj501005005027500j=cj-zj00-500-50 1、确定出基变量确定出基变量：在常数列中找一个最小的负常量，把该常量所在行的基变量为出基变量。2、确定入基变量确定入基变量：检查出基变量xk所在行的各系数akj(j=1,2,.,n)，若所有akj均0，则无可行解；若有akj0，计算所有相应的j/akj，求出其中最小值，确定具有最小比值的xt作为入基变量。3、以akt为主元，按照单纯形法进行迭代运算，得到新的单纯新表。本题选a23为主元。4对偶单纯形法迭代迭代次数次数基变基变量量cBx1x2s1s2s3b比值比值50100000bi/aij3x1501001/2-1/275s10001-1/2-1/225x210001001250zj501000257528750j=cj-zj000-25-75 4、检查常数列的值，若都已经非负，则结束迭代，此解即为最优解，如果还有负的常数，重复1-4步。谢谢 谢！谢！
