《对偶线性规划》课件.ppt

文档介绍：第二章线性规划的对偶理论及其应用窗含西岭千秋雪,门泊东吴万里船对偶是一种普遍现象*,问他们谈判原料价格的模型是怎样的?*、B资源的出售价格分别为y1和y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数ming(y)=25y1+15y2**(max,)标准型的对偶变换目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi,i=1,2,…,m对偶问题约束为型,有n行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义***弱对偶定理推论max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限;min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解,则其对偶min(max)问题无可行解如果原max(min)问题有可行解,其对偶min(max)问题无可行解,则原问题为无界解*,则X0,Y0分别是相应问题的最优解证:由弱对偶定理推论1,结论是显然的。即CX0=Y0bCX,Y0b=CX0Yb。证毕。,则它们都有最优解,且它们的最优解的目标函数值相等。证:由弱对偶定理推论1可知,原问题和对偶问题的目标函数有界,故一定存在最优解。现证明定理的后一句话。