北京交通大学经济管理学院提纲SchoolIofEconics andManagomentBoijing Jiaotong University对偶问题的性质对偶问题的经济解释一影子价格对偶单纯形法北京交通大学
提 纲 • 对偶问题的性质 • 对偶问题的经济解释—影子价格 • 对偶单纯形法
(D) minw = Ybmax z = CXPiYA3iAXfbs.t.is.t.iiY30iX30原问题（或对偶问题）对偶问题（或原问题）求最大求最小目标函数目标函数≥0≥≤变量（n个）≤0约束条件（n个）无约束二≥0≤约束条件（m个）NI≤0变量(m个)一无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项变量对约束，大同小异实例参考定价与生产！
原问题（或对偶问题） 对偶问题（或原问题） 目标函数 求最大 求最小 目标函数 变量(n个) ≥ 0 ≤ 0 无约束 ≥ ≤ = 约束条件(n个) 约束条件(m个) ≤ ≥ = ≥ 0 ≤ 0 无约束 变量(m个) 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 变量对约束,大同小异 实例参考定价与生产!
练习1：求下面线性规划问题的对偶问题P minZ=x +5x2- 7x,+2x4ix+x2-3+x34i1 2x+2x - 4x4 f 5s.t.iX2+ x+ 4=6ix无约束,20,0Dmax w =4y +5y2 +6y3=1iyi+2y21+y,f5iyis.t.i - 3yi +2y2 +y f - 7iyi - 4y2 +y,3 230,0,无约束
练习1：求下面线性规划问题的对偶问题
Pmaxw=4y+5y,+6y3DminZ=x +5x,-7x,+2x=1iy+2y21x +X2 - 3x, + x 3 4-T+y,f52xyi+2x, -4x4 f5口3y+2y+yf-7一x+ x=6i+1J- 4y2 +y,3 21x无约束,xx30.xt030.0.无约束Pmax w=4yi+5y2 +6y3min Z =x, +5x - 7x, +2xi X+x2-3x+ 3 4iyi+2y21112x+2x - 4x4 ±5+yf5yi1+ + =6-3yi+2y +y, f-7T11x无约束 x x30,x0yi- 4y2 +y, 3 2-y300,y无约束
2.4 对偶问题的基本性质(1)(D) minw = Yb(P)max z = CXiYA3Ci AX fbs.t.is.t.iiy30iX3 01.对称性：对偶问题的对偶是原问题CX< Yb弱对偶性：2.(D)无可行解，(P)不一定为无界解3.无界性若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解当原问题无可行解时,其对偶问题是否有无界解？(D)无可行解,(P)不一定为无界解(P)有可行解,(D)不一定有可行解
(D)无可行解，(P)不一定为无界解 1. 对称性：对偶问题的对偶是原问题. 2. 弱对偶性： CX≤Yb 3. 无界性 若原问题(对偶问题)为无界解,则其对偶问题 (原问题)无可行解. 当原问题无可行解时,其对偶问题是否有无界解？ 2.4 对偶问题的基本性质(1) (D)无可行解,(P)不一定为无界解 (P)有可行解,(D)不一定有可行解
北京交通大学经济管理学院School of EconicsandManagomentBojingJiaotong University当原问题(对偶问题)为无可行解，其对偶问题(原问题)或具有无界解或无可行解北京交通大学
• 当原问题(对偶问题)为无可行解, 其对偶 问题(原问题)或具有无界解或无可行解
北京交通大学经济管理学院SchngstoountaylofEics andManagoment4.可行解是最优解的性质若Xo、YO为可行解,则当CXO=Ybo时可得X、YO为最优解5.(强)对偶定理若原问题有最优解,则对偶问题也有最优解且目标函数值相等北京交通大学1
4. 可行解是最优解的性质 若X0 、Y0为可行解,则当CX0 =Yb0时可得X0 、Y0为最优解. 5. (强)对偶定理 若原问题有最优解,则对偶问题也有最优解, 且目标函数值相等
证：首先,当两者都有可行解时,对Yb的最小值有一个下界,对CX的最大值有一个上界,所以两者必定有最优解.再证它们有相同的最优值设X是(P)的最优解,它对应的基矩阵是B,这时必有C- C,BAf0 Z=CX=C,B-'b设Y=C,B-1,则YA3C，30,说明Y是(D)的可行解由于Yb=C,B-"b=CX根据性质4,Y是(D)的最优解
证：首先,当两者都有可行解时,对 Yb 的最小值有一个 下界,对 CX 的最大值有一个上界,所以两者必定有最优 解. 再证它们有相同的最优值
6.互补松驰定理设、分别为(P)和(D)的可行解,则它们为(P)和(D)的最优解的充分必要条件是： X,=0 和Y,X =0其中,Xs,Ys为(P)、(D)标准型问题中的松弛变量和剩余变量证将(P) (D)的约束化为等式AX +IX.=b,YA- YI =C,因为X是最优解,所以cX=Yb,即(YA - YI)X =Y(AX +IX,)故有-YX，=x而YX,,x30,故只有x、=x =0.亡（易证)
6. 互补松弛定理
7.(P)的单纯形表的检验数行对应(D)的一个基解其对应关系是XBXNXs0-CβB-1Cn-CpB-1N-Ys2Ys1-Y该性质是对偶单纯形法的一个基础可得出的结论：(P)）、（D）同时原问题与对偶问题达到最优同时可行
7. (P)的单纯形表的检验数行对应(D)的一个基解, 其对应关系是 可得出的结论： XB XN XS YS1 -YS2 -Y 0 CN -CBB-1N -CBB-1 （P）、（D）同时 达到最优 原问题与对偶问题 同时可行 该性质是对偶单纯形法的一个基础