《第6章 单纯形法的灵敏度分析与对偶2007-10-15》由会员分享，可在线阅读，更多相关《第6章 单纯形法的灵敏度分析与对偶2007-10-15（64页珍藏版）》请在金锄头文库上搜索。
1、第六章* 单纯形法的灵敏度分析与对偶,单纯形表的灵敏度分析 线性规划的对偶问题 对偶单纯形法,第六章* 单纯形法的灵敏度分析与对偶,如何利用最优单纯形表进行灵敏度分析。,单纯形表-求解结果：,第1节 单纯形表的灵敏度分析,一. 目标函数中变量系数 Ck灵敏度分析 现要利用单纯形表法来进行Ck 的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。 1.在最终的单纯形表里, xK 非基变量. 2.在最终的单纯形表里, xK 基变量.,第1节 单纯形表的灵敏度分析,1.在最终的单纯形表里, xK 非基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK 没
2、有任何关系，所以当CK 变为CK +CK 时，在最终单纯形表中其系数的增广矩阵不变，又因为xK 是非基变量，所以基变量的目标函数的系数不变，即CB 不变，可知ZK 也不变，只是CK 变为CK +CK 。这时K= CK ZK 变成了CK +CK ZK= K+ CK .要使得原来的最优解仍为最优解，只要K+ CK 0 即可，也就是 CK K 即可。,第1节 单纯形表的灵敏度分析,.在最终的单纯形表里, xK 为基变量。 由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK 没有任何关系，所以当CK 变为CK +CK 时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系
3、数CB变了，则Zj 也变了， 相应地，也变了。变化规律为：,目标函数： max z=50x1+100x2,x1+ x2300,2x1+x2400,x1 0, x20,s.t.,x2250,max z=50x1+100x2,x1+ x2+s1=300,2x1+x2+s2=400,x1 0, x20, si0,s.t.,x2+s3 =250,一、线性规划问题解的基本概念,基及基本解:,max z=50x1+100x2+0s1+0s2+0s3,1x1+1 x2+1s1+0s2+0s3 =300,2x1+1 x2+0s1+1s2+0s3 =400,x1 0, x20, s10， s20， s30,s.
4、t.,0x1+1x2+0s1+0s2+1s3 =250,表解形式的单纯形法,例子:,初始单纯形表,（）先分析非基变量s1: c3 3 由于是非基变量，故套用公式（1）,当C3 -3, 时最优解不变;已知3=-50, C3 （50）=50；c=c+C0, 不会破坏最优解。（B）aij=50y1+y2+y3100y1,y2,y3 =0,目标:min f=300y1+400y2+250y3s.t. Y1+2y2=50y1+y2+y3100y1,y2,y3 =0,目标:max z=50x1+100x2 S.t.x1+x2=0,原问题,对偶问题,1.求目标函数最大问题中有n个变量,m个约束条件,它的约束
5、条件都是小于等于不等式;其对偶则是m个变量,n个约束条件,并且是大于等于不等式;,2.原问题的目标函数系数C是对偶问题中的约束条件Bci=bi 3.原问题右边系数B成为对偶问题的目标系数C,bi=ci 4. 对偶问题的约束条件系数矩阵A是原问题的AT,转化例子： Max f=3x1+4x2+6x3+4x4x1+4x2+2x3-3x4353x1+x2+5x3+6x445x1,x2,x3,x40,Min g(y)= 35y1+45y2 Y1+3y2 3 4y1+y2 4 2y1+5y2 6 -3y1+6y2 4 Y1,y2 0,目标: min f=300y1+400y2+250y3s.t. Y1+
6、2y250y1+y2+y3100y1,y2,y3 0,目标: max z=50x1+100x2 S.t.x1+x23002x1+x2400x2250x1,x20,原问题,对偶问题,Max -f=-300y1-400y2-250y3-Ma1y1+2y2-s1+a1=50y1+y2+y3-s2=100y1,y2,y3,s1,s2,a10,对偶单纯形法求解：,初始单纯形表,初始单纯形表,(1/2),初始单纯形表,(1/2),最优解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值为-27500,即目标f的最小值为:27500 A设备租金为50元,B设备租金为0元,C设备租金为50元;,
