管理运筹学ppt课件.ppt

《管理运筹学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论窗含西岭千秋雪，门泊东吴万里船本章主要内容：线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析1第一节对偶问题的提出材料产品甲乙丙丁单件收益A32112000B41324000C22343000限额600400300200假设工厂考虑不进行生产而把全部资源都转让，问如何定价这些资源，既能使其获利不低于安排生产所获得的收益，又能使资源租让具有竞争力。一、引例MaxZ=2000x1+4000x2+3000x3s.t.3x1+4x2+2x3≤6002x1+x2+2x3≤4

2、00x1+3x2+3x3≤300x1+2x2+4x3≤200x1,x2,x3≥0MinW=600y1+400y2+300y3+200y4s.t.3y1+2y2+y3+y4≥20004y1+y2+3y3+2y4≥40002y1+2y2+3y3+4y4≥3000y1,y2,y3,y4≥0x1x2x3y1y2y3y42比较上述模型，可以得出两者之间的一些关系：1.两个问题，一个是极大化，另一个是极小化；2.一个问题的变量数等于另一问题的方程数，反之亦然；3.一个问题的目标函数系数是另一个问题的约束方程右端常数，反之亦然；4.

3、两个问题的约束方程系数矩阵互为转置。称变量yi为第一个LP的第i个对偶变量，或第一个LP的第i约束相应的对偶变量3二、对偶问题（1）对称LP问题的定义（2）对称LP问题的对偶问题第一类对称形式第二类对称形式（1）变量为非负；（2）约束条件为不等式。对于max，约束为“”；对于min，约束为“”4例1写出下列LP问题的对偶问题对偶MaxZ=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0MinW=8y1+16y2+12y3s.t.y1+4y2≥22y1+4y3≥3y1,y2,y3≥05（3

4、）对偶问题的对偶是原问题推导过程变形对偶变形对偶对偶变形MaxZ=CXs.t.AX≤bX≥0MinW=Ybs.t.YA≥CY≥0MaxW’=-Ybs.t.-YA≤-CY≥0MinZ’=(-C)Xs.t.(-A)X≥(-b)X≥0MaxW’=Y(-b)s.t.Y(-A)≤(-C)Y≥0加工6例2写出下列LP问题的对偶问题解:上述LP问题的对偶问题为：7三、非对称LP问题的对偶问题例3写出下列LP问题的对偶问题解：用x2=-x2’,x3=x3’-x3’’代入上述LP问题，并将其化为第一类对称形式MaxZ=x1+2x2+x3

5、x1+x2-x3≤2s.t.x1-x2+x3=12x1+x2+x3≥2x1≥0,x2≤0,x3无约束MaxZ=x1－2x2’+x3’－x3’’x1－x2’－x3’+x3’’≤2x1+x2’+x3’－x3’’≤1s.t.－x1－x2’－x3’+x3’’≤－1－2x1+x2’－x3’+x3’’≤－2x1,x2’,x3’,x3’’≥0x1-x2+x3≤1x1-x2+x3≥1x1-x2+x3≤1-x1+x2-x3≤-1-2x1-x2-x3≤-28上述第一类对称形式LP问题的对偶问题为：则上述问题变为：MinW=2y1+y2－y

6、3－2y4y1+y2－y3－2y4≥1－y1+y2－y3+y4≥-2s.t.－y1+y2－y3－y4≥1y1－y2+y3+y4≥-1y1,y2,y3,y4≥0MinW=2u1+u2+2u3u1+u2+2u3≥1s.t.u1－u2+u3≤2－u1+u2+u3=1u1≥0,u3≤0,u2无约束令u1=y1u2=y2－y3u3=－y4MaxZ=x1－2x2’+x3’－x3’’x1－x2’－x3’+x3’’≤2x1+x2’+x3’－x3’’≤1s.t.x1－x2’－x3’+x3’’≤－1－2x1+x2’－x3’+x3’’≤－2

7、x1,x2’,x3’,x3’’≥0-y1+y2-y3-y4≤1y1-y2+y3-y4≤29(D)MinW=2u1+u2+2u3u1+u2+2u3≥1s.t.u1-u2+u3≤2-u1+u2+u3=1u1≥0,u3≤0,u2无约束(L)MaxZ=x1+2x2+x3x1+x2-x3≤2s.t.x1-x2+x3=12x1+x2+x3≥2x1≥0,x2≤0,x3无约束对偶关系：一个问题第i个变量的约束情况决定另一问题第i个约束不等式的方向，反之亦然。正常的对正常的，不正常的对不正常的原问题约束条件是等式对应于对偶问题决策变量无

8、约束，反之亦然10例3直接写出LP问题的对偶问题1112原问题对偶问题目标函数MaxzMinw变量n个约束条件n个≥≤=≤0≥0无约束约束条件m个≥≤=变量m个≥0≤0无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项原问题对偶问题13第二节LP问题的对偶理论若X(0),Y(0)分别为(L),(D)的可行解，则