运筹学课程03-线性规划对偶理论及其应用.ppt

《运筹学课程03-线性规划对偶理论及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性规划对偶理论及其应用窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象1对偶问题的提出线性规划的对偶理论对偶问题的经济解释----影子价格对偶单纯形法灵敏度分析本章主要内容2一、问题的提出示例1：资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源又使总利润最大？1810单件利润150（设备）51C100（煤炭）32B170（钢材）25A资源限制乙甲单件产消耗品资源3相应的线性规划模型：一、问题的提出4下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工

2、任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？分析：1、每种资源收回的费用不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。一、问题的提出5一、问题的提出6一般而言，W越大越好，但因需双方满意，故为最好。该问题的数学模型为：一、问题的提出7模型对比一、问题的提出8一、问题的提出示例2：合理配料问题某饲养场用n种饲料B1,B2,…Bn配置成含有m种营养成分A1,A2,…Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？含饲量料成分最低需要量原料单价9其数学模型为：一、问题

3、的提出10假设工厂想把这m种营养成分分别制成一种营养丸销售，问如何定价（以保证总收入为最多）？11二、线性规划的对偶模型（一）、对偶问题的形式1、对称型对偶问题：已知P，写出D。12二、线性规划的对偶模型13例一、写出线性规划问题的对偶问题解：首先将原式变形14对偶模型不强调等式右端项b≥0二、线性规划的对偶模型152、非对称型对偶问题二、线性规划的对偶模型16例二、原问题173、混合型对偶问题1819原问题对偶问题例三、20综上所述，其变换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥

4、≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项21例四、线性规划问题222324三、对偶问题的基本性质为了便于讨论，下面不妨总是假设1、对称性定理：对偶问题的对偶是原问题。252、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有推论1原问题的任何可行解目标函数值是其对偶问题目标函数值的下限对偶问题的任何可行解目标函数值是其原问题目标函数值的上限26推论2如果原问题(max)有可行解且目标函数值无界，则其对偶问题(min)无可行解，反之也成立反之：如果对偶问题(m

5、in)有可行解且目标函数值无界，则原问题(max)无可行解注：逆不成立因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解推论3如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况27例无界如：（原）无可行解（对）28例：已知试用对偶理论证明原问题无界。解：=（0.0.0）是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y2≥0)。因此，对偶问题不可行，由推论⑶可知，原问题无界。29例：已知显然，这两个问题都无可行解。30例已知（P）试估

6、计它们目标函数的界，并验证弱对偶性原理。31解：（D）由观察可知：，，分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论⑴可知，W的最小值不能小于10，Z的最大值不能超过40。323、最优性判别定理若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*，Y*分别是问题P和D的最优解。证明：由上面推论，可得CX*＝Y*bCX，Y*b＝CX*Yb结论显然。4、强对偶性（对偶定理）如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论可知，原问题和对偶问题的目标函数有界，故一

7、定存在最优解。现证明定理的后一句话。33单纯形法计算的矩阵描述（回顾）线性规划问题化为标准型34单纯形法计算的矩阵描述（回顾）XS为松弛变量,XS=(xn+1,xn+2,…,xn+m),I为m×m矩阵35初始单纯形表非基变量基变量初始基变量单纯形法计算的矩阵描述（回顾）36基变量非基变量当前检验数当前基解设若干步迭代后，基变量为,在初始单纯形表中的系数矩阵为B，而A中去掉B的若干列组成矩阵N，则迭代后的单纯形表为：单纯形法计算的矩阵描述（回顾）37单纯形法计算的矩阵描述（回顾）检验数因此3839综述，一对对偶问题的关系，只能有下面三种情况之一出现：都

8、有最优解，分别设为X*和Y*，则必有CX*=Y*b；一个问题无界，则另一个问题无可行解；两个都无可行解。40