《数学规划及其应用.ppt》由会员分享，可在线阅读，更多相关《数学规划及其应用.ppt（12页珍藏版）》请在三一办公上搜索。
1、第一章 线性规划,第七节 对偶理论,弱对偶定理强对偶定理松紧定理,原规划和对偶规划最优解之间的关系,若 和 分别是(P)和(D)的可行解，且,一.弱对偶定理：,定理1-7：,证明：,推论1：,设X 和 分别是(P)和(D)的可行解，则有,则 和 分别是(P)和(D)的最优解。,弱对偶定理：,定理1-7：,推论1：,证明：,设X 和 分别是(P)和(D)的可行解，则有,若 和 分别是(P)和(D)的可行解，且,则 和 分别是(P)和(D)的最优解。,设X 是(P)的任意可行解，由定理1-7知：,所以 是(P)的最优解。,第一章 线性规划,第七节 对偶理论,弱对偶定理强对偶定理松紧定理,原规划和对
2、偶规划解之间的关系,是最优基本可行解。,二.强对偶定理：,定理1-8：,证明：,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,是(P)的最优解，,设对应的最优基为B,是(D)的可行解,是(D)的最优解。,若 是(P)的最优基本可行解，B是相应的最优基，,则单纯形乘子 是(D)的最优解。,强对偶定理：,定理1-8：,推论3：,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,是最优基本可行解。,二.强对偶定理：,定理1-8：,证明：,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,是(P)的最优解，,设对应的最优基为B,是(D)的
3、可行解,是(D)的最优解。,则单纯形乘子 是(D)的最优解。,强对偶定理：,定理1-8：,推论3：,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,若 是(P)的最优基本可行解，B是相应的最优基，,推论1：,若(P)和(D)中有一个有可行解，但没有有限的最优解，则另一个问题无可行解。,设(P)有可行解，但没有有限的最优解，,强对偶定理：,定理1-8：,推论1：,证明：,反证法：,若(P)和(D)中有一个有可行解，但没有有限的最优解，则另一个问题无可行解。,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,则(D)没有可行解。,若(D)有可行解,则由定理1-7，,矛盾。,所以(D)没有可行解。,第一章 线性规划,第七节 对偶理论,弱对偶定理强对偶定理松紧定理,原规划和对偶规划解之间的关系,三.松紧定理：,定理1-9：,证明：,设 分别是(P)和(D)的可行解，,则 分别是(P)和(D)的最优解,设 分别是(P)和(D)的最优解，由定理1-8有,由定理1-7的推论1，分别是(P)和(D)的最优解。,第一章 线性规划,第七节 对偶理论,弱对偶定理强对偶定理松紧定理,原规划和对偶规划解之间的关系,
