数学规划及其应用1-7.ppt

第一章第一章 线性规划线性规划第七节第七节 对偶理论对偶理论n弱对偶定理弱对偶定理n强对偶定理强对偶定理n松紧定理松紧定理 原规划和对偶规划最优解原规划和对偶规划最优解之间的关系之间的关系若若 和和 分别是分别是(P)和和(D)的可行解，且的可行解，且线性规划1-7一一.弱对偶定理：弱对偶定理：定理定理1-71-7：证明：证明：推论推论1 1：设设X 和和 分别是分别是(P)和和(D)的可行解，则有的可行解，则有则则 和和 分别是分别是(P)和和(D)的最优解。的最优解。线性规划1-7弱对偶定理：弱对偶定理：定理定理1-71-7：推论推论1 1：证明：证明：设设X 和和 分别是分别是(P)和和(D)的可行解，则有的可行解，则有若若 和和 分别是分别是(P)和和(D)的可行解，且的可行解，且则则 和和 分别是分别是(P)和和(D)的最优解。的最优解。设设X 是是(P)的任意可行解，由定理的任意可行解，由定理1-71-7知：知：所以所以 是是(P)的最优解。的最优解。第一章第一章 线性规划线性规划第七节第七节 对偶理论对偶理论n弱对偶定理弱对偶定理n强对偶定理强对偶定理n松紧定理松紧定理 原规划和对偶规划解之间原规划和对偶规划解之间的关系的关系是是最优基本可行解。最优基本可行解。线性规划1-7二二.强对偶定理：强对偶定理：定理定理1-81-8：证明：证明：(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即是是(P)的最优解，的最优解，设对应的最优基为设对应的最优基为B,是是(D)的可行解的可行解是是(D)的最优解。的最优解。若若 是是(P)的最优基本可行解，的最优基本可行解，B是相应的最优基，是相应的最优基，则单纯形乘子则单纯形乘子 是是(D)的最优解。的最优解。线性规划1-7强对偶定理：强对偶定理：定理定理1-81-8：推论推论3 3：(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即是是最优基本可行解。最优基本可行解。线性规划1-7二二.强对偶定理：强对偶定理：定理定理1-81-8：证明：证明：(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即是是(P)的最优解，的最优解，设对应的最优基为设对应的最优基为B,是是(D)的可行解的可行解是是(D)的最优解。的最优解。则单纯形乘子则单纯形乘子 是是(D)的最优解。的最优解。线性规划1-7强对偶定理：强对偶定理：定理定理1-81-8：推论推论3 3：(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即若若 是是(P)的最优基本可行解，的最优基本可行解，B是相应的最优基，是相应的最优基，推论推论1 1：若若(P)和和(D)中有一个有可行解，但没有有限的最优中有一个有可行解，但没有有限的最优解，则另一个问题无可行解。解，则另一个问题无可行解。设设(P)有可行解有可行解 ，但没有有限的最优解，但没有有限的最优解，线性规划1-7强对偶定理：强对偶定理：定理定理1-81-8：推论推论1 1：证明：证明：反证法：反证法：若若(P)和和(D)中有一个有可行解，但没有有限的最优中有一个有可行解，但没有有限的最优解，则另一个问题无可行解。解，则另一个问题无可行解。(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即则则(D)没没有可行解。有可行解。若若(D)有可行解有可行解则由定理则由定理1-7，矛盾。矛盾。所以所以(D)没没有可行解。有可行解。第一章第一章 线性规划线性规划第七节第七节 对偶理论对偶理论n弱对偶定理弱对偶定理n强对偶定理强对偶定理n松紧定理松紧定理 原规划和对偶规划解之间原规划和对偶规划解之间的关系的关系线性规划1-7三三.松紧定理：松紧定理：定理定理1-91-9：证明：证明：设设 分别是分别是(P)和和(D)的可行解，的可行解，则则 分别是分别是(P)和和(D)的最优解的最优解设设 分别是分别是(P)和和(D)的最优解，由定理的最优解，由定理1-81-8有有由定理由定理1-71-7的推论的推论1 1，分别是分别是(P)和和(D)的最优解。的最优解。第一章第一章 线性规划线性规划第七节第七节 对偶理论对偶理论n弱对偶定理弱对偶定理n强对偶定理强对偶定理n松紧定理松紧定理 原规划和对偶规划解之间原规划和对偶规划解之间的关系的关系