第2章线性规划对偶问题PPT课件.ppt

《第2章线性规划对偶问题PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章对偶理论线性规划续知识点了解对偶问题的特点，熟悉互为对偶的问题之间的关系；掌握对偶规划的理论和性质，如可逆性、弱对偶性、对偶定理、互补松驰定理等；掌握对偶单纯形法；主要内容一、对偶问题的基本概念二、对称的对偶线性规划三、对偶的基本性质四、对偶单纯形法一、对偶问题的基本概念载重汽车大轿车资源限制钢材劳动力座椅22.5025116002500400利润（千元/辆）34传统的线性规划问题：在有限的资源下如何安排生产以获得最大利润该问题的线性规划模型为：目标函数：maxZ=4x1+3x2约束条件：2x1＋2x216005x1+2.5x22500x1

2、400x10,x20现在的问题：如果工厂目前不再打算生产汽车，而是将钢材和座椅以比买价更高的价格卖出去（加价），把生产能力以更高的工时费接受外协加工，那么材料和工时的定价应该是多少才是合算的？假设y1表示出售单位钢材的利润，y2表示外协加工的工时利润，y3表示出售每套大轿车座椅的利润那么生产一辆载重汽车的材料销售利润和工时利润之和不应低于出售一辆载重汽车所得的利润，即：2y1+2.5y23同样有，2y1+5y2+y34为了不亏本，各种材料的利润（加价）不能为负值，即：y1、y2、y30工厂的总利润是出售材料的利润、工时利润和座椅利润之和，即：

3、W=1600y1+2500y2+400y3从工厂决策者的角度看W越大越好。但为了在市场实现交易，在满足上述条件的基础上，W应尽可能小。从而得到如下线性规划模型：MinW=1600y1+2500y2+400y32y1+2.5y23s.t.2y1+5y2+y34y1、y2、y30线性规划原问题和对偶问题原问题：MaxZ=c1x1+…+cnxna11x1+…+a1nxnb1a21x1+…+a2nxnb2s.t.……am1x1+…+amnxnbmX1,…,xn0对偶问题：MinW=b1y1+…+bmyma11y1+…+am1ymc1a12y1+

4、…+am2ymc2s.t.……a1ny1+…+amnymcny1,…,ym0矩阵表述原问题：MaxZ=CTXs.t.AXbX0对偶问题：MinW=bTYs.t.ATYCY0两个模型之间的关系：原问题是求最大值，而对偶问题是求最小值；原问题的约束条件是“”，而对偶问题的约束条件是“”；原问题的目标函数系数是对偶问题的约束条件右端的常数项；原问题的约束条件右端的常数项是对偶问题目标函数的系数；原问题约束条件中xi的系数是对偶问题第i个约束条件的系数，原问题第i个约束条件的系数是对偶问题的约束条件中yi的系数。对称的对偶线性规划定义：如果一

5、个线性规划具备下面两个条件，则称它具有对称形式：所有的变量都是非负的；所有的约束条件都是不等式，且在目标函数是求极大值的情况下，为“”型，求极小值时，为“”型。原问题（对偶问题）对偶问题（原问题）目标函数限定向量价值向量技术系数约束条件变量数目约束条件个数变量正负目标函数价值向量限定向量技术系数对偶变量约束条件个数对偶变量数目约束条件非对称形式的对偶问题在原线性规划问题为Max型，且变量非负的前提下：1.原问题约束条件是“”型两边都乘以“-1”转化为“”型，得到对偶规划的变量约束为：yi0例：MaxZ=x1+2x2-3x3S.t.x1+2x2

6、+5x312x1-3x2-4x32x1,x2,x30MaxZ=x1+2x2-3x3S.t.-x1-2x2-5x3-12x1-3x2-4x32x1,x2,x30MinW=-y’1+2y2S.t.-y’1+2y21-2y’1-3y22-5y’1-4y2-3y’1,y20令y1=-y’1，上述模型化为：MinW=y1+2y2S.t.y1+2y212y1-3y225y1-4y2-3y10,y20例：MaxZ=x1+2x2-3x3S.t.x1+2x2+5x312x1-3x2-4x32x1,x20,x30令x’3=-x3，得：

7、MaxZ=x1+2x2+3x’3S.t.x1+2x2-5x’312x1-3x2+4x’32x1,x2,x’30MinW=y1+2y2S.t.y1+2y212y1-3y22-5y1+4y23y1,y20第三个方程两边同乘-1，得MinW=y1+2y2S.t.y1+2y212y1-3y225y1-4y2-3y1,y202.原问题约束条件是“=”型看成两个约束条件：””+””组成，得到对偶规划的变量约束为：yi无非负约束（即可正可负）例：MaxZ=x1+2x2-3x3S.t.x1+2x2+5x312x1-3x2-4x3=2x1,x

8、2,x30MaxZ=x1+2x2-3x3S.t.x1+2x2+5x312x1-3x2-4x