运糖 92g 对偶问题(1) 运学 狼中教授
运筹学 熊中楷教授 对偶问题（1）
第二章:对偶问题(1) 复习典型引例:某王厂在计划期内安排甲,乙两种产品,已知生产单位 产品所消耗资源以及产生的利润如下表 甲产 乙产品 资源量 设备 8台时 原材料A 16公斤 原材料B 12公斤 产生的利润 2元 3元 运学 狼中教授
运筹学 熊中楷教授 复习典型引例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位 产品所消耗资源以及产生的利润如下表： 甲产品 乙产品 资源量 设备 1 2 8 台时 原材料A 4 0 16公斤 原材料B 0 4 12公斤 产生的利润 2元 3元 第二章：对偶问题（1）
第二章:对偶问题(1) Questions: if someone want to buy the resource b, what is the reasonable price For both of them?(buyer and supplier 运学 狼中教授
运筹学 熊中楷教授 Questions: if someone want to buy the Resource b , what is the reasonable price For both of them? (buyer and supplier ) 第二章：对偶问题（1）
第二章:对偶问题(1) 另一个相关问题的提出: 有人想把企业的资源租用,他应该出价多少?? 原问题 对偶问题 生产者追求利润最大 租用者希望租金最小 St.资源约束 St.租金不小于利润 市场约東 Max 2X +3X2 Min8Y1+16Y2+12Y3 X1+2X2=2 16 2Y1+4Y3 4X,=0 1>=0X2>= 运学 狼中教授
运筹学 熊中楷教授 另一个相关问题的提出： 有人想把企业的资源租用，他应该出价多少?? 原问题 对偶问题 生产者追求利润最大 租用者希望租金最小 St. 资源约束 St. 租金不小于利润 市场约束 Max 2X1 +3X2 Min 8Y1 +16Y2+12Y3 X1 + 2X2=2 4X1 =3 4X2 =0 X1>=0 X2>=0 第二章：对偶问题（1）
第二章:对偶问题(1) 对偶引例 单位产品 产品1产品资源对偶决策变量 约束资源定价 消耗资源 资源 设备 原料A 86 2 原料B 12 3 单位产品利润2元3元 原问题决策变量x1 X2 各产品产量 运学 狼中教授
运筹学 熊中楷教授 对偶引例： 单位 产品 产 品 消耗资源 资源 产品1 产品 2 资源 约束 对偶决策变量 资源定价 设备 原料 A 原料 B 1 4 0 2 0 4 8 16 12 y1 y2 y3 单位产品利润 2元 3元 原问题决策变量 各产品产量 x1 x2 第二章：对偶问题（1）
第二章:对偶问题(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. Ax0 运学 狼中教授
运筹学 熊中楷教授 对偶问题 租用者希望租金最小 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 X0 其对偶问题为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