《运筹学对偶灵敏》PPT课件

《《运筹学对偶灵敏》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章对偶理论和灵敏度分析对偶理论(DualTheory)灵敏度分析(SensitivityAnalysis)s.t用矩阵形式表示原问题：s.t对偶问题：minω=Y’bA’Y≥CY≥0maxZ=CXAX≤bX≥0项目原问题对偶问题系数矩阵A约束系数矩阵约束系数矩阵的转置右端常数b约束条件的右端项向量目标函数中价格系数向量系数列C目标函数中价格系数向量约束条件的右端项向量目标函数maxZ=CXminω=Y’b约束条件AX≤bA’Y≥C’决策变量X≥0Y≥0原问题(或对偶问题)对偶问题(或原问题)m

2、axZminω约束条件数m个第i个约束条件：“≤”“≥”“=”对偶变量数m个第i个对偶变量：“yi≥0”“yi≤0”yi为自由变量决策变量数n个第j个对偶变量：“xj≥0”“xj≤0”xj为自由变量约束条件数n个第j个约束条件：“≥”“≤”“=”原问题与对偶问题的关系在形式上可归结为表3.4对偶问题的基本性质s.t原问题：s.t对偶问题：minω=YbATY≥CTY≥0maxZ=CXAX≤bX≥0(1).对称性：对偶问题的对偶问题是原问题。即原问题和对偶问题之间是互为对偶的。证明：（略）(2).弱

3、对偶性：设X#、Y#分别是原问题和对偶问题的可行解，则有CX#≤Y#b。证明：（略）从弱对偶性可知，原问题(极大化问题)的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。对偶问题(极小化问题)的任意一个可行解所对应的目标函数值是其原问题最优目标函数值的一个上界。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值。(3).无界性：若原问题可行，但目标函数无上界，则对偶问题无可行解。若对偶问题可行，但目标函数无下界，则原问题无可行解。证明：（略）(4).最

4、优性：设X#、Y#分别是原问题和对偶问题的可行解，则当CX#=Y#b时，X#、Y#分别为原问题和对偶问题的最优解X*、Y*。证明：（略）(5).强对偶性：若原问题和对偶问题之一有最优解，则另一个问题也一定有最优解，且目标函数值相等。证明：（略）从强对偶性可知，若原问题有一个对应于基B的最优解，则CBB-1就是对偶问题的一个最优解，并且两个问题的最优值相等。另外，原问题获得最优解时，其松弛变量对应的检验数的相反数CBB-1，就是对偶问题的最优解。该性质常被称为主对偶定理。CBB-1称为单纯形乘子。(

5、6).互补松弛性：该性质常被称为对偶问题的松紧定理。(7).对应性：原问题对应其可行基的检验数的相反数是对偶问题的一个基解。证明：（略）从性质7可知，用单纯形法求解LP问题时，迭代的每一步在得到原问题的一个基可行解的同时，其检验数行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。在单纯形表中，原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应于原问题的变量；这些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。原问题与对偶问题之间的变量对应关系见表3

6、-5。原问题的变量基变量XB非基变量XN松弛变量Xs对应于可行基B的检验数0CN-CBB-1N-CBB-1对偶问题的变量-Ys1-Ys2-Y表3-5的进一步说明：用单纯形法求解LP问题时，原问题的检验数行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。在单纯形表中，原问题的松弛变量(Xs)对应于对偶问题的变量(-Y)，对偶问题的剩余变量(-Ys1、-Ys2)分别对应于原问题的变量(XB、XN)—利用这种对应关系，只需求解其中一个问题，就可以从原问题最终单纯形表中同时得到其对偶问题的最优解

7、，而不须求解过程。以上这些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。根据上述的一些性质，互为对偶的两个LP问题之间的解有以下几种情况，见表3-6。原问题对偶问题有最优解有可行解，但目标函数无界无可行解无可行解有最优解无可行解有可行解，但目标函数无界无可行解例3-4：求解下列LP问题。maxZ=x1+x2s.t.-x1+x2+x3≤2-2x1+x2-x3≤1x1，x2，x3≥0解：由于X=(0,0,0)T满足s.t.，所以X=(0,0,0)T为可行解。现写出其对偶

8、问题如下minω=2y1+y2s.t.-y1-2y2≥1∵x1≥0y1+y2≥1∵x2≥0y1-y2≥0∵x3≥0y1，y2≥0∵第i个约束条件(1)(2)由于第一个约束条件-y1-2y2≥1是矛盾不等式，所以对偶问题(2)无可行解。根据对偶问题的强对偶性可知，若原问题(1)有最优解，则对偶问题(2)一定也有最优解。因此，原问题(1)不可能有最优解，但是，原问题(1)有可行解，所以原问题(1)无有限最优解，即目标函数无上界。对偶问题的解在经济学上称为原问题的资源的影子价格，为什么呢