《运筹与优化--对偶规划.ppt》由会员分享，可在线阅读，更多相关《运筹与优化--对偶规划.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹与优化运筹与优化第二章 对偶问题与灵敏度分析福州大学体育馆第二章第二章 对偶问题与灵敏度分析对偶问题与灵敏度分析 对偶问题对偶问题 原问题与对偶问题的关系原问题与对偶问题的关系 对偶问题的基本性质对偶问题的基本性质 对偶单纯形法对偶单纯形法 对偶问题的经济解释对偶问题的经济解释 灵敏度分析灵敏度分析DUAL第一节 对偶问题1.1 对偶问题的提出对偶问题的提出 回顾第一章中例题回顾第一章中例题1：现在现在A、B两产品两产品销路不畅，可以将所有资源出租或外卖，现销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？在要谈判，我们的价格底线是什么？产品产品A产品产品B资源限制资源
2、限制劳动力劳动力设备设备原材料原材料 9 4 3 4 5 10 360 200 300单位利润单位利润 70 120例题的例题的对偶模型对偶模型l设每个工时收费设每个工时收费w1元，设备台时费用元，设备台时费用w2元，元，原材料附加费原材料附加费w3元。元。出租收入不低于生产收入：出租收入不低于生产收入：9w1+4w2+3w370 4w1+5w2+10w3 120 目标：目标：=360w1+200w2+300w3 出租收入越多越好？至少不低于某数。出租收入越多越好？至少不低于某数。原问题与对偶问题之比较原问题与对偶问题之比较原问题：原问题：对偶问题对偶问题：maxZ=70X1+120X2 mi
3、n=360w1+200w2+300w3 9X1+4X2360 9w1+4w2+3w3 70 4X1+5X2 200 (1)4w1+5w2+10w3120 (2)3X1+10X2300 w1 0,w2 0,w30X10 X201.2 对偶规则对偶规则 原问题一般模型：原问题一般模型：对偶问题一般模型：对偶问题一般模型：maxz=CX min=Wb(L)AX b (2.1);(DL)WA C (2.2)X 0 W 0 maxz=CX min=Wb(L)AX =b (2.3);(DL)WA C (2.4)X 0 W 无符号无符号约约束束l(2.1)与与(2.2)为对称形式的对偶为对称形式的对偶.l(
4、2.3)与与(2.4)为非对称形式的对偶为非对称形式的对偶.对偶规则对偶规则l原问题有原问题有m个约束条件，对偶问题有个约束条件，对偶问题有m个变量个变量.l原问题有原问题有n个变量，对偶问题有个变量，对偶问题有n个约束条件个约束条件.l原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项.l原问题的右端项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值系数.l原问题的技术系数矩阵转置后为对偶问题的原问题的技术系数矩阵转置后为对偶问题的系数矩阵系数矩阵.l极大化问题的约束型与极小化问题的变量符极大化问题的约束型与极小化问题的变量符号方向相反号方向相反.l原问题与对偶问
5、题优化方向相反原问题与对偶问题优化方向相反.对偶规则对偶规则 原问题原问题 对偶问题对偶问题目标函数目标函数 max min 目标函数目标函数约束条件约束条件 =变量符号变量符号无约束无约束 变量符号变量符号 无约束无约束 约束条件约束条件 =l例题例题2 minz=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x57 x1 +2x3 x4 4 -x1+3x2 x4+x5=-2 x1，x2，x30;x4 0,x5无限制无限制.max=7w1+4w2-2w3 s.t.2w1+w2 w33 w1 +3w32 -4w1+2w2 -6 w1 w2 w3 0 3w1 +w3=1 w1 0
6、,w2 0,w3 无约束无约束.第二节第二节 对偶问题的基本性质对偶问题的基本性质 1.对称性：对偶问题的对偶问题是原问题对称性：对偶问题的对偶问题是原问题.注：注：任何线性规划问题都具有唯一的对偶问题任何线性规划问题都具有唯一的对偶问题.2.弱对偶性：极大化原问题的任一可行解的目标弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行的目标函数值函数值，不大于其对偶问题任意可行的目标函数值,即即 C X W b.3.无界性：无界性：若原问题为无界解若原问题为无界解,则对偶问题无可行解则对偶问题无可行解.若若(L)可行可行,则则(L)具有无界解的充要条件是具有无界解的充要条件
7、是(DL 无可行解无可行解.注：注：原问题无可行解时原问题无可行解时,其对偶问题或具有无界解其对偶问题或具有无界解或无可行解或无可行解.例如下列一对问题两者皆无可行解例如下列一对问题两者皆无可行解.原问题：原问题：对偶问题：对偶问题：maxZ=X1+X2 min=-w1-w2 X1-X2-1 w1-w2 1 -X1+X2-1 (1)-w1+w21 (2)X10 X20 w1 0,w2 04.最优性准则最优性准则1：(L)和和(DL)有最优解的充要条件是有最优解的充要条件是 它们同时有可行解它们同时有可行解.最优性准则最优性准则2：若：若 x,w 分别为分别为(L)和和(DL)的可行解的可行解
8、且且 C X=W b，则则 x,w分别为分别为(L)和和(DL)的最优解的最优解.5.对偶定理：若一个问题有最优解，则另一问题也对偶定理：若一个问题有最优解，则另一问题也 有最优解，且目标函数值相等有最优解，且目标函数值相等.若原问题最优基为若原问题最优基为 B，则其对偶问题最优解则其对偶问题最优解 W*=CB B-1.6.原始问题和对偶问题最优解之间的互补松弛关系原始问题和对偶问题最优解之间的互补松弛关系min=Wbs.t.WA-Ws=C W,Ws0max z=CXs.t.AX+Xs=b X,Xs0min=Wbs.t.WAC W0max z=CXs.t.AXb X0对偶对偶引进剩余变量引进剩
9、余变量引进松弛变量引进松弛变量WXs=0 WsX=0互补松弛关系互补松弛关系W,WsX，Xs6.设设x、w分别是分别是(2.1)和和(2.2)的可行解的可行解,那么那么x、w都是都是 最优解的充分必要条件是最优解的充分必要条件是,对所有对所有i和和j,下列关系成立下列关系成立:(1).若若 ,则则 ;(其中其中Pj是是A的第的第j列列)(2).若若 ,则则 ;(3).若若 ,则则 ;(其中其中Ai是是A的第的第i行行)(4).若若 ,则则 .7.(2.1)的检验数的反数是的检验数的反数是(2,2)的一个基解的一个基解,其对应关系其对应关系 见下表见下表:例例3.已知线性规划已知线性规划(L)：
10、其最优解为其最优解为:(-5,0,-1)试利用对偶性质求对试利用对偶性质求对 偶问题的最优解及偶问题的最优解及k.例例4.已知线性规划已知线性规划(L)：试证明试证明(L)无最优解无最优解.例例5.已知线性规划已知线性规划(L):其其(DL)的最优解为的最优解为:(4/5,3/5)试求试求(L)的最优解的最优解.(书书P59)(1,0,0,0,1)T 1、原始问题是利润最大化的生产计划问题、原始问题是利润最大化的生产计划问题单位产品的利单位产品的利润润（元元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件
11、）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）第三节 对偶问题的经济解释2、对偶问题、对偶问题资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min y3、资源影子价格的性质资源影子价格的性质影子价格影子价格:影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越
12、是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0;若资源的影子价格若资源的影子价格0,表明该资源已耗尽表明该资源已耗尽.w1w2wm4、产品的机会成本、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源机会成本机会成本利润利润差额成本差额成本5、产品的差额成本（、产品的差额成本（Reduced Cost）差额成本=机会成本-
13、利润6、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源,其边际利润等于0（3）安排生产的产品，其机会成本等于利润（4）机会成本大于利润的产品不安排生产l对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基本解满足应用前提：有一个基，其对应的基本解满足 单纯形表的检验单纯形表的检验数数全部非正（对偶可行）全部非正（对偶可行）;变量取值可变量取值可以以有负数（非可行解）。有负数（非可行解）。*注：注：通过矩阵行变换运算，使所有相应通过矩阵行变换运算，使所有相应 变量取值均为非负数即得到最优单纯性表。变量取值均为
14、非负数即得到最优单纯性表。第四节 对偶单纯形法对偶单纯形法计算步骤对偶单纯形法计算步骤1、建立初始对偶单纯形表，对应一个基本解，所、建立初始对偶单纯形表，对应一个基本解，所有检验数均非正，转有检验数均非正，转2；2、若、若b 0，则得到最优解，停止；否则，若有，则得到最优解，停止；否则，若有 br 0 则选则选 r 行的基变量行的基变量xBr为出基变量为出基变量,转转3；3、若所有、若所有 arj 0(j=1,2,n)，则原问题无可行则原问题无可行解，停止；否则，若有解，停止；否则，若有 arj 0 则选则选 =min j/arj arj 0 br Min-bi/ir ir 05.5.1 1
15、资源向量资源向量 b b 的变化的变化例例1、求解线性规划（、求解线性规划（L）Max Z=2x1+3x2+0 x3+0 x4+0 x5 S.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5 =12 x1,x2,x3,x4,x5 0 最优单纯形表如下最优单纯形表如下(P66)0 0.25 0 B-1=-2 0.5 1 0.5 -0.125 0 B-1的各列分别对应的各列分别对应 b1、b2、b3 的单一变化的单一变化.设设 b1 增加增加 4，由新的，由新的bi*=(B-1b)i+brir,则则x1,x5 ,x2 分别变为：分别变为：4+4*0=4，4+4*(-2)=-4
16、0 =Max-6/1,-(13/3)/(1/3)=-6 Min-bi/i3 i3 0,则则将原最优表中将原最优表中 1 用用 1取代，继续单纯形法的取代，继续单纯形法的计算计算.得下得下表表:2).x2 xB,时最优解不变时最优解不变.最优解最优解 x=(x1,x2,x3)=(0,6,0),w=CB B-1=(c2,0)最优值最优值 z=CBB-1b=12+6(c2-2)=6c2 3)c2=01,由由2)知知B非最优基非最优基,将原将原最优表中第最优表中第r=1行的行的 -cc2=-(0-2)倍加到检验行倍加到检验行,并取并取 2=0,继续单纯形法计继续单纯形法计算算.得得 最优解最优解 x=
17、(x x1,x x2,x x3)=(0,0,6),w=(w w1,w w2)=(1,0)最优值最优值 maxz=min=65.5.3 3 技术系数技术系数a aijij的变化的变化lA A中元素发生变化中元素发生变化 （只讨论（只讨论 N N 中某一列变化情况）中某一列变化情况）假设假设 p pj j 变为变为P Pj j,那么计算出那么计算出 P*P*j j =B=B-1-1 P Pj j,j j=c cj j-C CB B B B-1-1 P Pj j 填入最优单纯形表，若填入最优单纯形表，若 j j 0 0 则最优解不变；否则，进一则最优解不变；否则，进一步用单纯形法求解。如例步用单纯形
18、法求解。如例1(P68):1(P68):可得最优解：可得最优解：x*=(3.2,0.8,0,0,2.4)T f*=15.2l增加一个变量增加一个变量 增加变量增加变量 xn+1 则有相应的则有相应的 pn+1，cn+1.那么，计算出那么，计算出 Pn+1=B-1pn+1 n+1=cn+1 CB B-1 Pn+1,填入最优单纯形表，若填入最优单纯形表，若 n+1 0,则最优解不变；否则最优解不变；否则，进一步用单纯形法求解。则，进一步用单纯形法求解。如例如例1(P66),增加增加 x6，p6=(2,6,3)T，c6=5。计算得到计算得到5.5.4 4 增加一个变量增加一个变量用单纯形法进一步求解
19、，可得：用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f*=16.5l增加一个新约束增加一个新约束 增加一个新约束后，应把原最优解带入新的增加一个新约束后，应把原最优解带入新的约束，若满足则最优解不变，否则填入最优单纯约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入形表作为新的一行，引入1个新的非负变量个新的非负变量若约若约束为束为“”型的，则两边乘型的，则两边乘(-1)，并通过矩阵行，并通过矩阵行变变换把对应基变量的元素列变为单位列，再用单纯换把对应基变量的元素列变为单位列，再用单纯形法或对偶单纯形法求解。形法或对偶单纯形法求解。如例如例2，增加，增加 -3x1+2x2+6x317，原最优解原最优解x=（1/3，0，13/3）不满足这个约束。于是将约）不满足这个约束。于是将约束方程束方程-3x1+2x2+6x3+x7=17 的系数置于原最优的系数置于原最优表，求解过程如下：表，求解过程如下：5.5.5 5 增加新的约束增加新的约束l由上表知由上表知,新问题的最优解新问题的最优解 x x*=(5/3,0,11/3),=(5/3,0,11/3),最优值最优值 minfminf=-13=-13