运筹学第6讲：对偶问题的基本概念.ppt

《运筹学第6讲：对偶问题的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第6讲：对偶问题的基本概念浙江工业大学经贸管理学院曹柬一、对偶问题的提出例1：习题3-1运筹学第6讲：对偶问题的基本概念某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗和各种资源的限制量，如下表所示。该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问应如何安排计划使该工厂获利最多？甲乙资源限量设备(台时)128原材料A(kg)4016原材料B(kg)0412例2：习题3-2对于例1，假设该工厂的决策者决定不生产甲、乙两种产品，而是将所有资源外售。你作为一个收购

2、者，该如何决策来购买这些资源？运筹学第6讲：对偶问题的基本概念设有LP问题(P)的数学模型为：（P）：maxZ=CXs.t.AX≤bX≥0则称(D)是(P)的对偶问题，(P)是原问题式中:设另一个LP问题(D)的数学模型为：s.t.YA≥CY≥0（D）：minω=Yb式中:运筹学第6讲：对偶问题的基本概念（P）：maxZ=CXs.t.AX≤bX≥0(P)和(D)具有对称性，即互为对偶上述两种形式称为LP问题的对称形式，请不要混淆对称形式和标准形式s.t.YA≥CY≥0（D）：minω=Yb运筹学第6讲：对偶问题的基本概念例

3、3：写出下述LP问题的对偶问题maxZ=2x1－3x2+4x3s.t.2x1+3x2－5x3≥23x1+x2+7x3≤3-x1+4x2+6x3≥5x1,x2,x3≥0运筹学第6讲：对偶问题的基本概念二、非对称形式的原-对偶问题关系例4(P33)：求下述LP问题的对偶问题maxZ=c1x1+c2x2+c3x3s.t.a11x1+a12x2+a13x3≤b1a21x1+a22x2+a23x3＝b2a31x1+a32x2+a33x3≥b3x1≥0,x2≤0,x3无约束运筹学第6讲：对偶问题的基本概念可根据以下规则求LP问题的对偶

4、问题，分3步骤(P34表3-3)若(P)为max型,则(D)为min型，反之亦然；同时，(P):bT=(D):C；(P):AT=(D):A；(P):CT=(D):b(D)中约束条件取向规则：(P)的第j个变量xj对应于(D)的第j个约束式若(P)为max型，且xj≤0，则(D)的第j个约束式取向为“≤”若(P)为min型，且xj≤0，则(D)的第j个约束式取向为“≥”若(P)中的xj无约束，则(D)中的第j个约束式取向为“＝”其余情况与对称形式相同(D)中变量取值规则：(P)的第i个约束式对应于(D)的第i个变量yi若(P

5、)为max型，且第i个约束式取向为“≥”，则yi≤0若(P)为min型，且第i个约束式取向为“≤”，则yi≤0若(P)中的第i个约束式为等式，则yi无约束其余情况与对称形式相同(P)中约束式为对称形式，则(D)中相应变量为对称形式；(P)中约束式为非对称形式，则(D)中相应变量为非对称形式；(P)中变量为对称形式，则(D)中相应约束式为对称形式；(P)中变量为非对称形式，则(D)中相应约束式为非对称形式；对称的变量与对称的约束式相对应！不对称的变量与不对称的约束式相对应！运筹学第6讲：对偶问题的基本概念对称对应对称，不对称

6、对应不对称！例5：求下述LP问题的对偶问题maxZ=-7x1+14x2+3x3s.t.x1+6x2+28x3≤52x1－3x2+17x3＝－6－x1+x2－4x3≥7x1≥0,x2≤0,x3无约束运筹学第6讲：对偶问题的基本概念例6：求下述LP问题的对偶问题maxZ=2x1－3x2+4x3s.t.2x1+3x2－5x3≥23x1+x2+7x3＝3－x1+4x2+6x3＝5x1,x2≥0,x3≤0运筹学第6讲：对偶问题的基本概念习题3-3（1,3）maxZ=2x1+3x2－5x3+x4s.t.运筹学第6讲：对偶问题的基本概念

7、（P）：maxZ=CXs.t.AX≤bX≥0s.t.YA≥CY≥0（D）：minω=Yb给定一对对称型对偶问题：有如下5个定理：定理1(对称性定理):对偶问题的对偶是原问题运筹学第6讲：对偶问题的基本概念三、对偶问题的基本性质(1)定理2(弱对偶定理):设和分别是(P)和(D)的可行解，则必有推论1：若和分别是(P)和(D)的可行解，则是(D)的minω的下界，是(P)的maxZ的上界推论2：在一对(P)和(D)中，若其中一个问题可行，但目标函数无界，则另一个问题无可行解推论3：在一对(P)和(D)中，若一个问题有可行解，

8、而另一个问题无可行解，则有可行解的问题无界运筹学第6讲：对偶问题的基本概念例1：试证如下LP问题无界maxZ=x1+2x2s.t.－x1+x2+x3≤2－2x1+x2－x3≤1x1,x2,x3≥0运筹学第6讲：对偶问题的基本概念定理3(最优性判别定理):若X*和Y*分别是(P)和(D)的可行解，且CX*