管理运筹学chapter 2.3 对偶与灵敏度分析1

《管理运筹学chapter 2.3 对偶与灵敏度分析1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划ChapterTwo：LP第三节对偶与灵敏度分析1.线性规划问题的对偶关系2.对偶单纯形法3.灵敏度分析4.对偶的经济解释1.线性规划问题的对偶关系1.1对偶问题的提出从多个角度观察同一个问题会得出不同的看法从多个角度对一个实际问题建模会怎么样？1.1对偶问题的提出例2-20某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表2-8所示。问:如何安排产品的生产计划,才能使企业获利最大?甲产品乙产品加工能力A设备2212B设备128C设备4016D设备0412利润（千元/件

2、）231.1对偶问题的提出根据题意，可以建立如下的线性规划模型：1.1对偶问题的提出假定另有一个企业意图收购生产企业拥有的资源，至少应付出多少代价，才能使生产企业愿意放弃生产活动，而选择出售资源呢？显然，对等量资源出售的原则是不低于生产企业自己组织生产活动所获得的利润。在获得了不低于组织生产的收入后，为了使资源出售的价格符合市场规律，具有一定的竞争力，生产企业所获得总收入应尽可能的小。1.1对偶问题的提出设企业所拥有的四种资源定价分别为y1，y2，y3，y4，建立的线性规划模型如下：后一个线性规划模型与原来的线性规划模型是对同一个问题，从两个角度进行的描述。如果称前者为原问题，则

3、后者称为它的对偶问题。反之亦然。1.1对偶问题的提出最大生产利润模型设生产甲产品为X1件，乙产品为X2件则资源最低售价模型设第i种资源价格为yi（i=1,2,3,4）则有1.1对偶问题的提出原问题对偶问题1.2其他形式的对偶问题项目原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项向量目标函数价格系数向量C目标函数价格系数向量约束条件右端项向量目标函数1.2其他形式的对偶问题原问题对偶问题1.2其他形式的对偶问题例2-221.2其他形式的对偶问题则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题习题1.3对偶问题的性质对称性对偶问题的对偶是原问题。弱对

4、偶性若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb。无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解1.3对偶问题的性质弱对偶性推论1：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论2：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。1.3对偶问题的性质最优性若X是原问题的可行解，Y是对偶问题的可行解，且有CX=Yb，则X是原问题的最优解，Y是其对偶问题的最优解。对偶定理（强对偶性）若原问题

5、及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。GO1.3对偶问题的性质兼容性互补基本解：原问题单纯形表的检验数行对应其对偶问题的一个基本解，且二者目标函数值相等。互补松弛性在线性规划规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。GOGO1.3对偶问题的性质例2-24已知线性规划问题如下，试用对偶理论分析该问题解的情况。1.3对偶问题的性质先求原问题的对偶问题由对偶问题的第1个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无可行

6、解两种情况。任意找到原问题的一个可行解，如X=（1，0）T，因此可以判断原问题有可行解，因此原问题解的情况应为无界解。1.3对偶问题的性质例2-25已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。1.3对偶问题的性质解：先写出它的对偶问题将y1*=4/5,y2*=3/5的值代入约束条件②=1/5<3，③=17/5<5，④=7/5<2它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。因y1，y2≥0；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解

7、为X*=(1，0，0，0，1)T；z*=52.对偶单纯形法2.对偶单纯形法单纯形法与对偶单纯形法的思想对比由对偶关系的兼容性可知，单纯形法各阶段迭代表格同时给出原始、对偶问题的互补基本解。单纯形法保证原始基本解的可行性，通过迭代使得对偶基本解变为可行；对偶单纯形法保证对偶基本解的可行性，通过迭代使得原始基本解变为可行。由对偶关系的强对偶性和最优性可知，这两种不同的思维角度都可以得到最优解且目标函数值相等2.对偶单纯形法对偶单纯形法步骤：初始化构造含有m阶单位阵的标准形LP，b值可