第二章对偶问题(运筹学重庆大学,熊中楷).pptVIP

所以，甲工厂设备的影子价格p1=44/15(美元/台)，乙工厂设备的影子价格p2=4/15（美元/台）利用外汇100美元可购买甲工厂设备50台或乙工厂设备100台。假设企业美台设备每日工作15小时，则可增加甲工厂设备能力750台时或乙工厂设备能力1500台时。利用影子价格可对这两种购买设备的方案的经济效益进行比较： 购买甲工厂每日增加的收入为 750×44/15=2200（美元） 购买乙工厂每日增加的收入为 1500×4/15=400（美元） 从上面计算可以看出，购买甲工厂设备对这个企业带来的效益更大。这笔100万美元的投资用于购买甲工厂设备约经过455天就可以收回，用于购买乙工厂的设备需过2500天才能收回。 第二章：对偶问题（1）毛羽同学谈影子价格 第二章：对偶问题（1）易震同学总结对偶 极小化问题（min） 极大化问题（max） ? 约束 ≥ ≤ = ? ? 变量 ≥ ≤ 自由 ? 变量 ≥ ≤ 自由 ? ? 约束 ≤ ≥ = 易震同学对原问题与对偶问题关系的一点总结 可这样来理解： 1．? 目标函数系数对应右端常数； 2．? 系数矩阵互为转置； 3．? 约束条件与变量对应； 4．? 若给定LP是极小化问题，则利用上表从左到右对应写出对偶；若给定LP是极大化问题，则利用上表从右到左对应写出对偶。 也可按照下面的方法来做： 由小变大，变量与约束异向，约束与变量同向。 由大变小，变量与约束同向，约束与变量异向。 自由变量与等于号相对应。 这里“变量与约束”中的“变量”指原问题的变量，“约束”指对偶问题的约束； 同理“约束与变量”中的“约束”指原问题的约束，“变量”指对偶问题的变量。 第二章：对偶问题（1）易震同学总结对偶 易震同学对原问题与对偶问题关系的一点总结 第二章：对偶问题（1） 为了你的开卷题目或者为锻炼自己的思维， 你是否也发表点什么？ 对偶问题（2） 第二章：对偶问题（2） Chapter 2 : dual problem (2) Property 5: dual theorem Property 6: complementary slackness Property 7: coefficient of check-up and basic feasible solution of duality Tow examples of Property about duality: Example 1: proof that some LP have no feasible solution by means of dual theorem. Example 2: find the feasible solution of original LP through dual theorem. 第二章：对偶问题（2） 对偶性质5：对偶定理 对偶性质6：互补松弛性 对偶性质7：原问题检验数与对偶基解 对偶单纯形法： 对偶性质的应用二例： 例1：用对偶理论证明线性规划无解 例2: 用对偶理论求原问题的解 第二章：对偶问题（2） ? 原问题 对偶问题 ? MaxZ=CX AX=b X ≥0 Min w=Y b YA≥C Y ≥0 经济意义 A，X，b，C, CX, AX Y, Y b , YA 标准化 松弛变量 剩余变量 MaxZ=CX AX+Xs=b X ,Xs ≥0 Min w=Y b YA--Ys=C Y,Ys ≥0 第二章：对偶问题（2） ?1.对称性 对偶问题的对偶是原问题。 2.弱对偶性 若X是原问题的可行解，Y是对偶问题的可行解，则存在 C X≤ Y b 3.无界性 若原问题无界解，则其对偶问题无可行解。 4.设X*是原问题的可行解，Y*是对偶问题的可行解，当C X*=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 则原问题单存形表的检验数行对应其对偶问题的一