第二章:对偶问题(1) 性质4的证明: 求证设X*是原问题的可行解,Y*是对偶问题的可行解,当CX*=Y*b时 X*,Y*是最优解 证明:如果CX*=Y*b,根据性质2,对偶所有可行解Y,都有Yb>=CX*=Yb 所以Y*是使目标值最小的可行解,因此Y是最优解 同理,X*是最优解 性质5的证明 AXb 求证对偶定理若原问题有最优解,则对偶问题也有Bxn+Nx、=b 最优解,且目标函数值相等。 B-b-BINX 证明:设X*是原问题最优解,B是最优基 ZF CX=CBXB+CNX ZF CX- CBXB+ CNXN=CD B-Ib - CB(Bb-BNXN+ CNXN 最优表中检验数=C-CBB1A=CYA<=0 CBB b+(CN-CB BIN). 这里令:Y=CBB +0X 即YA>=C,已知Y可行,W=Yb=CBB1b 运等 狼中教授
运筹学 熊中楷教授 性质5 的证明： 求证对偶定理 若原问题有最优解，则对偶问题也有 最优解，且目标函数值相等。 证明：设X* 是原问题最优解，B 是最优基， Z= CX= CBXB ＋ CNXN = CB B-1 b 最优表中检验数= C- CB B-1A= C-YA< ＝0 这里令： Y＝ CB B-1 即 YA>=C, 已知 Y 可行， W=Yb ＝ CB B-1 b 性质4 的证明： 求证 设X*是原问题的可行解，Y*是对偶问题的可行解，当C X*=Y* b时 X*，Y* 是最优解 证明：如果CX*=Y* b， 根据性质2，对偶所有可行解Y，都有Yb>= C X* =Y* b 所以Y* 是使目标值最小的可行解，因此Y*是最优解 同理， X*是最优解 第二章：对偶问题（1） AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN ) + CN XN = CB B-1b +( CN - CB B-1 N) XN ＋0 XB
第二章:对偶问题(1) 性质6的证明: 求证:互补松弛性若X*,Y*分别是原问题和对偶问题的可行解,那么 Y*Xs=0和YsX*=0,当且仅当X*Y*为最优解。 证明:MaxZ=CX AX+Xs=b XXS >O 对偶:Minw=Yb YA-YS=C 7=CX=( YA-YS) X= YAX-YS X w=Yb=Y(AX+XS)= YAX+Y Xs 如果Y*Xs=0和YsX*=0那么CX=Yb,性质4,X*Y*为最优解 如果X*,Y*为最优解,性质4:CX=Yb,YXs+YsX*=0 那么Y*Xs=0和YsX*=0 运学 狼中教授
运筹学 熊中楷教授 性质6 的证明： 求证:.互补松弛性若X*.Y*分别是原问题和对偶问题的可行解，那么 Y*Xs=0和YsX*=0，当且仅当X*.Y*为最优解。 证明： MaxZ=CX AX+Xs=b X ,Xs ≥0 对偶： Min w=Y b YA--Ys=C Y, Ys ≥0 Z=CX＝（ YA--Ys ）X＝ YAX --Ys X w=Y b＝Y(AX+Xs)= YAX+Y Xs 如果 Y*Xs=0 和 YsX*=0 那么 CX＝ Y b，性质4 , X*.Y*为最优解 如果 X*,Y*为最优解，性质4：CX＝ Y b， Y*Xs + YsX*=0 那么Y*Xs=0 和 YsX*=0 第二章：对偶问题（1）
第二章:对偶问题(1) 性质7的证明 求证:设原问题是 Max z= X AX+Xs=b XXs >0 其对偶问题为Minw=YbYA-Ys=CY,Ys≥0 则原问题单纯形表的松弛变量的检验数对应对偶问题的一个解 证明:Max=CX 非基变量的检验数:ON=CN=CBN AX+Xs=b B IX+Xs=b 对偶:Minw=Yb YA--YS=C Y,Ys 20 X=B-b- B-I..B 代入=CX=CBXB+CNXN=CB4b-CBB1NXN- CBBIXS+CNXN CBBb+(C B-NXN -CB B 注意非基变量的检验数和松弛变量的检验数,松弛变量X的检验数-CBB对应对 偶问题的一个解CBB1 运学 狼中教授
运筹学 熊中楷教授 性质7的证明： 求证: 设原问题是 Max Z=C X AX+Xs=b X ,Xs ≥0 其对偶问题为 Min w=Y b YA--Ys=C Y,Ys ≥0 则原问题单纯形表的松弛变量的检验数对应对偶问题的一个解 证明： MaxZ=CX 非基变量的检验数: AX+Xs=b B XB +NXN +XS = b X ,Xs ≥0 对偶： Min w=Y b YA--Ys=C Y,Ys ≥0 XB = B-1 b - B-1 NXN - B-1 XS 代入Z=C X = CB XB + CN XN = CB B-1 b - CB B-1 NXN - CB B-1 XS + CN XN = CB B-1 b + ( CN - CB B-1 N) XN - CB B-1 XS 注意非基变量的检验数和松弛变量的检验数，松弛变量XS的检验数 - CB B-1对应对 偶问题的一个解 CB B-1 第二章：对偶问题（1） N CN CBB N −1 = −
第二章:对偶问题(1) 对偶问题的经济解释(影子价格) 1对偶解的经济含义?(p61) 单位资源的变化引起最优值的变化:Z= CnB-1b Y=dZdb=CB1 2影子价格的特点 (1)影子价格是对系统资源的最优估价,不是真实价格 (2)对偶解-影子价格大小客观反映了资源在系统内部的稀缺程度 影子价格越高,该资源在系统中越稀缺 影子价格为0,该资源在系统中供大于求 (3)系统内部资源数量和市场价格的任何变化都会引起影子价格的变化 3影子价格在经济管理中的应用 若资源的影子价格高(低)于其市场价格,则该资源在系统中有(无)获 利能力应买入(卖出)该资源 运学 狼中教授
运筹学 熊中楷教授 第二章：对偶问题（1） 对偶问题的经济解释（影子价格） 1.对偶解的经济含义? ( p61 ) 单位资源的变化引起最优值的变化：Z=CB B-1 b Y=dZ\db＝ CB B-1 2.影子价格的特点 （1）影子价格是对系统资源的最优估价，不是真实价格 （2）对偶解---影子价格大小客观反映了资源在系统内部的稀缺程度 影子价格越高，该资源在系统中越稀缺 影子价格为0，该资源在系统中供大于求 （3）系统内部资源数量和市场价格的任何变化都会引起影子价格的变化 3.影子价格在经济管理中的应用 若资源的影子价格高（低）于其市场价格，则该资源在系统中有（无）获 利能力应买入（卖出）该资源
第二章:对偶问题(1) 松弛变量的检验数 对偶单纯形法 对偶解=Y CBB-lb+(CN-CB B-N)XN-CBB 1对偶单纯形法理论基础 蒸基变量XB非基变量X松池变量/基解Bb 变量检验数 原问题基解 CBB-IN Cn B 运学 狼中教授
运筹学 熊中楷教授 第二章：对偶问题（1） 基 变 量 基变量XB 非基变量XN 松弛变量XS 基解B-1b 检 验 数 CN - CB B-1N 对偶单纯形法 Z = CB B-1 b + ( CN - CB B-1 N) XN - CB B-1 XS 1.对偶单纯形法理论基础 原问题基解 - CB B-1 松弛变量的检验数 ＝－对偶解=-Y