运筹学——线性规划的对偶理论.ppt

1、第2章 线性规划的 对偶理论及其应用,线性规划最重要的理论之一 进行经济分析的重要工具,上堂课的主要内容：,1、对称型对偶问题：,2、标准型的对偶问题：,则对偶问题（D）为：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,3、混合型对偶问题,2.2 对偶线性规划 解的理论,最优单纯形表：,最优单纯形表：,常数项,0 1 0 -1/4 3/2 3/2,1 0 0 1/4 -1/2 7/2,0 0 1 5/4

2、-15/2 15/2,0 0 0 -1/4 -1/2 Z-17/2,最优值Z*=17/2,最优值W*=17/2,最优解 （7/2，3/2）,最优解 （0，1/4，1/2）,定理2.1 对偶问题的对偶就是原问题。,（即互为对偶规划）,一、对称定理：,设原问题（P） 对偶问题（D）,二、弱对偶性定理：,推论2、若原问题（P）和其对偶问题 （D）都存在可 行解，则（P） 和（D）都存在最优解,推论1： 若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无可行解,定理2.3 原线性规划（P）与其对偶规划（D）存 在以下对应关系： （1）（P）有最优解的充要条件是（D

3、）有最优解 （2）若X*和Y*分别是（P）和（D）的可行解， 则X*和Y*分别是（P）和（D）的最优解的充 要条件是： CX*=Y*b,三、对偶性定理：,由定理2.2的推论2知：,（D）有最优解,充分性：由定理2.1知，（P）与（D）互为对偶， 充分性同理证明,（1）（P）有最优解的充要条件是（D）有最优解,B为最优基,（2）若X*和Y*分别是（P）和（D）的可行解，则X*和 Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b,证明：,必要性，设X*和Y*分别是（P）和（D）的最优解，,由定理2.2,必有CX*Y*b,设（P）的最优解X* 对应的最优基为B,所以 CX*=Y*b,充分

4、性，设X*和Y*分别是（P）和（D）的可行解， 且CX*=Y*b,证：设X是（P）的任一可行解，由定理2.2，,必有CX Y*b,=CX*,所以X* 是（P）的最优解,同理可证Y*（D）的最优解,要证X*和Y*分别是（P）和（D）的最优解,定理2.3 原问题（P）与其对偶问题 （D）存在以下对应关系： （1）（P）有最优解的充要条件是（D）有最优解 （2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b,推论： 1、若（P）有可行解而(D)无可行解，则(P)无界。 若（D）有可行解而(P)无可行解，则(D)无界。,3：若（P）存在最

5、优解X*，则（D）一定存在 最优解Y*，且,2、原问题（P）与其对偶问题（D）最优值相同,只需求出（P）或(D)中一个的最优解和最优值，即可得另一个的最优解和最优值,0 1/2 1 1/4 1/4 1/4,1 2 0 1/2 -3/2 1/2,0 1/2 0 -11/4 9/4 Z+31/4,的最优单纯形表为：,求其对偶问题的最优解和最优值,解：,对偶问题的最优值,W*=-31/4,最优解,推论3*：若（P） （D）为对称型对偶问题，且（P） 存在最优解X*，则（D）一定存在最优解Y*， 且（-1）Y*是（P）的标准型的最优单纯形表 检验行中松弛变量的系数,设最优基为B,最优值Z=19,松弛变

6、量X3 X4 X5 的检验数为0，-1，-2,（D）的最优解 Y0 =（0，1，2）,最优值S0 =19,推论2、若原问题（P）和其对偶问题 （D）都存在可 行解，则（P） 和（D）都存在最优解,推论1： 若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无可行解,定理2.3 原问题（P）与其对偶问题（D）存在以 下对应关系： （1）（P）有最优解的充要条件是（D）有最优解 （2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b,推论： 1、若（P）有可行解而(D)无可行解，则(P)无界。 若（D

7、）有可行解而(P)无可行解，则(D)无界。,3：若（P）存在最优解X*，则（D）一定存在 最优解Y*，且,2、原问题（P）与其对偶问题（D）最优值相同,原问题与对偶问题解的关系：,一定,不可能,不可能,不可能,不可能,可能,不可能,可能,可能,（P）无可行解,（D）无可行解,无界,（P）无可行解,（D）有可行解,四、互补松弛定理：,定理2.4 设X*和Y*分别是（P）和（D）的可行解， 则X*和Y*分别是（P）和（D）的最优解的 充要条件是方程组,证明:,充分性,已知X*和Y*分别是（P）和（D）的 可行解，且,所以X*和Y*分别是（P）和（D）的最优解,必要性：已知X*和Y*分别是（P）和（D）的最优解,因为X*和Y*分别是（P）和（D）的最优解,定理2.4 设X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充 要条件是方程组 成立,互补松弛定理:,互补松弛定理： 设X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解 的充要条件是方程组 成立,把X*