《运筹学大学课件42对偶问题的基本性质文档.pptx》由会员分享，可在线阅读，更多相关《运筹学大学课件42对偶问题的基本性质文档.pptx（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、返回返回返回返回继续继续继续继续第二节第二节 对偶问题的基本性质对偶问题的基本性质n单纯形法计算的矩阵描述单纯形法计算的矩阵描述n引例引例n对称性对称性n弱对偶性弱对偶性n最优性最优性n对偶性（强对偶性）对偶性（强对偶性）n互补松弛性互补松弛性 单纯形法的矩阵描述单纯形法的矩阵描述不妨设基为不妨设基为基变量基变量非基变量非基变量设线性规划问题设线性规划问题则则 单纯形法的矩阵描述单纯形法的矩阵描述其中其中令令 得当前的基解为：得当前的基解为：当前基解当前基解约束方程组约束方程组当前目标值当前目标值目标函数目标函数令令 得当前的目标函数值为：得当前的目标函数值为：单纯形法的矩阵描述单纯形法的矩阵
2、描述当前检验数当前检验数 单纯形法的矩阵描述单纯形法的矩阵描述检验数检验数其中其中当前当前 对应的系数列对应的系数列单纯形法计算的矩阵描述单纯形法计算的矩阵描述线性规划问题线性规划问题化为标准型，引入松弛变量化为标准型，引入松弛变量初始单纯形表初始单纯形表非基变量非基变量基变量基变量初始基变量初始基变量单纯形法计算的矩阵描述单纯形法计算的矩阵描述基变量基变量非基变量非基变量当基变量为当基变量为 时，新的单纯形表时，新的单纯形表单纯形法计算的矩阵描述单纯形法计算的矩阵描述当前检验数当前检验数当前基解当前基解单纯形法计算的矩阵描述单纯形法计算的矩阵描述 从上两表可看出，当迭代后基变量为XB时，其在
3、初始单纯形表中的系数矩阵为B，则有：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 (2)初始单纯形表中基变量Xs b，迭代后的表中 (3)初始单纯形表中约束系数矩阵为A,I=B,N,I，迭代后的表中约束系数矩阵为 B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1。单纯形法计算的矩阵描述单纯形法计算的矩阵描述 (4)若初始矩阵中变量xj的系数向量为Pj 迭代后为 则有则有 (5)当B为最优基时,在新的单纯形表应有单纯形法计算的矩阵描述单纯形法计算的矩阵描述 可看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有
4、当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值对对偶偶问问题题原原问问题题收收购购厂厂家家n引例引例（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问
5、题的变量对偶问题的变量化为极小问题化为极小问题原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：n两个问题作一比较两个问题作一比较:1.两者的最优值相同两者的最优值相同2.变量的解在两个单纯形表中互相包含变量的解在两个单纯形表中互相包含原问题最优解原问题最优解（决策变量）（决策变量）对偶问题最优解对偶问题最优解（决策变量）（决策变量）对偶问题的松弛变量对偶问题的松弛变量原问题的松弛变量原问题的松弛变量从引例中可见：从引例中可见：原问题与对偶问题在某种意义上来说，原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题
6、仅仅在第实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。一个问题的另一种表达而已。理论证明：理论证明：原问题与对偶问题解的关系原问题与对偶问题解的关系对偶问题的基本性质对偶问题的基本性质一、对称定理：一、对称定理：定理：定理：对偶问题的对偶是原问题对偶问题的对偶是原问题。设原问题（设原问题（1 1）对偶问题（对偶问题（2 2）二、弱对偶性定理：二、弱对偶性定理：若若 和和 分别是原问题（分别是原问题（1 1）及对偶问题（及对偶问题（2 2）的可行解，则有）的可行解，则有 证明：证明：对偶问题的基本性质对偶问题的基本性质从弱对偶性可得到以下重要结论：从弱对偶性可得到以下重要结论：
7、n（1 1）极大化问题（原问题）的任一可行解所对应的目）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。标函数值是对偶问题最优目标函数值的下界。n（2 2）极小化问题（对偶问题）的任一可行解所对应的）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。目标函数值是原问题最优目标函数值的上界。n（3 3）若原问题有可行解，但其目标函数值无界，则对）若原问题有可行解，但其目标函数值无界，则对偶问题无可行解。偶问题无可行解。n（4 4）若对偶问题可行，但其目标函数值无界，）若对偶问题可行，但其目标函数值无界，则原问题无可行解。则原问题无
8、可行解。n（5 5）若原问题有可行解而其对偶问题无可行）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。解，则原问题目标函数值无界。n（6 6）对偶问题有可行解而其原问题无可行解，）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。则对偶问题的目标函数值无界。例题例题判断下例说法是否正确，为什么？A 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。A不对。因为原
9、问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。原问题原问题对偶问题对偶问题三、最优性定理：三、最优性定理：若若 和和 分别是（分别是（1 1）和（）和（2 2）的）的 可行解，且有可行解，且有 则则 分别是分别是（1 1）和（）和（2 2）的最优解）的最优解 。则则 为（为（1 1）的最优解，）的最优解，反过来可知：反过来可知：也是（也是（2 2）的最优解。）的最优解。证明：因为（证明：因为（1）的任一可行解）的任一可行解 均满足均满足对偶问题的基本性质对偶问题的基本性质证明：证明：原问题与
10、对偶问题的解一般有三种情况原问题与对偶问题的解一般有三种情况：n一个有有限最优解一个有有限最优解 另一个有有限最优解。另一个有有限最优解。n一个有无界解一个有无界解 另一个无可行解。另一个无可行解。n两个均无可行解。两个均无可行解。四、对偶定理（强对偶性）：四、对偶定理（强对偶性）：若原问题及其对偶问题有一个有最优若原问题及其对偶问题有一个有最优解，则另一个也有最优解，且它们最优解的目解，则另一个也有最优解，且它们最优解的目标函数值相等标函数值相等。对偶问题的基本性质对偶问题的基本性质从强对偶性可得到以下重要结论：从强对偶性可得到以下重要结论：(1)(1)若原问题有最优解若原问题有最优解X X
11、，对应最优基，对应最优基B B，则，则 是对偶问题的最优解，且两者的最优值相等。是对偶问题的最优解，且两者的最优值相等。(2)(2)原问题最优表中，松弛变量的检验数原问题最优表中，松弛变量的检验数 的的反号数反号数 ，是对偶问题的最优解，是对偶问题的最优解。五、互补松弛性：五、互补松弛性：若若 分别是原问题（分别是原问题（1 1）与对偶）与对偶问题（问题（2 2）的可行解，）的可行解，分别为（分别为（1 1）、）、（2 2）的松弛变量，则：）的松弛变量，则：即：即：为最优解为最优解原问题第原问题第i条约束条约束 A的第的第i行行 说明：说明：在线性规划问题的最优解中，如果对在线性规划问题的最优
12、解中，如果对应某一约束条件的对偶变量值为非零，则该应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。严格不等式，则其对应的对偶变量一定为零。另一方面：另一方面：对偶问题的第对偶问题的第j条约束条约束 性质性质5 5告诉我们已知一个问题的最优解时求另一个问告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知题的最优解的方法，即已知 求求 或已知或已知 求求 。两式称为两式称为互补松弛条件互补松弛条件。将互补松弛条件写成下式。将互补松弛条件写成下式 由由于于变变量量都都非非负负，要要
13、使使求求和和式式等等于于零零，则则必必定定每每一一分分量量为为零零，因而有下列关系：因而有下列关系：(1)当当 时，时，,反之当反之当 ,时时 ；利利用用上上述述关关系系，建建立立对对偶偶问问题题(或或原原问问题题)的的约约束束线线性性方方程组，方程组的解即为最优解。程组，方程组的解即为最优解。【例例】已知线性规划已知线性规划的最优解是的最优解是 ,求对偶问题的最优解。求对偶问题的最优解。【解解】对偶问题是对偶问题是因因为为x10，x20，所所以以对对偶偶问问题题的的第第一一、二二个个约约束束的松弛变量等于零，即的松弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对
14、对偶偶问问题题的的最最优优解解为为Y=(1，1)T，最优值，最优值w=26。【例例】已知线性规划已知线性规划 的对偶问题的最优解为的对偶问题的最优解为Y=(0，-2)T，求原问题的最优解。，求原问题的最优解。【解解】对偶问题是对偶问题是解方程组得：解方程组得：x 1=5,x 3=1,所以原问题的最优解为所以原问题的最优解为X=(5，0，1)T，最优值，最优值 Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量 =0，由，由 y1=0、y2=-2知，松弛变量知，松弛变量 故故x2=0，则原问题的约束条件为线性方程组：，则原问题的约束条件为线性方程组：n n互补松弛定理应
15、用：互补松弛定理应用：n（1）从已知的最优对偶解，求原问题最）从已知的最优对偶解，求原问题最优解，反之亦然。优解，反之亦然。n（2）证实原问题可行解是否为最优解。）证实原问题可行解是否为最优解。n（3）从不同假设来进行试算，从而研究）从不同假设来进行试算，从而研究原问题、对偶问题最优解的一般性质。原问题、对偶问题最优解的一般性质。n（4）非线性的方面的应用。）非线性的方面的应用。以上性质同样适用于非对称形式。以上性质同样适用于非对称形式。一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解(
16、有可行解有可行解)无可行解无可行解性质性质2解解无可行解无可行解无界解无界解(有可行解有可行解)性质性质2应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质6根据对偶性质根据对偶性质,可将原问题与对偶问题解的对应关系列表如下：可将原问题与对偶问题解的对应关系列表如下：【性性质质6】LP(max)的的检检验验数数的的相相反反数数对对应应于于DP(min)的的一一组组基基本本解解。其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于(DP)中中第第j个个松松弛弛变变量量 的的解解，第第i个个松松弛弛变变量量 的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，(DP)的的检检验验数数(注注意意：不不乘乘负负号号)对对应应于于(LP)的一组基本解。的一组基本解。4.2 对偶性偶性质Dual property注：注：应用性质应用性质6 6 的前提是线性规划为规范形式，而的前提是线性规划为规范形式，而性质性质1-51-5则对所有形式线性规划有效。则对所有形式线性规划有效。返回返回返回返回对偶问题的基本性质对偶问题的基本性质