第二章对偶理论与灵敏度分析.ppt

《第二章对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章LP的对偶理论与灵敏度分析§1线性规划的对偶问题§2对偶规划的基本性质§3影子价格§4对偶单纯形法§5灵敏度分析对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。第一节线性规划的对偶问题例1穗羊公司的例子III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利

2、润（万元）32一、对偶问题的提出问公司应每天制造两种产品各多少件，使获取的利润最大？生产计划问题（LP1）现在我们从另一个角度来考虑这个问题。假如有另外一个新公司要求租用穗羊公司的资源，那么新公司愿意以多大的代价才能使穗羊出让自己所拥有的生产资源？资源定价问题（LP2）设y1,y2和y3分别表示出让资源A，B和调试工序的单价，则该公司同意出让的条件将是同意出让生产产品I的资源同意出让生产产品II的资源购买者希望用最少的代价获得这些资源，因此这样得到一个新的线性规划问题这样从两个不同的角度来考虑同一种资源的最大利润（最小租金）的问题，所建

3、立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。1.求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。2.原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个

4、约束条件的右边常数项。3.原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4.对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。设则二、对称形式的LP问题与对偶问题的一般形式定义：满足下列条件的LP问题称为具有对称形式：变量：所有变量均具有非负约束约束条件：最大化问题所有约束条件都是“≤”型的最小化问题所有约束条件都是“≥”型的对称形式的LP问题与对偶问题的一般形式为对称形式的原问题对偶问题的矩阵形式对称形式的原问题的矩阵形式对称形

5、式的对偶问题的矩阵形式对称形式下的对偶关系项目原问题对偶问题AbC目标函数约束条件决策变量约束条件系数矩阵约束条件右端项向量目标函数系数向量maxz=CXAX≤bX≥0约束条件系数矩阵转置目标函数的系数向量约束条件的右端项向量minw=Y’bA’Y≥C’Y≥0原问题maxz对偶问题minwn个决策变量m个约束条件n个约束条件m个决策变量约束条件“≤”型决策变量≥0决策变量≥0约束条件“≥”型对称形式的对应关系对偶问题的对偶是原问题，即对偶关系是相互对称的关系对偶问题的特点若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然原问题的

6、约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。一般线性规划问题的对偶问题2、非对称形式下的原问题与对偶问题(x变)2、非对称形式下的原问题与对偶问题(方程变)2、maxz=2x1+x2+3x3+x4x1+x2+x3+x4≤5s.t.2x1-x2+3x3=-4x1+2x3+x4≥1x1,x3≥0,x2,x4无约束练习题：1、minz=3x1+2x2-3x3+4x4x1-2x2+3x3+4x4≤3s.t.x2+3x3+4x4≥-52x1-3x2-7x3-4

7、x4=2x1≥0,x2≤0,x3,x4无约束2、非对称形式下的原问题与对偶问题(方程变)结论：方程对变量变量对方程正常对正常不正常对不正常变量正常是非负方程正常看目标(max<=min>=)对称、非对称形式下的对偶关系原问题（对偶问题）maxz对偶问题（原问题）minwn个决策变量m个约束条件n个约束条件m个决策变量约束条件“≤”型约束条件“≥”型约束条件“=”型决策变量≥0决策变量≤0决策变量无约束决策变量≥0决策变量≤0决策变量无约束约束条件“≥”型约束条件“≤”型约束条件“=”型原问题对偶问题第二节对偶问题的基本性质1、对偶问题的

8、对偶问题是原问题对偶的定义对偶的定义maxz=CXs.t.AX≤bX≥0minw=b’Ys.t.A’Y≥CY≥0minz’=-CXs.t.-AX≥-bX≥0maxw=-b’Ys.t.-A’Y≤-CY≥0一、