对偶问题的分析.ppt

《对偶问题的分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划问题的对偶与灵敏度分析3.1线性规划的对偶问题概念、理论及经济意义3.2线性规划的对偶单纯形法3.3线性规划的灵敏度分析本章内容重点1线性规划原问题例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025002一、对偶问题：它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力若另外一个工厂要求租用该厂的设备A、B

2、、C，那么该厂应如何确定合理的租金。设y1，y2，y3分别为每工时设备A、B、C的租金。3.1线性规划对偶问题3设备的租金收入不能低于自己组织生产时的获利收入：3y1+2y2≥1500（不少于甲产品的利润）2y1+y2+3y3≥2500（不少于乙产品的利润）用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润租方希望在满足上述条件下尽量要求全部设备的总租金越少越好，即MinW=65y1+40y2+75y34对偶变量的经济意义可以解释为对工时及原材料的单位定价若工厂自己不生产产品A、B和C，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及

3、原材料的总价格最低）当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：Zmax=Wmin=85原问题的对偶问题DP：MinW=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥06Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤40原问题3x2≤75x1,x2≥0MinW=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500对偶问题y1,y2,y3≥07原问题求极大化，对偶问题求极小化从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个

4、模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从数据b、C的位置看：在两个规划模型中，b和C的位置对换。8对偶问题与原问题的对比原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min不同≤0≥约束≥0变量≤不同条件=无约束≥0≥变量≤0约束≤相同无约束条件=9原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinF约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件数：n第i

5、个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”10例3.1写出下面线性规划的对偶规划模型11Maxz=x1-x2+5x3-7x4s.t.x1+3x2-2x3+x4=252x1+7x3+2x4≥-602x1+2x2-4x3≤30x4≥-5x4≤10x1,x2,≥0x3,x4取值无约束12Minf=25y1–60y2+30y3-5y4+10y5s.t.y1+2y2+2y3≥13y1+2y3≥-60-2y1+7y2-4y3=5y1+2y2+y4+y5=-7y1取值无约束y3,y5≥0y2,y4≤013Ⅰ对称性定理对偶问题的对偶是原问题。Ⅱ主对偶定理若(LP)和(DP)均

6、可行，那么(LP)和(DP)均有最优解,且最优值相等。如果原问题有最优解，则其对偶问题也一样具有最优解，且有maxz=minw。二、对偶问题的基本性质14Ⅲ弱对偶定理若x,y分别为（LP)和（DP）的可行解，那么cTx≤bTy。推论①若LP（或DP）可行，那么LP（或DP）无有限最优解(有无界解)的充分必要条件是DP（或LP）无可行解。？？当LP（或DP）无可行解时，则DP（或LP）具有无界解。②极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。③极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。15Ⅳ最优性准则定理若x,y分别

7、(LP)，(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。16三、影子价格市场价格影子价格，确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。对偶变量yi：代表对一个单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价。bi是线性规划原问题约束条件右端项，它代表第i种资源的拥有量。17影子价格是一个向量，它的分量表示最优目