第二章:对偶问题(1) Chapter 2: dual problem(1) 对偶问题的引例 A example of dual problem(economic(经济含意 interpretation) 乙方为购买甲方资源而给 Factory B must set a price for the resources owned by factory A. Factory 甲方资源定价,一方面乙方 b want to pay less money to get these希望少付钱,又要保证甲方 resources. but also need ensure the 利益 profit of factory A Property1 of duality: the duality of对偶性质1:对偶的对偶问 dual problem is primal problem. 题是原问题 Property2 of duality: weak duality.对偶性质2:弱对偶性 Property3 f duality: the dual is对偶性质3:无界性 unbounded 对偶性质4:可行解是最优 Property 4 of duality: the feasible解性质 ptma 运学 狼中教授
运筹学 熊中楷教授 Chapter 2:dual problem (1) A example of dual problem (economic interpretation) Factory B must set a price for the resources owned by Factory A . Factory B want to pay less money to get these resources, but also need ensure the profit of Factory A. Property 1 of duality : the duality of dual problem is primal problem. Property 2 of duality : weak duality. Property 3 of duality : the dual is unbounded. Property 4 of duality: the feasible solution is the optimal. 对偶问题的引例 （经济含意） 乙方为购买甲方资源而给 甲方资源定价，一方面乙方 希望少付钱，又要保证甲方 利益 对偶性质1：对偶的对偶问 题是原问题 对偶性质2：弱对偶性 对偶性质3：无界性 对偶性质4：可行解是最优 解性质 第二章：对偶问题（1）
第二章:对偶问题(1) 对偶问题的提出: 原问题 生产者追求利润最大 对偶问题 St.资源约束 租用者希望租金最小 市场约束 St.租金不小于利润 模型: Maxc.x St. Ax<b 模型 Miny St.YA≥c >0 运学 狼中教授
运筹学 熊中楷教授 对偶问题 租用者希望租金最小 St. 租金不小于利润 模型：Min y·b St. YA ≥c y ≥0 对偶问题的提出： 原问题 生产者追求利润最大 St. 资源约束 市场约束 模型： Max c·x St. Ax≤b x≥0 第二章：对偶问题（1）
第二章:对偶问题(1) 原问题 对偶问题 MaxZFcX Min w=y b AX<=b YA≥C 经济意义A,X,b,C, CX,AX Y,Yb,YA 标准化 MaxzFCX Min w=Y b 松弛变量XsAX+Xs=b 剩余变量Ysx,Xs20 YA-YS=C Y,Ys≥0 运学 狼中教授
运筹学 熊中楷教授 第二章：对偶问题（1） 原问题 对偶问题 MaxZ=CX AX<=b X ≥0 Min w=Y b YA≥C Y ≥0 经济意义 A，X，b，C, CX, AX Y, Y b , YA 标准化 松弛变量Xs 剩余变量Ys MaxZ=CX AX+Xs=b X ,Xs ≥0 Min w=Y b YA--Ys=C Y,Ys ≥0
第二章:对偶问题(1) 七个性质 1对称性对偶问题的对偶是原问题。 2弱对偶性若X是原问题的可行解,Y是对偶问题的可行解,则存在 C X<Y b 3.无界性若原问题无界解,则其对偶问题无可行解。 4设X*是原问题的可行解,Y*是对偶问题的可行解,当CX*=Y*b时 X*,Y*是最优解 5对偶定理若原问题有最优解,则对偶问题也有最优解,且目标函数 值相等。 6.互补松弛性若X*,Y*分别是原问题和对偶问题的可行解,那么 Y*Xs=0和YsX*=0,当且仅当XY*为最优解。 7设原问题是 Max 7FC X AX+Xs=b X Xs>0 其对偶问题为Minw=YbYA-Ys=CY,Ys≥0 则原问题单纯形表的松弛变量的检验数对应对偶问题的一个解 运学 狼中教授
运筹学 熊中楷教授 第二章：对偶问题（1） 七个性质 1.对称性 对偶问题的对偶是原问题。 2.弱对偶性 若X是原问题的可行解，Y是对偶问题的可行解，则存在 C X≤ Y b 3.无界性 若原问题无界解，则其对偶问题无可行解。 4.设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y* b时 X*，Y* 是最优解 5.对偶定理 若原问题有最优解，则对偶问题也有最优解，且目标函数 值相等。 6.互补松弛性 若X*.Y*分别是原问题和对偶问题的可行解，那么 Y*Xs=0和YsX*=0，当且仅当X*.Y*为最优解。 7.设原问题是 Max Z=C X AX+Xs=b X ,Xs ≥0 其对偶问题为 Min w=Y b YA--Ys=C Y,Ys ≥0 则原问题单纯形表的松弛变量的检验数对应对偶问题的一个解
第二章:对偶问题(1) 性质1的证明: 求证:对称性对偶问题的对偶是原问题。 证明:原问题: Max cx,AX≤b,X≥0 对偶: Min y b,MA≥C,Y20 即Max-Yb,YA≤-C,Y≥0 对偶问题的对偶:Min-CX,-AX≥-b,X≥0即:原问题 性质2的证明: 求证:弱对偶性若X是原问题的可行解,Y是对偶问题的可行解,则存在 CX<Y b 证明:因为C≤YA,所以CX≤YAX 因为AX≤b,所以YAX≤Yb,即CX≤YAx≤Yh 性质3的证明: 求证:无界性若原问题无界解,则其对偶问题无可行解。 证明:若原问题无界解,存在X,CX≥M(M任意大) 由性质2任意的Y,MYb 等 狼中教授
运筹学 熊中楷教授 性质2 的证明： 求证: 弱对偶性 若X是原问题的可行解，Y是对偶问题的可行解，则存在 C X≤ Y b 证明： 因为 C ≤ YA, 所以 C X≤ YAX 因为 AX ≤ b ， 所以 YAX ≤ Y b ， 即 C X≤ YAX ≤ Y b 性质1的证明： 求证: 对称性 对偶问题的对偶是原问题。 证明：原问题 ： Max CX， AX ≤ b， X ≥0 对偶： Min Y b， YA ≥ C， Y ≥0 即 Max -Y b， -YA ≤ - C， Y ≥0 对偶问题的对偶： Min - CX， - AX ≥ - b， X ≥0 即 : 原问题 第二章：对偶问题（1） 性质3的证明： 求证: 无界性 若原问题无界解，则其对偶问题无可行解。 证明：若原问题无界解，存在X， C X ≥ M （M任意大） 由性质2 任意的Y， M≤ Y b