[经济学]第4章 对偶理论与灵敏度分析.pptVIP

对称性：对偶问题的对偶问题是原问题 证明：原问题为： maxZ=CX AX ≤b X ≥0 对偶问题为： min ω=Yb YA ≥C Y ≥0 ， 取负号，变为： max(- ω)=-Yb -YA ≤-C Y ≥0 , 则上述对偶问题为： min(- ω*)=-CX -AX ≥-b X ≥0 即： maxZ=CX AX ≤b X ≥0 §3 对偶问题的基本性质 2 弱对偶性：极大化原问题的任一可行解的目标函数值大于其对偶问题任意可行解的目标函数值。即： CX1 ≤ Y1b 证明：设原问题为maxZ=CX， AX ≤b ，X ≥0. X1为原问题的可行解，有AX1 ≤b， Y1为对偶问题的可行解，则 Y1AX1 ≤Y1b . 对偶问题为： min ω=Yb， YA ≥C ，Y ≥0 . Y1为对偶问题的可行解，所以， Y1A ≥C，有 Y1AX1 ≥CX1 .于是 CX1 ≤ Y1AX1 ≤Y1b .  * 1．对称性。即对偶问题的对偶是原问题。 2．弱对偶性。即对于原问题（Ⅰ）和对偶问题（Ⅱ）的可行解 都有C ≤bT 。 由弱对偶性，可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。 * 3．最优性。如果 是原问题(Ⅰ)的可行解， 是对偶问题(Ⅱ)的可行解，并且 C = bT ，则 和 分别为原问题(Ⅰ)和对偶问题(Ⅱ)的最优解。 4．强对偶性。即若原问题(Ⅰ)及其对偶问题(Ⅱ)都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。 5．互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若 ，则有yi*=0 3 无界性：原问题（对偶问题）为无界解，对偶问题（原问题）无可行解证明：若对偶问题有可行解Y1，则CX1 ≤ Y1b ，与原问题有无界解矛盾。逆不成立。即：一个为无可行解，则另一个必为无界解或无可行解。 例如： 原问题（对偶问题） 原问题（对偶问题） minw=-X1-X2 maxz=y1+y2 X1-X2≥1 y1-y2≤-1 -X1+X2 ≥1 -y1+y2≤-1  X1≥0 X2≥0 y1≥0 y2≥0 4 可行解是最优解的性质 ：设X*是原问题的可行解， Y*是对偶问题的可行解，当CX*=Y*b时，X*,Y*是最优解。 证明：若CX*=Y*b，由性质2，对偶问题的所有可行解Y1，因CX*=Y*b，所以Y*b =CX* ≤ Y1b，故Y*是对偶问题的最优解；对原问题的可行解X1，有CX1 ≤Y*b= CX*,故X*是原问题的最优解。 5 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1 证明： 设X*是原问题的最优解，则其对应的基为B，有C-CBB-1 A ≤ 0，设Y*= CBB-1 ，则Y*A ≥C.又对偶问题目标函数值w=Y*b= CBB-1 b；原问题目标函数值z=CX*= CBB-1 b=w.由性质4， Y*是对偶问题的最优解。 6 对偶松弛性1：若X*， Y*是原问题和对偶问题的可行解，那么Y*Xs= YsX *=0,当且仅当X*， Y*是最优解。 证明：原问题 对偶问题 maxZ=CX min ω=Yb AX + Xs =b YA- Ys =C X ， Xs ≥0 Y ，Ys ≥0 则：z=(YA- Ys )X